2017年桂林理工大学信息科学与工程学院878数据结构及程序设计考研导师圈点必考题汇编
● 摘要
一、选择题
1．
对（ ）。
A. 该树一定是一棵完全二叉树 B. 树中一定没有度为1的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值 【答案】A
【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，选项A 错误；哈夫曼树中没有度为1的结点，选项B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P 的左右子树根结点处于同一层的结点中，若存在权值大于结点P 权值的结点Q ，那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结 点的权值一定不小于下一层任一结点的权值。
2． 假定编译器将赋值语句“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次。
3． 用户在删除某文件的过程中，操作系统不可能执行是（ ）
A. 删除此文件所在的目录 B. 删除与此文件关联的目录项
第 2 页，共 59 页
个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是
C. 删除与此文件对应的控制块 D. 释放与此文件关联的内存级冲区 【答案】A
【解析】删除文件不需要删除文件所在的目录，而文件的关联目录项和文件控制块需要随着文件一同删除，同时释放文件的关联缓冲区。
4． 下列关于最小生成树的叙述中，正确的是（ ）。
I . 最小生成树的代价唯一 II. 所有权值最小的边一定会出现在所有的最小生成树中III. 使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树一定相同IV . 使用普里姆算法和克鲁斯卡尔（Kruskal ）算法得到的最小生成树总不相同
A. 仅I B. 仅II C. 仅 I 、III D. 仅 II 、IV 【答案】A 。
【解析】当图中存在相同权值的边时，其最小生成树可能是不唯一的，但最小生成树的代价 所以说法I 正确。一定是相同的，从n 个顶点的连通图中选取n-1条权值最小的边可能构成回路，所以说法II 错误。当某个顶点有权值相同的边，使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树并不一定相同，所以说法III 错误。当最小生成树不唯一时，使用普里姆算法和克鲁斯卡尔（Krnskal ）算法得到的最小生成树可能相同，也可能不同，所以说法IV 错误。由此可得出正确答案。
5． 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。
A. 选择排序法B. 插入排序法C. 快速排序法D. 堆排序法 【答案】A
【解析】选择排序的基本思想是：
第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录和
6． 执行完下列语句段后，f 值为（ ）。
A.2 B.4 C.8
第 3 页，共 59 页
和该趟排序
交换，使
将它与无序区的第1个记录
分别变为新的有序区和新的无序区。
D. 无限递归 【答案】B
【解析】该程序使用了递归调用，由题知，
7． 在双向链表指针P 的结点前插入一个指针q 的结点操作是（ ）。
A.
B.
C.
D. 【答案】C
8． 下列程常段的时间复杂度是（ ）
A.
B.
C.
D. 【答案】C
【解析】外部循环的退出条件是内部循环的退出条件是
而对于k ，每次循环都执行
对于j ，每次循环都执行
所以结果为4。
所以循环次数为
所以每次循环次数为n 次。所以此程序
段的时间复杂度为O 即选C 。
9． 在OSI 参考模型中，直接为会话层提供服务的是（ ）
A. 应用层 B. 表示层 C. 传输层 D. 网络层 【答案】C
【解析】OSI 参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。
10．设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2, 再建立F1的硬链接文件F3, 然后删除F1。此时，F2和F3的引用计数值分别是（ ）。
A.0、1 B.1、1 C.1、2 D.2、1 【答案】B
第 4 页，共 59 页