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

一、填空题

1． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。

【答案】m/2

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

2． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

3． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）

【答案】93

【解析】对于上三角矩阵，将

4． 一个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】完全二叉树的高度

5． 在循环队列中，队列长度为n ，存储位置从0到，

【答案】

代入得93。

在B

编号，以rear 指示实际的队尾元素，现

要在此队列中插入一个新元素，新元素的位置是（ ）。

6． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。

【答案】2（N-1）

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。

7． 设有两个算法在同一机器上运行，其执行时闻分别为_____。

【答案】15 【解析】当

时，

而

，

时，

要使前者快于后者，n 至少为

8． 在有n 个顶点的有向图中，每个顶点的度最大可达。

【答案】2（n-l ）

【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。

9． 求最短路径的Dijkstra 算法的时间复杂度为_____。

【答案】

10．已知如下程序段：

语句1执行的时间复杂度为_____；语句2执行的时间复杂度为_____；语句3执行的时间复杂度为_____；语句4执行的时间复杂度为_____。

【答案】（1）n ＋1 （2）n

（3）n （n ＋3）/2 （4）n （n ＋l ）/2

【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋（n ＋l ）加起来就是n （n ＋3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n （n ＋l ）/2。

二、选择题

11．下列有关RAM 和ROM 的叙述中，正确的是（ ）。

I.RAM 是易失性存储器，ROM 是非易失性存储器 II.RAM 和ROM 都采用随机存取方式进行信息访问 III.RAM 和ROM 都可用作Cache IV .RAM 和ROM 都需要进行刷新 A. 仅I 和II B. 仅II 和III C. 仅 I 、II 和IV D. 仅II 、III 和IV 【答案】A

RAM 中的内容断电后即丢失ROM 中的内容断电后不会丢失，，【解析】（易失性）（非易失性），区别在同时RAM 和ROM 都采用随机存取方式（即CPU 对任何一个存储单元的存取时间相同）

于RAM 可读可写，ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新，所以III 和IV 的叙述都是错误的。

12．下列哪一种图的邻接矩阵是对称矩阵？（ ）

A. 有向图 B. 无向图 C.AOV 网 D.AOE 网 【答案】B

【解析】邻接矩阵存储，就是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间关系的二维数组称为邻接矩阵。因为无向图中边是没有方向的，所以所以无向图的邻接矩阵是对称矩阵。

13．引入二叉线索树的目的是（ ）。

A. 加快查找结点的前驱或后继的速度 B. 为了能在二叉树中方便地进行插入与删除 C. 为了能方便地找到双亲 D. 使二叉树的遍历结果唯一 【答案】A

【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。

14．对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。

A.95, 22, 91, 24, 94, 71 B.92, 20, 91, 34, 88, 35 C.21, 89, 77, 29, 36, 38 D.12, 25, 71, 68, 33, 34

【答案】A

【解析】各选项对应的查找过程如下图所示，从中看到选项B 、C 、D 对应的查找树都是二叉排序树，只有选项A 对应的查找树不是一棵二叉排序树，因为在以91为根的左子树中出现了比91大的结点94。