2016年西南林业大学计算机与信息学院数据结构(同等学力加试)复试笔试仿真模拟题
● 摘要
一、选择题
1． 设系统缓冲区和用户工作均采单，从外读入1个数据块到系统缓冲区的时间为100, 从系统缓冲区读入1个数据块到用户工作区的时间为5, 对用户工作区中的1个数据块行分析的时间为90 （如下图所示）。进程从外设读入并分析2个数据块的最短时间是（ ）
A.200
B.295
C.300
D.390
【答案】C
【解析】数据块1从外设到用户工作区的总时间为105, 在这段时间中数据块2没有进行操作。在数据块1进行分析处理时, 数据块2从外设到用户工作区的总时间为105, 这段时间是并行的。再加上数据块2进行处理的时间90, 总共是300, 故答案为C 。
2． 某设备中断请求的相应和处理时间为100m ，每400ns 发出一次中断请求，中断相应所容许的最长延迟时间为50ns , 贝U 在该设备持续工作过程中CPU 用于该设备的
百分比至少是（ ） A. B. C. D.
【答案】B
【解析】每400m 响应一次中断并且用100m 进行处理，所以该设备的时间占用CPU 时间
百分比为中断响应容许的延迟时间对此没有影响，属于干扰条件。
3． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多是（ ）。
A.4
第 2 页，共 39 页 时间占整个CPU 时间
B.5
C.6
D.7
【答案】B
【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为（l 〇g2n ） +1，在本题中，n=16, 故比较次数最多为5。
4． 某主机的IP 地址为180.80.77.55, 子网掩码为255.255.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是（ ）。
A.180.80.76.0
B.180.80.76.255
C.180.80.77.255
D.180.80.79.255
【答案】D 。
【解析】IPv4地址中的特殊地址，直接广播地址，也就是把主机位全部设置为1，这里77的二进制是01001101, 子网掩码252的二进制是11111100，由此可以看到77的前6位作为子网位，后四位作为主机位，由此可以知道 其广播地址是180.80.01001111.255，也就是180.80.79.255，因此答案是D 。
5． 栈和队的共同点是（ ）。
A. 都是先进后出
B. 都是后进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点
【答案】C
【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队列的共同点是都只能在端点处插入和删除元素。
6． 在任意一棵非空二叉排序树T1中，删除某结点v 之后形成二叉排序树T2, 再将v 插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是（ ）
I. 若v 是T1的叶结点，则T1与T3不同
II. 若v 是T1的叶结点，则T1与T3相同
III. 若v 不是T1的叶结点，则T1与T3不同
IV. 若v 不是T1的叶结点，则T1与T3相同
A. 仅 I 、III
B .仅 I 、IV
C. 仅 II 、III
D. 仅 II 、IV
【答案】C
第 3 页，共 39 页
【解析】在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树可能发生变化，不完全相同。
7． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便地进行插入与删除
C. 为了能方便地找到双亲
D. 使二叉树的遍历结果唯一
【答案】A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
8． —次总线事物中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元格读出或写入的个数，这种总线事务方式称为（ ）
A. 并行传输
B 串行传输
C. 突发
D. 同步
【答案】C
【解析】猝发数据传输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式
9． 下列排序算法中，占用辅助空间最多的是（ ）。
A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序
【答案】A
【解析】
归并排序的辅助空间为
快速排序所占用的辅助空间为堆排序所占 用的辅助空间为
10．设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，放于中，那么第i 行的对角元素存放于B 中（ ）处。
【答案】A
【解析】
第 4 页，共 39 页 存中列标不大于行标，
又
存放在中，
所以
存放的位置为
相关内容
相关标签