2020年上海理工大学848数据结构及操作系统考研大纲硕士研究生入学考试大纲 下载本文

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

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

考试大纲

第一部分:数据结构

一、参考书目

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

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

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

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

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

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

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

2) 抽象数据类型及面向对象概念:数据类型;数据抽象与抽象数据类型;

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

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

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

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

组;数组的顺序存储方式

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

删除;使用顺序表的事例

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

3、链表

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

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

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