广州大学        学年第      学期考试卷
课程  数据结构与算法 考试形式（闭卷，考试）
信息学院      系        专业    级    班 学号：    姓名：           
题次
一
二
三
四
五
六
总分
评卷人
分数
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.  (  ) 假设以数组]存放循环队列的元素，其头指针是front，当前队列有k个元素，则队列的尾指针为（  ）
A.(front+k) mod (n-m+1)
B.(m+k) mod n + front
C.(front-m+k) mod (n-m+1) +m
D.(front-m+k) mod (n-m+1)
2.  (  ) 若用冒泡排序对关键字序列{20, 17, 11, 8, 6, 2} 从小到大进行排列, 则需要交换的总次数为(  )
A.3      B.  6          C. 12          D. 15
3.  (  ) 具有842个结点的完全三叉树，其叶子结点共有（    ）个
A. 421  B. 422  C.420    D.423    E.以上都不是
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个结点的二叉树，按层次从上到下，同一层从左到右的顺序存储在一维数组]中，则二叉树中第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,Vj>        B.G中有一条从Vi到Vj的路径
C. G中没有弧<Vi,Vj>      D. G中有一条从Vj到Vi的路径
10. (    )设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是(    )
A. m-n    B. m-n-1    C. n+1    D. 条件不足，无法确定
三、判断题（在括号内填上“√”或“╳”，每题1分，共10分，做错不倒扣）
1 （  ）数据对象就是一组数据元素的集合。
2  (  ) 任何一棵前序线索二叉树，都可以不用栈实现前序遍历。
3 （  ）就平均查长度而言，分块查最小，折半查次之，顺序查最大
4 （  ）用Shell方法排序时，若关键字的排列杂乱无序，则效率最高。
5 （  ）在任何条件下，快速排序的效率总是最好的。
6 （  ）二叉排序树查和折半查的时间性能相同。
7 （  ）N个顶点的图至少含有N-1条边
8 （  ）拓扑排序是判断一个有向图是否存在回路的唯一方法。
9 （  ）在一棵二叉排序树T中，先删除结点N，然后再插入结点N，得到新的二叉排序树T1，则T和T1相同。
10 （  ）栈和队列都是限制存取点的线性结构。
四、画图/计算/证明 (30分)
1． 证明题（5分）
试证明有n0个叶子的哈夫曼树共有2n0-1个结点。
2．一项工程由P1、P2、.......P6六项子工程组成, 这些工程之间有下列关系: P1<P2，P3<P6，P4<P3，P2<P6，P4<P5，P1<P3，P5<P6，符号“<”表示“先于”关系，例如P2<P6表示P2完成后P6才能开始。请给出工程P的三种可能的施工顺序。（5分）

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