《数据结构与算法》试卷与答案.docVIP

PAGE

PAGE1

广州大学学年第学期考试卷

课程数据结构与算法考试形式（闭卷，考试）

信息学院系专业级班学号：姓名：

题次

一

二

三

四

五

六

总分

评卷人

分数

20

10

10

30

20

10

100

评分

填空题：（每空2分，共20分）

1．在拓扑排序中，拓扑序列的第一个顶点必定是的顶点。

2.由四个分别带权值为5,12,9,30,7,16的叶子结点构造一棵哈夫曼树，该树的结点个数为，树的带权路径长度为。

3．对表长为n的顺序表进行分块查找，若以顺序查找确定块，且每块长度为s，则在等概率查找的情况下，查找成功时的平均查找长度为。

4．如果结点A有3个兄弟，而且B是A的双亲，则B的度是

5．一个无序序列可以通过构造一棵树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

6．设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为

7.求从某源点到其余各顶点的Dijkstra算法，当图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则当图的顶点数为40时，计算时间为ms

8.设一棵后序线索树的高度是50，结点x是树中的一个结点，其双亲是结点y，y的右子树高度是31，x是y的左孩子，则确定x的后继最多需经过个中间结点（不含后继及x本身）

9．对于单向链表，在两个结点之间插入一个新结点时需修改的指针

共有个。

单项选择题（每题1分，共10分）

1.()假设以数组A[m..n]存放循环队列的元素，其头指针是front，当前队列有k个元素，则队列的尾指针为（）

(front+k)mod(n-m+1)

(m+k)modn+front

(front-m+k)mod(n-m+1)+m

(front-m+k)mod(n-m+1)

2.()若用冒泡排序对关键字序列{20,17,11,8,6,2}从小到大进行排列,则需要交换的总次数为()

3B.6C.12D.15

3.()具有842个结点的完全三叉树，其叶子结点共有（）个

A.421B.422C.420D.423E.以上都不是

4.（）顺序查找方法适用于存储结构为（）的线性表

A.压缩存储B.散列存储C.顺序存储D.链式存储

E以上都不是

5.（）以下序列不是堆的是（）

A．（100，85，98，77，80，60，82，40，20，10，66）

B.（100，98，85，82，80，77，66，60，40，20，10）

C．（10，20，40，60，66，77，80，82，85，98，100）

D．（100，85，40，77，80，60，66，98，82，10，20）

6．（）如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的查找方法是（）

A．分块查找B.顺序查找C.折半查找D.基于属性

7.（）一棵有n个结点的二叉树，按层次从上到下，同一层从左到右的顺序存储在一维数组A[1...n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（）

A.A[2i](2i=n)B.A[2i+1](2i+1=n)C.A[i/2]D.条件不充分，无法确定

8．（）有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列输入（）

A.45，24，53，12，37，96，30

B.37，24，12，30，53，45，96

C.12，24，30，37，45，53，96

D.30，24，12，37，45，96，53

9．()在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是()

A.G中有弧Vi,VjB.G中有一条从Vi到Vj的路径

C.G中没有弧Vi,VjD.G中有一条从Vj到Vi的路径

10.()设森林F对应的二叉树为B，它