一．选择题
1．某二叉树的前序遍历为：abdefc，中序遍历为：bedfac，则后序遍历为（ ）。
A．efdbca B．befdca C．edfbca D．efdbac
2．某无向图G是连通的，则结点数n和边数e一定有如下关系（ ）。
A . e>=n-1 B . e>=n-2 C . e>=n-3 D . e>=n-4
3．能采用二分查找的数据结构是（ ）
A .线性表 B. 二叉树 C. 有序表 D . 哈希表
4．已知某图G，e 为G中边的总数，则图G中所有顶点的度之和为（ ）。
A . 2e B . e C . 2e+1 D . 2e-1
5．下列哪一个不属于算法的性质（ ）。
A．输入性 B．输出性 C．可执行性 D．可修改性
6．一棵有n（n>0）个结点的满二叉树共有( )个叶子结点。
A. n/2 B. n/2-1 C. (n+1)/2 D. (n-1)/2
7．顺序表的主要优点是（ ）。
A．不支持随机存取 B．内存空间利用率高
C．时间效率高 D．可方便扩充数组大小
8．假设指针p指向单链表中的某一结点，若在p指针的后面插入一个新结点q，只需修改下列哪个指针值即可（ ）。
A．p=q;q=p.next; B．p=q.next;q.next=p.next
C．p.next=q;q.next=p.next; D．q.next=p.next;p.next=q;
9．若进栈系列为：a，b，c，d，则下列哪一个不可能是出栈系列（ ）。
A．a，b，c，d B．c，d，b，a C．a，c，d，b D．c，a，b，d
10．某二叉树共有1001个结点，其中叶结点的个数为501个，则度为2的结点个数为（ ）。
A．498 B．499 C．500 D．不能确定
二．填空题
1．若规定二叉树根结点的层次为1，则第4层上最多有（ ）个结点。
2．具有N个结点的无向完全图共有（ ）条边。
3．数据结构课程是研究数据的（ ）、（ ）、（ ）等三个方面的内容。
4．树转换为二叉树，其根结点的（ ）子树一定为空。
5．若串s=“Data Structure”，则执行语句s=s.substring(5, s.length())后,
s的值为( )。
6．已知二维数组a[10][8]采用行优先存储方式，每个元素占2个存储单元，第一个元素的存储地址是1012，则元素a[4][5]的存储地址为（ ）。
7．具有N个数据的无序表中，若采用顺序查找算法，且每个数据查找的概率相等，那么查找成功时，平均查找长度ASL=（ ）。
8．画出具有3个结点的二叉树的所有形态：（ ）。
三．判断题（正确的请打“√”，错误的请打“×”，每题1分，共10分）
1．堆栈是一种先进先出表。 （ ）
2．递归算法是指存在自调用的算法。 （ ）
6．满二叉树一定是完全二叉树。 （ ）
4．数据元素之间的相互联系方式称为数据的逻辑结构。 （ ）
5．算法执行的时间越长说明算法的时间效率越高。 （ ）
6．实现顺序存储结构的方法是使用数组。 （ ）
7．对二叉树和图进行遍历所得的次序都是唯一的。 （ ）
8．含有N（N>1）个结点的二叉树前序和后序遍历次序一定不相同。（ ）
9．二叉排序树中根结点的权值最大。 （ ）
10．图的最小生成树是惟一的。 （ ）
四．应用题
1．对于下列二叉树，请写出：
（1）前、中、后序遍历次序；
（2）中序线索二叉链表；
2．给定数据元素系列为{47，23，2，15，98，57，22，6，12}，请写出冒泡排序各趟的结果。
3．给定叶子结点的权值{1，4，6，2，9}，请构造哈夫曼树，并给出叶子结点的哈夫曼编码。
4．给定数据元素系列为{47，23，2，15，98，57，22，6，12}，请写出直接选择排序各趟的结果。
5．画出中序遍历次序为xyz的所有二叉树的形态。
五．算法设计题
1．下列程序是二分查找的非递归算法,请填空:
public static int biSeach(int a[],int x){
int n=a.length();
int i=0,j=n-1,mid;
while ( )
{mid= ;
if (a[mid]==x) return mid;
else if ( )
;
else
;
}
rerurn -1;
}
2．请写出冒泡排序的算法：
public static void bubbleSort(int a[])