哈尔滨工程大学2021年计算机专业基础综合考研大纲
数据结构部分
考试内容范围:
一、绪论
1.了解有关数据结构的各个名词和术语的含义,以及语句频度和时间复杂度、空间复杂度的估算。
二、线性表
1.了解线性表的逻辑结构特性是数据元素之间存在线性关系,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。
2.熟练掌握顺序存储结构和链式存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。
3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
三、栈和队列
1.掌握栈和队列这两种抽象数据类型的特点,并能在相应的应用问题中正确选用它们。
2.熟练掌握栈类型的两种实现方法。
3.熟练掌握循环队列和链队列的基本操作实现算法。
4.理解递归算法执行过程中栈的状态变化过程。
四、串
1.理解串类型定义中各基本操作的特点,并能正确利用它们进行串的其它操作。
2.理解串类型的各种存储表示方法。
五、数组和广义表
1.理解多维数组类型的特点及其在高级编程语言中的存储表示和实现方法,并掌握数组在“以行为主”和“以列为主”的存储表示中的地址计算方法。
2.掌握特殊矩阵的压缩存储表示方法。
3.理解稀疏矩阵的压缩存储方法的特点及其适用范围,领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。
六、树和二叉树
1.领会树和二叉树的类型定义,理解树和二叉树的结构差别。
2.熟记二叉树的主要特性,并掌握它们的证明方法。
3.熟练掌握二叉树的各种遍历算法,并能灵活运用遍历算法实现二叉树的其它操作。
1.理解二叉树的线索化过程以及在线索化树上找给定结点的前驱和后继的方法。
2.熟练掌握二叉树和树的各种存储结构及其建立的算法。
3.学会编写实现树的各种操作的算法。
4.了解哈夫曼树的特性,掌握建立哈夫曼树和哈夫曼编码的方法。
七、图
1.领会图的类型定义。
2.熟悉图的各种存储结构及其构造算法,了解各种存储结构的特点及其选用原则。
3.熟练掌握图的两种遍历算法。
4.理解各种图的应用问题的算法及其应用场合。
八、查找
1.理解查找表的结构特点以及各种表示方法的适用性。
2.熟练掌握以顺序表或有序表表示静态查找表时的查找方法。
3.熟练掌握二叉排序树的构造和查找方法。
4.理解平衡二叉排序树的构造过程。
5.熟练掌握哈希表的构造方法,深刻理解哈希表与其它结构的查找表的实质性的差别。
6.掌握描述查找过程的判定树的构造方法,以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
九、内部排序
1.理解排序的定义和各种排序方法的特点,并能加以灵活应用。
2.掌握各种排序方法的时间复杂度和空间复杂度的分析方法,能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。
3.理解排序方法“稳定”或“不稳定”的含义,弄清楚在什么情况下要求应用的排序方法必须是稳定的。
十、文件
1.熟悉各类文件的特点、构造方法以及如何实现检索、插入和删除等操作。
2.了解各种文件的适用场合。
考试总分:90分 考试时间:1.8小时 考试方式:笔试
考试题型:选择题(30分)
简答题(20分)
计算题(30分)
算法题(10分)
参考书目(材料)
严蔚敏 吴伟民编著,数据结构(C语言版),北京:清华大学出版社