一.应用题:
1 经过两趟排序后的数据序列(2,1,4,9,8,10,6,20).对于快速排序,冒泡排序,选择排序和插入排序
(1) 该排序属于哪种排序.
(2)给出初始的数据排序和两趟排序排序过程.
2.有一个二叉树按顺序存储结构存放在一维数组中,如图所示
1 2 3 4 5 6 7 8 9 10 11
A C B E D G
画出该树后序线索树的存储结构示意图.
3.下图为无向带权图,按prim算法画出可能的最小生成树。
4．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t）使用折半查找
（1）写出在查找关键字b的过程，先后进行比较的关键字序列
（2）画出该有序表的判定树。
5．在平衡二叉树中插入一个结点后造成了不平衡。设最低的不平衡结点为A。并已知A的左孩子B的平衡因子为0右孩子C的平衡因子为1。
（1）若调整以使其平衡画出该调整过程示意图。
（2）给出调整过程中的指针变化的局部算法。
二．算法阅读：
Lnode
data next
1.下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。
（1） 给出单链表L的存储结构定义（typedef）
（2） Void select (linkedlist L )
{
Linkedlist p,q,min;
Elemtype rcd;
P= (1) ;
While (p) {
Min=p
Q=p->next;
While(a){
If (2)
Min=q
Q=q->next;
}//while
If (3) {
Rcd=p->data;
p->data=min->data;
min->data=rcd
}//if
(4) ;
}//while
}//selectsort
2.已知带头结点的单链表中的关键字为整数，为提高查找效率需将它改建为采用拉链法处理冲突的散列表设散列表的长度为m散列函数为hash(key)=key%m
链表的结点结构为
key next
(1) 画出此散列表的存储结构示意图。
（2）
Void L-to-H (linklist L, linklist H [ ] , int m).
{//由带头结点的单链表L生成散列表H。散列表生成之后原链表不再存在
Int I,j;
Linklist p,q;
For (i=0;i<m;i++)
H[i] = (1) ;
P=L->next;
While (p){
q=p->next:
j=p->key%m;
(2)
H[j]=p;
(3)
}//while
Free(L);
}//L-to-H
三．算法设计：
1．用图的广度优先遍历求解邻接表的有向图的两点间的连通性
2．用图的深度优先遍历递归地求解邻接矩阵的无向图的两点间的连通性
3．先序遍厉非递归地求解二叉链表的二叉树中非叶子结点个数。
4．先序遍历递归求解二叉链表的二叉树中叶子结点的个数。