828数据结构与操作系统大纲（2007版）.doc

《828数据结构与操作系统大纲（2007版）.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构与操作系统》考试大纲一、考试性质硕士研究生入学考试是为招收硕士研究生而实施的具有选拔功能的水平考试，其指导思想是既要有利于国家对高层次人材的选拔，又要有利于促进高等学校各类课程教学质量的提高，考试对象为2006年参加硕士研究生入学考试的考生。二、考试的基本要求要求学生比较系统地理解数据结构的基本概念和基本知识，掌握表、栈、队列、树和图等数据结构的基本特征和在计算机上实现的方法，要求考生具有抽象思维能力、逻辑推理能力、综合运用所学的知识分析问题和解决问题的能力，以及软件设计和编程能力。要求学生在完成程序设计语言

2、（汇编、C、C++等）、数据结构、计算机组成原理等课程学习的基础上，系统地学习操作系统这一计算机最重要系统软件的基本概念、基本原理和方法，对操作系统如何管理和控制计算机系统的所有硬件和软件资源以达到方便用户、提高资源的使用效率有较清楚的认识，为将来在软件开发设计具有较强的分析、解决问题的能力打下坚实的基础。三、考试方法和考试时间硕士研究生入学专业考试为笔试，考试时间为3小时，考试分数150分。四、考试科目、考试内容、考试要求和试卷结构考试科目《数据结构与操作系统》第一部分：数据结构（60%）第一章绪论1.什么是数据结构

3、2．基本概念和术语3．算法的描述和算法分析基本要求：了解《数据结构》所研究的问题，理解数据结构的基本概念，掌握算法的描述、算法设计的要求和算法效率的度量方法。重点：数据的逻辑结构和存储结构；用类C（C++）语言描述算法。第二章线性表1．线性表的逻辑结构2．线性表的顺序存储结构3．线性表的链式存储结构单向链表、循环链表、双向链表基本要求：掌握线性表的逻辑结构、存储结构及描述方式；掌握顺序表和链表的插入、删除等操作。重点：线性结构的定义和特点；顺序表和单链表的组织方法、特点和算法。第一章栈和队列1、栈的定义、栈的表示和实现

4、2、表达式求值3、队列的定义、队列的链式存储结构（链队列）、队列的顺序存储结构（循环队列）基本要求：了解栈和队列的定义；理解线性表、栈和队列特点及区别，栈对实现递归过程的作用；掌握顺序栈、链栈的入栈和出栈操作，顺序队列、链队列的入队和出队操作，循环队列的队空和队满的判断。重点：栈和队的特点；顺序栈和链栈上基本运算的实现和简单算法设计；链队上基本运算的实现和简单算法设计，栈与递归。第二章串1、串的逻辑结构定义及其基本操作2、串的静态存储结构和动态存储结构基本要求：了解串的有关定义；理解串的逻辑结构和存储结构；掌握串的模式

5、匹配传统方法和KMP方法。重点：串的基本运算及串的传统匹配方法和改进的KMP方法。第三章数组和广义表1、数组的定义和运算2、数组的顺序存储结构3、矩阵（特殊矩阵、稀疏矩阵）的压缩存储4、广义表的定义5、广义表的存储结构及算法基本要求：了解数组、特殊矩阵和稀疏矩阵的定义，广义表的概念、链表表示和算法；理解矩阵的压缩存储的概念；掌握矩阵的压缩存储的有关计算方法。重点：特殊矩阵的非零元下标与数组下标的对应关系。第四章树和二叉树1、树的结构定义和基本操作2、二叉树定义与基本操作、性质、存储结构、遍历和线索化3、树和森林。树的存

6、储结构、森林与二叉树的转换、树的遍历4、哈夫曼树及其应用基本要求：了解树的定义和二叉树的定义；理解二叉树的性质、二叉树的存储结构；掌握遍历二叉树的方法、线索二叉树的构造，森林与二叉树的转换，最优二叉树和哈夫曼编码。重点：利用二叉树的先根、中根和后根遍历解决有关二叉树的应用问题；哈夫曼树及其应用。第五章图1、图的定义和术语2、图的存储结构：数组表示法、邻接表3、图的遍历：深度优先搜索、广度优先搜索4、图的连通性问题：无向图的连通分量和生成树、最小生成树5、最短路经6、拓扑排序7、关键路经基本要求：了解图的定义和术语，生成

7、树和最小生成树的概念；理解邻接矩阵中元素的含义和邻接表中结点的含义；掌握深度优先搜索和广度优先搜索算法；理解求最小生成树、最短路径、拓扑排序和关键路径等各种图解方法。重点：图的两种表示，两种遍历；用Prim算法和Kruskal算法构造最小生成树；单源点、多源点的最短路径；用拓扑排序算法求关键路径等。第一章动态存储管理1、可利用空间表及分配方法2、边界标识法3、伙伴系统基本要求：了解动态存储管理的含义及分配方法。重点：边界标识法中可利用空间表的结构及分配算法和回收算法。第九章查找1、静态查找表：顺序表的查找、有序表的查找

8、、索引顺序表的查找2、动态查找表：二叉排序树和平衡二叉树、B_树和B+树3、哈希表：哈希函数的构造方法、处理冲突的方法、哈希表的查找及其分析基本要求：了解顺序查找、二分查找和分块查找、二叉排序树和平衡二叉树、哈希查找等的概念；理解顺序查找、二分查找和分块查找算法，二叉排序树的性质；掌握哈希函数的构造方法和处理冲突的方法，平衡二叉树