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

一、单项选择题

1． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。

A.4

B.5

C.6

D.7

【答案】C

【解析】设度为0的结点数为x ，则度为3的树总结点数n ＝度为0的结点数＋度为1的结点数＋度为2的结点数＋度为3的结点数＝x ＋2＋l ＋2＝x ＋5；从每个结点所指向的结点数的和的角度来计算度为3的树总结点数n ＝2×3＋1×2＋2×1＋1＝11。两种方法所计算出来的n 相等，所以x ＝6。

2． 若用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 则关于该图拓扑序列的结论是（ ）。

A. 存在, 且唯一

B. 存在, 且不唯一不唯一

C. 存在, 可能不唯一

D. 无法确定是否存在

【答案】C 。

【解析】图的基本应用--拓扑排序, 用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 说明该图为有向无环图, 所以其拓扑序列存在, 但不一定唯一,

如图的邻接矩阵为, 则存在两个拓扑序列。

3． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A. 单链表

B. 仅有头指针的单循环链表

C. 双链表

D. 仅有尾指针的单循环链表

【答案】D

【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。

4． 设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单个文件最大长度是（ ）.

A.33KB

B.519KB

C.1057KB

D.16513KB

【答案】C

【解析】4个地址项为直接地址索引，其指向的数据块大小4×256B ＝lKB ，一级间接地址索引可以索引256/4＝64个直接地址索引，故2个一级间接地址索引指向的数据块大小为2×64×256B ＝32KB ，二级间接地址索引为256/4×256/4＝4096个直接地址索引，故1个二级间接地址索引指向的数据块大小为4096×256B ＝1024KB ，共计1KB ＋32KB ＋1024KB ＝1057KB.

5． 已知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。

A.CBEFDA

B.FEDCBA

C.CBEDFA

D. 不定

【答案】A

【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B 的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。

6． 就平均性能而言，目前最好的内排序方法是（ ）排序法。

A. 起泡

B. 希尔插入

C. 交换

D. 快速

【答案】D

【解析】快速排序的平均时间复杂度是nlogn 所需要的辅助存储为

间复杂度也是

注意仅仅表示的是一个量级，比如和的量级都为，虽然堆排序的时。之所以说，所需要的辅助存储为O(1)，看似堆排序比快速排序的性能好，但是需要快排最好，是在综合考虑的情况下。

7． 在双向链表指针P 的结点前插入一个指针q 的结点操作是（ ）。

A.p ﹣＞llink ＝q ；q ﹣＞Rlink ＝p ；p ﹣＞Llink ﹣＞Rlink ＝q ；q ﹣＞Llink ＝q ；

B.p ﹣＞llink ＝q ；p ﹣＞Llink ﹣＞Rlink ＝q ；q ﹣＞Rlink ＝p ；q ﹣＞Llink ＝p ﹣＞Llink ；

C.q ﹣＞Rlink ＝p ；q ﹣＞Llink ＝p ﹣＞L1ink ；p ﹣＞L1ink ﹣＞Rlink ＝q ；p ﹣＞Llink ＝q ；

D.q ﹣＞llink ＝p ﹣>llink；q ﹣＞Rlink ＝q ；p ﹣＞llink ＝q ；p ﹣＞llink ＝q ；

【答案】C

8． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素, 则关键字的比较次数最多是（ ）。

A.4

B.5

C.6

D.7

【答案】B

【解析】

折半查找法在查找不成功时和给定值进行比较的关键字个数最多为

题中, n=16, 故比较次数最多为5。

9． 已知循环队列存储在一维数组

的值分别是（ ）。

A.0, 0

B.0, n-1

C.n-1, 0

D.n-1, n-1

【答案】B

【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素, 若初始时队列为空, 且要求第1个进入队列的元素存储在A[0]处, 则此时front 和rear 的值都为0。由于进队操作要执

行, 则初始时front 的值为0、rear 的值为n-1。

10．将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。

A.N

B.2N －1

C.2N

D.N －1

【答案】A

【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为O(n)。

11．float 型数据通常用IEEE754单精度浮点数格式表示。若编译器将float 型变量x 分配在一个32位浮点寄存器FR1中,

且

A.C1040000H

B.C2420000H , 则FR1的内容是（ ）。 , 在本中, 且队列非空时front 和rear 分别指向队头元素和处, 则初始时front 和rear 队尾元素。若初始时队列为空, 且要求第1个进入队列的元素存储在