2017年考试内容范围说明

1、2017年考试内容范围说明考试科目代码：847 考试科目名称：计算机学科专业综合数据结构部分一、绪论 1、理解数据结构的基本概念；了解数据类型和抽象数据类型的概念；2、理解算法的设计目标；掌握算法的时间、空间复杂度概念以及时间、空间复杂度的分析方法。 二、线性表 1、理解线性表的逻辑结构和基本操作；2、熟练掌握线性表的顺序存储结构和实现方法；3、熟练掌握线性表的链式存储结构和实现方法；4、理解单循环链表和双向链表的概念和基本设计方法。 三、栈和队列 1、熟练掌握栈的概念、顺序栈和链式栈的设计方法及应用方法; 2、熟练掌握队列的概念、顺序循环队列和链式队列的设计方法及应用方法3、理解递归算法的思

2、想，递归算法执行过程中工作栈的变化过程。 四、数组 1、理解多维数组的概念及存储结构，掌握多维数组的地址计算方法；2、掌握特殊矩阵的压缩存储方法；3、掌握稀疏矩阵的压缩存储方法及应用，用三元组存储稀疏矩阵时的基本矩阵运算方法。 五、树和二叉树 1、理解树的定义、表示方法和树的几种典型存储结构；2、熟练掌握二叉树的定义、二叉树的性质、二叉树的存储结构和二叉树操作的实现方法；3、熟练掌握二叉树的遍历算法和二叉树问题的遍历算法设计分析和实现；4、理解哈夫曼树的概念，掌握建立哈夫曼树和哈夫曼树编码的方法；5、掌握树与二叉树的转换方法；树的遍历；森林与二叉树的转换；森林的遍历。 六、图 1、理解图的基本

3、概念和术语；熟练掌握图的邻接矩阵和邻接表存储结构以及图基本操作的实现方法；2、熟练掌握图的深度和广度遍历方法和算法设计方法；3、理解最小生成树的概念，熟练掌握普里姆算法和克鲁斯卡尔算法并掌握其生成方法；4、掌握单源点最短路径的算法，拓扑排序方法，理解关键路径的概念。 七、查找 1、掌握查找的基本概念和查找方法的评判标准；2、熟练掌握顺序查找和有序查找的算法设计方法，理解索引查找的基本结构；3、理解二叉排序树的特点；掌握二叉排序树的构造和查找方法4、熟练掌握哈希函数、哈希表的构造方法，解决哈希冲突的方法，哈希表的查找及其分析 八、排序 1、掌握排序的基本概念，理解排序“稳定”和“不稳定”的含义，

4、理解排序算法的评判标准；2、熟练掌握直接插入排序、希尔排序、直接选择排序、堆排序、快速排序、二路归并排序、基数排序的算法思想和算法设计方法；理解各种排序方法的性能特点并能灵活应用。计算机组成原理部分考试内容范围：一、计算机系统概论 1.理解计算机系统的层次结构。2.掌握冯.诺依曼机的组成及特点。3.掌握计算机硬件的主要技术指标，如机器字长、存储容量、CPU时钟周期、主频、CPI、CPU执行时间、MIPS、MFLOPS等。二、系统总线 1.掌握总线定义、总线组成及性能指标；了解常用总线标准。2.掌握总线集中仲裁方式。三、存储器 1.理解存储器分类及层次结构（Cache-主存结构、主存-辅存结构）

5、。2.掌握主存储器的设计及与CPU的连接方法。3.掌握Cache的基本工作原理、Cach和主存之间的映射方式；理解Cache替换算法。四、输入输出系统 1.掌握输入输出系统的基本结构和功能、I/O端口及其编址方式。2.掌握三种I/O方式：程序查询方式、程序中断方式（中断的基本概念、中断响应过程、中断处理过程、多重中断和中断屏蔽的概念）、DMA方式（DMA传送过程）。五、计算机中数的表示和运算方法 1.掌握数的表示方法：包括无符号数、有符号数（原码、反码、补码、移码）、定点数和浮点数的表示。2.掌握数的运算方法：包括移位运算、定点加减运算、浮点加减运算。3.理解算术逻辑单元ALU的功能和结构。六

6、、计算机指令系统 1.了解指令的基本格式，掌握定长操作码指令格式。 2.掌握有效地址的概念、掌握指令寻址和数据寻址及常见数据寻址方式。3.了解CISC和RISC的基本概念。 七、CPU结构和功能 1.理解CPU的功能和基本结构。2.掌握指令执行流程（按取指周期、间址周期、执行周期分析指令的微操作及相关控制号）。3.掌握微程序控制器（微程序、微指令和微命令，微指令的编码方式，微地址的形式方式）；了解硬布线控制器。考试总分：150分（数据结构75分 组成原理75分） 考试时间：3小时 考试形式：笔试考试题型：数据结构：选择题、填空题、判断题、计算题、算法题组成原理：选择题（30分） 计算题、综合题（45分）参考教材：1、严蔚敏，数据结构，