2017年西北民族大学电气工程学院849计算机学科专业基础之数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 若对如下的二叉树进行中序线索化，则结点x 的左、右线索指向的结点分别是（ ）
A.
B.
C.
D.
【答案】D
【解析】此二叉树的中序遍历序列为：debxac ，由于节点x 左右孩子都为空，所有进行中序线索化时，它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b 和直接后继结点a , 所以选D
2． 下列四个序列中，哪一个是堆（ ）？
A.75，65，30，15，25，45，20，10 B.75，65，45，10，30，25，20，15 C.75，45，65，30，15，25，20，10 D.75，45，65，10，25，30，20，15
【答案】C
【解析】堆的定义： n 个关键字序列
且
且
称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
小根堆：满足第①种情况的堆； 大根堆：满足第②种情况的堆。 根据堆定义即可得出答案。
3． 设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，放于
中，那么第i 行的对角元素【答案】A
【解析】
中列标不大于行标，
又
存放在
中，
所以
存放于B 中（ ）处。
存
存放的位置为
4． 若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的是（ ）
I. 处理越界错 II. 置换页 III. 分配内存 A. 仅I 、II B .仅II 、III C. 仅I 、III D.I 、II 、和III 【答案】B
【解析】用户进程访问内存时缺页会发生缺页中断。发生缺页中断，系统地执行的操作可能是置换页面或分配内存。系统内没有越界的错误，不会进行越界出错处理。
5． 已知小根堆为8，15，10，21，34， 16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是（ ）。
A.1 B.2 C.3 D.4
【答案】C
【解析】堆排序中，依次输出堆顶的最小值，然后重新调整堆，如此反复执行，便得到一个有序序列。本题中，删除堆顶元素8后将最后一个元素12置于堆顶，然后调整堆：首先与15比较，12小于15, 所以不用交换；然后与10比较，因为10小于12，所以交换10和12的位置；调 整后12再与16比较，12小于16，调整堆过程结束。因此12共与15、10、16进行了三次比较。
6． 下面关于B 和B+树的叙述中，不正确的是（ ）
A.B 树和B+树都是平衡的多叉树 B.B 树和B+树都可用于文件的索引结构 C.B 树和B+树都能有效地支持顺序检索 D.B 树和B+树都能有效地支持随机检索 【答案】C
【解析】B 树是一种平衡的多分树，通常我们说m 阶的B 树，它必须满足如下条件：①每个结点至多有m 个子结点；②除根结点和叶结点外，其它每个结点至少有个子结点；③若根结点不是叶子结点，则至少有两个子结点；④所有的叶结点在同一层；⑤有k 个子结点的非根结点恰好
包含k-1个关键码。B+树是B 树的一种变形树，它与B 树的差异在于：有k 个子结点的结点必然有k 个关键码；非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。其中B 树适合与随即检索，不适合于顺序检索，所以C 项错误。
7． 若需在0（nlog2n ）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 【答案】C
【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。不稳定排序有：快速排序、堆排序、shell 排序。时间复杂度平均为
的有：归并排序、堆排序、shell 排序、快
速排序。
8． 本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是（ ）。
A. 命令解释程序 B. 中断处理程序 C. 系统调用服务程序 D. 用户登录程序 【答案】B
【解析】外部设备在与计算机连接时有多种方式，中断技术就是一种常用方式。其工作原理是：利用处理机中断信号线，外部设备在需要服务的时候将该线设置为有效，计算机若同意接受，中断则会停止当前进程的运行，转而服务发出中断的物理设备（注意与陷阱，即软中断有区别）那么对不同外部设备进行服务的程序代码是不同的，如何找到这些代码呢? 这就要借助中断向量，中断向量一般是由硬件根据中断的类型（不同外设不同）计算所得，或计算机系统在开机配置时所配置的。处理机取得中断向量，其实就是一个物理地址，该地址下存放的是为此中断服务的代码的起始地址。所以，当键盘按下的时候，键盘控制器获得该操作动作，先将键盘扫描码读入键盘缓冲区，再向处理机发出键盘中断，适当的时候（一条指令的末尾或一条原语结束）处理机会响应中断，调用指定服务程序将键盘缓冲区中的键盘扫描码输入到登录进程中去。如此，最先响应键盘的必然是中断处理程序。本题中，像命令解释器（例如cmd 窗口）、系统调用服务和用户登录程序都在中断处理程序后面。
9． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。