2016年武汉大学测绘遥感信息工程国家重点实验室数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 下列存储器中，在工作期间需要周期性刷新的是（ ）。
A.SRAM B.SDRAM C.ROM D.FLASH 【答案】B
【解析】动态随机存储器（DRAM ）是利用存储元电路中栅极电容上的电荷来存储信息的，电容上的电荷一般只能维持
因此即使电源不掉电，信息也会自动消失。为此，每隔一定时
间必须刷新。
2． 折半查找的时间复杂性为（ ）。
【答案】D
【解析】顺序查找的事件复杂度为
因为折半查找是查找效率最高的算法，它的事件复杂
度为
3． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
【答案】C
【解析】两个循环嵌套，那么语句x :=x＋l :
则被执行了次。
4． 下列关于无向连通图特性的叙述中，正确的是（ ）。
I. 所有的顶点的度之和为偶数 II. 边数大于顶点个数减1 III. 至少有一个顶点的度为1 A. 只有I B. 只有II C.I 和II D.I 和III 【答案】A
【解析】在图中，顶点的度TD 点数，
之和与边的数目满足关系式：（n 为图的总结
e 为总边数），因此，I 项正确。对于II 、III 项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。
图
5． 下列关于闪存（FlashMemory ）的叙述中，错误的是（ ）。
A. 信息可读可写，并且读、写速度一样快 B. 存储元由MOS 管组成，是一种半导体存储器 C. 掉电后信息不丢失，是一种非易失性存储器 D. 采用随机访问方式，可替代计算机外部存储器 【答案】A 。
【解析】考查闪存的特性，闪存是EEPROM 的进一步发展，可读可写，用MOS 管的浮栅上有无电荷来存储信息，它依然是ROM 的一种，故写速度比读速度要慢不少。闪存是一种非易失性存储器，它采用随机访问方式，现在常见的SSD 固态硬盘就是由flash 芯片组成的，故答案为A 。
6． 主机甲和乙已建立了TCP 连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗 口为8KB , 则从t 时刻起，不再发生超时的情况下，经过10个RTT 后，甲的发送窗口是（ ）。
A.10KB B.12KB C.14KB D.15KB 【答案】A
【解析】发送窗口是接受窗口和拥塞窗口的最小值，这里接收窗口总是10KB 。拥塞窗口到那个时候是大于10KB 的，取最小值。
7． 下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序 B. 快速排序，堆排序
C. 直接选择排序，归并排序 D. 归并排序，起泡排序 【答案】D
8． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
【答案】D
【解析】至少探测次数
9． 某机器有一个标志寄存器，其中有进位/借位标志CF 、零标志ZF 、符号标志SF 和溢出标志OF ，条件转移指令bgt （无符号整数比较大于时转移）的转移条件是（ ）。
A.CF+OF=0 B.SF+ZF=0 C.CF+ZF=0 D.CF+SF=0 【答案】C
【解析】判断无符号整数A>B成立，满足的条件是结果不等于0, 即零标志ZF=0, 且不发生进位，即进位/借位标志CF=0。所以正确选项为C 。其余选项中用到了符号标志SF 和溢出标志OF , 显然可以排除掉。
10．对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是:（ ）
A.05，46，13，55，94，17，42 B.05，13，17，42，46，55.94 C.42，13，94，05，55，46，17 D.05，13，46，55，17，42，94
【答案】C
【解析】基数排序有两种：最低位优先和最高位优先。
最低位优先的过程
先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。
以r 为基数的最低位优先排序的过程 假设线性表由结点序列组成，
其中
分配：开始时，把收集：把
构成，每个结点aj 的关键字由d 元组（k ，k... ，k ，k ）在排序过程中，使用r 个队列
排序过程就是
对i=0，1，... ，d-1，依次做一次“分配”和“收集”。
各个队列置成空队列，然后依次考察线性：表中的每一个结
队列中。
各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新
点（==0.1，... ，n-1）。如果的关键字k=k，就把放进