（1）画出无向图G。 （2）画出G的邻接表
7.设某带权无向图如下图，画出用Prim算法和Kruskal算法，从顶点A开始生成最小生成树的每一步结果。并求出最小生成树的带权路径长度。
A138E45F95B2D7C6 8．下面的邻接表表示一个给定的无向图 （1）画出其邻接矩阵存储；
（2）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列； （3）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。 0123456 1 2 3 4 5 6 7 1 1 0 0 1 1 34 2 2 1 5 6 3 4
9.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
①画出描述折半查找过程的判定树； ②若查找元素54，需依次与哪些元素比较？ ③若查找元素90，需依次与哪些元素比较？
④假定每个元素的查找概率相等，求查找成功时的平均查找长度。 （1）
折半查找判定树为
（2） 查找元素54，需依次与30，63，42，54比较 （3） 查找元素90，需依次与30，63，87，95比较 （4） ASL=1/12*（1+2*2+4*3+5*4）=3
10．给定一组整数26，9，34，62，30，23，请构造一棵二叉排序树。，并计算查找成功时的ASL。
11.试画出从空树开始，由字符序列(t,d,e,s,u,g,b,j,a,k,r,i)构成的二叉平衡树，为每一次的平衡处理指明旋转类型，并计算出在等概率情况下查找成功时的平均查找长度。
12.设散列表长13，散列函数为H(key) = key % 13，对关键字序列93, 63, 81, 78, 17, 8, 85, 7, 30, 22造表，用线性探测再散列法解决冲突，画出相应的散列表，并计算等概率下查找成功时的平均查找长度。
13.设散列表长13，散列函数为H(key) = key % 13，对关键字序列19，14，23，1，68，20，84，27，55，11，10，79造表，用拉链法解决冲突，画出相应的散列表，并计算等概率下查找成功时的平均查找长度。
14．已知一组元素的关键码为 ( 77, 16, 48, 21, 19, 51, 62, 37, 60, 22, 99, 66 )，利用Shell排序使之按关键字递增次序排序，设排序间隔分别是5、3、1，依次写出各趟排序后的结果。 15. 给定一个关键字序列{24，19，32，43，38，6，13，22}，请写出冒泡排序各趟的排序结果。
五、算法设计（6个） 1. 简述以下算法的功能 Status
A(LinkedList L) {
if (L&&L->next){ Q=L;L=L->next;P=L; While(P-> next) P=P-> next;
P-> next= Q; Q-> next=NULL; }
return OK ; }
2.写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){ Stack S; Char x,y; InitStack(S); X=’c’;y=’k’;
Push(S,x); Push(S,’a’); Push(S,y); Pop(S,x); Push(S,’t’); Push(S,x); Pop(S,x); Push(S,’s’);
while(!StackEmpty(S)){ Pop(S,y);printf(y); }; Printf(x); }
输出为“stack”。
Pop()函数是出栈并且将出栈的元素存放在第二个行参里，所以在这里x的值不再是c了，而是出栈的元素。。 过程：
首先是三个压栈操作，之后栈里的元素为：cak，左边的为栈底，右边是栈顶。
然后一个出栈，此时栈里的元素为：ca，x中存的是k； 之后两次压栈，此时栈里的元素为：catk；
之后一个出栈，此时栈里的元素为：cat，x中存的是k；
最后一次压栈，此时栈里的元素为：cats，x中存的是k； 之后while(!StackEmpty(S)){ Pop(S,y);printf(y); }; 结果是stac， Printf(x); 结果是k，
3．简述以下算法的功能（栈和队列的元素类型均为int）。 voidnizhi(Queue &Q){ Stack S; int d; InitStack(S);
while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d);}; while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); }} 功能：队列中的数据元素逆置 4．已知二叉树的结点数据类型如下： typedefstruct node {ElemType data;
//数据元素
struct node *lchild; //指向左孩子 struct node *rchild; //指向右孩子
}BTNode,*BiTree;
阅读下列二叉树算法,回答问题。 voidexchange(BiTreebt) { if(bt) {BiTree s;
s=bt->lchild; bt->lchild=bt->rchild;bt->rchild=s; exchange(bt->lchild); exchange(bt->rchild); } }
该算法执行二叉树运算的什么功能？
将二叉树中所有结点的左，右子树相互交换
5．将下面算法填完整。
intSearch_Bin(SSTable ST, KeyType key){
//在有序表ST中折半查找其关键字等于key的数据元素，若找到，则返回该元素//在表中的位置，否则返回0 low=1;high=; while(low<=high){ mid=____________;
if(EQ(key, ST.elem[mid].key)) return ____________; else if(LT(key, ST.elem[mid].key)) high=____________; else low=____________; }
return ____________;
intSearch_Bin(SSTableST,KeyType key)
//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为 //该元素在表中的位置，否则为0. {
low = 1; high = ST.length; while(low <= high) {
mid = (low + high)/2;
if(EQ(key, ST.elem[mid].key)) return mid;
else if (LT(key,ST.elem[mid].key)) high = mid -1;
else low = mid + 1; }
return 0;
}//Search.Bin
6.试写出改进的冒泡排序算法描述，当某一趟排序没有数据交换时结束排序过程
public static void bubbleSort_2(int[] list) { int temp = 0; // 用来交换的临时数 boolean bChange = false; // 交换标志
// 要遍历的次数
for (int i = 0; i < list.length - 1; i++) { bChange = false;
// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
for (int j = list.length - 1; j > i; j--) { // 比较相邻的元素，如果前面的数大于后面的数，则交换 if (list[j - 1] > list[j]) { temp = list[j - 1]; list[j - 1] = list[j]; list[j] = temp; bChange = true; } }
// 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序 if (false == bChange) break; } }