广州大学        学年第      学期考试卷
课程  数据结构与算法 考试形式（闭卷，考试）
信息学院      系        专业    级    班 学号：    姓名：           
题次
一
二
三
四
五
六
总分
评卷人
分数
20
10
10
30
20
10
100
评分
一、填空题：（每格2分，共20分）
1．在双向循环链表中，设指针p指向待删除的结点，则删除结点p需执行的语句为_________________        。
2．由a, b, c三个结点构成的二叉树，共有        种不同的结构。
3．设根结点处在第一层，那么具有n个结点的完全二叉树，其高度为                  。
4．克鲁斯卡尔的时间复杂度为                  ；它对                图较为适合。
5．给定表（55，63，44，38，75，80，31，56），用筛选法建立初始堆，则初始堆表为                                  。
6．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为
            。
7．已知8个数据元素由（35，75，40，15，20，55，95，65）按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为             
8．假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做      次插入和探测操作。
9．如果含n个顶点的图形成一个环，则它有        颗生成树。
10．对有17个元素的有序表A[1..17]作二分查，在查其等于A[8]的元素时，被比较的元素的下标依次是                            。
二、单项选择题（每题1分，共10分）
1．（      ）线性表采用链式存储时，其地址是（    ）
A．必须是连续的
B．一定是不连续的
C．部分地址必须是连续的
D．连续与否均可以
2．（      ）串的逻辑结构与（  ）的逻辑结构不同
A．线性表
B．栈
C．队列
D．树
3．（      ）设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为
A．3，2，5，6，4，1
B．1，5，4，6，2，3
C．2，4，3，5，1，6
D．4，5，3，6，2，1
4．（      ）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占一个存储空间，则a85的地址为
A．13
B．33
C．18
D．40
5．（      ）二叉树在线索化后，仍不能有效求解的问题是
A．前（先）序线索二叉树中求前（先）序后继；
B．数据结构与算法分析答案中序线索二叉树中求中序后继；
C．中序线索二叉树中求中序前趋；
D．后序线索二叉树中求后序后继。
6．（      ）如果结点A有3个兄弟，而且B为A的双亲，则B的度为
A．3
B．4
C．5
D．1
7．（      ）设有100个元素，用二分法查时，最大比较次数是
A．25
B．7
C．10
D．1
8．（      ）快速排序在（  ）情况下最不利于发挥其长处
A．被排序的数据量太大
B．被排序的数据中含有多个相同的关键字
C．被排序的数据完全无序
D．被排序的数据已基本有序
9．（      ）判定一个有向图是否存在回路，除了可以利用拓扑排序外，还可以利用
A．求关键路径的方法
B．求最短路径的Dijkstra方法
C．深度优先遍历算法
D．宽度优先遍历算法
10．（      ）对于含有个n顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为（  ），利用Kruskal时间复杂度为（  ）
A．O(log2n)
B．O(n2)
C．O(ne)
D．o(elog2e)
三、判断题（在括号内填上“√”或“╳”，每题1分，共10分，做错不倒扣）
1（  ）具有线性序关系的集合中，若a，b是集合中的任意两个原子，则必定有a<b的关系。
2（  ）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。
3（  ）一个满二叉树同时又是一棵平衡树。
4（  ）任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。
5（  ）只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。
6（  ）删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。
7（  ）对一个堆按层次遍历，不一定能得到一个有序序列。
8（  ）在索引顺序表查方法中，对索引顺序表可以使用顺序表查方法，也可以使用二分查方法。
9（  ）双循环链表中，任一结点的前驱指针均为不空。
10（  ）哈希表的查效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。
四、画图/计算/证明/应用题 (30分)
（1）  （6分）
试说明是否存在这样的二叉树，可以实现后序线索树进行后序遍历时不使用栈？对前序线索二叉树进行前序遍历时，什么样的二叉树可不使用栈？   
   
（2）解答下面的问题（6分）
（1）求网的最小生成树有哪些算法？各适用何种情况？为什么？
（2）由以下的网络邻接矩阵，画出一棵最小生成树
（3）已知一棵非空二叉树，其按中根和后根遍历的结果分别为：
中根：CGBAHEDJFI  后根：GBCHEJIFDA
试将这样的二叉树构造出来。若已知先根和后根的遍历结果，能否构造出这棵二叉树，为什么？  5分
（4）对于如图所示的事件结点网络，求出各活动可能的最早开始时间和允许的最晚完成时间，并问哪些活动是关键活动？ （6分）
（5）已知某字符串S共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用{0，1}进行前缀编码，问该字符串的编码至少有多少位？（7分）
五、程序填空题 （20分）
（1） 读程序，分析其时间复杂度：  4分
m=91;
n=100;
while(n>0)
if (m>0)
{ m=m-10;
n=n-1;
}
else m=m+1;
此程序的时间复杂度是             。