资源描述
西 安 建 筑 科 技 大 学 2018 年攻读硕士学位 研究生招生考 试试题 共 4 页 考试科目: 适用专业: （835）数 据结构 一、单项选 择题 （共10 题， 每小 题 2 分， 共 20分） 。 计 算机科学与技术、计算机技术、控制工程 1、算 法分 析的 目的 是（） 。 A找 出数 据结 构的 合理 性 B研究 算法 中的 输入和 输出关 系 C分 析算 法的 效率 以求 改进 D分析 算法 的可 读性和简 明性 2、若一个 顺序 表中 第一 个元素的 存储 地址 为 1000， 每个元 素占 4 个 地址 单元 ，那么 ，第 6 个元素 的存储 地址 应是 （） 。 A 1020 B1010 C1016 D1024 3、带头结 点的 单链 表（ 以 head 为头指 针） 为空 的判断条 件是 （） 。 Ahead!=NULL Bhead-next=head C head-next=NULL Dhead=NULL 4、 在一个 单链 表中 ，已知 q 指向 p 所指 结点 的前 驱结点 ， 若在p 、q 所指 结点之间 插入 一个 s 所指 向的新 结点 ，则 执行 的操 作是（ ） 。 Aq-next=s; s-next=p; Bp-next=s; s-next=q; Cs-next=p-next; p-next=s; Dp-next=s-next; s-next=p; 5、在一个 单链 表中 ，若 删除 p 指向结 点的 后继 结点 ，则执 行的 操作 为（ ） 。 Aq=p-next; p-next= p-next-next; free(q); Bp=p-next; q=p-next; p=q-next; free(q); Cq=p-next-next; p = p-next-next; free(q); Dp=p-next-next; q = p-next-next; free(q); 6、栈的操 作原 则是 （） 。 A 顺序进 出 B后进 后出 C 后 进先 出 D 先 进先出 7、一个队 列的 入队 序列 是 1，3，5 ，7 ，9， 则出 队的输 出序 列只 能是 （） 。 A9，7，5 ，3 ，1 B 1，3 ，5 ，7，9 C 1，5，9，3 ，7 D9 ，5，1 ，7 ，3 8、将一棵 有 100 个结 点 的完全 二叉 树从 根开 始， 每一层 从左 到右 依次 对结 点进行 编号 ，根 结点 的 编号 为 0，则编 号为 49 的 结点的 左孩 子编 号为 （） 。 A 99 B98 C50 D48 9、 以二 叉链 表作 为二 叉树 的存储 结构 ， 在 具有n 个结点的 二叉 链表 中 （n0 ） ， 空链 域的 个数 为 （） 。 A2n-1 B n+1 C n-1 D2n+1 10、无向图 的邻 接矩 阵是 一个（ ） 。 A对角 矩阵 B对 称矩 阵 C 上 三角 矩阵 D零矩 阵 第 1 页 第 2 页 二、填空题 （共20 空， 每空 1 分，共 20分） 。 1、数据结构一般包 括 、 和数据运算 三个方 面的 内容 。 2、数据的存储结构（物理 结构）可以用 、 存储方法表示。设 有一批 数据 元素 ， 为了最 快地存 取某 元素 ， 宜用 结构 存储； 为了方 便地 插入 一个 元素， 宜用 结构存 储。 3、 在长 度为n 的顺序 表的 第 i 个位置 上插 入一 个元 素，i 的合法 范围 是 ，元素 的 移动次 数为 ；删除 表中 第 i 个元素 ，i 的合 法范 围是 ，需 要向 前移 动 个元 素。 4、栈和队列都是 结构；对于栈，只能在 插入和删除元素；对于队列，只 能在 插入元 素，在 删除元 素。 5、 假设 以S 和X 分别 表示 进栈和 退栈 操作 ， 则对输 入序列 a， b， c ， d， e 进行一 系列栈操 作 SSXSXSSXXX 之后， 得到 的输 出序 列为 。 6、 对于一 个具 有 n 个顶点 和 e 条边的 无向 图， 若 采用邻接表 表示 ， 则表头 向量 的大小为 ， 所有邻 接表 中的 结点 总数 是 。 7、二分查 找的 存储 结构 仅限于 ，且是 。 8、对于二叉排序树上的查找，若结点元素的关键字值大于被查找元素的关键字值，则应该在该二 叉树的 继续 查找 。 三解 答题 （ 共7 题，共59 分） 。 1、 （14 分） 已知二 叉树 如 右图所 示。 请按 要求 回答 问题： （1）列出 该二 叉树 的所 有叶子结 点。 （2）请写 出 该二叉 树的 先序遍历 序列 、中序遍 历序 列 、后序遍 历序 列。 （3）请写 出该 二叉 树的 按层次遍 历序 列。 （4）将该 二叉 树调 整成 AVL 树。 （5） 若该 图为 “左 孩子 右兄弟 ”的 二叉 存储 结构 ，请画 出该 图所 对应 的树 （森林 ） 。 2、 （15 分） 已知图 G 的邻接表如 右图 所示 。 （1）请画 出该 存储 结构 对应的 图。 （2）请写 出该 图的 邻接 矩阵。 （3）请写 出该 图的 逆邻 接表。 （4）请写 出该 图从 顶点 1 出发的 深度 优先 搜索 序列 。 （5）请写 出该 图从 顶点 1 出发的 广度 优先 搜索 序列 。 1 2 3 4 5 2 3 4 4 5 2 4 e b a c d f西 安 建 筑 科 技 大 学 2018 年攻读硕士学位 研究生招生考 试试题 共 4 页 考试科目: 适用专业:（835）数据 结构 3、 （3 分）有一 组记 录的 关键字 序列 为46，79 ，56 ，38 ，40 ，84 ，利用 快速 排序的 方法 ，写出 以第 一个记 录为 基准 得到 的一 趟排序 结果 。 4、 （6 分） 对于给 定的 一组关键 字 41 ，62 ，13 ，84 ，35 ，96，57 ，39 ，79 ，61 ，15 ，83 ，写 出执 行 希尔排 序算 法的 第一 趟排 序结果 ，增 量 为5。 5、 （4 分） 对于 给定 的一 组关键 字26 ，18 ，60 ，14，7，45 ，13 ，32 ，写出 执行堆排 序算 法的 第一 趟排序 结果 。 6、 （8 分） 已知 带权 图如 下图所 示。 （1）请用 普里 姆 （Prim ）算法 求出 该图 的最 小生 成树。 （2）请用 克鲁 斯卡 尔 （Kruskal ）算法 求出 该图 的最小生 成树 。 计算机科学与技术、计算机技术、控制工程 7、（ 9 分） 试分 析以 下 3 个程序 片段 的时 间复 杂度 。 第 3 页 第 4 页 四、算法设 计题 （ 共5 题， 共51分） 。 1、 （15 分） 求两个 正整 数的最大 公约 数可 以使 用欧 几里德 算法 。该 算法 的基 本思想 如下 ：两个正 整数的 最大 公约 数等 于其 中较小 的那 个数 和两 数相 除余数 的最 大公 约数 。 （1） 请设计 递归 版本的 欧几里德 算法 。 int EuclideanRecursive (int a, int b) （2） 请设计 非递归 版本 的欧几里 德算 法。 int EuclideanIterative (int a, int b) 2、（ 10 分） 设二叉 树的 根指针 为 bt ， 设计 算法求二叉 树的高度 。 int HeightTree(BTreeNode *bt) 3、（ 8 分） 已知 数组R 中存储 的 m 项数据 是乱 序的 （即没 有按 照从 小到 大的 顺序排 列好 ） ，请 设计 算法判断待 查元 素 x 是否 在数组 中出 现。 int Search(int R, int m, int x) 4、（ 8 分） 设二 叉排 序树 的根指 针为 bt ， 设计算法求二叉 排序 树中 最大 的关 键字值 。 int Maximum(BSTreeNode *bt) 5、（ 10 分） 基于 合理的 有向图 存储结 构， 设计 算法 判定给 定连 通有向图 G 是否存在 回路 。 bool ExistCyclePath(Graph G)
展开阅读全文