1、 科目代码:814 科目名称:数据结构 第 1 页 共 2 页 南京审计大学南京审计大学 20202020 年硕士研究生招生年硕士研究生招生考试考试初试初试(笔试)(笔试)试题试题( A A 卷卷 ) 科目代码: 814 满分: 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 的邻接矩阵如图所示,画出其邻接表。 科目代码:814 科目名称:数据结构 第 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;