2005-2006第一学期数据结构卷12026b答案

《2005-2006第一学期数据结构卷12026b答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南昌大学2005～2006学年第1学期期末考试试卷试卷编号：12026(B)卷课程名称：数据结构适用班级：自动化03级姓名：学号：班级：专业：学院：系别：考试日期：题号一二三四五六七八九十总分累分人签名题分100得分一、填空题(每空2分，共18分)得分评阅人1.1)acis(are)thetreedatastructures.(树形结构)2)bis(are)thegraphdatastructures(图形结构)3)dis(are)lineardatastructures(线性结构)adcb(d)Abccdgef(a)abdefacb(b)(c)2.accordingth

2、efollowingfigures,acfis(are)thecompletetrees(完全二叉树)abfis(are)thefulltrees(满二叉树).第7页共7页(a)abccdefg(b)(c)(e)(f)(d)3.fig.1isanexamplebinarytree.Nodedghi___________areleaves(叶子).Thedepth(深度)ofeis2_________.Theheightofthistreeis(这棵树的高度是)4_____.fig(1)4.thebinarysearchtreeproperty:allnodestoredi

3、ntheleftsubtreeofanodewhosekeyvalueisKhavekeyvalues__lessthan_____(lessthan/graterthan/lessthanorequalto/graterthanorequalto)K.二、简答题（共46分）得分评阅人1．DetermineO(.)forthefollowingcodefragmentsintheworstcase.(计算时间复杂度)。(每小题4分共8分)I=1;j=0;while(I+j<=n){if(I>j)j++;O(n)elseI++;}第7页共7页(b)intlow,mid,hi

4、gh;low=0;high=N-1;while(low<=high){mid=(low+high)/2;if(a[mid]x)high=mid-1;elsereturnmid;}returnNOTFOUND;O(log2n)2.finishthefollowingimplementation.(18’)(程序填空，每空2分)a)Assumethequeueiscircularqueue.inqueuefunctiontypedefstruct{intdata[MAXSIZE];intfront,rear;}sequeu

5、e;sequeuesquein(sequeueQ,intx){if(Q.rear+1%MAXSIZE==Q.front){printf("full");exit(0);}Q.rear=(Q.rear+1)%MAXSIZE;Q.data[Q.rear]=x;returnQ;}第7页共7页b)deletetheithelementofthelinkedlist.voidlistdel(linkedlistL,inti){linkedlistp,q;intj;p=L;j=1;while(p->next&&jnext;j++;}if(p->next==NUL

6、L

7、

8、j>i){printf("positionerror");exit(0);}q=p->next;p->next=q->next;free(q);}c)insertsort(assumearraya[]containsnvalues).voidinssort(inta[],intn){intj,p,tmp;for(p=1;ptmp;j--)________________a[j]=a[j-1];________________a[j]=tmp;}}3.Thepreorderenumerationfor

9、thebinarytree(一棵二叉树的先序遍历是)isABCDEFGH,Andtheinorderenumerationforthetreeis(它的中序遍历是)CBEDAGHF.Drawthetreeandthepostorderenumerationforthetreeis_______CEDBHGFA__(3分)_____.(8’)(画出这棵树并写出它的后序遍历)AFcB5分CDGEH第7页共7页4.ifvaluesareinsertedintheorder120,42,42,7,2,32,37,24,40.drawt