《数据结构》期末考试试题及答案

《数据结构》期末考试试题及答案(2003-2004学年第2学期)单项选择题1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C一、1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（c）。(A)、正确性(B).可行性(C).健壮性(D).输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d）。for(i=n-1；i=0；i--)for(j=0；ji；j++)S；(A)、n2(B).O(nlgn)(C).O(n)(D).O(n2)3．折半查找法适用于（a）。（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（d）。（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（c）层上。（A）、k-1（B）、k（C）、k-1和k（D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11（B）、13（C）、48（D）、377．图的Depth-FirstSearch(DFS)遍历思想实际上是二叉树（a）遍历方法的推广。（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（ab）Q（A）、p=Q.front-next;p-next=Q.front-next;（B）、p=Q.front-next;Q.front-next=p-next;（C）、p=Q.rear-next;p-next=Q.rear-next;（D）、p=Q-next;Q-next=p-next;9．Huffman树的带权路径长度WPL等于（c）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值bcd∧afrontrear10．线索二叉链表是利用（c）域存储后继结点的地址。（A）、lchild（B）、data（C）、rchild（D）、root二、填空题1．逻辑结构决定了算法的设计，而存储结构决定了算法的实现。2．栈和队列都是一种特殊的线性表，栈的插入和删除只能在栈顶进行。3．线性表（a1,a2,…,an）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOC(ai)为4．已知一双向链表如下(指针域名为next和prior)：qp现将p所指的结点插入到x和y结点之间，其操作步骤为：；；；；5．n个结点无向完全图的的边数为，n个结点的生成树的边数为。6．已知一有向无环图如下：任意写出二种拓扑排序序列：、。7．已知二叉树的中序遍历序列为BCA，后序遍历序列为CBA，则该二叉树的先序遍历序列为，层序遍历序列为。三、应用题1．设散列函数H(k)=k%13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲突。(6分)(1)构造HASH表。(2)分别求查找成功和不成功时的平均查找长度。xyeBACDFEG2．给定表（19,14,22,15,20,21,56,10）.（8分）（1）按元素在表中的次序，建立一棵二叉排序树（2）对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。（3）画出对(2)中的遍历序列进行折半查找过程的判定树。3．已知二个稀疏矩阵A和B的压缩存储三元组表如下：ABijVijV13-525224633725241342-152-9529558写出A-B压缩存储的三元组表。（5分）4．已知一维数组中的数据为（18,12,25,53,18）,试写出插入排序（升序）过程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分)5．已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(8分，要有过程)ABCDEF（1）求从顶点A开始的最小生成树。（2）分别画出以A为起点的DFS生成树和BFS生成树。6．已知数据六个字母及在通信中出现频率如下表：ABCDEF0.150.150.10.10.20.3把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。（1）画出对应的Huffman树。64266346751275356156FEDCBA（2）计算带权路径长度WPL。（3）求A、B、C、D、E、F的Huffman编码。7．已知有如下的有向网：求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分）三、设计题（30分，每题10分,用C语言写出算法，做在答题纸上）1．已知线性表（a1,a2,…,an）以顺序存储结构为存储结构，其类型定义如下：#defineLIST_INIT_SIZE100//顺序表初始分配容量typedefstruct{Elemtype*elem;//顺序存储空间基址intlength;//当前长度（存储元素个数）}SqList;设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下：StatusListDelete(Sqlist&L,Elemtypex){……}2．设顺序栈如左图所示。其中结点定义如下：toptypedefstruct{Elemtype*base;//栈底指针Elemtype*top;//栈顶指针}Stack;设计算法，将栈顶元素出栈并存入e中．base3．设二叉链树的类型定义如下：typedefintElemtype;typedefstructnode{Elemtypedata;25364106122ABCDEan…a2a1structnode*lchild,*rchild;}BinNode,*BinTree;试写出求该二叉树叶子结点数的算法:StatusCountLeaves(BinTree&root,int&n){//nisthenumberofleaves……}答案：选择题（每题1分）1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C一、填空题1．设计、实现2．特殊、栈顶3．LOC（a1）+(i-1)*L4．p-next=q-next;q-next-prior=p;q-next=p;p-prior=q;5．n(n-1)/2、n-16．ADCBFEG、ABCDEFFG7．ABC、ABC二、应用题1（1）Hash表（4分）地址0123456789101112关键安132164572282412探测次数171231311（2）查找成功的平均查找长度：（1分）（5*1+1*2+2*3+1*7）/9=20/9查找不成功的平均查找长度：（1分）（2+1+9+8+7+6+5+4+3+2+1）/13=2（1）、构造（3分）(2)、1014151920212256（2分）（3）、（3分）19142210152056213、(5分，每行0.5)ijv13-524633741342-152185584、初始关键字：[18]12255318第一趟：[1218]255318第二趟：[121825]5318第三趟：[12182553]18第四趟：[1218182553]（4分）O（n2）（1分）。5、7分（1）4分（2）4分6、(1)3分AB1C325D4EFEFABCD（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21=(1分)（3）A：010B：011C：110D：111E：00F；10（3分）12、A-B：（A、B）1分A-C：（A、D、C）2分A-D：（A、D）1分A-E：（A、D、E）2分三，设计题（20分）1、(10分)StatusListDelete(Sqlist&L,ElemTypex){inti,j;for(i=0;iL-length;i++)if(L-elem[i]==x)break;if(i=L-length)returnERROR;for(j=i;jL-lengthi-1;j++)L-elem[j]=L-elem[j+1];L-length--;}（8分）平均时间复杂度：（2分）设元素个数记为n，则平均时间复杂度为：nininnE121)(12（10分）voidpop(Stack&S,Elemtype&e){if(S.top==S.base)returnERROR;S.top--;e=*s.top;}2、（10分）voidCountLeaves(BinTreeT,int&n){if(T){if((!(T-lchild)&&!(T-rchild))n++;CountLeaves(T-lchild,n);CountLeaves(T-rchild,n);}}人生中每一次对自己心灵的释惑，都是一种修行，都是一种成长。相信生命中的每一次磨砺，都会让自己的人生折射出异常的光芒，都会让自己的身心焕发出不一样的香味。我们常常用人生中的一些痛，换得人生的一份成熟与成长，用一些不可避免的遗憾，换取生命的一份美丽。在大风大雨，大风大浪，大悲大喜之后，沉淀出一份人生的淡然与淡泊，静好与安宁，深邃与宽厚，慈悲与欣然……生活里的每个人，都是我们的一面镜子，你给别人什么，别人就会回待你什么。当你为一件事情不悦的时候，应该想想你给过人家怎样负面的情绪。世界上的幸福，没有一处不是来自用心经营和珍惜。当你一味的去挑剔指责别人的时候，有没有反思过自己是否做得尽善尽美呢？假如你的心太过自我，不懂得经营和善待，不懂得尊重他人的感受，那么你永远也不会获得真正的爱和幸福……人生就像一场旅行，我们所行走的每一步都是在丰富生命的意义。我们一边穿越在陌生的吸引里，一边咀嚼回味着一抹远走光阴的旧味，一切都是不可预料，一切又似在预料之中。人生看的多了，走的多了，经历的多了，也就懂得多了。每一份深刻的感悟大多来自一个人深刻的经历。人生总有那么一两件重大的事情让你成熟和改变。这份错失，会让你反思自己，检讨自己，叩问自己，也让你意识到了自己真正的缺失，这或许就是一份痛苦的领悟吧！人生可以平平淡淡，亦可以异彩纷呈。相信只要自己的德馨足够善美，上天就会把最好的一切赐予你。予人快乐，收获快乐；予人幸福，收获幸福；予人真情，收获厚意。人生的一切往来皆有因果，生活只善待有心人……假如你有一颗计较的心，你就会很难获得一份幸福。当一个人放下了自己内心的那份累心的奢求，你的心空就会变得更加蔚蓝干净。宽容，不仅是一种豁达的态度，更是一种心灵的品德，是一种处事的修行，宽容别人不是低矮了自己，而是释放了自己，升华了自己。你把世界宽待在心中，世界也同样装饰了你的一份美丽。当你简约、释然了自己的时候，你会发现另一份生命中的快乐。那快乐是发自一颗简单的心，那快乐是从心灵的草地里欢快的迸发出来，通过你温柔的眼眸和开心的笑声来传递。所以，心宽便心悦，你人生的天空是什么颜色，往往取决于你对人生的态度和对于自己情绪的驾驭……世界上美好的东西那么多，有缘来到你的身旁，被你握到掌心的却又那么少。所以一切在的时候请学会珍惜，因为大多美丽的东西只会为你来过一次。你一不小心就会失落，无处找寻，增加了你人生的又一次遗憾……过往，终是回不去的曾经。人总是在失去的时候才懂得珍惜，人总是在回味的时候才知道甜美。往事已矣，该放下的终归要放下，该忘记的一定要学会忘记。其实这个世界上什么都不是我们的，在人间，我们只是一场心灵的路过而已……或许唯一属于过我们的，只是生命刹那的快乐与悲伤，以及自己一颗思索的灵魂……站在时光的路口回望曾经，盘点每一份经历过的心情，人生有太多得不到的美好，有太多想不到的结局。终有一天，我们热望过的，贪念过的，彷徨过的，握紧过的，放手过的，都将化作尘埃随风飞去……人生渺如尘埃，小如露珠，寻常如泥土，从不可知处而来，到不可知处而去。我们用灵魂结伴身体，走过这短暂的一朝一夕的寒暖，踏过流年的坎坷与花香，便是在世间真正的来过了。