2022哈尔滨工程大学考研初试大纲：811计算机专业基础综合

　　附件5：

　　2022年考试内容范围说明

　　考试科目名称: 计算机专业基础综合 R初试

　　数据结构部分

　　考试内容范围:

　　一、绪论

　　1. 了解有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。

　　二、线性表

　　1. 了解线性表的逻辑结构特性是数据元素之间存在线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。

　　2. 熟练掌握顺序存储结构和链式存储结构的描述方法以及线性表的操作在这两种存储结构上的算法实现。

　　3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

　　三、栈和队列

　　1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。

　　2. 熟练掌握栈类型的两种实现方法。

　　3. 熟练掌握循环队列和链队列的基本操作实现算法。

　　4. 理解递归算法执行过程中栈的状态变化过程。

　　四、串

　　1. 理解串类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。

　　2. 理解串类型的各种存储表示和实现，理解串的应用场合。

　　五、 数组和广义表

　　1. 理解多维数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”和“以列为主”的存储表示中的地址计算方法。

　　2. 掌握特殊矩阵的压缩存储表示和实现方法。

　　3. 理解稀疏矩阵的压缩存储方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。

　　4. 理解广义表定义及其从各种基本操作的特点，并能正确利用它们进行广义表的操作。理解广义表的存储表示。

　　六、 树和二叉树

　　1. 领会树和二叉树的类型定义，理解树和二叉树的结构差别。

　　2. 熟记二叉树的主要特性，并掌握它们的证明方法。

　　3. 熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。

　　4. 理解二叉树的线索化过程以及在线索化树上找给定结点的前驱和后继的方法。

　　5. 熟练掌握二叉树和树的各种存储结构及其建立的算法。

　　6. 学会编写实现树的各种操作的算法。

　　7. 了解哈夫曼树的特性，掌握建立哈夫曼树和哈夫曼编码的方法。

　　七、 图

　　1. 领会图的类型定义。

　　2. 熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。

　　3. 熟练掌握图的遍历算法，并理解掌握图的连通性问题及相关应用。

　　4. 理解掌握各种图的应用问题的算法及其应用场合。

　　八、 查找

　　1. 理解查找表的结构特点以及各种表示方法的适用性。

　　2. 熟练掌握以顺序表或有序表表示静态查找表时的查找方法。

　　3. 熟练掌握二叉排序树的特点、构造和查找方法。

　　4. 熟练掌握平衡二叉排序树的特点、构造过程和查找方法。

　　5. 理解B-树的特点及查找方法。

　　6. 熟练掌握哈希表的构造和处理冲突方法，深刻理解哈希表与其它结构的查找表的实质性的差别。

　　7. 掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。

　　九、 内部排序

　　1. 理解排序的定义和各种排序方法的特点，并能加以灵活应用。

　　2. 掌握各种排序方法及其时间复杂度和空间复杂度的分析方法，能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。

　　3. 理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。

　　十、 文件

　　1. 熟悉各类文件的特点、构造方法以及如何实现检索、插入和删除等操作。

　　2. 了解各种文件的适用场合。

　　考试总分：90分 考试时间：1.8小时 考试方式：笔试

　　考试题型：选择题(20分)

　　简答题(25分)

　　计算题(30分)

　　算法题(15分)

　　参考书目(材料)

　　严蔚敏 吴伟民编著，数据结构(C语言版)，北京：清华大学出版社

　　计算机组成原理部分

　　考试内容范围:

　　一、计算机系统组成的基本概念

　　1. 要求考生理解计算机系统的层次结构。

　　2. 要求考生掌握计算机硬件系统的组成、冯·诺依曼计算机的结构和“存储程序”工作原理。

　　3. 要求考生了解信息的数字化表示。

　　4. 要求考生了解计算机系统的主要性能指标。

　　二、数据的表示、运算和校验

　　1.要求考生熟练掌握进位计数制、机器数以及定点和浮点表示法、数据代码的处理与存储。

　　2.要求考生熟练掌握定点数的四则运算的算法、运算规则及“溢出”判断方法。

　　3.要求考生理解浮点数四则运算流程并能正确实现计算，掌握浮点数对阶及规格化的含义。

　　4.要求考生掌握常用的数据校验方法(奇偶校验、海明校验、循环冗余校验)。

　　三、CPU子系统

　　1.要求考生掌握指令格式及可扩展操作码指令系统设计方法。

　　2.要求考生熟练掌握常见寻址方式并能够正确计算操作数地址，掌握外设端口编址方式。

　　3.要求考生了解常见指令类型，理解RISC和CISC两种指令集的各自特点。

　　4.要求考生理解CPU的逻辑组成及CPU内部的数据通路结构。

　　5.要求考生掌握指令执行的流程(寄存器传输级微操作序列)，了解微命令序列。

　　6.要求考生理解组合逻辑控制器和微程序控制器的基本思想、逻辑组成及各自优缺点。

　　7.要求考生掌握微指令格式、微命令编码方式以及常见的微地址形成方式。

　　四、存储子系统

　　1.要求考生理解存储系统的层次结构，存储器的分类及技术指标。

　　2. 要求考生理解半导体静态存储器和动态存储器存储信息的原理，了解磁表面存储器的存储原理和常用磁记录编码方式。

　　3. 要求考生掌握主存储器的逻辑结构设计方法、动态存储器的刷新。

　　4. 要求考生理解磁盘信息分布、寻址信息以及磁盘主要性能指标。

　　5. 要求考生掌握计算机的三级存储体系，掌握Cache与内存、内存与外存的数据交互。

　　五、总线与输入/输出子系统

　　1. 要求考生掌握总线定义，了解总线分类及常用总线标准。

　　2. 要求考生掌握程序查询、中断、DMA传送方式的基本概念及各自优缺点和适用场合。

　　3. 要求考生理解中断全过程及CPU进入中断响应阶段的必要条件。

　　4. 要求考生理解DMA传输操作过程及DMA与中断的关系。

　　考试总分：60分 考试时间：1.2小时 考试方式：笔试

　　考试题型：选择题(10分)

　　简答题(20分)

　　综合设计题(30分)

　　参考书目(材料)

　　纪禄平 罗克露 刘辉 张建 编著，计算机组成原理(第5版)，北京：电子工业出版社