6、一个具有5个结点的有向图最少有______________ 条弧。
7、二叉排序树采用______________ 序遍历可以得到结点的有序序列。
8、设有1000个元素，用二分法查找时，最大比较次数是_________ 。
三、判断题（每题1分，共8分，对的打√，错的打×）
1、如果某数据结构的每一个元素都最多只有一个直接后继结点，则必为线性表。（ ）
2、如果某有向图的所有顶点可以构成一个拓扑排序，则说明该有向图存在回路。（ ）
3、如果把一个大顶堆看成一棵二叉树，根元素层次为1，则层次越大的元素值越小。（ ）
4、Huffman树没有度为1的结点。（ ）
5、在冒泡排序中，关键字的比较次数与记录的初始排列无关。（ ）
6、设一棵二叉树共有50个叶子结点（终端结点），则它共有49个度为1的结点。（ ）
7、一个有序的单链表采用折半查找法比采用顺序查找法效率要高得多。（ ）
8、一个图可以没有边，但不能没有顶点。（ ）
四、简答题（共38分）
1、排序。
（1）写出线性表（26，45，12，2.，30，6，15，29，16，2，18）采用基数排序后，第一趟结束时的结果。（4分）
（2）采用简单选择排序算法对线性表（26，15，12，16，5，30）进行排序，进行交换的第一对元素是哪两个元素?在什么情况下，第一趟不需进行元素的交换？（6分）
2、已知二叉树如图9.9所示。
（1）给出该二叉树的后序遍历的结果。（5分）
（2）如果图9.9表示的是采用孩子——兄弟法
转换后的一棵树，请画出原来的树。（5分）
3、已知图9.10是一个有向图
（1）画出该有向图的邻接矩阵。（5分）
（2）基于你给出的邻接矩阵，求从顶点B出发的深度
优先遍历。（5分）
4、已知有序表（4，11，13，19，26，28，33，39，42），采用折半查找
（1）各元素的平均查找长度是多少？（4分）
（2）查找值为10的元素，查找时与哪几个元素进行了比较？（4分）
五、程序填空题（共15分）
1、已知STACK表示栈的数据结构，push是将一个值为e的元素进栈，成功返回1，否则返回0。完成以下程序。（7分）
public class Stack<T>
{
private T[] data = new T[100];