2018年安徽理工大学软件工程841数据结构考研核心题库
● 摘要
一、单项选择题
1． 循环队列A[0..m﹣1]存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是（ ）。
A.(rear﹣front ＋m)%m
B.rear ﹣front ＋1
C.rear ﹣front ﹣1
D.rear ﹣front
【答案】A
【解析】对于循环队列，需要深刻理解队头(font)和队尾(rear)的概念，在队头进行出队操作，在队尾进行进队操作。rear-front 可能为正也可能为负，为正时元素个数＝(rear-front)；如果为负则元素的个数＝(rear-front+m)，所以统一的公式就是(rear-front+m)%m。
2． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1, 则该平衡二叉树的结点总数为（ ）。
A.12
B.20
C.32
D.33
【答案】B 。
【解析】本题的实际问题是, 具有6层结点的平衡二叉树含有最少的结点数是多少。
深度为h 的平衡二叉树中含有的最少结点数, 有
由此可得。对应的平衡二叉树如下图所示。
表示
3． 在任意一棵非空二叉排序树T1中, 删除某结点v 之后形成二叉排序树T2, 再将v 插入T2形成二叉排序树T3。下列关于T1与T3的叙述中, 正确的是（ ）
Ⅰ. 若v 是T1的叶结点, 则T1与T3不同
Ⅱ. 若v 是T1的叶结点, 则T1与T3相同
Ⅲ. 若v 不是T1的叶结点, 则T1与T3不同
Ⅳ. 若v 不是T1的叶结点, 则T1与T3相同
A. 仅Ⅰ、Ⅲ
B. 仅Ⅰ、Ⅳ
c. 仅Ⅱ、Ⅲ
d. 仅Ⅱ、Ⅳ
【答案】C
【解析】在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中, 如果删除的结点是叶子结点那么在插入结点后, 后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点, 那么再插入这个结点后, 后来的二叉树可能发生变化, 不完全相同。
4． 在子网中, 能接收目的地址为的IP 分组的最大主机数是（ ）。
A.0
B.1
C.2
D.4
【答案】C
【解析】每个子网中忽略子网内全为0和全为1的地址剩下的就是有效主机地址, 本题中由于子网的比特数是30, 因此用于主机的只有2位, 即00, 01, 10, 11, 有效主机地址是2个,
这里
显然是其广播地址, 因此答案是C 。
5． 单处理机系统中，可并行的是（ ）.
(1)进程与进程
(2)处理机与设备
(3)处理机与通道
(4)设备与设备
A. (1)、(2)和(3)
B. (1)、(2)和(4)
C. (1)、(3)和(4)
D. (2)、(3)和(4)
【答案】D
【解析】注意区分并发和并行. 在单处理机系统中，进程只能并发. 微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的. 通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行. 显然，设备和设备之间也是可以并行的.
6． 下列选项中, 对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA
B.CDMA C.
D.
【答案】D
【解析】可采用排除法。CDMA 是码分多址复用, 是物理层的内容; CSMA/CD即带冲突检测的载波监听多路访问, 接收方并不需要确认; CSMA/CD是CSMA 的加强版, 故CSMA 也无确定; CSMA/CD是中的协议, 其利用ACK 信号来避免冲突的发生, 也就是说, 只有当客户端收到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址, 因此答案是D 。
7． 用希尔排序方法对一个数据序列进行排序时, 若第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 正确
8． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 直接插入排序
B. 起泡排序
C. 基数排序
D. 快速排序
【答案】C
【解析】C 项, 基数排序是采用分配和收集实现的, 不需要进行关键字的比较。ABD 三项都依赖关键字的比较, 不同的初始排列次序下元素移动的次数有很大变化, 最好情况元素正序, 则不用移动, 最坏情况元素反序, 则需要移动次(n为元素个数) 。
9． 下列排序算法中，占用辅助空间最多的是（ ）。
A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序
【答案】A
【解析】归并排序的辅助空间为O(n)，快速排序所占用的辅助空间为
，堆排序所占