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

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

ID:11158501

大小:122.50 KB

页数:6页

时间:2018-07-10

2006-2007第一学期数据结构期末试卷c答案_第1页
2006-2007第一学期数据结构期末试卷c答案_第2页
2006-2007第一学期数据结构期末试卷c答案_第3页
2006-2007第一学期数据结构期末试卷c答案_第4页
2006-2007第一学期数据结构期末试卷c答案_第5页
资源描述:

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

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的结点其右子树中所有的结点值____(少于/大于/小于等于/大于等于)

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

6、,7,2,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)popth

7、eelementfromthestackst.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)finishtheimplementationtocreatatreetypedef

8、structnode{chardata;structnode*lc

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。