上海理工大学《数据结构及计算机组成原理》2011年考研大纲

　《数据结构及计算机组成原理》考试大纲和参考书目

　　第一部分 数据结构

　　参考教材：

　　《数据结构》（C语言版），严蔚敏等主编，清华大学出版社，1997年4月第二版

　　第一章 绪论

　　明确数据结构的定义、研究的内容，掌握算法及算法分析的概念，了解抽象数据类型的概念。

　　第二章 线性表

　　掌握线性表的概念，两种存储结构顺序表和链表的表示和实现、掌握链表（单链表、单循环链表和双向链表）上的查找、插入、删除基本操作及能编写链表上的综合操作程序。

　　第三章 栈和队列

　　掌握栈的概念，掌握顺序栈、链栈的进栈、出栈操作程序。能利用栈写出表达式求值过程，能用栈读写递归程序。

　　掌握队列的概念，掌握循环队列、循环链队列的入队、出队操作程序。

　　第四章 串

　　掌握串的基本运算的含义，掌握求子串位置的定位函数，理解KMP模式匹配算法和时间复杂度。

　　第五章 多维数组和广义表

　　掌握多维数组及特殊矩阵的地址公式，广义表的运算和存储。了解广义表的递归算法。

　　第六章 树和二叉树。

　　掌握树、二叉树的定义、术语，二叉树的性质，掌握二叉树的递归和非递归遍历算法，掌握中序线索二叉树的概念和遍历算法，掌握Haffman树及其应用，了解树与二叉树的关系，了解回溯法与树的遍历。

　　第七章 图

　　掌握图的定义、术语，掌握图的存储，图的遍历算法，掌握比较小生成树、拓扑排序、关键路径、比较短路径概念，了解其算法。

　　第九章 查找

　　掌握有序表的查找算法和查找的时间复杂度，掌握二叉排序树的查找、插入和删除算法，掌握平衡二叉树和B-树的插入、删除概念。

　　掌握哈希表构造、解决冲突的方法及哈希表的查找。

　　第十章 内部排序

　　掌握直接插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序和希尔排序算法和时间复杂度，了解基数排序的概念。

　　专业课《数据结构》考试大纲和参考书目

　　参考教材:《数据结构·C语言版》 , 严蔚敏主编 , 清华大学出版社

　　参考用书:《数据结构习题详解》, 李春葆编著, 清华大学出版社

　　课程内容（无标记章节一般了解、不考，打*号标记章节要求掌握，打**号标记章节要求重点掌握）

　　绪论

　　数据结构定义

　　基本概念和术语

　　*算法描述和算法分析

　　抽象数据类型的表示和实现

　　线性表

　　线性表的基本概念

　　线性表顺序表示和实现

　　线性表的链式表示和实现：

　　**线性链表

　　**循环链表

　　*双向链表

　　顺序存储结构与链式存储结构的比较

　　**线性表的应用举例

　　栈和队列

　　*抽象数据类型栈的定义

　　*栈的表示和实现

　　栈的应用举例：

　　迷宫求解

　　**表达式求值

　　**栈与递归的实现

　　*抽象数据类型队列的定义

　　*链队列—队列的链式表示和实现

　　**循环队列—队列的顺序表示和实现

　　串

　　串类型的定义

　　串的表示和实现

　　**串的模式匹配算法

　　串的应用举例

　　数组和广义表

　　数组的定义

　　*数组的顺序表示和实现

　　*矩阵的压缩存储：

　　特殊矩阵

　　稀疏矩阵

　　*广义表的概念

　　*广义表的存储

　　广义表的应用举例

　　树和二叉树

　　树的定义和基本术语

　　*二叉树：

　　二叉树的定义

　　二叉树的性质

　　二叉树的存储结构

　　**二叉树的遍历

　　**线索二叉树

　　树和森林：

　　树的存储结构

　　静态链表

　　树、森林和二叉树的转换

　　树的遍历

　　*树的应用举例：

　　哈夫曼树

　　哈夫曼编码

　　回溯法与树的遍历

　　图

　　*图的定义和基本术语

　　图的存储结构：

　　**邻接矩阵

　　**邻接表

　　十字链表

　　邻接多重表

　　**图的遍历：

　　深度优先搜索遍历

　　广度优先搜索遍历

　　*比较小生成树：

　　生成树和比较小生成树

　　普里姆算法

　　克鲁斯卡尔算法

　　有向无环图及应用：

　　*拓扑排序

　　关键路径

　　比较短路径

　　查找

　　查找基本概念

　　顺序表的查找：

　　顺序查找

　　**有序表的查找

　　分块查找

　　8.3树表的查找

　　*8.3.1二叉搜索树

　　*8.3.2平衡二叉树

　　8.3.3 B_树

　　8.3.4 B+树

　　*8.4哈希表

　　8.4.1哈希表的基本概念

　　8.4.2构造哈希函数的方法

　　8.4.3解决哈希冲突的方法

　　8.4.4哈希表的查找

　　*第九章 排序

　　9.1排序的基本概念

　　9.2插入排序

　　9.2.1直接插入排序

　　9.2.2希尔排序

　　9.3交换排序

　　9.3.1冒泡排序

　　9.3.2快速排序

　　9.4选择排序

　　9.4.1直接选择排序

　　9.4.2堆排序

　　9.5归并排序

　　9.6基数排序

　　9.7各种内部排序方法比较

　　9.8外排序

　　**二叉排序树

　　*平衡二叉树

　　*B_树

　　B+树

　　哈希表：

　　*哈希表的基本概念

　　构造哈希函数的方法

　　*解决哈希冲突的方法

　　*哈希表的查找

　　内部排序

　　排序的基本概念

　　**插入排序：

　　直接插入排序

　　希尔排序

　　**冒泡排序

　　**快速排序

　　**选择排序：

　　直接选择排序

　　堆排序

　　**归并排序

　　基数排序

　　*各种内部排序方法比较

　　第一部分 计算机组成原理

　　一、考试范围

　　计算机系统概论，运算方法与运算器，内部存储器，指令系统，中央处理机，总线系统，外围设备，输入输出系统，操作系统支持。

　　在考查基本概念、基本理论的基础上，注重考查学生运用基本知识分析和解决实际问题的能力。要求学生对计算机组成原理有比较深入的认识，主要包括下面3个方面：

　　1、深刻理解计算机系统各功能部件的功能、组成和工作原理，正确理解各功能部件之间相互关系以及它们在计算机系统中所起的作用。

　　2、了解和掌握计算机系统某些部件的设计与分析技术，包括数据与指令的编码、存储、输人输出等。

　　3、理解和掌握计算机系统中的基本概念和方法，并能将这些概念和方法运用在后继课的学习中。

　　二、考试形式与试卷结构

　　1.考查内容及其考查比例：基本概念占30%分、理解占30%分、综合能力占40%分。

　　2.试卷结构与考试题型：填空题、选择、问答题、综合计算题等。

　　三、参考书目

　　《计算机组成原理》（第四版），白中英主编，科学出版社，2007年12月。

　　四、考查要点

　　1、计算机系统层次结构的实际含义，各部件的基本功能。计算机系统的基本概念： 寄存器、算术逻辑单元、存储器、字、字节、地址、指令流、 地址流、CPU、总线、主存、辅存、DMA等。

　　2、数的基本知识，计算机中数的表示方法，机器数的定义及与真值的互换，信息校验的实际意义和方法。定点数运算方法；浮点数四则运算方法；算术逻辑单元的组成及工作原理。运算器的功能，功能部件和结构。

　　3、存储器的基本知识，现代主存储器的结构和工作原理、设计原理和方法；高速缓冲存储器的组织、工作原理，地址影象方法及替换算法；软硬盘存储器的结构及工作原理，磁记录原理和磁记录方式；存储器的校验和CRC码校验。虚拟存储器概念及有关内容。

　　4、指令系统的意义和重要性；指令格式，指令和操作数的寻址方式和寻址过程；完备性指令系统的设计。

　　5、中央处理机的功能与组织，指令处理的相关知识和控制原理，时序发生器设置的意义及时序产生器的组织和工作原理。微程序控制器和硬布线控制器的设计思想、原理、组织特征、工作原理及有关知识；流水CPU的有关概念。

　　6、单机系统总线结构及其特征，总线的仲裁与通信及其有关知识。

　　7、外围设备的类型、功能和特点；多种信息存储或显示方式的工作原理。

　　8、几种输入输出控制方式的控制原理和数据传送的过程。中断系统设置的意义及中断过程实现的技术和相关知识。

　　9、操作系统对计算机各功能部件的工作机理。