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

一、单项选择题

1． 在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。

A. 顶点v 的度

B. 顶点v 的出度

C. 顶点v 的入度

D. 依附于顶点v 的边数

【答案】B

【解析】在有向图中，第j 个链表中的结点个数只是顶点的出度，为求入度，必须遍历整个邻接表。因此顶点V 在链表中出现的次数是顶点V 的出度。

2． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。

A.(2，5，12，16)26(60，32，72)

B.(5，16，2，12)28(60，32，72)

C.(2，16，12，5)28(60，32，72)

D.(5，16，2，12)28(32，60，72)

【答案】B

【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。

第一次比较:28比72小，不交换;

第二次比较:28比5大，交换，此时为(5，16，32，12，60，2，28，72) ;

第三次比较:16比28小，不交换；

第四次比较:32比28大，交换，此时为(5，16，28，12，60，2，32，72) ;

第五次比较:28比2大，交换，此时为(5，16，2，12，60，28，32，72) ;

第六次比较:28比12大，不交换；

第七次比较:28比60小，交换，此时为(5，16，2，12，28，60，32，72) ;

一次划分结束。

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

A.4

B.5

C.6

D.7

【答案】B

【解析】

折半查找法在查找不成功时和给定值进行比较的关键字个数最多为, 在本题中, n=16, 故比较次数最多为5。

4． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。

A.h ﹣＞next ＝s ；

B.s ﹣＞next ＝h ；

C.s ﹣＞next ＝h ；h ﹣＞next ＝s ；

D.s ﹣＞next ＝h ﹣next ；h ﹣＞next ＝s ；

【答案】D

【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。

5． 文件系统中，文件访问控制信息存储的合理位置是（ ）.

A. 文件控制块

B. 文件分配表

C. 用户口令表

D. 系统注册表

【答案】A

【解析】文件控制块是文件存在的标志，文件的相关信息(基本信息、存取控制信息以及使用信息) 都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息.

6． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有（ ）个叶子。 A.

B.

C.

D. 【答案】D

【解析】二叉树结点总数n ＝n 0＋n 1＋n 2(n0，n 1，n 2分别代表度为0，度为1，度为2的结点数) 。又在非空二叉树中:n 0＝n 2＋l ，且本题所给树为正则二叉树，n 1＝0，所以n ＝2*n0﹣l ，因此n 1＝(n+1)/2。

7． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。

A. 其中任意一个结点均无左孩子

B. 其中任意一个结点均无右孩子

C. 其中只有一个叶结点

D. 其中度为2的结点最多为一个

【答案】C

【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。

8． 下列选项中, 不能构成折半查找中关键字比较序列的是（ ）。

A.500, 200, 450, 180

B.500, 450, 200, 180

C.180, 500, 200, 450

D.180, 200, 500, 450

【答案】A

【解析】折半查找的过程是:先确定待查找记录所在的范围, 然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足:对每一个关键字, 其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A 项错误, 第三次比较的关键字为450, 说明待查关键字位于200〜450间, 所以第四次比较时不会遇到关键字180。

9． 若X 是后序线索二叉树中的叶结点, 且X 存在左兄弟结点Y , 则X 的右线索指向的是 （ ）

A.X 的父结点

B. 以Y 为根的子树的最左下结点

C.X 的左兄弟结点Y

D. 以Y 为根的子树的最右下结点

【答案】A

【解析】根据后续线索二叉树的定义, X 结点为叶子结点且有左兄弟, 那么这个结点为右孩子结点, 利用后续遍历的方式可知X 结点的后继是其父结点, 即其右线索指向的是父结点。

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趟排序是按然十位数字的大小