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

 注 意 ：所 有 答 案 必 须 写 在 答 题 本 上 ， 不 得 写 在 试 题 纸 上 ， 否 则 无 效 。

一 、名词解释 （ 共 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.  4

2 、 已知一棵完全二叉树的第六 层 （ 根为 第一层〉 有 8 个叶子结点 ，则完 全 二叉树的结点个数最多是 ：

A. 39 B. 52 C. 111 D. 119

3 、下列叙述中不符 合 m 阶 B 树定义要求的是 ：

A. 根结点最多有 m 棵子树 B. 所有叶结点在同 一层上

C. 各结点内关键 字均升序或降序排列 D. 叶结点之间 通过指针链接

4 、若无向图中含有 7 个顶点 ，贝。保证图在任何情 况下都是连通的 ，需要的 边数最少是 ：

A . 6 B. 15 C. 16 D. 21

5、对一组数据 （ 7 , 17 , 21,93 , 10 , 16 ） 进行排序 ，若前三趟排序结果如 下， 则采用的排序方法是 ：

第一趟 ：7 , 17 ,21, 10 , 16, 93

第 二趟 ：7 , 17 , 10, 16 ,21, 93

第 二趟 ：7 , 10 , 16 ,17 ,21,93

A . 冒泡排序 B. 希尔排序 C. 归并排序 D. 基数排序

6、已知一才果有 2011个结点的树 ，其叶结 点个数 为 116 ，该树 对应的二叉树 中无右孩子的结点个数是 ：

A. 115 B. 116 C. 1895 D. 1896

7 、已知字符 串 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. 平均查找长度

9、循环队列放在一维数组  A [O ···M-1］ 中，endl  指向队头元 素 ，end2  指向 队尾元素的后一个位置 。假设队列 两端均可 进行入队和出队操作 ，队列中最多 能容纳 M-1 个元素 。初始时为 空 。下列判断队空和队满的条件中 ，正确的是 ：

A . 队空 ：endl == end2 ; 队满：endl == (end2+1) mod M

B.  队空 ：endl  ==  end2 ; 队满：end2  ==  (endl+1) mod   (M-1)

c.  队空 ：end2  ==   (endl+l) mod  M; 队满：endl  ==   (end2+1) mod  M

D. 队空 ：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==head

11、查找效率最高的 二叉排序树是 ：

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->next=p一＞next ; p  ＞next=s ;

C. P一＞next=s ; s一＞next=q;

D.   q一＞next=s ; s->next=p;

14 、设有 一个对称矩阵 A ，采用压 缩存储方式 ，以行序为 主序存储 ，all为 第一个元 素 ，其存储地址为 1，每个元 素 占一个地 址空 间，则 a85 地 址为 ：

A. 23 B. 33 C. 18 D. 40

15、就平均查找速度而言，下列几种查找速度从慢 至快的关系是 ：

A. JI顶序

折半 哈希 分块

B. 分块 折半 哈希 顺序

C. 顺序

分块 折半 哈希

D. 顺序 哈希 分块 折半

三 、填空题 （ 共 20 分 ，每题 2 分）

1、广义表 A= (x ，旬，b, c , d） ） 的表尾是一一一

注 意 ：所 有 答 案 必 须 写 在 答 题 本 上 ， 不 得 写 在 试 题 纸 上 ， 否 则 无 效 。

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、下图是一个无向带权图 ，请按照 Prim 算法从 A  节 点出发构造一棵最小 生成树 ，并画出其 生成过程 。

3、给定一组数列 （ 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 的希尔排 序 ；请写出建好一个大根堆的结果 ；请写 出第一趟堆排 序 以后的结果。

注 意 ：所 有 答 案 必 须 写 在 答 题 本 上 ， 不 得 写 在 试 题 纸 上 ， 否 则 无 效 。

6 、设散列 表的长 度为 13 ，散列 函数为 H(k) =k%13 ，给定的关键码 序列 为

19 ,13, 22 ,02, 68 , 15 ,84, 26 。试 画出用 线性探测法解决冲突 时所构 成的散列 表， 并求出平均查找长度 ASL 。

7 、用 迪杰斯特拉 （ Dijk stra ） 算法 求下图 中 V l  顶点到其他个顶点的 最短 距离和最短路径 ，请根据下表补充完整的求解过程 。

五 、程序设计题 （ 共 30 分 ，每题 10 分）

l、设计一个求二叉树的宽度 的算法。

2、已知一个带表头结点的线性链表 ，试写出用 直接插入排序方法将 其结点 按递增顺序排序的算法 ，算法 中要尽可 能少用辅助存储 空 间。

3、请设计深度遍历图的非 递归算 法 。

文章来源: aaaedu.blog.csdn.net，作者：tea_year，版权归原作者所有，如需转载，请联系作者。

原文链接：aaaedu.blog.csdn.net/article/details/105282898