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

江西师范大学计算机科学技术专业09-10第1学期《数据结构》期末考试试题A课程代号：262208注意事项：请将答案全部写到答题纸上，并注明题号！一、填空题（每小题2分，共10分）1.算法有5个基本特征。其中，特征，程序可以不必具备。2.在一个具有n各结点的有序链表中插入一个新结点并保持单链表依然有序的渐近时间复杂度是。3.表达式a+b*(c-d)的后缀表达式为。4.在关键字序列（0，2，4，6，8，10，12，14，16）中，使用折半查找方式查找键值14和15，需要的比较次数分别为和。5.有n个元素的顺序型循环队列，其队首和队尾指针分别为f和r，从队列中删除1个元素，再插入2个元素，其队首和队尾指针分别是和。二、程序填空（每小题10分，共20分）1、下面代码实现对数组a[]的快速排序,L和H是数组a的边界（10分）voidqksort(inta[],intL,intH){inti,j,x;if((1))return;i=L;j=H;x=a[i];while(ij){while((2))j--;if(ij){(3);(4);}while((ij)&&(a[i]=x))i++;if(ij){a[j]=a[i];j--;}}(5);qksort(a,L,j-1);qksort(a,j+1,H);}2、以下代码实现通用的折半检索，L、H刻画在数组a中检索的范围。(10分)BS(int[]a,intkey,intL,intH){intm;if(LH)return-1；m=(6);if(a[m]==key)returnm;}三、综合1.给定堆。若不最小的堆2.给定对应的三3.已知输出序列4.给定7，f，分）a.构b.并5.使用树的过程四、算法1、给定键单链表，typedint}LinkLinkL/*补}2、编写算if(a[mif(a[m解答题（每定关键字序列不是，将其调堆）。（10分定如下所示三元组表示。知某棵二叉树列为：e、f、定如下字母9，g，构造对应的并写出各字用Kruskal程图示（10设计题（每键值按升序并返回新链defstrucd;strukL;L*merge补充完整*算法，返回m]key)m]key)每小题10分列{12，10调整为小根分）的稀疏矩阵。（10分）树的前序遍、b、a、c母，频度组5，h，的Huffman字母的编码。l算法，针分）每小题10分序排列的带头链表的表头ctL{uctL*neList(Li*/回二叉树中序returnreturn分，共计500，13，23根堆（即根阵，写出其遍历输出序列c、g、d；组合：a，113，in树。针对右图画出分，共20分头结点的单头指针。要求next;inkL*h1,序遍历的第(7(8分）3，14，9，列为：a、b画出该树的12，b，，21，出构造最小分）单链表h1和求利用原表,LinkL*第一个结点；););22，33}，b、e、f、的后序二叉3，c，4j，28，小生成和h2，将其表的结点数据*h2){；1501150，首先判断c、d、g；穿线树。（14，d，5解答下列问其合并成升据空间。032100301020032032100301020断其是否是中序遍历10分）6，e，问题：（10升序排列的4310060434310060typedefstructpp{intd;structpp*l,*r;}Btree;Btree*inFirstNode(Btree*t){/*补充完整*/}课程代号注意事项一、填空1.终止5.(r+二、程序(1).L(3).a[(6).(L三、综合1.给定22，33}整为小根答：不是2.给定的三元组{(6,7,8(3,1,-3(4,3,24(6,4,-7注意：建议格式，都标刻画上3.已知江09-10第号：262208项：请将答案题（每小题止性2.+2)%n和(f填空（每小=Hi]=a[j]L+H)/2解答题（每定关键字序，首先判断根堆（即根最是堆。调整后定如下所示组表示。（108),(1,2,3),4),(5,2,7)}议无论是以都可以给满分上述矩阵，也知某棵二叉树江西师范第1学期案全部写到题2分，共.O(n)f+1)%n小题10分，;(7).BS(每小题10分列{12，10断其是否是最小的堆）。后如右图所的稀疏矩阵0分）12),18),以表格格式分。另外，也算做正确树的前序遍大学计算期《数据参考到答题纸上，10分）3.abcd-共20分）(2).(i(4).i++a,key,L,分，共计500，13，23是堆。若不是。（10分）所示。阵，写出其(1,3,(3,6,1(6,1,1，还是以元基于从0确。遍历输出序列算机科学据结构》期考答案，并注明题-*+nij)&&+;,m-1);(分）3，14，9是，将其调其对应,9),14),15),元素对开始的下列为：a、学技术专期末考试题号！4.3和4&(a[j](5).a8).BS(a,，调eee业试试题A=x)a[i]=x;,key,mabfabfabfm+1,H);cdgcdgcdgb、e、f、c、d、g；中序遍历输出序列为：e、f、b、a、c、g、d；画出该树的后序二叉穿线树。（10分）4.给定如下字母，频度组合：a，12，b，3，c，4，d，56，e，7，f，9，g，5，h，13，i，21，j，28，解答下列问题：（10分）a.构造对应的Huffman树b.并写出各字母的编码。a（0001）、b（000000）、c（000001）、d（01）、e（1000）、f（1001）、g（00001）、h（101）、i（001）、j（11）5.使用Kruskal算法，针对右图画出构造最小生成树的过程图示（10分）四、算法设计题（每小题10分，共20分）1、给定键值按升序排列的带头结点的单链表h1和h2，将其合并成升序排列的单链表，并返回新链表的表头指针。要求利用原表的结点数据空间。typedefstructL{intd;structL*next;}LinkL;LinkL*mergeList(LinkL*h1,LinkL*h2){LinkL*h,*tail,*q;h=h1;tail=h;h1=h1-next;h2=h2-next;while(h1!=NULL&&h2!=NULL){if(h1-d=h2-d){q=h1;h1=h1-next;}else{q=h2;h2=h2-next;}04321101005030102060043210432110100503010206004321初始0432111004321210100432131010200432141010203004321初始0432104321初始04321110043210432104321110043212101004321043210432121010043213101020043210432104321043213101020043214101020300432104321043210432104321410102030313556479122138313556479122138tail-next=q;tail=q;}if(h1==NULL)tail-next=h2;elsetail-next=h1;returnh;}2、编写算法，返回二叉树中序遍历的第一个结点；typedefstructpp{intd;structpp*l,*r;}Btree;Btree*inFirstNode(Btree*t){if(bt==NULL)return;p=bt;while(p-L!=NULL)p=p-L;returnp;}江西师范大学计算机科学技术专业09-10第1学期《数据结构》期末考试试题B课程代号：262208注意事项：请将答案全部写到答题纸上，并注明题号！一、填空题（每小题2分，共10分）1.算法有5个基本特征。其中，特征，程序可以不必具备。2.代码段intn=100;while(n1)n=n/10;的渐近时间复杂度是。3.有n个元素的顺序型循环队列，其队首和队尾指针分别为f和r，则该队列中的元素个数有个。4.表达式a+b*(c-d)的前缀表达式为。5.对半带宽为b的带状矩阵（也称2*b+1对角阵），其特点是：对矩阵元素aij，若它满足，则aij=0。二、程序填空（每小题10分，共20分）1、以下代码实现折半检索，L、H刻画在数组a中检索的范围。(10分)BS(int[]a,intkey,intL,intH){intm;if(LH)return-1；m=(1);if(a[m]==key)returnm;if(a[m]key)return(2);if(a[m]key)return(3);}2．下面代码创建前序线索二叉树。（10分）typedefstructbinTreeNode{chard;intltag,rtag;structbinTreeNode*l,*r;}Btree;/*定义线索树结构*/Btree*pre=NULL;/*定义外部变量pre*/voidVisit(Btree*p){/*实现具体线索的创建*/if(p-l==NULL){}voi}三、综合1.依次输二叉排序2.给定应的三元3.已知列为：f、画出该树4.S={数组a[]散列。将数组a5.使用过程图示四、算法1、给定键单链表，p-if(preidcreaTBtree*if(t==L=t-l;Visit(tcreaThrcreaThr解答题（每输入键值{序树。（10分右图所示的元组表示。（知某棵二叉、e、b、g树的后序二叉15，10，中，其中散将下面数组a0用Prim算示（10分）设计题（每键值按升序并返回新链l=pre;!=NULL&(5)ThreadTrL,*R;NULL)reR=t-r;);(eadTree(eadTree(每小题10分12，10，1分）的稀疏矩阵（10分）叉树的后序g、d、c、a叉穿线树。25，23，散列函数为a存储各元12法，针对右每小题10分序排列的带头链表的表头(4&&pre-;pree(Btreeeturn;;6)(L);(R);分，共计503，23，14阵，写出其对遍历输出序a；中序遍（10分）45，35，为H(key)=元素的位置示34右图画出构分，共20分头结点的单头指针。要求);}r==NULL)re-rtag=e*t){/*;分）4，15，17，对序历输出序列17，27，=key%10，示意图填写45构造最小生成分）单链表h1和求利用原表}){=1;}创建线索树27，22，列为：e、f22，33}依冲突处理的写完整。（1067成树的和h2，将其表的结点数据1501150树*/33}，画出f、b、a、依次按散列的方法是线0分）78其合并成降据空间。03211010301020032103211010301020出其对应的c、g、d；列方式存入线性探测再9降序排列的4310060434310060typedefstructL{intd;structL*next;}LinkL;LinkL*mergeList(LinkL*h1,LinkL*h2){/*补充完整*/}2、编写算法，返回二叉树中序遍历的最后一个结点；typedefstructpp{intd;structpp*l,*r;}Btree;Btree*InLastNode(Btree*bt){/*补充完整*/}课程代号注意事项一、填空1.终止4.+a*二、程序(1).(L(4).p-三、综合1.依次输15，17，等于根，对应的二2.给定稀{(6,7,8),(注意：建从0开始3.已知b、g、da、c、g、江09-10第号：262208项：请将答案题（每小题止性/或有穷b-cd5填空（每小L+H)/2-ltag=1解答题（1输入键值{27，22，3右子树大于二叉排序树。稀疏矩阵，(1,2,12),(1,建议无论是以始的下标刻画知某棵