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