2018年中国农业科学院家禽所808数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法（ ）。
A. 分块
B. 顺序
C. 折半
D. 哈希
【答案】A
【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。
2． n 个结点的完全有向图含有边的数目（ ）。
A.n*n
B.n(n+1)
C.n/2
D.n*(n－1)
【答案】D
【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有条边。如是有向图，需要在无向图的最多边的基础上乘以2，则为n(n－1) 。
3． 下列选项中，能引起外部中断的事件是（ ）.
A. 键盘输入
B. 除数为0
C. 浮点运算下溢
D. 访存缺页
【答案】A
【解析】所谓外部中断是指由外部事件引起的中断，在这4个选项中，只有键盘输入是真正由外部事件引起的中断.
4．
协议对0111110001111110组帧后对应的比特串为（ ）
A.011111000011111010
B.011111000111110101111110
C.01111100011111010
D.011111000111111001111101
【答案】A
【解析】HDLC 协议对比特串进行组帧时, HDLC 数据帧以位模式
个“0”。所以答案为A 。
5． 下列关于中断方式和DMA 方式比较的叙述中, 错误的是（ ）
A. 中断方式请求的是方式请求的是CPU 处理时间, DMA 方式请求的是总线使用权
B. 中断响应发生在一条指令执行结束后, 中断响应发生在一条指令执行结束后, DMA 响应发生在一个总线事务完成后
C. 中断
送由硬件完成
D. 中断
设备
【答案】D
【解析】中断处理方式:在
与设备输入每个数据的过程中, 由于无需CPU 干预, 因而可使CPU
设备并行工作。仅当输完一个数据时, 才需CPU 花费极短的时间去做些中断处理。因此中断
设备方式适用于所有外部设备, 方式适用于所有外部设备, DMA 方式仅适用于快速外部方式下数据传送通过软件完成, 方式下数据传送通过软件完成, DMA 方式下数据传标识每一个帧的开始和结束, 因此在帧数据中凡是出现了5个连续的位“1”的时候, 就会在输出的位流中填充一申请使用的是CPU 处理时间, 发生的时间是在一条指令执行结束之后, 数据是在软件的控制下完成传送。而DMA 方式与之不同。DMA 方式:数据传输的基本单位是数据块, 即在CPU 与
之间, 每次传送至少一个数据块, DMA 方式每次申请的是总线的使用权, 所传送的数据是从设备直接送入内存的或者相反; 仅在传送一个或多个数据块的开始和结束时, 才需CPU 干预, 整块数据的传送是在控制器的控制下完成的。答案D 的说法不正确。
6． 在采用中断方式控制打印输出的情况下, CPU 和打印控制接口中的
息不可能是（ ）。
A. 打印字符
B. 主存地址
C. 设备状态
D. 控制命令
【答案】B 【解析】接口的功能包括:①选址功能; ②传送命令功能; ③传送数据功能; ④反映
要的, 因此, 它不可能是CPU 和打印控制接口中的
端口之间交换的信息。 设备工作状态功能。A 项为数据, C 项为设备状态, D 项为命令。B 项, 主存地址在中断方式控制下是不需端口之间交换的信
7． 某计算机使用4体交叉存储器, 假定在存储器总线上出现的主存地址(十进制) 序列为8005, 8006, 8007, 8008, 8001, 8002, 8003, 8004, 8000, 则可能发生发生缓存冲突的地址对是（ ）。
A.8004, 8008
B.8002、8007
C.8001、8008
D.8000、8004
【答案】D
【解析】交叉存储器, 又称低位交叉编址, 即低位地址为体号, 高位地址为体内地址。本题中, 主存地址对应的体号分别是:1, 2, 3, 4, 1, 2, 3, 4, 4。地址为8004和8000都是存取的四号储存器, 可能导致8004存储还未完成而又存取8000地址, 因此可能发生缓存冲突。
8． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
A.(100, 80, 90, 60, 120, 110, 130)
B.(100, 120, 110, 130, 80, 60，90)
C.(100, 60, 80, 90, 20, 110, 130)
D.(100, 80, 60, 90, 120, 130, 110)
【答案】C
【解析】二叉排序树:左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
9． 将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是（ ）.
(1)父子关系
(2)兄弟关系
(3)U的父结点与V 的父结点是兄弟关系
A. 只有(1)
B.(1)和(2)
C.(1)和(3)
d.(1)、(2)和(3)
【答案】B
【解析】首先，在二叉树中，若结点U 是结点v 的父结点的父结点，那么u 和v 的关系有如下4种情况：