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

一、填空题

1． 在n 个顶点的非空无向图中，最多有_____个连通分量。

【答案】n

【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。

2． 在一棵m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____; 若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。 【答案】

【解析】m 阶B-树除根结点和叶子结点外，结点中关键字个数最多是m －1，最少

3． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

4． 串是一种特殊的线性表，_____；其特殊性表现在_____；串的两种最基本的存储方式是_____、两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等

5． 表达式23＋((12*3﹣2)/4＋34，5/7) ＋108/9的后缀表达式是_____。 【答案】

(表达式中的点(.)是数分隔符，如是三个数)

二、单项选择题

6． 已知序列25, 13, 10, 12, 9是大根堆, 在序列尾部插入新元素18, 将其再调整为大根堆, 调整过程中元素之间进行的比较次数是（ ）。

A.1

B.2

C.4

D.5

【答案】B

【解析】对堆插入或删除一个元素, 有可能不满足堆的性质, 堆被破坏, 需要调整为新堆。

(1)为原堆,

(2)为插入18后,

(3)比较10与18, 交换后,

(4)比较25与18, 不交换, 即为调整后的新的大根堆。

因此调整过程中元素之间进行的比较次数为2。

7． 下列关于图的叙述中, 正确的是（ ）。

Ⅰ. 回路是简单路径

Ⅱ. 存储稀疏图, 用邻接矩阵比邻接表更省空间

Ⅲ. 若有向图中存在拓扑序列, 则该图不存在回路

A. 仅Ⅱ

B. 仅Ⅰ、Ⅱ

C. 仅Ⅲ

D. 仅Ⅰ、Ⅲ

【答案】C

【解析】第一个顶点和最后一个顶点相同的路径称为回路; 序列中顶点不重复出现的路径称为简单路径; 回路显然不是简单路径, 所以选项Ⅰ错误。稀疏图用邻接表表示比邻接矩阵节省存储空间, 稠密图适合用邻接矩阵的存储表示, 所以选项Ⅱ错误。利用拓扑排序算法可以判断图中是否存在回路, 即在拓扑排序输出结束后所余下的顶点都有前驱, 则说明了只得到了部分顶点的拓扑有序序列, 图中存在回路。所以选项Ⅲ正确。

8． 给定二叉树如下图所示. 设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树. 若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）.

A.LRN

B.NRL

C.RLN

D.RNL

图

【答案】D

【解析】对“二叉树”而言，一般有三条搜索路径：

①先上后下的按层次遍历；

②先左(子树) 后右(子树) 的遍历；

③先右(子树) 后左(子树) 的遍历.

其中第1种搜索路径方式就是常见的层次遍历，第2种搜索路径方式包括常见的先序遍历NLR 、中序遍历LNR 、后序遍历LRN ，第3种搜索路径方式则是不常使用的NRL 、RNL 、RLN. 本题考查的是第3种搜索路径方式的一种情况. 根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D.

9． 若x=103, y=-25测下列表达式采用8位定点补码运算实现时, 会发生溢出的是（ ）

A.x+y

B.-x+y

C.x-y

D.-x-y

【答案】C

答:8位定点补码能表示的数的范围为:-128~127

A 结果为78, B 结果为-128, D结果为-78都在此范围内, 只有C 结果128超过了8位定点补码能表示的数的范围, 会发生溢出

10．对矩阵压缩存储是为了（ ）。

A. 方便运算

B. 方便存储

C. 提高运算速度

D. 减少存储空间

【答案】D

【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。

11．下列选项中，降低进程优先级的合理时机是（ ）.

A. 进程的时间片用完