2017年杭州师范大学杭州国际服务工程学院826计算机基础之数据结构考研仿真模拟题
● 摘要
一、选择题
1． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
【答案】C
【解析】二叉排序树：左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
2． 组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。
A. B. C. D. 【答案】B
【解析】因组与组之间已有序，故将
个组分别排序即可，基于比较的排序方法每组的时
间下界为
0全部时间下界为
3． 下列选项中，不可能是快速排序第2趟排序结果的是（ ）
A.2, 3, 5, 4, 6, 7, 9 B.2, 7, 5, 6, 4, 3, 9 C.3, 2, 5, 4, 7, 6, 9 D.4, 2, 3, 5, 7, 6, 9
【答案】C
【解析】对于快速排序，每一趟都会使一个元素位于有序时的位置，而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比，只有9位于它有序的时候的位置，显然不是第二趟快速排序的结果
4． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多是（ ）。
A.4 B.5 C.6 D.7
【答案】B
【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为（l 〇g2n ） +1，在本题中，n=16, 故比较次数最多为5。
5． 已知循环队列存储在一维数组rear 的值分别是（ ）。
A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-1
【答案】B
【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，且要求第1 个进入队列的元素存储在A[0]处，则此时front 和rear 的值都为0。由于进队操作要执行（rear+1） % n，则初始 时front 的值为0、rear 的值为n-1。
6． 处理外部中断时，应该由操作系统保存的是（ ）。
A. 程序计数器（PC ）的内容 B. 通用寄存器的内容 C. 快表（TLB ）的内容 D.Cache 中的内容 【答案】B
【解析】外部中断处理过程首先要保护现场，使得中断处理完后能够恢复程序的状态继续执；②由中断服务程序保行。保护现场有两个含义：①由中断隐指令保存程序的断点（程序计数器）
存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
7． 若某通信链路的数据传输速率为采用4相位调制，则该链路的波特率是（ ）。
A.600波特 B.1200波特 C.4800波特 D.9600波特 【答案】B
【解析】注意无噪声下的码元速率极限值B 与信道带宽H 的关系：B = 2xH （Baud ）, 而奈奎斯特公式一无噪信道传输能力公式是而可以得到波特率与数据传输速率的关系，即N=4，因此波特率是1200, 答案是B 。
N 为一个码元所取的离散值个数。从
在本题中数据传输速率C = 2400,
中，且队列非空时front 和rear 分别指向队头元素和
队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和
8． 某CPU 主频为1.03GHz , 采用4级指令流水线，每个段的执行需要1个时钟周期。假定CPU 执行了100条指令，在其执行过程中没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）
A. B. C. D. 【答案】C
【解析】采用4级流水线执行100条指令，在执行过程中共用
条指令/秒，故答案为C 。
9． 采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。
A. 数据元素过多 B. 负载因子过大 C. 哈希函数选择不当 D. 解决冲突的算法选择不好 【答案】D
【解析】开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。
10．下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）。
A. 连续结构 B. 索引结构
C. 链式结构且磁盘块定长 D. 链式结构且磁盘块变长 【答案】B
【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问。链式结构的优点是文件易于扩展，缺点是不易随机访问。索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展。
11．主机甲和主机乙之间已建立了一个TCP 连接，TCP 最大段长度为1000字节，若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是（ ）。
A.1000 B.2000 C.3000 D.4000
条指令/秒 条指令/秒 条指令/秒 条指令/秒
个时钟周期。
CPU 的主频是1.03GHz , 也就是说每秒钟有1.03G 个时钟周期。流水线的吞吐率
为