一个连通图的生成树是一个（），它包含图中所有顶点，但只有足以构成一棵树的n-1条边。

(1)【◆题库问题◆】：[填空题] 一个连通图的生成树是一个（），它包含图中所有顶点，但只有足以构成一棵树的n-1条边。

【◆参考答案◆】：极小连通子图

(2)【◆题库问题◆】：[名词解释] 抽象数据类型

【◆参考答案◆】：
ADT，指一个数学模型以及定义在该模型上的一组操作。通常用数据对象、数据关系、基本操作集这样的三元组来表示。有数据抽象和数据封装两个重要特性。

(3)【◆题库问题◆】：[单选] 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）
A．2h
B．2h-1
C．2h+1
D．h+1

【◆参考答案◆】：B

(4)【◆题库问题◆】：[问答题,简答题] 编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。

【◆参考答案◆】：voidlinklist_c（Lnode*heaD.{Lnode*p；p=head；if（!p）returnERROR；while（p->next!=NULL）p=p->next；p->next=head；}设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）。

(5)【◆题库问题◆】：[问答题] 已知关键字序列{418，347，289，110，505，333，984，693，177}，按递增排序，求初始堆（画出初始堆的状态）。

【◆参考答案◆】：418，347，289，110，505，333，984，693，177 

(6)【◆题库问题◆】：[判断题] 二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面
A．正确
B．错误

【◆参考答案◆】：正确

(7)【◆题库问题◆】：[单选] 任一个有向图的拓扑序列（）。
A．不存在
B．有一个
C．一定有多个
D．有一个或多个

【◆参考答案◆】：D

(8)【◆题库问题◆】：[单选] 一个具有n个顶点的有向图最多有（）条边。
A．n×（n-1）/2
B．n×（n-1）
C．n×（n+1）/2
D．n2

【◆参考答案◆】：B

(9)【◆题库问题◆】：[判断题] 对二叉排序树进行中根遍历，可得到结点的有序排列。
A．正确
B．错误

【◆参考答案◆】：正确

(10)【◆题库问题◆】：[名词解释] 完全图

【◆参考答案◆】：
任何一个有N个结点的无向图，若其边数为N（N-1）/2，则这个无向图就是完全图。