2017年齐鲁工业大学理学院872数据结构考研仿真模拟题
● 摘要
一、选择题
1． 若对如下的二叉树进行中序线索化，则结点x 的左、右线索指向的结点分别是（ ）
A.
B.
C.
D.
【答案】D
【解析】此二叉树的中序遍历序列为：debxac ，由于节点x 左右孩子都为空，所有进行中序线索化时，它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b 和直接后继结点a , 所以选D 2． 用直接插入排序方法对下面4个序列进行排序，
（由小到大）元素比较次数最少的是（ ）。
【答案】C
3． 假定有4个整数用8位补码分别表示为若将运算结果存放在一个8位寄存器中，则下列运算会发生溢出的是（ ）。
A.r1×r2 B.r2×r3 C.r1×r4 D.r2×r4 【答案】B
【解析】用补码表示时8位寄存器所能表示的整数范围为
在4个选项中，只有
第 2 页，共 50 页
现在4个整数都是负数
，结果溢出，其余3个算式结果
都未超过127, 不发生溢出。
4． 为支持 中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（ ）
A. 连续结构 B. 链式结构 C. 直接索引结构 D. 多级索引结钩 【答案】A
【解析】为了实现快速随机播放，要保证最短的查询时间，即不能选取链表和索引结构，因此连续结构最优。
5． 设有数组数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素
【答案】B
【解析】在计算中，可以考虑按照列存放时，址。比如
顺序存放时，它是第
在内存的位置，比较容易计算元素的首地
个元素，由于首地址为BA ，
所以它的存储首地址为
的存储首地址为（ ）。
6． 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A. 栈 B. 队列 C. 树 D. 图 【答案】B
【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。栈和队列是操作受限的线性表，栈具有先进后出的特性而队列具有先进先出的特性。由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列。
7． 下列选项中，降低进程优先级的合理时机是（ ）。
A. 进程的时间片用完
B. 进程刚完成1/0, 进入就绪队列 C. 进程长期处于就绪队列 D. 进程从就绪状态转为运行态
第 3 页，共 50 页
【答案】A
【解析】进程时间片用完可以降低其优先级，完成
的进程应该提升其优先级，处于就绪队
列等待调度的进程一般不会改变其优先级。进行这样的操作主要是为了改善交互式系统的响应时间，并均衡各个作业的公平性。采用时间片轮转技术主要为改善交互式用户的感受，使其觉得是，时间片用完后降低其优独享计算机（时间片轮转可以有效地防止计算繁忙型的进程独占计算机）先级是为了改善新进程的响应时间（新进程优先级较高，老进程降低优先级可以保证新进程具有，对于刚进入就绪队列的新进程，往往在创建时已经根据其特点和要求确定好优先级，不优先权）
会随意改变。而对于从阻塞状态唤醒的进程，由于阻塞带来了较长时间的等待，一般会根据阻塞队列的不同适当地提高优先级，以改善用户响应时间。
8． 下列关于银行家算法的叙述中，正确的是（ ）
A. 银行家算法可以预防死锁
B. 当系统处于安全状态时，系统中一定无死锁进程 C. 当系统处于不安全状态时，系统中一定会出现死锁进程 D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件 【答案】B
【解析】银行家算法是避免死锁的方法。利用银行家算法，系统处于安全状态时没有死锁进程，故答案选B 。
9． 归并排序中，归并的趟数是（ ）。
【答案】B
【解析】不妨设归并的趟数为m ，第一次归并每组有两个元素，最后一次归并只剩下一组，这组的元素个数为n
。因此每次归并元素的个数增加一倍。所以
所以归并的趟数为
10．协议对组帧后对应的比特串为（ ）
A.011111000011111010
B.011111000111110101111110 C.01111100011111010
D.011111000111111001111101 【答案】A
HDLC 协议对比特串进行组帧时，HDLC 数据帧以位模式0111 1110标识每一个帧的【解析】
开始和结束，因此在帧数据中凡是出现了 5个连续的位“1”的时候，就会在输出的位流中填充一个“0”。所以答案为A 。
11．在下面的排序方法中，辅助空间为
A. 希尔排序 B. 堆排序
第 4 页，共 50 页
的是（ ）。
相关内容
相关标签