2007年硕士研究生入学考试『计算机专业基础』覆盖知识点.docVIP

2007年硕士研究生入学考试『计算机专业基础』覆盖知识点 数据结构部分（50分） 第1章?????? O表示法，实际可行的复杂性，性能测量，C++中的模板，模板函数，模板类。 第2章 线性表：线性表与数组，多项式，多项式的表示，多项式相加，稀疏矩阵，稀疏矩阵的表示，稀疏矩阵的转置，字符串，字符串模式匹配的简单算法，KMP算法，失败函数f的计算，栈，队列。 第3章 链表：单链表，单链表的表示，可重用链表类，用模板定义链表， 链表游标，链表操作，环链表，链式栈和队列，链式多项式，多项式表示，多项式相加，删除多项式，环链多项式，稀疏矩阵的链表实现，稀疏矩阵表示，双链表。 第4章 树：树和森林的概念及其表示，二叉树，二叉树性质，二叉树表示，二叉树遍历与树游标， LVR, LRV, VLR，中序游标，按层次遍历，线索二叉树，线索，中序遍历线索二叉树，将结点插入线索二叉树，选择树，胜者树，败者树，森林的二叉树表示及遍历。 第5章 堆结构：最大堆（最小堆情况对称，也应该掌握），优先队列与最大堆，插入操作，删除操作。 第6章 图：图的基本定义，图的表示，邻接矩阵，邻接表，邻接多表，连通图的遍历，深度优先有哪些信誉好的足球投注网站，广度优先有哪些信誉好的足球投注网站，生成树 ，图的连通性，连通分量，最小代价生成树，克鲁斯卡尔算法，最短路径和传递闭包，边长非负时的单源点到所有终点的最短路径，所有顶点对之间的最短路径，传递闭包，AOV网络，AOE网络，活动的最早开始时间，活动的最迟开始时间，关键活动。 第7章 排序：排序问题，插入排序，快速排序，归并排序，堆排序，基数排序，外排序，k路归并，生成初始归并段，归并段的最佳归并和哈夫曼树。 第8章 查找结构：符号表，二叉查找树，二叉查找树的查找、插入和删除操作，AVL树，高度平衡，AVL树的插入算法，AVL树的时间复杂性分析，m叉查找树，m叉查找树的查找，B树的定义和性质，B树的插入操作，B树的删除操作，静态散列，散列表，散列函数，溢出处理。 主要参考书目：《数据结构（C++描述）》，金远平编著，清华大学出版社 离散数学部分（40分） 1 数理逻辑：命题，联结词，命题公式，真值表，等价式，重言式，蕴含式，对偶式，范式，推理理论，谓词，量词，命题函数，谓词公式，变元的约束，谓词演算的等价式与蕴含式，前束范式，谓词演算的推理理论 2 集合论：集合，集合运算，序偶，笛卡尔积，关系，关系的性质，关系运算，集合的划分和覆盖，等价关系，等价类，相容关系，序关系，哈斯图，函数，逆函数，复合函数，基数，可数集与不可数集 3 代数系统：代数运算及其性质，半群，幺半群，群（子群，阿贝尔群，循环群），环，域，同态，同构，格，分配格，有补格，布尔代数 4 图论：图的基本概念（无向图，有向图，简单图，完全图，子图，生成子图，导出子图，补图，图的同构，顶点的度数等），路径，回路，图的连通性，点割集，割点，边割集，割边，带权图，最短通路，Dijkstra算法，图的矩阵表示，欧拉图，汉密尔顿图，二分图，匹配，无向树，森林，生成树，有向树，子树，有序树，二元树，Huffman树及算法 主要参考书目：《离散数学》耿素云、屈婉玲编著，高等教育出版社《离散数学》朱一清编，电子工业出版社 操作系统部分（30分） 考试内容分基础部分和提高部分。基本部分是必须掌握的，提高部分要求在理解的基础上能够作某种程度的应用。 ●???? 基本部分包括如下内容： 1．? 引言部分（OS定义、功能、特征、类型、启动过程） 2．? 作业管理（用户界面，系统调用，批处理，Spooling，作业调度） 3．? 存储管理（虚存，地址变换，请求页式，页面置换算法） 4．? 进程管理（进程定义、状态及变迁，PCB，同步与互斥，PV操作，进程间通信各算法，死锁概念，优先级抢夺调度） 5．? 线程管理（线程概念、状态，多线程实例） 6．? 文件管理（文件概念，卷，目录，i结点，逻辑/物理地址，文件表） 7．? 设备管理（特别文件，I/O进程，设备入口表，字符/块设备驱动） ●???? 提高部分包括如下内容： 8．? 并发程序设计（进程/子进程，并发PASCAL，CSP） 9．? 操作系统的设计与实现（设计方法，实现语言） 10．? 多处理操作系统，网络/分布式操作系统，操作系统的安全机制 方法：紧扣教材内容，以基本部分为主。试题类型一般为：概念题，简答题、计算题、编程题。 主要参考书目：实用操作系统概念（英文版），西尔伯莎茨编著，高教出版社 现代操作体统教程，滕至阳编著，高教出版社 编译原理部分（30分） 该课程作为计算机专业的核心课程，其主要作用是帮助理解程序的本质、以设计出更有效的程序。主要知识点包括编译程序构造过程中所基于的原理、所采用的技术和工具。 重点掌握如下知识点： 对于原理，