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

考试科目：814数据结构

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

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

1．物理结构

2．数据类型

3．算法

4．二叉平衡树

5．十字链表

6．关节点

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

1．结构是指数据元素之间的相互关系。请简要描述常用基本结构。

2．请简述希尔排序基本原理。

3．请简述哈希表的基本工作原理。

4．一棵二叉树，叶子结点数为n0，度为2的结点数为n2。证明等式成立：n0=n2+1

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

1．已知二叉树中序遍历序列为ABCDEFGH;后序遍历序列为BADCGHFE.请写出前序遍历序列。

2．已知无向图G,如图所示。请画出其邻接矩阵，并写出从V1开始深度优先遍历的结点序列。

3．假设南京审计大学2021级学生共7个专业，每个专业的招生人数是:A300、B240、C200、D180、E160、F120、G100。请为每个专业赋予唯一2进制编码，使学生专业编码的总存储空间占用最少。

4．已知初始关键字序列54、94、59、80、53、78、28、19、64。请以54作为枢轴关键字，演示第一趟快速排序的交换过程。

5．已知带权无向连通图，如图所示。用图表演示普里姆算法从V2起始构造最小生成树过程。

6．已知有向无环图AOE网G，边代表活动，采用邻接表存储，其拓扑排序后顶点存储于T栈，数组ve[i]记录每个顶点事件i的最早开始时间。请把如下计算关键路径的算法补充完整。

7．已知La和Lb是按元素值递增排列的单链线性表。写算法把La和Lb合并为Lc，保持数据递增排列规律，并分析其时间复杂度。