(9)--算法与数据结构期末试卷2

福州大学 学年第一学期考试 卷
课程名称算法与数据结构考试日期
考生姓名学号专业或类别
题号一二三四五六七八总分累分人
签名题分30 10 40 20 100
得分
考生注意事项：1、本试卷共9 页，请查看试卷中是否有缺页。

2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。

一、选择题(每小题2分，共30分)
得分评卷人
请将答案填入下表中
题
1 2 3 4 5 6 7 8 9 101112 13 14 15号
答
案
1、下面关于算法的说法正确的是（）
A.算法最终必须由计算机程序实现
B.为解决某问题的算法同为问题编写的程序含义是相同的
C.算法就地工作的含义是指不需要任何额外的辅助空间
D.以上几个都是错误的
第 1 页共9 页
2、设线性表有n个元素，以下操作中，（）在顺序表上实现比在链表上实现效率更高。

A.输出第i个元素
B.交换第1个元素与第２个元素的值
C.顺序输出这n个元素的值
D.输出与给定值x相等的元素在线性表中的序号
3.一个栈的入栈序列为1, 2, 3,...,n ，其出栈序列是p1, p2 , p3 ,..., pn 。

若p2=3，则p3 可能取值的个数是（）。

A. n-3
B. n-2
C. n-1
D. 无法确定
4.已知三叉树T 中6 个叶结点的权分别是2，3，4，5，6，7，T 的带权路径长度最小是（）。

A. 27
B. 46
C. 54
D. 56
5.若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y，则X 的右线索指向的是（）。

A. X 的父结点
B. 以Y 为根的子树的最左下结点
C. X 的左兄弟结点Y
D. 以Y 为根的子树的最右下结点
6.在任意一棵非空二叉排序树T1 中，删除某结点v 之后形成二叉排序树T2，再将v 插入T2 形成二叉排序树T3。

下列关于T1 与T3 的叙述中，正确的是（）。

I.若v 是T1 的叶结点，则T1 与T3 不同
II. 若v 是T1 的叶结点，则T1 与T3 相同
III. 若v 不是T1 的叶结点，则T1 与T3 不同
IV. 若v 不是T1 的叶结点，则T1 与T3 相同
A.仅I、III
B. 仅I、IV
C. 仅II、III
D. 仅II、IV
7. 利用无圈有向图DAG的无圈性，在( )的时间内可以解关于DAG的多源最短路径问题。

A. O(n)
B. O(n＋e)
C. O(n*n)
D. O(n*e)
第 2 页共9 页
第 3 页 共 9 页
8.
若对如下无向图进行遍历，则下列选项中，不是宽度优先遍历序列的是（ ）。

A. h ，c ，a ，b ，d ，e ，g ，f
B. e ，a ，f ，g ，b ，h ，c ，d
C. d ，b ，c ，a ，h ，e ，f ，g
D. a ，b ，c ，d ，h ，e ，f ，g
9、已知循环队列存储在一维数组A[0,…..,n-1]中，且队列非空时，front 和rear 分别指向队首和队尾元素，若初始队列为空，且要求第一个进入队列的元素存储在A[0]处，则初始时front 和rear 的值分别是（ ）。

A.0,0 B.0,n-1 C.n-1,0 D.n-1, n-1
10、对于一个具有n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ）。

A.n B.(n-1)2 C.n-1 D.n2
11、含有n 个元素的集合A 和含有m 个元素的集合B 分别存放在两张有序链表中，现需完成A 和B 的并集操作，平均时间复杂性为（ ）。

A.O(n) B.O(m) C.O(n+m) D.O(n+m)
12、对关键字序列28,16,32,12,60,2,5,72 进行快速排序，第一趟划分结果为（ ）。

A ．{2，5，12，16} 28 {60，32，72} B ．{2，16,5,12} 28{60,32,72} C ．{2,16,12,5}28{60,32,72} D ．{5,16,2,12}28{32,60,72}
13、已知序列25，13，10，12，9是一个极大化堆，在其中插入新元素18，并将其调整为极大化堆，调整过程中元素之间进行的比较次数是（ ）。

A.1 B.2 C.4 D.5
14、Hash函数有一个共同的性质，即函数值应当尽量以（）取其值域的每个值。

A.最大概率
B.最小概率
C.平均概率
D.同等概率
15、用父结点数组法实现并查集时，每个子集合用（）来表示。

A.一棵树
B.一个数组
C.一张链表
D.一张图
二、填空题(每空 2 分，共10 分)
得分评卷人
1、假定n为线性表中关键字个数，且每次查找都是成功的，若查找ｉ个关键字的概率均
等，则顺序查找法的平均查找长度是，二分查找法的平均查找长度是。

2、对下列两序列L1={25，57，48，37，92，86，12，33}和序列L2={25，37，33，12，
48，57，86，92}，分别用冒泡排序方法进行排序，交换键值次数较少的是序列。

3、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为。

4、中缀表达式（3+4X）-2Y/3对应的后缀表达式为。

三、简答题(共40 分)
得分评卷人
第 4 页共9 页
1、（8分）高度为H的满k叉树T是具有以下性质的一棵树：根结点为第0层，
第H层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，起始编号为1，自根结点始，自上而下，自左而右，对T中全部结点进行编号，求（1）各层的结点数目分别是多少？
（2）编号为n的结点，其父结点编号是多少？
（3）编号为n的结点，其自左而右第i个儿子结点（若存在）的编号是多少？
提示：k叉树中编号为i的结点从右往左数第二个儿子结点的编号为k*i
2、(6分) 设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，N m个度数为m的结点，则该树中共有多少个叶子结点？（请写出求解过程）
3、(6分) （1）对于连通的无向图，采用Dijkstra最短路径算法，在Dist数组中
第 5 页共9 页
能否给出足够形成一棵支撑树的信息？
（2）是否能给出一棵最小支撑树？请证明你的结论或举反例说明。

4、(8分) 给定关键字序列{7，8，30，11，18，9，14，33}和散列函数h(key)=(key*3)(mod11)，闭散列表大小为11，采用线性探测法处理冲突，（1）请画出所构造的闭散列表；
（2）分别计算等概率并且未经过删除的情况下，查找成功和查找不成功的平均查找长度。

5、(12分)对于下图所示的无向连通赋权图：
第 6 页共9 页
第 7 页 共 9 页
（1）写出与该图对应的邻接矩阵（在顶点的邻接矩阵中，无边标记为∞）；
（2）用Prim 算法构造最小生成树并写出构造过程，画出最后得到的最小生成树，顶点1作
为最小生成树的起始点。

（1）、该图对应的邻接矩阵为：
（2）、用Prim 算法构造最小生成树的过程为： 1 2 3 4 5 6 U v closest lowcost closest lowcost closest lowcost closest lowcost closest lowcost closest lowcost
（其中v 为在该次择边完成后选择并入U 中的顶点）
构造得到的最小生成树为：
263 462
357
7
54698
四、算法设计题(共20 分)
得分评卷人
1、（8分）已知一个整数序列A(a0 , a1,..., an-1) ，其中0 ≤ a i < n(0 ≤ i < n)。

若存在x，
P1=x，P2= x，P3=x，...，Pm=x且m > n / 2(0 ≤ p k < n,1 ≤ k ≤ m)，则称x 为A 的主元素。

例如A=( 0，5，5，3，5，7，5，5 )，则 5 为主元素；又如A= ( 0，5，5，3，5，1，5，7 )，则A 中没有主元素。

假设A 中的n 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 A 的主元素。

若存在主元素，则输出该元素；否则输出-1。

并请分析你给出的算法的时间复杂性和空间复杂性。

2、（12分）给定一张有向图G，求一个结点数最大的结点集合，使得该结点集
合中任意两个结点u和v满足：或者从u出发可以到达v，或者从v出发可以
第8 页共9 页
达到u（u和v互相可达也可以）。

第9 页共9 页。