2017年华南农业大学工程学院854数据结构与计算机组成原理之数据结构考研题库
● 摘要
目录
2017年华南农业大学工程学院854数据结构与计算机组成原理之数据结构考研题库（一） ... 2 2017年华南农业大学工程学院854数据结构与计算机组成原理之数据结构考研题库（二） . 15 2017年华南农业大学工程学院854数据结构与计算机组成原理之数据结构考研题库（三） . 25 2017年华南农业大学工程学院854数据结构与计算机组成原理之数据结构考研题库（四） . 36 2017年华南农业大学工程学院854数据结构与计算机组成原理之数据结构考研题库（五） . 48
一、选择题
1． 下列选项中，能引起外部中断的事件是（ ）。
A. 键盘输入
B. 除数为0
C. 浮点运算下溢
D. 访存缺页
【答案】A
【解析】所谓外部中断是指由外部事件引起的中断，在这4个选项中，只有键盘输入是真正由外部事件引起的中断。
2． 现在有一颗无重复关键字的平衡二叉树（A VL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。
A. 根节点的度一定为2
B. 树中最小元素一定是叶节点
C. 最后插入的元素一定是叶节点
D. 树中最大元素一定是无左子树
【答案】D
【解析】二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：①中序遍历左子树；②访问根节点；③中序遍历右子树”。A 项错误，当树中仅有一个或者两个结点时，根节点的度就可能不为2；B 项错误，树中最小元素是中序遍历时最后访问的节点，当没有右子树时，最后访问的节点是根节点；C 项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间节点；D 项正确，由中序遍历的特点可知，左子树的值大于根节点，所以最大元素一定没有左子树。
3． 在下述结论中，正确的有（ ）。
①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换，④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A. ①②③
B. ②③④
C. ②④
D. ①④
【答案】D
【解析】只有根节点的二叉树的度为0，二叉树的左右子树隐含着他们的位置关系。因此，②③均错。
4． 假定编译器将赋值语句“x=x+3; ”转换为指令” add xaddt, 3”，其中xaddt 是x 对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB ，且Cache 使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（ ）。
A.0
B.1
C.2
D.3
【答案】C
【解析】采用页式虚拟存储管理方式时，若页表全部放在内存中，则存取一个数据最少要访问两次内存：第一次是访问页表，得到所存取的数据或指令的物理地址；第二次根据该地址存取数据或指令。在配有TLB 的页式虚拟管理方式中，如果给出的地址在TLB 中，则直接根据该地址取数据或指令，仅需要一次访问内存。Cache 使用直写方式时，计算完需要将数据写回到内存中，因此完成整个指令功能至少需要访问主存2次。
5． 假定一台计算机的显示存储器用DRAM 芯片实现，若要求显示分辨率为1600x1200, 颜色深度为24位，帧频为85Hz , 显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（ ）。
A.245Mbps
B.979Mbps C. D.
【答案】D
【解析】显存的容量=分辨率×色深，带宽=分辨率×色深×帧频，考虑到的时间用来刷新
1600×1200×24×85×2＝7834Mbps 屏幕，故显存总带宽应加倍。所以需要的显存总带宽至少约为：
6． 下列选项中，不可能在用户态发生的事件是（ ）。
A. 系统调用
B. 外部中断
C. 进程切换
D. 缺页
【答案】C 。
【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设
，在用户态运行用户的程序，在内核定了用户态和内核态（可以通过设置软、硬件标志位来实现）
运行系统的程序。所以，从选 项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在
用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制
，必定分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻）
是在内核态（进程调度）发生的。
7． 下列排序算法中，占用辅助空间最多的是（ ）。
A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序
【答案】A
【解析】
归并排序的辅助空间为
快速排序所占用的辅助空间为堆排序所占 用的辅助空间为
8． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表
【答案】A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进
行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
9． 处理外部中断时，应该由操作系统保存的是（ ）。
A. 程序计数器（PC ）的内容
B. 通用寄存器的内容
C. 快表（TLB ）的内容
D.Cache 中的内容
【答案】B
【解析】外部中断处理过程首先要保护现场，使得中断处理完后能够恢复程序的状态继续执
；②由中断服务程序保行。保护现场有两个含义：①由中断隐指令保存程序的断点（程序计数器）
存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
10．在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性
相关内容
相关标签