2018年东南大学计算机科学与工程学院935计算机专业基础之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 下列选项中, 属于多级页表优点的是（ ）
A. 加快地址变换速度
B. 减少缺页中断次数
C. 减少页表项所占字节数
D. 减少页表所占的连续内存空间
【答案】D
【解析】多级页表避免了把所有的页表一直保存在内存中
2． 直接插入排序在最好情况下的时间复杂度为（ ）。 A.
B.O(n) C. 2D.O(n)
【答案】B
【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾的一个元素进行比较，此时的时间复杂度最好，为O(n)。
3． 设栈S 和队列Q 的初始状态均为空，元素a ，b ，c ，d ，e ，f ，g 依次进入栈S. 若每个元素出
d ，c ，f ，e ，a ，g ，. 栈后立即进入队列Q ，且7个元素出队的顺序是b ，则找S 的容量至少是（ ）
A.1
B.2
C.3
D.4
【答案】C
【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序.. 在本题中，每个元素出栈S 后立即进入队列Q ，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序. 根据出桟顺序可以分析各个元素进出栈的过程：第一个出栈元素为b ，表明栈内还有元素a ，b 出栈前的深度为2；第二个出栈元素为d ，栈内元素为a 和c ，d 出栈前的深度为3；c 出栈后，剩余元素为a ，c 出栈前的深度为2；f 出栈后，剩余元素为a 和e ，f 出栈前的深度为3；e 出栈后，剩余元素为a ，e 出栈前的深度为2；a 出栈后，无剩余元素，a 出栈前的深度为1；g 出栈后，无剩余元素，g 出栈前的深度为1. 所以栈容量至少是3.
4． 已知小根堆为8, 15, 10, 21, 34, 16, 12, 删除关键字8之后需重建堆, 在此过程中, 关键字之间的比较数是（ ）。
A.1
B.2
C.3
D.4
【答案】C
【解析】堆排序中, 依次输出堆顶的最小值, 然后重新调整堆, 如此反复执行, 便得到一个有序序列。本题中, 删除堆顶元素8后将最后一个元素12置于堆顶, 然后调整堆:首先与15比较, 12小于15, 所以不用交换; 然后与10比较, 因为10小于12, 所以交换10和12的位置; 调整后12再与16比较, 12小于16, 调整堆过程结束。因此12共与15、10、16进行了三次比较。
5． 已知待排序的n 个元素可分为n/k个组，每个组包含k 个元素，且任一组内的各元素均分别大干前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。 A.
B.
C.
D.
【答案】B
【解析】因组与组之间己有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时
，全部时间下界为间下界为
0 。
6． 已知一算术表达式的中缀表达式为a ﹣(b＋c/d)*e，其后缀形式为（ ）。 A.
B.
C.
D.
【答案】D
【解析】后缀表达式:在程序语言中，运算符位于两个操作数后面的表达式。
7． 下列选项中, 不能构成折半查找中关键字比较序列的是（ ）。
A.500, 200, 450, 180
B.500, 450, 200, 180
C.180, 500, 200, 450
D.180, 200, 500, 450
【答案】A
【解析】折半查找的过程是:先确定待查找记录所在的范围, 然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足:对每一个关键字, 其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A 项错误, 第三次比较的关键字为450, 说明待查关
键字位于200〜450间, 所以第四次比较时不会遇到关键字180。
8． 在采用中断方式控制打印输出的情况下, CPU 和打印控制接口中的
息不可能是（ ）。
A. 打印字符
B. 主存地址
C. 设备状态
D. 控制命令
【答案】B 端口之间交换的信
【解析】接口的功能包括:①选址功能; ②传送命令功能; ③传送数据功能; ④反映设备工作状态功能。A 项为数据, C 项为设备状态, D 项为命令。B 项, 主存地址在中断方式控制下是不需要的, 因此, 它不可能是CPU 和打印控制接口中的端口之间交换的信息。
9． 某网络拓扑如下图所示, 路由器R1
只有到达子网的路由。为使R1可以将IP 分组正确地路由到图中所有子网, 则在R1中需要增加一条路由(目的网络, 子网掩码, 下一跳) 是（ ）。
A.
B.
C.
D.
【答案】D
因此是 【解析】首先从题目给出的路由表项可以确定下一跳肯定是路由器R1直接相连的R2的地址, , 此时可以排除A 和B 两个选项了。进而分析路由器R2所连接的网络特点, 注意
和, 但答案选项中只有一条信息, 因此这里其连接了2
个网络分别是
用到了超网的概念, 超网是与子网类似的概念一IP 地址根据子网掩码被分为独立的网络地址和主机地址。但是, 与子网把大网络分成若干小网络相反, 它是把一些小网络组合成一个大网络一超网,
这里
和
, 那么子网掩码就是
10．算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
前24位是相同的,
因此所构成的超网就是即, 因此答案是D 。