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

2020年南京审计大学数据结构考研真题911.pdf 科目代 码：911 科目 名称 ： 数据 结构 第1 页 共2 页 南京审计大学 2020 年硕士研究生招生 考试 初试（笔试） 试题 （ A 卷 ） 科目代码: 911 满分: 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 的邻 接 矩阵如 图所 示， 画出 其邻 接表。