2018年中国农业科学院蜜蜂所808数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 一个具有1025个结点的二叉树的高h 为（ ）。
A.11
B.10
C.11至1025之间
D.10至1024之间
【答案】C
【解析】当一棵树是完全二叉树时，其高度最低，此时高度为11，当一棵树的结点在一条线上时，此时最高，这时二叉树的高度是1025。
2． 对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储
B. 以顺序方式存储，且数据元素有序
C. 以链接方式存储
D. 以链接方式存储，且数据元素有序
【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
3． 某CPU 主频为, 采用4级指令流水线, 每个段的执行需要1个时钟周期。假定CPU 执行了100条指令, 在其执行过程中没有发生任何流水线阻塞, 此时流水线的吞吐率为（ ） A.
B.
C.
D.
【答案】C
【解析】采用4级流水线执行100条指令, 在执行过程中共用
CPU 的主频是
故答案为C 。
条指令/秒 条指令/秒 条指令/秒 条指令/秒 个时钟周期。 , 也就是说每秒钟有个时钟周期。流水线的吞吐率为
条指令/秒,
4． ARP 协议的功能是（ ）。
A. 根据IP 地址查询MAC 地址
B. 根据MAC 地址查询IP 地址
C. 根据域名查询IP 地址
D. 根据IP 地址查询域名
【答案】A 。
【解析】ARP 协议是网络层协议, 因此只能和传输层和数据链路层有关系, 从这一点出发, 域名是应用层的范畴, 选项C 和D 是不正确的, 根据MAC 地址查询IP 地址是RARP 协议的功能, 因此进而得出正确答案是A 。
5． 有n(n＞0) 个分支结点的满二叉树的深度是（ ）。
A.n 2﹣l
B.log 2(n＋1) ＋1
C.log 2(n＋1)
D.log 2(n—1)
【答案】C
【解析】满二叉树的结点总数＝分支的结点总数＋非分支的结点总数。由于此树为满二叉树，
所以非分支的结点总数为1，所以满二叉树共有n ＋1个结点，所以满二叉树的深度为log 2 (n＋1) 。
6． 用希尔排序方法对一个数据序列进行排序时, 若第1趟排序结果为9, 1, 4, 13, 7, 8, 20, 23, 15, 则该趟排序采用的增量(间隔) 可能是（ ）
A.2
B.3 C.4
D.5
【答案】B
【解析】对于A , 增量为2, 那么9, 4, 7, 20, 15是一组, 而它们是无序的, 所以A 错误
对于C , 增量为4, 那么9, 7, 15是一组, 而它们是无序的, 所以C 错误
对于D , 增量为5, 那么9, 8是一组, 降序, 1, 20是一组, 而它们是升序, 所以D 也错误。对于B , 分为3组:9, 13, 20; 1, 7, 23; 4, 8, 15都是升序有序, 所以B 正确
7． 在下图所示的平衡二叉树中, 插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中, 关键字37所在结点的左、右子结点中保存的关键字分别是（ ）。
A.13、48
B.24、48
C.24、53
D.24、90
【答案】C
【解析】题目中, 插入48以后, 树根结点的平衡因子由-1变为-2, 失去平衡。这属于RL(先右后左) 型平衡旋转, 需做两次(先右旋后左旋转) 旋转操作。过程如下图所示:
显然, 在调整后的新平衡二叉树中, 关键字37所在结点的左、右子结点中保存的关键字分别是24, 53。
8． 直接插入排序在最好情况下的时间复杂度为（ ）。 A.
B.O(n) C. 2D.O(n)
【答案】B
【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾的一个元素进行比较，此时的时间复杂度最好，为O(n)。
9． 线性表的顺序存储结构是一种（ ）。
A. 随机存取的存储结构
B. 顺序存取的存储结构
C. 索引存取的存储结构
D.Hash 存取的存储结构
【答案】A
【解析】线性表包括顺序存储结构和链式存储结构，顺序存储结构能够随机存取表中的元素，但插入和删除操作较麻烦，链式存储结构不能随机访问表中的元素，但是能够表示元素之间的先后次序，而且插入和删除操作较容易。
10．已知串其Next 数组值为（ ）。
A.0123
B.1123
C.1231
D.1211
相关内容
相关标签