833计算机学科专业基础综合复习参考提纲

《833计算机学科专业基础综合复习参考提纲》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、833“计算机学科专业基础综合”复习参考提纲一、考察目标计算机学科专业基础综合考试涵盖数据结构和计算机组织与体系结构等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。二、考试形式和试卷结构1、试卷满分及考试时间：本试卷满分为150，考试时间为180分钟2、答题方式：闭卷，笔试3、试卷内容结构：数据结构75分、计算机组织与体系结构75分三、考察范围数据结构：【总体要求】“数据结构”要求学生掌握数据

2、结构的基本理论和基本方法，使学生具备基本的数据结构分析、设计、求解实际问题的能力。要求掌握数据结构的基本概念、基本原理和基本方法；掌握线性表、树与二叉树、图的逻辑结构、物理结构、基本操作，以及基本操作在不同的物理结构上的实现，并能够对操作算法进行基本的时间复杂度和空间复杂度进行分析；掌握基本的查找和排序方法，并能够利用这些方法对实际问题进行分析和求解，具备采用C或C++或JAVA语言设计与实现算法的能力。（一）数据结构基本概念1.复习内容数据结构、算法的基本定义，数据结构的逻辑结构和物理结构，算法的性能评价方

3、法。2.具体要求数据结构的定义数据结构的逻辑结构数据结构的物理结构算法的概念和算法的性能评价（二）线性表1.复习内容线性表的概念和基本运算，线性表的顺序存储和链式存储，线性表的基本运算在顺序存储和链式存储结构上的实现。2.具体要求线性表的概念和基本运算线性表的顺序存储线性表的链式存储线性表的应用 （三）栈和队列1.复习内容栈和队列的基本概念、基本操作和存储结构。2.具体要求栈和队列的基本概念和基本操作栈和队列的顺序存储结构栈和队列的链式存储结构栈和队列的应用（四）串1.复习内容串的基本概念、存储结构和模式匹配

4、算法2.具体要求串的基本概念和基本操作串的顺序存储结构串的链式存储结构模式匹配算法（五）数组和广义表1.复习内容数组和广义表的基本概念、数组的顺序存储和特殊矩阵的压缩存储。2.具体要求数组的基本概念和基本操作数组的顺序存储和实现特殊矩阵的压缩存储广义表的基本概念和存储（六）树与二叉树1.复习内容树与二叉树的基本概念、存储结构和性质，树与二叉树的遍历，树、森林与二叉树的转换，哈夫曼(Huffman)树的概念和应用。2.具体要求（一）树的概念（二）二叉树二叉树的定义及主要特征二叉树的顺序存储结构二叉树的链式存储结

5、构二叉树的遍历线索二叉树的基本概念和构造（三）树、森林树的存储结构树、森林与二叉树的转换树和森林的遍历（四）树与等价问题（五）哈夫曼(Huffman)树和哈夫曼编码（七）图1.复习内容图的基本概念和存储结构、图的遍历、图的基本应用算法。2.具体要求(一)   图的基本概念(二)   图的存储结构　　 邻接矩阵法　　 邻接表法 逆邻接表法十字链表邻接多重表(三)   图的遍历　　 深度优先遍历　　广度优先遍历(四)   图的基本应用算法　　连通分量与最小生成树　　拓扑排序关键路径 最短路径（八）查找1.复习内容

6、查找的基本概念、静态查找表和动态查找表、哈希表。2.具体要求(一)   查找的基本概念(二)   静态查找表顺序查找法 折半查找法索引顺序查找法(三) 动态查找表  　二叉排序树及其基本操作　平衡二叉树概念B树及其基本操作B+树的基本概念(五)   哈希(Hash)表哈希表的基本概念哈希函数的构造冲突的解决方法(六)   查找算法的分析及应用 （九）排序1.复习内容排序的基本概念、排序算法和性能分析。2.具体要求(一)   排序的基本概念(二)   插入排序　直接插入排序折半插入排序2-路插入排序表插入排序希

7、尔排序(三)   交换排序起泡排序快速排序(四)   选择排序简单选择排序　堆排序(五)  归并排序(六)   基数排序(七)外部排序计算机组织与体系结构:【总体要求】“计算机组织与体系结构”要求学生掌握单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。要求掌握计算机系统层次化结构概念，熟悉硬件与软件之间的界面；掌握计算机数据表示的方法，包括定点数和浮点数的表示；掌握运算器的原理和实现电路；掌握存储层次的概念，会解决Cache存储的一些基本问题；掌握不同类型存

8、储器形式，包括SRAM，DRAM，ROM；掌握磁盘基本原理及RAID；掌握指令集体系结构的基本知识和基本实现方法；掌握中央处理器控制器部分的两种基本设计方法，即硬布线和微程序控制，能够根据模拟中央处理器化简控制信号逻辑或者编写简单微操作流程；熟悉中央处理器的时序逻辑，即指令周期、CPU周期、节拍周期、时钟周期之间的关系；掌握计算机输入输出系统的基本概念，程序查询方式、中断方式和直接内存获取方式；掌握