南京审计大学2020年考研真题：814数据结构

考试科目：814数据结构

适用专业：081200计算机科学与技术

一、名词解释（共6小题，每题5分，总分30分）

1．抽象数据类型

2．数据逻辑结构

3．链式存储

4．线索二叉树

5．（排序）堆

6．关键路径

二、简答题（共4小题，每题10分，总分40分）

1．说明哈希表工作原理以及常见的哈希冲突处理方法。

2．说明快速排序的基本原理，以及其优缺点。

3．说明顺序存储和链式存储的优缺点。

4．结合数据结构课程，举例说明“空间换时间”。

三、综合应用题（共8小题，每题10分，总分80分）

1．一棵二叉树，先序遍历顺序为：ABDCEFG；后序遍历顺序为：DBFEGCA。画出所有满足上述条件的二叉树。

2．在一份电文中共使用有A,B,C,D,E,F，6种字符，他们出现的频率依次为3,8,6,17,7,26。画出对应的编码哈夫曼树，设计每个字符的哈夫曼编码。

3．已知带权有向图G如下图所示，用Dijstra迪杰斯特拉算法计算最短路径。S用来记录求解过程已求得最短路径的终点集合。用图表演示A到达其它结点最短路径求解过程。

4．已知无向图G的邻接矩阵如图所示，画出其邻接表。

5．对起始为空的平衡二叉树依次插入关键字序列10，20，30，60，50。画出平衡二叉树的生成过程。

6．写出以下代码的功能，并分析时间复杂度和空间复杂度。

7．已知顺序表LC[m]和LM[n]分别存储有语文成绩和数学成绩，且以学号从低到高排序，个别缺考学生在成绩表中未出现。写时间复杂度最优算法输出总分最高的人。已知成绩单结构：