一、填空题

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

【答案】2(N-1)

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

2． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。

；算法 【答案】逻辑结构；物理结构；操作(运算)

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

【答案】度；出度

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

【答案】2(n-l )

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

5． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端)结点和_____个叶子，该满二叉树的深度为_____。 【答案】

或

【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。

6． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，

【答案】比较；移动

7． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。

【答案】有穷性；确定性；可行性

8． 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶

head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。

void leafchain(BiTree Abt)

{p={BiTree)malloc (sizeof (BiTNode ));

If (!p ){print£(“OVERFLOW\n”; exit (1); }

head=p; top=0;

if (bt )

{top++; stack[top]=bt;

while (top )

{t=stack[top]; top--;

if (it->Lchild && !t->Rchild){ (1) ; (2) ; (3) ; }

else {if( (4) ){top++; stack[top]= (5) ; }

if ( (6) ){top++; stack[top]= (5) ; }

}

}

(8) ; (9) ; } }

【答案】

p->Rchild=t:t->Lchild=p:p=t:

p->Rchild=head:head->Lchild=p

9． 已知如下程序段：

t->Rchild!=null:t->Rchild: t->Lchild!=null: t->Lchild:

语句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。

10．VSAM (虚拟存储存取方法)文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。

【答案】分配和释放存储空间；重组；对插入的记录

二、选择题

11．在下述结论中，正确的有( )。

①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换，④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A. ①②③

B. ②③④

C. ②④

D. ①④

【答案】D

【解析】只有根节点的二叉树的度为0，二叉树的左右子树隐含着他们的位置关系。因此，②③均错。

12．某自治系统内采用RIP 协议，若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量，距离矢量中包含信息

B.R2可以到达netl ，跳数为16

C.R1可以经过R2到达netl , 跳数为17

D.R1不能经过R2到达netl

【答案】D

【解析】RIP 允许一条路径最多只能包含15个路由器，因此距离等于16时相当于不可达，因此RIP 协议里规定16为路由不可达，答案为D 。

13．循环两列放在一维数组中，endl 指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是( )

A. 队空

：

B. 队空：

C. 队空：

D. 队空：

【答案】A

【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环

则能得出的结论是( )。 A.R2可以经过R1到达netl ，跳数为17 队满：队满

：队满：modM ; 队满：