2020年南京审计大学数据结构考研真题814.pdf0页

2020年南京审计大学数据结构考研真题814.pdf 科目代码：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 的邻接矩阵如图所示，画出其邻接表。