当前位置：问答库＞考研试题

一、单项选择题

1． 已知串

A.0123

B.1123

C.1231

D.1211

【答案】A

【解析】KMP 算法的next 数组建立的原则

其Next 数组值为（ ）。

2． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。

A.n

B.n ﹣2

C.n ﹣1

D.n ＋1

【答案】c

【解析】每个结点(除根节点外) 都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n ﹣1。

3． 已知小根堆为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进行了三次比较。

4． 若需在

（ ）。

A. 快速排序

B. 堆排序

C. 归并排序

D. 直接插入排序

【答案】C 的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是

【解析】稳定排序有:插入排序、起泡排序、归并排序、基数排序。不稳定排序有:快速排序、

堆排序、shell 排序。时间复杂度平均为的有:归并排序、堆排序、shell 排序、快速排序。

5． 设二维数组(即m 行n 列) 按行存储在数组中，则二维数组元素A[i，j]在一维数组B 中的下标为（ ）。

A.(i﹣1)*n＋j

B.(i﹣1)*n＋j ﹣l

C.i*(j﹣1)

D.j*m＋i ﹣l

【答案】A

【解析】前i ﹣1的元素个数为(i﹣1)*n，所以二维数组元素A[i，j]在一维数组B 中的下标为(i﹣1)*n＋j 。需要注意数组B 的下标是从0开始，还是从1开始。

6． 某计算机有16个通用寄存器, 采用32位定长指令字操作码字段(含寻址方式位) 为8位, Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式, 若基址寄存器可使用任一通用寄存器, 且偏移量用补码表示, 则Store 指令中偏移量的取值范围是（ ） A. B. C. D.

【答案】A

【解析】寄存器个数

指令编址方式如下所示:

16位补码取值范围为 , 所以偏移量取值范围为

7． 设有数组A[i，j]，数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（ ）。

A.BA+141

B.BA+180

偏移量有32-8-4-4=16位

C.BA+222

D.BA+225

【答案】B

【解析】在计算中，可以考虑按照列存放时，A[5，8]在内存的位置，比较容易计算元素的首地址。比如A[5，8]顺序存放时，它是第7*8＋5＝61个元素，由于首地址为BA ，所以它的存储首地址为BA ＋(61﹣1)*3＝180+BA。

8． 已知一棵有2011个结点的树, 其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。

A.115

B.116

C.1895

D.1896

【答案】D

【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点(因为一个非终端结点至少有一个孩子结点, 其最右边的孩子结点转换成二叉树后一定没有右孩子) , 另外, 树根结点转换成二叉树后也没有右孩子。题目中树的总结点数是2011, 叶结点个数是116, 则非终端结点个数是2011-116=1895, 则该树对应的二叉树中无右孩子的结点个数是1895+1=1896。

9． 用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中结点，使j 沿链移动的操作为（ ）。

A.j ＝r[j].next

B.j ＝j ＋l

C.j ＝j ﹣＞next

D.j ＝r[j]﹣＞next

【答案】A

【解析】因为是用数组存储，这里所说的工作指针j 相当于数组的下标，结点是存储一个值域和next 域，next 域就是存放下一个结点的下表，所以只要将next 域中的值赋给j 就可以实现j 沿链移动。

10．对给定的关键字序列110, 119, 007, 911, 114, 120, 122进行基数排序, 则第2趟分配收集后得到的关键字序列是（ ）

A.007.110.119.114.911.120.122

B.007, 110, 119, 114, 911, 122, 120

C.007, 110, 911, 114, 119, 120, 122

D.110, 120, 911, 122, 114, 007, 119

【答案】C

【解析】基数排序的第1趟排序是按照个位数字来排序的, 第2趟排序是按然十位数字的大小进行排序的, 故答案是C 选项。