资源描述
科目代码： 814 科目名称： 数据结构 第 1 页 共 2 页 南京审计大学 2021 年硕士研究生招生 考试 初试 （笔试） 试题 （ A 卷 ） 科目代码 : 814 满分 : 150 分 科目名称 : 数据结构 注意 : 认真阅读答题纸上的注意事项； 所有答案必须写在 答题纸 上，写在本试题纸或草稿纸上均无 效； 本试题纸须随答题纸一起装入试题袋中交回！ 一名词解释（共 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个专业，每个专业的招生人数是 : 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起始构造最小生成树过程。 科目代码： 814 科目名称： 数据结构 第 2 页 共 2 页 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)_; for(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 struct BinaryTree *Left; struct BinaryTree *Right; struct BinaryTree *Parent; Node; /递归求二叉树深度 int TreeDepth(BinaryTree* root)
展开阅读全文