2016年武汉大学测绘学院数据结构和数据库之数据结构(同等学力加试)考研复试题库
● 摘要
一、选择题
1． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有（ ）个叶子。
答:D
【解析】二叉树结点总数分别代表度为0，度为1，度为2的结点数）。
因
此又在非空二叉树中
：且本题所给树为正则二叉树
，所
以
2． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 直接插入排序
B. 起泡排序
C. 基数排序
D. 快速排序
答:C
【解析】C 项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD 三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n （n-1） /2次（
为元素个数）。
3． 主机甲和乙已建立了TCP 连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗
口为8KB , 则从t 时刻起，不再发生超时的情况下，经过10个RTT 后，甲的发送窗口是（ ）。
A.10KB
B.12KB
C.14KB
D.15KB
答:A
【解析】发送窗口是接受窗口和拥塞窗口的最小值，这里接收窗口总是10KB 。拥塞窗口到那个时候是大于10KB 的，取最小值。
4． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ） A. B. C. D.
答:D
【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。
5． 若磁盘转速为7200转/分，平均寻道时间为8ms , 每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是（ ）。 A. B. C. D.
答:B
【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms , 平均等待时间与磁盘转速有关，
为
因此总的时间为：磁盘的存取一个扇区的时间
为
6． 响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（ ）。
I. 开关中断II. 保存通用寄存器的内容III. 形成中断服务程序入口地址并送PC
A. 仅I 、II
B. 仅 I 、III
C. 仅 II 、III
D.I 、II 、III
答:B 。
【解析】中断隐指令完成的操作有3个：①保存断点；②关中断；③引出中断服务程序（形成中断服务程序入口地址并送PC ）。而保存通用寄存器内容的操作是由软件来实现，不是由中断隐指令实现的。
7． 某计算机的Cache 共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache 组号是（ ）。
A.0
B.2
C.4
D.6
答:C
【解析】首先根据主存地址计算所在的主存块号，然后根据组相联映射的映射关系K=ImodQ