武汉科技大学数据结构2013-2016,2018,2019年考研真题(都有答案)

第第页共49页分别用Prim和kruskal算法构造最小生成树。（需标示每一步构造过程）四、算法设计（第1题10分，第2,3题各15分，共40分）设计算法，在不带头结点的单链表L上实现删除data域值为x的所有结点，返回删除结点的个数；intList_Delete（structLNode*L，KeyTypex）采用链式存储实现栈的操作（数据元素类型为ElemType）,包括栈的初始化InitStack、入栈Push、出栈Pop、取栈顶元素Peek、判栈空Empty、清空栈ClearStack以及返回栈中元素个数GetLen等操作，并作简单注释。根据给定的n个权值可以构造一颗哈夫曼树。若哈夫曼树采用顺序存储结构,每个结点的数据结构采用如下格式。Typedefstruct{unsignedintweight;//结点的权值unsignedintparent,lchild,rchild;//分别存放双亲、左右孩子的下标}Huffman;试设计如下算法CreatHuffman，根据给定的n个权值构造一颗哈夫曼树。voidCreatHuffman（HuffmanHT[],intn,intw[]）;其中：HT为构造的哈夫曼树，n表示权值个数，w用来存储所有权值下图是根据权值7,5，2，4所构造出来的哈夫曼树（-1表示空）。参考答案⑷一、选择题（10小题，每题2分，共20分）DBACDADCAB二、填空题（10小题，每题2分，共20分）1.关系和操作2.O（n）3.栈4.15.146.A[2i+2]7.28.队列9.Dijkstra10.11

三、综合应用题(7小题，每题10分，共70分)3(3)(4)(1)k=2i+j-3(2)i=(k+l)/3+lj=(k+l)/3+(k+l)%3(1).三、综合应用题(7小题，每题10分，共70分)3(3)(4)(1)k=2i+j-3(2)i=(k+l)/3+lj=(k+l)/3+(k+l)%3(1).-'(2)先序中序后序:eadcbjfghi:abcdjefhgi:bcjdahigfe01234567891011121314151617181938202142242526452931332041111111211123.散列函数H(k)=k%19成功：ASL=14/12=7/6不成功：ASL=(4+3+2+1+6+5+4+3+2+1+2+1+2+1+3+2+1+1+1+1)/20=46/20=2.34.1)4)1)快速排序一趟后的结果:25351640728761502)堆排序进行升序初始堆:87726150401625353)堆排序1趟以后的结果:72506135401625874)1趟冒泡排序后的结果:35406172162550875)1趟归并排序后的结果:35406187167225505.(2)7291(3)724531查找成功的平均查找长度:(1+2*2+4*3+6*4)/13=41/13不成功时的平均查找长度:(2*3+12*4)/14=54/14=27/76.(1)事件V1V2V3V4V5V6V7V8V9V10V11最早发生时间01510655080160190220250270最迟发生时间0151565205801602052202502702)活动a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14e100015106510801908016050220250190l15051557651659520580160205220250210(3)关键路径:a1-〉a3-〉a5-〉a9-〉a10-〉a12-〉a134)12四、算法设计(第1题10分，第2，3题各15分，共40分)1.intList_Delete(structLNode*L,KeyTypex){intc=0;if(L==NULL)return0;p=L;while(p->next){if(p->next->data==x){c++;s=p->next;p->next=s->next;free(s);}elsep=p->next;}if(L->data==x){c++;p=L;L=L->next;free(p);}returnc;}2.typedefstructnode{ElenTypedata;structnode*next;}LinkStack;voidInitStack(LinkStack&L){L=NULL;}voidPush(LinkStack&L,ElemTypex){p=(LinkList*)malloc(sizeof(LinkList));p->data=x;p->next=L;L=p;}voidPop(LinkStack&L,ElemType&x){if(L==NULL)return;p=L;L=L->next;x=p->data;free(p);}voidPeek(LinkStack&L,ElemType&x){if(L==NULL)return;x=L->data;}intEmpty(LinkStackL){returnL==NULL;}voidClearStack(LinkStack&L){while(L){p=L->next;free(L);L=p;}}intGetLen(LinkStackL){inti=0;p=L;while(p){i++;p=p->next;}returni;}3.voidCreatHuffman(HuffmanHT[]，intn，intw[]){for(i=0；i<n；i++){HT[i].lchild=T;HT[i].rchild=T;HT[i].weight=w[i];HT[i].parent=T;}for(i=n；i<2*n-