数据结构与算法试卷及答案7.pdfVIP

士不可以不弘毅，任重而道远。仁以为己任，不亦重乎?死而后已，不亦远乎?——《论语》

学院领导

AB卷

审批并签名

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

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

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

题次一二三四五六总分评卷人

分数201010302010100

评分

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

1．已知二叉树的中序遍历序列为B,H,D,C,E,F,A,G，后遍历序列为

H,D,F,E,C,B,G,A,其前序遍历列为。

2．若一个非连通的无向图最多有21条边，则该无向图至少有个顶点。

3．若具有n个顶点的无向连通图采用邻接矩阵表示，则邻接矩阵中至少有

________个非零元素。

4．若从无向图的任意一个顶点出发进行一次深度优先有哪些信誉好的足球投注网站便可以访问该图的

所有顶点，则该图一定是一个________________图。

5．将数据元素2，4，6，8，10，12，14，16，18，20依次存放于一个一维数

组中（设该数组第一个元素的下标为1），然后采用折半查找元素15，被比

较过的数组元素的下标依次为_____________。

6．顺序查找法，折半查找法，树形查找法和散列查找法这四种方法中，只有

_____________________的平均查找长度与元素的个数n无关。

7．设无向连通图G的顶点数与边数和一立方体相同，即有8个顶点和12条边。

任意一棵G的生成树共有________________条边

8．字符串’abcd’中共有________________个长度大于0小于4的子串。

9．将字符数组a[0..7,0..7]按行优先次序存储在起始地址为1000的连续的内存

士不可以不弘毅，任重而道远。仁以为己任，不亦重乎?死而后已，不亦远乎?——《论语》

单元中，则元素a[6,2]的地址是：__________________________

10．已知某带权连通无向图采用邻接矩阵存储方式，邻接矩阵以三元组表形

式给出，部包括主对角线元素在内的下三角形部分元素对应的各三元组分别



为(2,1,7),(3,1,6),(3,2,8),(4,1,9)(4,2,4),(4,3,6),(5,1,),(5,2,4),(5,3,),(5,4,2)。该

连通图的最小生成树的权值之和是。

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

1．（）堆排序的时间复杂度和需附加的存储空间分别是：

2

AO(n)和O(1)

BO(nlogn)和O(1)

2

CO(nlogn)和O(n)

2

2

DO(n)和O(n)

2．（）最佳二叉排序数的结构特点是：