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

一、填空题

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

【答案】11

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

2． 阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】

【解析】本题是在哈希表

3． 有向图G=(V, E) ，其中权d 。E(G)为

，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50；4

4． 在单链表中设置头结点的作用是_____。

【答案】方便运算

中插入值为item 的元素，如该元素已在哈希表中，报告出错。

，用

三元组表示弧

及弧上的

5． 以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。

【答案】

6． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。

【答案】度；出度

7． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。

注:(1)图的顶点号从0开始计；

(2)indegree是有n 个分量的一维数组，放顶点的入度， (3)函数crein 用于记算顶点入度； (4)有三个函数回1，否则0) 。

其含义为数据data 入栈，出栈和测试栈是否空(不空返

("图有回路") ;

【答案】

【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

8． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。

【答案】

. 。

【解析】无向完全图中任意一个顶点都和其他n －1个顶点都有一条边，即为n(n－1) 。又因为每条边重复出现两次，所有无向完全图的边数为

9．

＝_____

【答案】5

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

【答案】9

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

二、判断题

11．数组是同类型值的集合。（ ）

【答案】 ×

【解析】数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数组是元素值和下标构成的偶对的有穷集合。

12．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ）

【答案】 ×

【解析】对于链式存储，数据元素之间的存储地址不一定是相邻的，即结点的存储空间可以是不连续的。而结点内部的存储空间需要是连续的，因为它是一个完整的数据。

13．若一个有向图无环，则它一定有唯一的拓扑序列。（ ）

【答案】×

【解析】有向图无环说明它一定有拓扑序列，但这个拓扑序列不唯一。如果在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，在做拓扑排序时，则排序的结果是唯一的，即它有唯一的拓扑序列。