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

数据结构参考答案一、 选择题1. A2B3B4B5B6D7. A8D9D10C11B12D13. D 14. C 15.A 16.B 17.C 18.D 19. C 20.C 21.B 22.D二、填空题1. 4，10 2.O(nlog2n)，O(n2) 3.n 4.1，2 5. n+16. q-next 7.线性结构，树型结构，图型结构 7. 8.O(n2)， O(n+e) 9.8/3 10. (38，13，27，10，65，76，97)11. (10，13，27，76，65，97，38) 12. 12465313. struct node *rchild，bt=0，createbitree(bt-lchild)14. lklist，q=p15. 19/7 16. 8 17. 6 , 8 18. head-rlink, p-link 19. 020. Ij&rI.keyx.key , rI=x 21. O(n)22 线性结构，树型结构，图型结构 23（16，20，25，35，38，42，80）24 O（n2） 25k1；k2，k4，k5， k7；2，3；4；k5，k6； k126 A，D，B，C三、算法设计题1、/设枢轴记录的关键字为pivotkeyint Partition (SqList &L,int low,int high) /交换顺序表L中子表rlow.high的记录，枢轴记录到位， /并返回其所在的位置，此时在它之前(后)的记录均不大(小) /于它。 Lr0=Lrlow pivotkey=L.rlow.key； while (lowhigh) while (low=pivotkey) high； Lrlow=Lrhigh While (lowhigh &L.rlow.keydatadata)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; else s-next=ha;3 bitree *bstsearch1(bitree *t, int key) bitree *p=t; while(p!=0) if (p-key=key) return(p);else if (p-keykey)p=p-lchild; else p=p-rchild; return(0);4. int isriselk(linklist *head)if(head=0|head-next=0) return(1);else for(q=head,p=head-next; p!=0; q=p,p=p-next) if(q-datap-data) return(0);return(1);5status Huiwen(Sqstack S, LinkQueue Q)Char ch,eh;ch=getchar();while(ch!=”) Push(Spush(s;en(Sqstack S, LinkQueue Q),ch); Enqueue(Q,ch);ch=getchar();TF=.TRUE.while(!StackEmpty(S) & TF) eh=Pop(S); Dequeue(Q,ch); if(eh!ch) TF=.TRUR.; return TF;/Huiwen6Status ListDelete_Sq(SqList &L,int i,ElemType &e) if (iL.length) return ERROR； p=&(L.elemi1)； e=*p； q=L.elem+L.length1； for (+p；p=q；+p) * (p1)=*p； L.length； return OK；/ListDelete_Sq四、应用题1. WPL=78。哈夫曼树图如下： 35 15 20 8 7 9 11 3 5 2. 二叉排序树构造过程如下：空集 45 45 45 45 80 80 80 48 48 40（1） （2） （3） （4） （5） 45 80 48 40 22（6）3、1234FEBDAC268345fromvexAEAECEndvexEDCBFweight23468图d 图e4、第四趟简单选择排序结果：22, 40, 45, 48, 80, 78第四趟直接插入排序结果：(40, 45, 48, 80, 22, 78)5、（1） 26 38 47 59 24 80 37 62 15 46 （2）