21 15 30 36 25 40 26 37
14．设一哈希表长为13，采用线性探测法解决冲突，哈希函数H(key)=key,
（1）画出在空表中依次插入关键字25，20，36，15，41，52，29，72，67后的哈希表。 （2）求在等概率情况下，查找成功的平均查找长度。 （1）哈希表
（1） 100 101 102 103 104 105 106 107 108 109 110 111 112 52 15 41 29 67 20 72 36 25 （2）平均查找长度
查找成功的平均查找长度=(5*1+3*2+1*4)/9=1.6
15. 对下面的关键字集{35，15，21，99，25，26，36，37，01，18}写出快速排序的每趟结果和最终结果。
第一趟 {18,15,21,01,25,26}35{36,99} 第二趟 {01,15}18{21,25,26} 第三趟 01{15}
第四趟 21{25,26} 第五趟 25{26}
第六趟 36{99} 最终结果： {01,15,18,21,25,26,35,36,99}
16．设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k,最好采用什么排序
方法？为什么？
（1）采用堆排序最合适。
（2）因为当部分序列较小时，堆排序的时间复杂度近似为O(n)。
四、算法阅读题
1. 设有一个由正整数组成的无序单链表，阅读下面的算法，指出该算法的功能，并在“//”后面加上必要的注释。
void F1(Linklist &L){
p=L→next; pre=p; //pre为最小结点指针 while(p){ if(p→data pre=p; p=p→next; //（1） }//while printf(pre→data); //（2） if(pre→next && pre→data%2！=0) { //（3） temp=pre→data; pre→data=pre→next→data; pre→next→data=temp; }//if }//F1 算法功能：找出最小值结点，且打印该数值。若该数值是奇数且有后继，则与后继结点的数值交换。 (1)查找最小值结点； （2）输出最小值结点； （3）若该数值是奇数且有后继，则与后继结点的数值交换。 2. 已知二叉树的存储结构为二叉链表，LinkList和BiTree为已定义的指针类型，ListNode为已定义的结点类型，阅读下面算法并回答： LinkList L=Null; p; void F2(BiTree T){ if(T){ F2(T→lchild); if((!T→lchild)&&(!T→child){ p=(ListNode *)malloc(sizeof(ListNode)); p→data=T→data; p→next=L;L=p; }//if 9 F2(T→rchild); }//if }//F2 （1） 说明该算法的功能； （2） 对于一棵有8个结点的完全二叉数（假设结点顺序为A、B、C、D、E、F、G、H），画出执行上述算法后建立 的结构。 （1） 按中序遍历二叉树，逆序建立以叶子结点为链表结点、以L为头指针的无头结点的单链表。（2）（略） 3．假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树 T 中，阅读下面的算法，指出该算法的 功能，并在“//”后面加上必要的注释。 int F1(BiTrec T){ if(!T) return 0; if(!T→lchild &&!T→rchild)//（1）判断是否为叶子结点 return (T→data); Lv= F1(T→lchild);Rv= F1(T→rchild); switch(T→data){//（2）运算 case ’+’ : V=Lv+Rv; break; case’-’ : V=Lv-Rv; break; case’*’: V=Lv*Rv; break; case’/’: V=lv/Rv; break; } //switch return V;//（3）返回结果 }//F1 算法功能：后序遍历二叉树，求算术表达式的值。 4．假设哈希函数为H（key）,下面算法的功能是用链地址法解决冲突的哈希表的插入算法。请填空补全算法，并在“//”后面给以注释。 Void F2( HashTable &H, keytype Key){//哈希表插入，用链地址法解决冲突 (1)___________;// if(H[i]==Null){ s=(Linklist)malloc(sizeof(Lnode)); s→data=key; s→next=H[i]; H[i]=s; }//if else{ (2)___________)// while(p&&p→data!=key) p=p→next; if(p→data==key) exit(1); else{ (3)___________;// s→next=H[i]; H[i]=s; }// else }//else }//F2 5．下面算法的功能是实现单链表中的简单选择排序，其中L为链表的头结点指针，请填空补全算法，并在“//” 后面给以注释。 void F2(LinkList &L){//用单链表实现简单选择排序 p=L－>next; //初始化，p为工作指针 while(p){ min=p; (1)___________;// while((2)___________){ // if(q－>data 10 if( (3)___________){// temp=p－>data; p－>data=min－>data;min－>data=temp; }//if p=p－>next; }//while(p) }//F2 （1）q=p－>next; q为插入指针，min为当前最小指针 （2）q 或q !=null一趟选择排序 （3）min 交换结点数据 6．在有向图G中，如果r到G的每个结点都有路径可达，则称结点r为G的根结点，下面算法的功能是判断有向图G是否有根，若有，则打印出所有根结点的值。请填空补全算法，并在“//”后面给以注释。 void F2(ALGraph G){ //利用深度优先搜索，判断有向图G是否有根结点。 int visited[maxsige],count; //count为记录结构的顶点数。 for(v=0;v for(v=0;v count=0; DFS(G,v) ; if(count==(2)_)// printf(G.ver[v].data); } }// F2 void DFS(ALGraph G,int v){ //从第v个顶点出发递归地深度优先遍历图G visited[v]=1; count++; for(p=G.vertices[v].firstarc; p; p=p→nextarc){ w=p→adjvex; if(!visited[w]) (3)_;// } }//DFS （1）visited[v]=0；初始化顶点数组 （2）G.vexnum 判断是否为根 （3）DFS(G,w) ; 深度优先搜索 7．设有n个大小不等的数据组（n个数据组中数据的总数为m），顺序存放在空间区D内，每个数据占一个存储单 元。数据组的首地址由数组S给出，阅读下面的算法，指出该算法的功能，并在“//”后面加上必要的注释。 void F1(sqlist &L,int i, ElemType x){ if(i>=1&&i<=L.length){ //（1）插入到D区 for(j=0,p=L.elem[0];j<=m;j++) p++; //（2）求D区空闲空间首地址 if(i==L.length) *p=x;//（3）插入到第n个数组 else { for(q=L.elem[i];p>=q;--p) *(p+1)=*p; *p=x; //插入x for(q=&L.elem[i],p=&L.elem[L.length-1]; p>=q;q++) (*q)++;//else m++; }//if }//F1 算法功能：将数据x插入到D区，插入后D和S关系不变。 8. 假设哈希函数为H（key）,阅读下面的算法，指出该算法的功能，并在“//”后面加上必要的注释。 void f8(HashTable &H, KeyType key){ //用链地址法解决冲突哈希表 i=H(key); //获得哈希地址 if(H[i]= =Null) exit(1); p=H[i];q=p; // p为工作指针，q为p前趋 while(p&&p→data!=key) {//(1) 查找 q=p; p=p→next; 11 }//while if(!p) exit(1); if(q==H[i]){ //(2) key为第一结点 H[i]p→next; free(p); }// if else{ q→next=p→next; //(3) 删除结点 free(p); }//else }// f8 算法的功能：链地址法解决冲突的哈希表的删除算法。 9、设有一个正整数序列组成的非递减有序单链表，阅读下面的算法，指出该算法的功能，并在“// 后面加上必要的注释。 void F1 (Linklist L;int,x){ p= L→next; q=p; //p为工作指针 pre=L; L→next=NULL; .//q指最小元素 while(P&&P→data r=p→next; p→next=L→next; L→next=p; p=r; //（2）置逆 }//while q→next=p; pre=q; //（3）重新链接 }//F1 算法功能：在单链表中将比正整数x小的数按递减次序排列。 10、设计算法DeleteX的功能是：删除单链表L中值为x的结点的直接前趋结点。（设L是带头结点的单链表的头 指针，并为已知的LinkList类型） void DeleteX(LinkList &L){ //删除单链表中的直接前驱结点 p=L－>next; //初始化，p为工作指针 while(p&& p－>next－>data!=x){//q为前驱结点指针 q=p;p=p－>next; }// while if(p){ //删除 q－>next=p－>next; free(p); }//if }// DeleteX 11．假设哈希函数为H（key）,编写用链地址法解决冲突的哈希表的插入和删除算法。 void F2( HashTable &H, keytype Key){//哈希表插入，用链地址法解决冲突 i=H(Key);;// 获取哈希地址 if(H[i]==Null){ s=(Linklist)malloc(sizeof(Lnode)); s→data=key; s→next=H[i]; H[i]=s; }//if else{ p=H[i];// 查找 while(p&&p→data!=key) p=p→next; if(p→data==key) exit(1); else{ s=(Linklist)malloc(sizeof(Lnode));// 产生新结点，插入表头 12