2006-2007第一学期数据结构期末试卷c答案.doc

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

1、试卷编号：(c)卷课程编号：X61010508课程名称：数据结构考试形式：闭卷适用班级：自动化04级姓名：学号：班级：学院：信息工程学院专业：自动化考试日期：题号一二三四五六七八九十总分累分人签名题分223012100得分考生注意事项：1、本试卷共7页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、填空题(每空2分，共22分)得分评阅人1.1)bcis(are)thetreedatastructures.(树形结构)2)ais(are)thegraphdatastructures(图形结构

2、)3)dis(are)lineardatastructures(线性结构abcd(d)gbccvid(b)(c)zvbccnmmdcv(a)2.accordingthefollowingfigures,ecis(are)thecompletetrees(完全二叉树)南昌大学2006～2007学年第一学期期末考试试卷第6页共6页edis(are)thefulltrees(满二叉树).(b)ca(c)(a)(e)c(d)eadfbcFig13.fig.1isanexamplebinarytree.Nodedef_areleaves(叶子).Thedepth(深度

3、)ofeis2_________.Theheightofthistreeis(这棵树的高度是)3____.4.thebinarysearchtreeproperty:allnodestoredintherightsubtreeofanodewhosekeyvalueisKhavekeyvaluesgraterthanorequalto__(lessthan/graterthan/lessthanorequalto/graterthanorequalto)K.(二叉查找树的性质:值为K的结点其右子树中所有的结点值____(少于/大于/小于等于/大于等于)K)5

4、.Therearetwostandardapproachestoimplementinglists:thearray-basedlist,andthelinkedlist.二、简答题（共30分）得分评阅人1．DetermineO(.)forthefollowingcodefragmentsintheworstcase.(计算时间复杂度)。(8’)1)k=1;m=0;while(k+m<=n){if(k>m)m++;O(n)elsek++;}2)s=0;第6页共6页for(j=1;j<=n;j*=2)for(k=1;k

5、)CDEcHKGFI2.Thepreorderenumerationforthebinarytree(一棵二叉树的先序遍历是)isCDFHEKGI,Andthepostorderenumerationforthetreeis(它的后序遍历是)HFDKIGEC_.(6’)3.ifvaluesareinsertedintheorder120,42,42,7,2,5,37,24,40.drawtheBinarySearchTreesforthecollectionofvalues.(8’)1204237c274240524(依次插入结点120,42,42,7,2,

6、5,37,24,40,画出所形成的二叉查找树)271611c5678331200000111114.buildtheHuffmantreeforthemessage“PPAMBCMCCMCPMPPMMMFPMABBCP”anddeterminetheHuffmancodes.(8对电文“PPAMBCMCCMCPMPPMMMFPMABBCP”，设计赫夫曼编码（画出构造的赫夫曼树）F1A2B3C5P7M8（2分）4分F:1110A:1111B:110C:10P:00M:01（2分）第6页共6页三.程序填空(每空2分,共12分)得分评阅人a)poptheeleme

7、ntfromthestackst.structstnode{intdata;structstnode*next;};typedefstructstnodestacknode;typedefstacknode*linkedstack;intstackpop(linkedstack*st){intx;if(st->top==-1){printf("empty");exit(0);}x=st->data[st->top];st->top--;returnx;}b)finishtheimplementationtocreatatreetypedefstructn

8、ode{chardata;structnode*lc