2012-2014年武汉科技大学考研真题C语言程序设计与参考答案

第第页共21页参考答案（A）一、选择题（10小题,每题2分，共20分）1.D2・D3.C4.C5.B6.B7.A8.A9.A10.C二、填空题（10小题,每题2分，共20分）2h-l5・[log：i]二[logj][logzil+l10.21.s->next二p2h-l5・[log：i]二[logj][logzil+l10.2深度7.0(n：)8.k(k+l)/29.三、综合应用题（7小题，每题10分，共70分）1.根据完全二叉树的性质,A[i]的双亲是A[i/2],双亲的双亲是A[i/2/2],...同理，A[j]的双亲是A[j/2],双亲的双亲是A[j/2/2],...if（i==j）A[i]和A[j]的最近的共同祖先就是A[i/2]；elsewhile(i!=j){if(i>j)i=i/2;elsej=j/2;}A[i]和A[j]的最近的共同祖先就是A[i];2.设总结点数为n,度为1和2的结点数分别为nl和n2n=B-l=nO+nl+n2nl=0n2=n0-l3.4.B=2n0-2(4)i!=min(2)j<=n-l-i(5)max==i(3)rLj]・key<r[minZ.key(1)1562738415627834156723841567283415678234(2)事件VIV2V3V4V5V6V7V8最早发生时间Ve030506510172535最迟发生时间VI030506515274459(3)活动<1-2><1-5><1-4><2-3><3-4><5-2><5-6>最早开始时间e00030501010最迟开始时间105530501520活动〈6-2><6-3><6-7><7-3><7-4><7-8><8-4>最早开始时间e17171725252535最迟开始时间127343644624959（4）给出其关键路径：<l-2><2-3><3-4>5.（1）线性探测法012315678910key449381324322110num11212123等概率下查找成功时的平均查找长度ASL沁二（1+1+2+1+2+1+2+3）/8二13/8等概率下查找失败时的平均查找长度ASL^/(l+2+l+l+8+7+6+5+4+3+2)/ll=10/ll(2)链地址法等概率下查找成功时的平均查找长度ASL沁=(1*4+2*3+3*1)/8=13/8等概率下查找失败时的平均查找长度ASL^u/(l*7+2*l+3*2+4*l)/ll=19/ll6.只有堆排序，在未结束全部排序前，可以有部分排序结果。建立堆后，堆顶元素就是最大(或最小，视大堆或小堆而定)元素，然后，调堆又选出次大(小)元素。凡要求在n个元素中选.llk(k«n,k>2)个最大(或最小)元素，一般均使用堆排序。因为堆排序建堆比较次数至多不超过4n,对深度为k的堆，在调堆算法中进行的关键字的比较次数至多为2(k-l)次，且辅助空间为0(1)。7.若查找元素54,需依次与元素35584054比较若査找元素20,需依次与元素3551724比较等概率情况下查找成功的平均查找氏度ASL=(1*1+2*2+3*4+4*5)/12=37/12等概率情况下查找不成功时的平均查找长度ASL=(3*3+4*10)/13=49/13U!算法设计与编程(4小题,每题10分，共40分)1.ElemtypeLocate(LinkListL,KeyTypex){P=L；p=p->next;while(p->next&&p->next->data!=x)if(p->next)p=p->next;s=p->next;s->freq++;while(p!=head&&p->freq〈s->freq)q=s->pred;s->next->pred=q;s->next=p->next;s->pred=p;p=p->pred;q->next=s->next;p->next->pred=s;p->next=s;第19页共21页returns;elsereturnNULL}2.voidpre_visit(structtreeT[],intr){pre_visit(T,T[r].Rc);}if(r){visit(T[r]・data);pre_visit(T,T[r].Rc);}}3.BiTreePre_Search(BiTreeT){if(T->ltag=0)//左孩子没有returnT->left;if(T->rtag==0)//右孩子没有returnT->left;p=T->right;while(p->right)p=p->right;:returnp;}4.voidsort(LinkListL){if(L->next==NULL)return;start=L->next;end二p;while(end-〉next)end二end-〉next;while(start〈end){p=start;while(p!=end){p->next一p->next一>data二key;}{key=p->data;p->data二p->next-〉data;p=p->next;}end二end-〉prior;p=end;while(p!=sta