广州大学        学年第      学期考试卷
课程  数据结构与算法 考试形式（闭卷，考试）
信息学院      系        专业    级    班 学号：    姓名：           
题次
一
二
三
四
五
六
总分
评卷人
分数
20
10
10
30
20
10
100数据结构与算法分析答案
评分
一、填空题：（每格2分，共20分）
1．对于一个以顺序实现的循环队列-1]， 队头、队尾指针分别是f，r，其判空的条件是               ，判满的条件是                  。
2．前序序列和中序序列相同的二叉树为                  。
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．设图G有n个顶点e条边，采用邻接表存储，则拓扑排序算法的时间复杂度为                            。
10．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用二分法查
100时，需进行        次查时才能确定不成功。。
二、单项选择题（每题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（  ）哈希表的查效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。
四、（1）  （6分）
给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构.
         
（2）解答下面的问题（6分）
（1）求网的最小生成树有哪些算法？各适用何种情况？为什么？
（2）由以下的网络邻接矩阵，画出一棵最小生成树
（3）已知一棵非空二叉树，其按中根和后根遍历的结果分别为：
中根：CGBAHEDJFI  后根：GBCHEJIFDA
试将这样的二叉树构造出来。若已知先根和后根的遍历结果，能否构造出这棵二叉树，为什么？  5分
（4）一项工程由P1、P2、.......P6六项子工程组成, 这些工程之间有下列关系: P1<P2，P3<P6，P4<P3，P2<P6，P4<P5，P1<P3，P5<P6，符号“<”表示“先于”关系，例如P2<P6表示P2完成后P6才能开始。请给出工程P的三种可能的施工顺序。 （6分）
（5）假定用于通信的电文由8个字母A，B，C，D，E，F，G，H组成，各字母在电文中出
现的概率为5%,25%,4%,7%,9%,12%,30%,8%，试为这8个字母设计哈夫曼编码。（7分）
五、（1） 读程序，分析其时间复杂度：  4分
m=91;
n=100;
while(n>0)
if (m>0)
{ m=m-10;
n=n-1;
}
else m=m+1;
此程序的时间复杂度是             。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。