《数据结构与操作系统》考试大纲

数据结构与操作系统考试大纲一、 考试性质硕士研究生入学考试是为招收硕士研究生而实施的具有选拔功能的水平考试，其指导思想是既要有利于国家对高层次人材的选拔，又要有利于促进高等学校各类课程教学质量的提高，考试对象为2006年参加硕士研究生入学考试的考生。二、 考试的基本要求要求学生比较系统地理解数据结构的基本概念和基本知识，掌握表、栈、队列、树和图等数据结构的基本特征和在电脑上实现的方法，要求考生具有抽象思维能力、逻辑推理能力、综合运用所学的知识分析问题和解决问题的能力，以及软件设计和编程能力。要求学生在完成程序设计语言汇编、C、C+等、数据结构、电脑组成原理等课程学习的基础上，系统地学习操作系统这一电脑最重要系统软件的基本概念、基本原理和方法，对操作系统如何管理和控制电脑系统的所有硬件和软件资源以到达方便用户、提高资源的使用效率有较清楚的认识，为将来在软件开发设计具有较强的分析、解决问题的能力打下坚实的基础。三、 考试方法和考试时间硕士研究生入学专业考试为笔试，考试时间为3小时，考试分数150分。四、 考试科目、考试内容、考试要求和试卷结构考试科目数据结构与操作系统第一部分：数据结构60%第一章绪论1. 什么是数据结构2基本概念和术语3算法的描述和算法分析基本要求：了解数据结构所研究的问题，理解数据结构的基本概念，掌握算法的描述、算法设计的要求和算法效率的度量方法。重点：数据的逻辑结构和存储结构；用类CC+语言描述算法。第二章线性表1线性表的逻辑结构2线性表的顺序存储结构3线性表的链式存储结构单向链表、循环链表、双向链表基本要求：掌握线性表的逻辑结构、存储结构及描述方式；掌握顺序表和链表的插入、删除等操作。重点：线性结构的定义和特点；顺序表和单链表的组织方法、特点和算法。第三章栈和队列1 、栈的定义、栈的表示和实现2、表达式求值3、队列的定义、队列的链式存储结构链队列、队列的顺序存储结构循环队列基本要求：了解栈和队列的定义；理解线性表、栈和队列特点及区别，栈对实现递归过程的作用；掌握顺序栈、链栈的入栈和出栈操作，顺序队列、链队列的入队和出队操作，循环队列的队空和队满的判断。重点：栈和队的特点；顺序栈和链栈上基本运算的实现和简单算法设计；链队上基本运算的实现和简单算法设计，栈与递归。第四章串1 、串的逻辑结构定义及其基本操作2、串的静态存储结构和动态存储结构基本要求：了解串的有关定义；理解串的逻辑结构和存储结构；掌握串的模式匹配传统方法和KM昉法。重点：串的基本运算及串的传统匹配方法和改良的KMPT法。第五章数组和广义表2 、数组的定义和运算3 、数组的顺序存储结构4 、矩阵特殊矩阵、稀疏矩阵的压缩存储5 、广义表的定义6 、广义表的存储结构及算法基本要求：了解数组、特殊矩阵和稀疏矩阵的定义，广义表的概念、链表表示和算法；理解矩阵的压缩存储的概念；掌握矩阵的压缩存储的有关计算方法。重点：特殊矩阵的非零元下标与数组下标的对应关系。第六章树和二叉树1 、树的结构定义和基本操作2、二叉树定义与基本操作、性质、存储结构、遍历和线索化3、树和森林。树的存储结构、森林与二叉树的转换、树的遍历4、哈夫曼树及其应用基本要求：了解树的定义和二叉树的定义；理解二叉树的性质、二叉树的存储结构；掌握遍历二叉树的方法、线索二叉树的构造，森林与二叉树的转换，最优二叉树和哈夫曼编码。重点：利用二叉树的先根、中根和后根遍历解决有关二叉树的应用问题；哈夫曼树及其应用。第七章图1 、图的定义和术语2、图的存储结构：数组表示法、邻接表3、图的遍历：深度优先搜索、广度优先搜索4、图的连通性问题：无向图的连通分量和生成树、最小生成树5、最短路经6、拓扑排序7、关键路经基本要求：了解图的定义和术语，生成树和最小生成树的概念；理解邻接矩阵中元素的含义和邻接表中结点的含义；掌握深度优先搜索和广度优先搜索算法；理解求最小生成树、最短路径、拓扑排序和关键路径等各种图解方法。重点：图的两种表示，两种遍历；用Prim算法和Kruskal算法构造最小生成树；单源点、多源点的最短路径；用拓扑排序算法求关键路径等。第八章动态存储管理1、可利用空间表及分配方法2、边界标识法3、伙伴系统基本要求：了解动态存储管理的含义及分配方法。重点：边界标识法中可利用空间表的结构及分配算法和回收算法。第九章查找1、静态查找表：顺序表的查找、有序表的查找、索引顺序表的查找2、动态查找表：二叉排序树和平衡二叉树、B_W和B+树3、哈希表：哈希函数的构造方法、处理冲突的方法、哈希表的查找及其分析基本要求：了解顺序查找、二分查找和分块查找、二叉排序树和平衡二叉树、哈希查找等的概念；理解顺序查找、二分查找和分块查找算法，二叉排序树的性质；掌握哈希函数的构造方法和处理冲突的方法，平衡二叉树的查找、插入和删除操作算法及相关查找方法的成功平均查找长度ASL。重点：二分查找的基本条件和方法；建立二叉排序树和平衡二叉树的过程；根据散列函数和解决冲突的方法建立散列表及等概率下成功平均查找长度ASL。第十章内部排序1、概述2、插入排序：直接插入排序、希尔排3、交换排序：冒泡排序、快速排序4、选择排序：简单项选择择排序、树形选择排序、堆排序5、归并排序：二路归并6、基数排序7、各种内部排序方法的比较讨论基本要求：了解排序算法的稳定性问题；理解直接插入排序、希尔排序、快速排序、简单项选择择排序、堆排序、归并排序和基数排序的基本思想；掌握直接插入排序、希尔排序、快速排序、简单项选择择排序、堆排序、归并排序的算法和时间分析。重点：对直接插入排序、简单项选择择排序、快速排序、堆排序、归并排序基本过程的掌握和算法的理解及评价。第十一章外部排序1、外存信息的存取2、外存排序的方法3、多路平衡归并的实现4、置换-选择排序基本要求：了解外排序的基本过程及方法。重点：外部排序方法及利用“败者树”解决K路平衡归并和置换-选择排序问题第十二章文件1、有关文件的基本概念2、顺序文件3、索引文件4、ISAM文件和VSAMt件5、直接存取文件散列文件6、多关键字文件：多重表文件、倒排文件基本要求：熟悉各类文件的特点及构造方法。重点：顺序文件、索引文件和散列文件。参考教材：严蔚敏、吴伟民数据结构C语言版清华大学出版社1997第二部分：操作系统40%第一章操作系统概述1. 操作系统的概念2. 操作系统的历史3. 操作系统的特性4. 操作系统的功能5. 操作系统的发展基本要求：了解操作系统的作用、发展历史和分类等。重点：操作系统的定义、分类和功能。第二章处理机管理1.多道程序设计2进程的引入3中断与中断系统4处理机调度基本要求：了解多道程序设计概念、掌握进程的基本概念、熟悉处理机调度算法。重点：进程的概念、处理机调度算法。第三章存储管理1. 存储管理的功能2. 内存资源管理3. 存储管理方式4. 虚拟存储系统基本要求：熟悉操作系统存储管理的方式和虚拟存储系统。重点：页式、段式、段页式存储管理；虚拟存储系统。第四章文件管理1、文件与文件系统2、文件的访问方式3、文件的组织4、文件目录5、文件的共享6、文件的保护、保密和安全7、文件系统的实现8、文件系统的界面9、盘存储管理基本要求：理解文件系统的基本目的是为用户提供按名存取的功能，以使得用户能透明地存储访问文件。为了实现按名存取，需要对文件存储设备进行合理的组织、分配和管理，对存储在文件存储设备上的文件进行保护、保密和提供共享的手段。重点：如何对文件存储设备进行组织、分配和管理；文件的共享和保护、保密。第五章设备管理1. 设备的分类2. 设备的物理特性3. 通道技术4. 设备的分配和去配5. 设备驱动6. 缓冲技术7. 虚拟设备基本要求：由于现代电脑系统外部设备的复杂性和多样性以及不同设备需要不同的处理程序，设备管理成了操作系统中最复杂、最具多样性的部分。要求了解设备管理的基本概念，理解通道技术和缓冲技术、设备驱动和虚拟设备技术。重点：通道、缓冲、设备驱动、设备分配与去配。第六章操作系统接口1. 联机命令接口2. 程序接口3. 图形用户接口基本要求：了解操作系统的用户接口。重点：了解操作系统的用户接口第七章进程管理1. 并发进程2. 进程互斥3. 进程同步4. 进程通信5. 进程死锁基本要求：掌握死锁的概念以及死锁发生的条件，熟悉发现死锁、预防或防止死锁的一些方法。重点：进程的互斥和同步、死锁产生的必要条件；死锁的预防和防止。第八章UNIX操作系统介绍1. 历史回忆2. 系统结构3. 进程管理4. 存储管理5. 文件系统6. 设备管理7. 系统调用基本要求：了解UNIX操作系统的进程管理、存储管理、文件管理、设备管理以及系统调用。重点：进程管理、存储管理和文件系统。参考教材：汤子瀛、哲凤屏电脑操作系统西安电子科技大学出版社2002学习文档 仅供参考