2017年电子科技大学自动化工程学院820计算机专业基础之数据结构考研冲刺密押题
● 摘要
一、选择题
1． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0（n ） B.0（n+e） C.0（n*n） D.0（n*n*n）
【答案】B
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0（n+e）
2． 将森林F 转换为对应的二叉树T , F中叶结点的个数等于（ ）
A.T 中叶结点的个数
B.T 中度为1的结点个数
C.T 中左孩子指针为空的结点个数
D.T 中右孩子指针为空的结点个数
【答案】C
【解析】森林转化为对应的二叉树是‘孩子-兄弟’存储的，即左孩子指针指向当前节点的孩子节点，右孩 子指针指向当前节点的兄弟节点，所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以 选C
3． 内部异常（内中断）可分为故障（fault ）、陷讲（trap ）和终止（abort ）三类。下列有关内部异常的叙述中，错误的（ ）。
A. 内部异常的产生与当前执行指令相关
B. 内部异常的检测由CPU 内部逻辑实现
C. 内部异常的响应发生在指令执行过程中
D. 内部异常处理后返回到发生异常的指令继续执行
【答案】D
【解析】内中断分为：①由软中断指令启动的中断；②在一定条件下由CPU 自身启动的中断。D 项错误，如突然掉电引发的内中断经处理后不会继续执行。
4． 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。
A.95, 22, 91, 24, 94, 71
B.92, 20, 91, 34, 88, 35
C.21, 89, 77, 29, 36, 38
D.12, 25, 71, 68, 33, 34
【答案】A
【解析】各选项对应的查找过程如下图所示，从中看到选项B 、C 、D 对应的查找树都是二叉排序树，只有选项A 对应的查找树不是一棵二叉排序树，因为在以91为根的左子树中出现了比91大的结点94。
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 和
【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，且要求第1 个进入队列的元素存储在A[0]处，则此时front 和rear 的值都为0。由于进队操作要执行（rear+1） % n，则初始 时front 的值为0、rear 的值为n-1。
6． 假定有4个整数用8位补码分别表示为
存放在一个8位寄存器中，则下列运算会发生溢出的是（ ）。
A.r1×r2
B.r2×r3
C.r1×r4
D.r2×r4
【答案】B
若将运算结果
【解析】用补码表示时8位寄存器所能表示的整数范围为
在4个选项中，只有现在4个整数都是负数
，结果溢出，其余3个算式结果
都未超过127, 不发生溢出。
7． 某主机的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 。
8． 下列关于虚拟存储的叙述中，正确的是（ ）。
A. 虚拟存储只能基于连续分配技术
B. 虚拟存储只能基于非连续分配技术
C. 虚拟存储容量只受外存容量的限制
D. 虚拟存储容量只受内存容量的限制
【答案】D 。
【解析】所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运行的一种技术，在运行过程中，当所需要的代码部分不在内存时，通过一种技术（例如缺页中断
，技术）将所需要的页面调入内存，从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件 机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配，虚拟存储器和外存大小没有关系，所以选项中 的A ，B ，C 都是错误的，所以答案是D 项。
9． 某二叉树结点的中序序列为BDAECF ，后序序列为DBEFCA ，则该二叉树对应的森林包括（ ）棵树。
A.1
B.2
C.3
D.4
【答案】C
【解析】由两序列可知，A 为根节点，ECF 为右子树，C 为右子树的根，F 为C 的右孩子。再由二叉树和森林的对应关系可知该二叉树对应的森林包括3棵树。根据中序序列和后序序列画出二叉树，根据二叉树得出对应的森林包含的树的棵数。