2018年大连理工大学管理与经济学部810数据结构和计算机组成原理之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 对于循环队列（ ）。
A. 无法判断队列是否为空
B. 无法判断队列是否为满
C. 队列不可能满
D. 以上说法都不是
【答案】D
【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断:①另设一个布尔变量来区别队列是空还是满；②队满时，
(rear+1)
font 。
2． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入
B. 选择
C. 希尔
D. 二路归并
【答案】A
【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是:假设待排序的记
录存放在数组中，排序过程的某一中间时刻，R
被划分成两个子区间
插入到有序区中适当的位置上。使和，其中:前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。将当前无序区的第1个记录变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
3． 在下图所示的采用“存储一转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbps ，分组大小为1000B ，其中分组头大小20B ，若主机H1向主机H2发送一个大小为980000B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是（ ）
.
A.80ms B.
C.
D.
【答案】c
【解析】由题设可知，分组携带的数据长度为980B ，文件长度为980000B ，需拆分为1000个分组，加上头部后，每个分组大小为1000B ，总共需要传送的数据量大小为IMB. 由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过分组交换机. 当t ＝lM ×8/100Mbps＝80ms 时，HI 发送完最后一个比特；到达目的地，最后一个分组，需经过两个分组交换机的转发，每次转发的时间为t 0＝lK ×8/100Mbps＝，所以，在不考虑分组拆装时间和传播延时的情况下，当时，H2接受完文件，
即所需的时间至少为
4． 某计算机有16个通用寄存器, 采用32位定长指令字操作码字段(含寻址方式位) 为8位, Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式, 若基址寄存器可使用任一通用寄存器, 且偏移量用补码表示, 则Store 指令中偏移量的取值范围是（ ） A. B. C. D.
【答案】A
【解析】寄存器个数
指令编址方式如下所示:
16位补码取值范围为, 所以偏移量取值范围为
5． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
A.push ，pop ，push ，pop ，push ，pop
B.push ，push ，push ，pop ，pop ，pop
C.push ，push ，，pop ，pop ，push ，pop
偏移量有32-8-4-4=16位
D.push ，pop ，push ，push ，pop ，pop
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进找，然后再出找。从中可以看出，push 的数目始终大于等于pop 的数目。
6． 若串S ＝'software'%其子串的数目是（ ）。
A.8
B.37
C.36
D.9
【答案】B
【解析】子串的定义是:串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为n(n＞0) ，长为n 的子串有1个，长为n ﹣1的子串有2个，长为n ﹣2的子串有3个，...... ，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案为:8*(8＋1)/2十1＝37。故选B 。
7． 4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7 B.
C.15
D.16
【答案】C
【解析】Hanoi 问题总移动次数为:2M 次。
8． 程序段
与对换；
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。
A.D(n)
B.O(nlogn)
C.O(n3)
D.O(n2)
【答案】D
【解析】这个是冒泡排序，最坏的情况下需要进行l ＋2＋... ＋n ﹣l 次交换，即时间复杂度是0(n2) 。
9． 最大容量为n 的循环队列，队尾指针是rear ，队头:front ，则队空的条件是（ ）。
A.(rear+1)MODn＝front
B.rear ＝front