1、 科目代码：911 科目名称：数据结构 第 1 页 共 2 页 南京审计大学南京审计大学 2022021 1 年硕士研究生招生年硕士研究生招生考试考试初试初试（笔试）（笔试）试题试题（ A A 卷卷 ） 科目代码: 911 满分: 150 分 科目名称: 数据结构 注意: 认真阅读答题纸上的注意事项；认真阅读答题纸上的注意事项；所有答案必须写在所有答案必须写在答题纸答题纸上，写在本试题纸或草稿纸上均无上，写在本试题纸或草稿纸上均无效；效；本试题纸须随答题纸一起装入试题袋中交回！本试题纸须随答题纸一起装入试题袋中交回！ 一名词解释（共一名词解释（共 6 小题，每题小题，每题 5 分，共分，共 3
2、0 分）分） 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
3、, 如图所示。请画出其邻接矩阵，并写出从 V1 开始深度优先遍历的结点序列。 3假设南京审计大学 2021 级学生共 7 个专业，每个专业的招生人数是: A 300、B 240、C 200 、D 180 、E 160、F 120、G 100。请为每个专业赋予唯一 2 进制编码，使学生专业编码的总存储空间占用最少。 4已知初始关键字序列 54、94、59、80、53、78、28、19、64。请以 54 作为枢轴关键字，演示第一趟快速排序的交换过程。 5已知带权无向连通图，如图所示。用图表演示普里姆算法从 V2 起始构造最小生成树过程。 科目代码：911 科目名称：数据结构 第 2 页 共 2 页
4、 6已知有向无环图 AOE 网 G，边代表活动，采用邻接表存储，其拓扑排序后顶点存储于 T 栈，数组 vei记录每个顶点事件 i 的最早开始时间。请把如下计算关键路径的算法补充完整。 Status CriticalPath ( AOEGraph G) vl0.G.vexnum-1=ve0.G.vexnum-1;/初始化顶点最迟开始时间 while(!StackEmpty(T) for(Pop(T, j), p=G.verticesj.firstarc; p; p=p-nextarc) k=p-adjvex; dut=*(p-info);/耗时权重 if(vlk-dutvlj) _(1)_; f
5、or(j=0;jnextarc) k=p-adjvex; dut=*(p-info); (2) (3) tag=(ee=el)?*:; printf( j, k, dut, ee, el, tag);/输出关键活动 7已知 La 和 Lb 是按元素值递增排列的单链线性表。写算法把 La 和 Lb 合并为 Lc，保持数据递增排列规律，并分析其时间复杂度。 void Merge_List( LinkList &La, LinkList &Lb, LinkList &Lc) 8请把计算二叉树深度函数 TreeDepth( )补充完整。 typedef struct BinaryTree int data; struct BinaryTree *Left; struct BinaryTree *Right; struct BinaryTree *Parent; Node; /递归求二叉树深度 int TreeDepth(BinaryTree* root)
