1、 科目代码：911 科目名称：数据结构 第 1 页 共 2 页 南京审计大学南京审计大学 20202020 年硕士研究生招生年硕士研究生招生考试考试初试初试（笔试）（笔试）试题试题（ A A 卷卷 ） 科目代码: 911 满分: 150 分 科目名称: 数据结构 注意: 认真阅读答题纸上的注意事项；认真阅读答题纸上的注意事项；所有答案必须写在所有答案必须写在答题纸答题纸上，写在本试题纸或草稿纸上均无上，写在本试题纸或草稿纸上均无效；效；本试题纸须随答题纸一起装入试题袋中交回！本试题纸须随答题纸一起装入试题袋中交回！ 一、一、 名词解释（共名词解释（共 6 6 小题，每题小题，每题 5 5 分，
2、总分分，总分 3030 分）分） 1抽象数据类型 2数据逻辑结构 3链式存储 4线索二叉树 5 （排序）堆 6关键路径 二、二、 简答题（共简答题（共 4 4 小题，每题小题，每题 1010 分，总分分，总分 4040 分）分） 1说明哈希表工作原理以及常见的哈希冲突处理方法。 2说明快速排序的基本原理，以及其优缺点。 3说明顺序存储和链式存储的优缺点。 4结合数据结构课程，举例说明“空间换时间”。 三、三、 综合应用题（共综合应用题（共 8 8 小题，每题小题，每题 1010 分，总分分，总分 8080 分）分） 1一棵二叉树，先序遍历顺序为：ABDCEFG；后序遍历顺序为：DBFEGCA。
3、画出所有满足上述条件的二叉树。 2在一份电文中共使用有 A,B,C,D,E,F 6 种字符，他们出现的频率依次为 3,8,6,17,7,26。画出对应的编码哈夫曼树，设计每个字符的哈夫曼编码。 3已知带权有向图 G 如下图所示，用 Dijstra 迪杰斯特拉算法计算最短路径。S 用来记录求解过程已求得最短路径的终点集合。用图表演示 A 到达其它结点最短路径求解过程。 4已知无向图 G 的邻接矩阵如图所示，画出其邻接表。 科目代码：911 科目名称：数据结构 第 2 页 共 2 页 5对起始为空的平衡二叉树依次插入关键字序列 10，20，30，60，50。画出平衡二叉树的生成过程。 6写出以下代
4、码的功能，并分析时间复杂度和空间复杂度。 7已知顺序表 LCm和 LMn分别存储有语文成绩和数学成绩，且以学号从低到高排序，个别缺考学生在成绩表中未出现。写时间复杂度最优算法输出总分最高的人。已知成绩单结构： typedef struct int sno;/学号 int mark;/分数 score; /成绩 score LCm , LMn;/语文和数学成绩清单 8完成二叉树按层次遍历算法 void LevelOrder(BiTree T)。已知二叉链表存储结构： typedef struct BiTnode TElemType data; Struct BiTnode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;
