東南大學(xué)十套數(shù)據(jù)結(jié)構(gòu)試題及答案,推薦文檔

數(shù)據(jù)結(jié)構(gòu)試卷（九）參考答案四、算法設(shè)計題1．設(shè)計計算二叉樹中所有結(jié)點值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);}}2．設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]%2==0)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]%2==1)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}3．設(shè)計判斷單鏈表中元素是否是遞增的算法。intisriselk(lklist*head){if(head==0||head->next==0)return(1);elsefor(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)return(0);return(1);}數(shù)據(jù)結(jié)構(gòu)試卷（十）參考答案、填空題1.q->next2.線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu)3.O(n2)，O(n+e)4.8/35.(38，13，27，10，65，76，97)6.(10，13，27，76，65，97，38)7.1246538.structnode*rchild，bt=0，createbitree(bt->lchild)9.lklist，q=p三、算法設(shè)計題1.設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->data<hb->data){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}2.設(shè)計在二叉排序樹上查找結(jié)點X的算法。bitree*bstsearch1(bitree*t,intkey){bitree*p=t;while(p!=0)if(p->key==key)return(p);elseif(p->key>key)p=p->lchild;elsep=p->rchild;return(0);}設(shè)關(guān)鍵字序列%,k2,…，kni)是堆，設(shè)計算法將關(guān)鍵字序列%,k2,…，kni,x)調(diào)i2n-ii2n-i整為堆。voidadjustheap(intr[],intn){intj=n,i=j/2,temp=r[j-i];while(i>=i)i