上海理工大学硕士研究生入学

《数据结构及操作系统》-2020年上海理工大学硕士研究生入学

考试大纲

第一部分：数据结构

一、参考书目

《数据结构》（C语言版），严蔚敏等主编，清华大学出版社，2012年 二、 考试内容要求

1、了解数据结构及其分类、数据结构与算法的密切关系。

2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。

3、掌握设计算法的步骤和算法分析方法。

4、掌握数据结构在排序和查找等常用算法中的应用。

5、初步掌握文件组织方法和索引技术。 三、考试内容

1、 数据结构基本概念及简单的算法分析 1)什么是数据结构

2) 抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；

面向对象的概念；用于描述数据结构的语言 3) 数据结构的抽象层次 4) 算法定义

5) 性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；

空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂. 2、 数组

1)作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数

组；数组的顺序存储方式

2)顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和

删除；使用顺序表的事例

3) 字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配

3、链表

1) 单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带

表头结点的单链表；用模板定义的单链表类；单链表的游标类；静态链表 2) 循环链表：循环链表的类定义；用循环链表解约瑟夫问题；多项式及其

相加：多项式的类定义；多项式的加法 3) 双向链表