《数据结构》试卷及答案2.docVIP

广州大学2017-2018学年第二学期考试卷

课程《数据结构》考试形式（闭卷，考试）

物理与电子工程学院电子系电子061、062、063专业学号姓名

题号

一

二

三

四

总分

评卷人

1

2

3

4

100

分数

15

20

4

6

9

11

35

评分

判断题（对打√，错打×。每题1分，共15分）

在单链表中，任何两个元素的存储位置之间都有固定的联系，因此可以从头结点进行查找任何一个元素。()

线性表的线性存储结构优于链表存储结构。()

完全二叉树的某结点若无左孩子，则必定是叶子结点。()

无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。()

在图结构中，结点可以没有任何前趋和后继（）。

在拓扑排序序列中，任意两个相继结点vi和vj都存在从vi到vj的路径。()

结点数固定的二叉树中，完全二叉树具有最小路径长度()。

中序线索树中，右线索若不为空，则一定指向其双亲结点()。

有向图用邻接矩阵表示，容易实现求结点度数的操作()。

二叉树是度最大为2的有序树()。

11、按广度优先搜索遍历图时，与始点相邻的结点先于不与始点相邻的结点访问()

若有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑排序序列必定存在()。

若有向图G中包含一个环，则G的结点间不存在拓扑排序()。

图的拓扑排序序列是唯一的()。

网络的最小代价生成树是惟一的（）。

二、选择题（每题2分，共20分）

1．在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构

C．线性结构和非线性结构 D．内部结构和外部结构

2．常对数组进行的两种基本操作是()。

A．建立与删除 B．索引和修改C．查找和修改 D．查找和索引

3．下列结论中不正确的是()。

A．按广度优先搜索遍历图时，与始点相邻的结点先于不与始点相邻的结点访问。

B．一个图按广度优先搜索法遍历的结果是唯一的。

C．无向图的邻接表表示法中，表中结点的数目是图中边的条数2倍。

D．图的多重邻接表表示法中，表中结点的数目是图中边的条数。

4．已知一个图如下所示，则由该图得到的一种拓扑序列为（）。

1

1

2

3

4

5

6

（A）v1,v4,v6,v2,v5,v3(B)v1,v2,v3,v4,v5,v6

(C)v1,v4,v2,v3,v6,v5(D)v1,v2,v4,v6,v3,v5

设有一个堆栈，元素进栈的次序为12345。不可能得到()出栈序列：

A．12345 B．54321 C．45312 D．43521

设n为正整数。下列程序段中前置以记号@的语句的频度为（）。

i=1;k=0;

while(in-1){

@ k+=10*i;

i++;

}

A．n B．n-1 C．n-2 D．n-3

7．具有n个顶点且每一对不同的顶点之间都有一条边的图被称为()。

A．线性图 B．无向完全图 C．无向图 D．简单图

8．下列结论中正确的是()。

A．在无向图中，边的条数是结点度数之和。

B．用Prim算法和Kruskal算法求得的图的最小生成树相同。

C．在图的邻接多重表表示中，任意一条边只用一个表目表示。

D．在拓扑排序序列中，任意两个相继结点vi和vj都存在从vi到vj的路径。

9．循环队列Q采用数组空间Q.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判断此循环队列Q为空的条件是()。

A．Q.rear–Q.front==n B．Q.rear–Q.front-1==n

C．Q.rear==Q.front D．Q.rear+1==Q.front

abecd

a

b

e

c

d

f

A．abecdf

B．acfebd

C．acebfd

D．acfdeb

三、问答题（共30分）

1．指出树和二叉树的主要差别。对于一个有1004个结点的二叉树，树叶最多有多少个？最少有多少个？（4分）

画出和下列已知序列对应的森林F（6分）：

森林的先序次序访问序列为：ABCDEFGHIJKL；

森林的中序次序访问序列为：CBEFDGAJIKLH。

图G的邻接矩阵如下所示：

试画出该图，并使用Kruskal算法构造出一棵最小生成树。（9分）

4．已知一组关键字为（10，24，32，17，31，30，46，47，40，63，4