资源描述
科目代码： 814 科目名称： 数据结构 第 1 页 共 2 页 南京审计大学 2020 年硕士研究生招生 考试 初试 （笔试） 试题 （ A 卷 ） 科目代码 : 814 满分 : 150 分 科目名称 : 数据结构 注意 : 认真阅读答题纸上的注意事项； 所有答案必须写在 答题纸 上，写在本试题纸或草稿纸上均无 效； 本试题纸须随答题纸一起装入试题袋中交回！ 一、 名词解释（共 6 小题，每题 5 分，总分 30 分） 1 抽象数据类型 2 数据逻辑结构 3 链式存储 4 线索二叉树 5 （排序）堆 6 关键路径 二、 简答题（共 4 小题，每题 10 分，总分 40 分） 1 说明哈希表工作原理以及常见的哈希冲突处理方法。 2 说明快速排序的基本原理，以及其优缺点。 3 说明顺序存储和链 式 存储的优缺点。 4 结合数据结构课程，举例说明 “空间换时间 ”。 三、 综合应用题（共 8 小题，每题 10 分，总分 80 分） 1 一棵二叉树，先序遍历顺序为： ABDCEFG；后序遍历顺序为： DBFEGCA。 画出 所有 满足上述 条件的二叉树。 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 写出以下代码的功能，并分析时间复杂度和空间复杂度。 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;
展开阅读全文