2017年齐齐哈尔大学计算机与控制工程学院823数据结构考研导师圈点必考题汇编
● 摘要
目录
2017年齐齐哈尔大学计算机与控制工程学院823数据结构考研导师圈点必考题汇编（一）.... 2 2017年齐齐哈尔大学计算机与控制工程学院823数据结构考研导师圈点必考题汇编（二）.. 16 2017年齐齐哈尔大学计算机与控制工程学院823数据结构考研导师圈点必考题汇编（三）.. 28 2017年齐齐哈尔大学计算机与控制工程学院823数据结构考研导师圈点必考题汇编（四）.. 41 2017年齐齐哈尔大学计算机与控制工程学院823数据结构考研导师圈点必考题汇编（五）.. 54
一、选择题
1． 某系统有n 台互斥使用的同类设备，3个并发进程需要3, 4, 5台设备，可确保系统不发生死锁的设备数n 最小为（ ）
A.9 B.10 C.11 D.12
【答案】B
【解析】2+3+4+1 = 10
2． 有关二叉树下列说法正确的是（ ）。
A_二叉树的度为2
B. —棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 【答案】B
【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，... ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
3． 设图的邻接矩阵A 如下所示，各顶点的度依次是（ ）
A.1, 2, 1, 2 B.2, 2, 1, 1 C.3, 4, 2, 3 D.4, 4, 2, 2 【答案】C
【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
4． 执行完下列语句段后，f 值为（ ）。
A.2 B.4 C.8
D. 无限递归 【答案】B
【解析】该程序使用了递归调用，由题知，所以结果为4。
5． 若数据元素序列11, 12, 13, 7, 8, 9, 23, 4, 5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。
A. 起泡排序 B. 插入排序 C. 选择排序 D. 二路归并排序 【答案】B
【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确。
6． 假定变量i 、f 和d 的数据类型分为int 、float 和double （int 用补码表不，float 和double 分，已知别用IEEE754单精度和双精度浮点数格式表示）
位机器中执行下列关系表达式，则结果为“真”的是（ ）。
A. 仅I 和II B. 仅I 和III C. 仅II 和III D. 仅III 和IV 【答案】B
II 中，f 的数据类型从float 【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。转换为int 时，小数点后面4位会丢失，故II 的结果不为真；IV 中，d+f时需要对阶，对阶后f 的尾数有效位被舍去而变为0, 故d+f仍然为d , 再减去d 后结果为0, 故IV 的结果也不为真。I 和II 进行数据类型的转换的时候并没有改变其值。
若在32
7． 已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（ ）。
A.39 B.52 C.111 D.119
【答案】C
【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层。题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度。根据题意，一棵完全二叉树的第6层（设根为第1层）有8个叶结点，可知此二叉树的高度是6或7。题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7。由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是-1=63。又根据二叉树的性质1可知，题目中二叉树的第6层结点数是
=32个结点，已知有8个叶子结点，那么其余32-8=24
个结点均为分支结点，这些结点在第7层上最多有48个子结点（即叶子结点）。所以此二叉树的结点数最多可达-1+（-8）×2=lll。
8． 某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第1字节为操作码字段，第2字节为相对位移量字段。假定取指令时，每取一个字节PC 自动加1。若某转移指令所在主存地址为2000H ，相对位移量字段的内容为06H , 则该转移指令成功转移后的目标地址是（ ）。
A.2006H B.2007H C.2008H D.2009H 【答案】C
【解析】相对寻址方式的有效地址EA=（PC ）+D, 其中PC 为程序计数器，D 为相对偏移量。主存按字节编址，取指令时，每取一个字节PC 值自动加1。由于转移指令由两个字节组成，取出这条转移指令之后的PC 值自动加2，为2002H ，故转移的目标地址为2002H+06H=2008H。
9． 在一个文件被用户进程首次打开的过程中，操作系统需做的是（ ）
A. 将文件内容读到内存中 B. 将文件控制块读到内存中 C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程 【答案】B 【解析】概念