华中农业大学2018考研真题之867-数据结构与算法.docx

返回 相关 举报
华中农业大学2018考研真题之867-数据结构与算法.docx_第1页
第1页 / 共4页
亲,该文档总共4页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
华 中 农 业 大 学 2018 年 硕 士 研究生 入 学 考 试试科 目 代码及名称 : 867 数 据 结 构与算法题 纸第 1 页 共 4页注 意 : 所 有 答 案 必 须 写 在 答 题 本 上 , 不 得 写 在 试 题 纸 上 , 否 则 无 效 。一 、 名 词 解 释 ( 共 20 分 , 每 题 4 分)1、 算 法 及 算 法的特性 2 、树的度及深度 3、 完 全 二 叉 树4、 索 引 文 件 5、 强 连 通 性二 、 选 择 题 ( 共 30 分 , 每 题 2 分)1、 设 核 S 和队列 Q 的初始状态均为 空 , 元 素 ABCDEFG 依次进技 S。 若 每 个 元 素 出 校 后 立 即 进 入 队 列 Q, 且 7 个元 素 的 出 队 顺 序 是 BDCFEAG, 则 核 S 的容量 至 少 是 :A. 1 B. 2 C. 3 D. 42 、 已知一棵完全二叉树的第六 层 ( 根为 第一层 有 8 个 叶 子 结 点 , 则 完 全 二 叉 树 的 结 点 个 数 最 多 是 :A. 39 B. 52 C. 111 D. 1193 、 下列叙述中不符 合 m 阶 B 树定义要求的是 :A. 根结点最多有 m 棵子树 B. 所有叶结点在同 一层上C. 各结点内关键 字 均 升 序 或 降 序 排 列 D. 叶结点之间 通过指针链接4 、 若 无 向 图 中 含 有 7 个顶点 , 贝 。 保 证 图 在 任 何 情 况 下 都 是 连 通 的 , 需 要 的 边数最少是 :A . 6 B. 15 C. 16 D. 215、 对 一 组 数 据 ( 7 , 17 , 21,93 , 10 , 16 ) 进行排序 , 若 前 三 趟 排 序 结 果 如 下 , 则采用的排序方法是 :第一趟 : 7 , 17 ,21, 10 , 16, 93第 二趟 : 7 , 17 , 10, 16 ,21, 93第 二趟 : 7 , 10 , 16 ,17 ,21,93A . 冒泡 排序 B. 希 尔 排 序 C. 归并排序 D. 基 数 排 序6、 已知一 才 果有 2011 个结点的树 , 其叶结 点 个数 为 116 , 该树 对 应的二叉树 中无右 孩 子的结点个数是 :A. 115 B. 116 C. 1895 D. 18967 、 已知 字 符 串 S 为 “abaabaabacacaabaabcc“ . 模式串 t 为 “abaabc ” , 采 用 KMP 算 法进行匹配 , 第一次出现 “ 失 自 己 ” ( s i != t i ) 时 , i=j 习 , 则 下 次 开 始 匹 配时 , i 和 j 的 值 分别是 :A. i= l ; j=O ; B. i二 5; j =O ; C. i=5 ; j =2 ; D . i=6 ; j=2 ;8、用哈希 ( 散列 方法处理冲突 ( 碰撞 时可能出现堆积 ( 聚集) 现象 , 下列选项 中,会受堆积现象直接影响的是 :A. 存储效率 B. 数列函数C. 装填 ( 装载 因 子 D. 平 均 查 找 长 度华 中 农 业 大 学 2018 年 硕 士 研究生 入 学 考 试试科 目 代码及名称 : 867 数 据 结 构与算法题 纸第 2 页 共 4页2注 意 : 所 有 答 案 必 须 写 在 答 题 本 上 , 不 得 写 在 试 题 纸 上 , 否 则 无 效 。9、 循环队列放在一维数组 A O M- 1 中 , endl 指向队头元 素 , end2 指向 队尾 元 素的后一个位置 。 假设队列 两 端均可 进 行 入 队 和出队操作 , 队列 中 最多 能容纳 M-1 个元素 。 初始时为 空 。 下列判断队空和队满的条件中 , 正确的是 :A . 队空 : endl = end2 ; 队 满 : endl = (end2+1) mod MB. 队空 : endl = end2 ; 队 满 : end2 = (end l+1) mod (M- 1)c. 队空 : end2 = (end l+) mod M; 队 满 : endl = (end2+1) mod MD. 队空 : endl = (end2+ 1) mod M; 队 满 : end2 = (end 1+1) mod (M- 1)10、 非 空 的循环单链表 head 的 尾 结 点 ( 由 p 所指向 满足 :A . P一 next= =N1JLL ; B. p=NULL;C. p-next=head ; D. p=head11、 查 找效率最高的 二叉排序树是 :A . 所有结点的左 子树都为 空 的二叉排序树B. 所有结点的右子树都为 空 的 二 叉 排 序 树c. 平衡二叉树D. 没 有 左 子 树 的 二 叉 排 序 树12、 下 面 关 于 求 关 键 路 径 的 说 法 不 正 确 的 是 :A . 求 关 键 路 径 是 以 拓 扑 排 序 为 基 础 的B. 关键活动一定位于关键路径上C. 一 个 事 件 的 最 早 开 始 时 间 同 以该事件为 尾的弧的活 动最早开始时间 相 同D. 一 个 事 件的最迟开 始时间 为 以 该 事 件 为 尾的弧的活 动 最迟开 始时间 与 该 活 动的持续时间的差13 、 在 一 个 单 链 表 中 , 若 q 结点是 p 结 点的前驱结点 , 若 在 q 和 p 之 间 插 入结点 s, 则 执 行 :A . P甲 next=s一 next ; s-nex t=p:B. s-nex t=p一 next ; p next=s ;C. P一 next=s ; s一 next=q;D. q一 next=s ; s-next=p;14 、 设 有 一个对 称 矩阵 A , 采用压 缩存储方式 , 以行序为 主序存储 , al l 为 第 一个元 素 , 其存储地址为 1, 每个元 素 占 一个地 址空 间 , 则 a85 地 址 为 :A. 23 B. 33 C. 18 D. 4015、 就平均 查找速度 而 言, 下列几种查找速度从慢 至快的关系是 :A. JI顶 序 折半 哈希 分块 B. 分块 折半 哈希 顺序C. 顺序 分块 折半 哈希 D. 顺序 哈希 分块 折 半三 、 填 空 题 ( 共 20 分 , 每题 2 分 )1 、 广义表 A= (x , 旬 , b, c , d) ) 的表 尾 是 一 一 一华 中 农 业 大 学 2018 年 硕 士 研究生 入 学 考 试试科 目 代码及名称 : 867 数 据 结 构与算法题 纸第 3 页 共 4页32211注 意 : 所 有 答 案 必 须 写 在 答 题 本 上 , 不 得 写 在 试 题 纸 上 , 否 则 无 效 。2、在双循环链表中 , 删 除 指 针 p 所指结 点 的 语 句 序 列 是 一 一 一 和 一 一 一 。3、 快 速 排 序 是 一 一 一 排 序 改进后的结果 。4 、求解一个图的单源和多 源 最 短 路 径 的 算 法 分 别 是 一 一 一 和 Floyd 算 法 。5、 通常称 表示前驱和后继的指针叫做一 一 一 而 这种使树中 结点的空指针 成 员存放前驱或后继信息的过程叫做一 一 一 。6、 图 的 一 一 一 优 先 搜 索 类 似 于树的层次遍历 。7 、设给定权值总数有 n 个 , 其 哈 夫 曼 树 的 结 点总数为 一 一 一 。8、 希 尔 排 序 、快速排序和冒泡排序中 一 一 一 是 稳 定 的 排 序 方 法 。9 、 堆排序的 两 个 重 要 步 骤其 一 是 一 一 一 其 二 是 调 整 堆 。10、 KMP 算 法 中 , 串 ababaaababaa 的 next 数 组 为 一 一 一 。四 、 应用题 ( 共 50 分 , 第 1- 6 题 每题 7 分 , 第 7 题 8 分) l 、 给定二叉树的 两种遍历 序列 , 分别是 : 前 序 遍历序列 : EBIDGCAH F;中序遍历序列 : EIGDCBHFA ,( 1 ) 试画 出二叉 树 ;( 2 ) 并给出二叉树的后序 遍历序列 。2、 下图是一个无向带权图 , 请按照 Pri m 算法从 A 节 点出发构造一棵最小 生成树 , 并画出其 生 成过程 。781210 16 8203、 给定一组数列 ( 10, 18 , 16, 25 , 6 , 9 , 16) 分别代表 字 符 A, B, C , D , E , F, G 出 现的频 率 , 试画 出哈夫曼树的构造过程 , 并给出各 字 符的编码值 。4 、 已知长度为 12 的表 ( jan , f eb, mar , apr , may , j une , ju ly , aug , sep, oct , nov , dec ) , 请 按 表 中 元 素 顺 序 构 造 一 棵 二 叉 平 衡 树 , 并 简 单的 画 出构造过程 。 其中 , 无 旋 转 的 调 整 可 以 直 接 画在一张图上 , 有 旋 转 的 调 整 请 单独 画图并备注 清 楚 。5 、 给定关键 字 序列 : 15, 38, l l , 84 , 49, 20 , 7 , 33, l4 , 29 , 36 。 请 写 出以下 3 种排序 方 法 的 第 一趟 排序 结 果 (1) 选 择排序 ( 2) 快速排序 ( 3) 增量 为 4 的 希 尔 排 序 ; 请写出建好一个大根堆的结果 ; 请写 出 第 一 趟堆排 序 以后的结 果 。华 中 农 业 大 学 2018 年 硕 士 研究生 入 学 考 试试科 目 代码及名称 : 867 数 据 结 构与算法题 纸第 4 页 共 4页4注 意 : 所 有 答 案 必 须 写 在 答 题 本 上 , 不 得 写 在 试 题 纸 上 , 否 则 无 效 。6 、设散列 表的长 度为 13 , 散 列 函 数 为 H(k) =k%13 , 给 定 的 关 键 码 序列 为19 ,13, 22 ,02, 68 , 15 ,84, 26 。 试 画出用 线性探测法解决冲突 时 所 构 成的散列 表 , 并求出平均查找长度 ASL 。7 、 用 迪杰斯特拉 ( Dijk stra ) 算法 求 下图 中 V l 顶点到其他个顶点的 最短 距 离 和最短路径 , 请根据下表补充完整的求解过程 。从 vl 到各终点的距离值和最短路径的求解过程终点I= l I=2 I=3 1=4V2V3V4V5V js提示 : V j 为 每次新并入的顶点 , S 为 巳求得最短路径的顶点的集合 。五 、程序设计题 ( 共 30 分 , 每 题 10 分)l 、 设 计 一个求二叉树的宽度 的 算 法 。2、 已 知 一 个 带 表 头 结 点 的 线 性 链 表 , 试 写 出 用 直接插入排序方法将 其结点 按递增顺序排序的算法 , 算 法 中要尽可 能少用辅助存储 空 间 。3、 请 设 计 深 度 遍 历 图 的 非 递归算 法 。
展开阅读全文
相关资源
相关搜索
资源标签

考研文库@kaoyanwenku.com