2018年河北大学电子信息工程学院929数据结构(电)考研强化五套模拟题
● 摘要
一、单选题
1． 某计算机有五级中断
的顺序为
A.11110
B.01101
C.00011
D.01010
【答案】D , 则, 中断屏蔽字为表示对级中断进行
屏蔽。若中断响应优先级从高到低的顺序是, 且要求中断处理优先级从高到低的中断处理程序中设置的中断屏蔽字是（ ）。
B
排除掉。【解析】由于L 2的中断处理优先级下降, 屏蔽字中需要3个0, 所以可以将选项A 、
需要对开放, 所以相应位应该为“0”, 即为01010。
2． 数据链路层采用选择重传协议(SR)传输数据, 发送方已发送了0H3号数据帧, 现已收到1号帧的确认, 而0、2号帧依次超时, 则此时需要重传的帧数是（ ）。
A.1
B.2
C.3
D.4
【答案】B
【解析】在选择重传协议中, 接收方逐个地确认正确接收的分组, 不管接收到的分组是否有序, 只要正确接收就发送选择ACK 分组进行确认。因此选择重传不支持累积确认, 要特别注意其与GBN 协议的区别。本题收到1号帧的确认, 说明1号帧正确接收, 0和2号帧依次超时, 因此必须重传, 然而3号帧尚未超时, 是否正确接收未知, 故不用重传, 因此必须重传0和2号帧, 答案是B 。
3． 一个非空广义表的表尾（ ）。
A. 不能是子表
B. 只能是子表
C. 只能是原子
D. 是原子或子表
【答案】B
【解析】广义表的定义是一个递归定义，当广义表非空时，称第一个元素是它的表头，称其余元素构成的表称为它的表尾。因此一个非空广义表的表尾只能是子表。
4． 若对如下无向图进行遍历, 则下列选项中, 不是广度优先遍历序列的是（ ）
A.h , c , a , b , d , e , g , f
B.e , a , f , g , b , h , c , d
C.d , b , c , a , h , e , f , g
D.a , b , c , d , h , e , f , g
【答案】D
【解析】根据广度优先遍历的定义, 可知选项A 、B 、C 都为广度优先遍历, 而选项D 是深度优先遍历而不是广度优先遍历, 故答案为D 。
5． 若需在的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
【答案】C
【解析】稳定排序有:插入排序、起泡排序、归并排序、基数排序。不稳定排序有:快速排序、堆排序、shell 排序。时间复杂度平均为
6． 设有向图G=(V, E) , 顶点集
边集 的有:归并排序、堆排序、shell 排序、快速排序。,
,
若从顶点V0开始对图进行深度优先遍历, 则可能得到的不同遍历序列个数是（ ）。
A.2
B.3
C.4
D.5
【答案】D
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索, 所以可能得到的不同遍历序列分别是: ①
④
' ; ②; ⑤; ③。 ;
7． 若用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 则关于该图拓扑序列的结论是（ ）。
A. 存在, 且唯一
B. 存在, 且不唯一不唯一
C. 存在, 可能不唯一
D. 无法确定是否存在
【答案】C 。
【解析】图的基本应用--拓扑排序, 用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 说明该图为有向无环图, 所以其拓扑序列存在, 但不一定唯一,
如图的邻接矩阵为, 则存在两个拓扑序列。
8． 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为（ ）。 A.
B.n/2 C.
D.n
【答案】C
【解析】最快查找一次成功，最慢查找n
次成功。平均查找次数为
。
9． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素, 则关键字的比较次数最多是（ ）。
A.4
B.5
C.6
D.7
【答案】B
【解析】
折半查找法在查找不成功时和给定值进行比较的关键字个数最多为
题中, n=16, 故比较次数最多为5。
10．下列有关总线定时的叙述中, 错误的是（ ）。
A. 异步通信方式中, 全互锁协议最慢
B. 异步通信方式中, 非互锁协议的可靠性最差
那么, 在本