数据结构综合练习题参考答案[1]

《数据结构综合练习题参考答案[1]》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构参考答案一、选择题1.A2．B3．B4．B5．B6．D7.A8．D9．D10．C11．B12．D13.D14.C15.A16.B17.C18.D19.C20.C21.B22.D二、填空题1.4，102.O(nlog2n)，O(n2)3.n4.1，25.n+16.q->next7.线性结构，树型结构，图型结构7.8.O(n2)，O(n+e)9.8/310.(38，13，27，10，65，76，97)11.(10，13，27，76，65，97，38)12.12465313.structnode*rchil

2、d，bt=0，createbitree(bt->lchild)14.lklist，q=p15.19/716.817.6,818.head->rlink,p->link19.020.I

3、SqList&L,intlow,inthigh){//交换顺序表L中子表r[low.high]的记录，枢轴记录到位，//并返回其所在的位置，此时在它之前(后)的记录均不大(小)//于它。L·r[0]=L·r[low]pivotkey=L.r[low].key；while(low=pivotkey)－－high；L·r[low]=L·r[high]While(low

4、·r[high]=L·r[low]}L·r[low]=L·r[0]Returnlow；}//Partition2．voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->datadata){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;};h

5、b=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}3．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);}4.intisriselk(linklist*head){if(head==0

6、

7、head->next==0)return(1);els

8、efor(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)return(0);return(1);}5．statusHuiwen(SqstackS,LinkQueueQ){Charch,eh;ch=getchar();while(ch!=”@”){Push(Spush(s"; en(SqstackS,LinkQueueQ)

9、,ch);Enqueue(Q,ch);ch=getchar();}TF=.TRUE.while(!StackEmpty(S)&&TF){eh=Pop(S);Dequeue(Q,ch);if(eh!ch)TF=.TRUR.;}returnTF;}//Huiwen6．StatusListDelete_Sq(SqList&L,inti,ElemType&e){if((i<1)

10、

11、(i>L.length))returnERROR；p=&(L.elem[i－1])；e=

12、*p；q=L.elem+L.length－1；for(++p；p<=q；++p)*(p－1)=*p；－－L.length；returnOK；}//ListDelete_Sq四、应用题1.WPL=78。哈夫曼树图如下：35152087911352.二叉排序树构造过程如下：空集45454545808080484840（1）（2）（3）（4）（5）4580484022（6）3、1234FEBDAC2683