数据结构期末考试试题及答案.pdf
《数据结构期末考试试题及答案.pdf》由会员分享，可在线阅读，更多相关《数据结构期末考试试题及答案.pdf（12页珍藏版）》请在冰点文库上搜索。
江西师范大学计算机科学技术专业09-10第1学期数据结构期末考试试题A江西师范大学计算机科学技术专业09-10第1学期数据结构期末考试试题A课程代号：
262208注意事项：
请将答案全部写到答题纸上，并注明题号！
一、填空题（每小题2分，共10分）一、填空题（每小题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分）二、程序填空（每小题10分，共20分）1、下面代码实现对数组a的快速排序,L和H是数组a的边界（10分）voidqksort（inta,intL,intH）inti,j,x;if
（1）return;i=L;j=H;x=ai;while（ij）while
（2）j-;if（ij）（3）;（4）;while（ij）&（ai=x）i+;if（iH）return-1；m=（6）;if（am=key）returnm;三、综合三、综合1.给定堆。
若不最小的堆2.给定对应的三3.已知输出序列4.给定7，f，分）a.构b.并5.使用树的过程四、算法四、算法1、给定键单链表，typedintLinkLinkL/*补补2、编写算if（amif（am解答题（解答题（每每定关键字序列不是，将其调堆）。
（10分定如下所示三元组表示。
知某棵二叉树列为：
e、f、定如下，key）m组5，h，的Huffman字母的编码。
l算法，针分）每每小题小题10分分序序排列的带头链表的表头ctLuctL*neList（Li*/回二叉树中序returnreturn分分，共计50，共计500，13，23根堆（即根阵，写出其遍历输出序列c、g、d；组合：
，小生成和h2，将其表的结点数据*h2）；1501150，首先判断c、d、g；穿线树。
（4，（3）.a（6）.（L三、综合三、综合1.给定22，33整为小根答：
不是2.给定的三元组（6,7,8（3,1,-3（4,3,24（6,4,-7注意：
建议格式，都标刻画上3.已知江江09-1009-10第第号：
262208项：
请将答案题（每小题（每小题题止性2+2）%n和（f填空（每填空（每小小=Hi=ajL+H）/2解答题（解答题（每每定关键字序，首先判断根堆（即根最是堆。
调整后定如下所示组表示。
（108）,（1,2,3）,4）,（5,2,7）议无论是以都可以给满分上述矩阵，也知某棵二叉树江江西师范西师范第第11学期学期案全部写到题题2分，共2分，共.O（n）f+1）%n小小题10分，题10分，;（7）.BS（每每小题10小题10分分列12，10断其是否是最小的堆）。
后如右图所的稀疏矩阵0分）12）,18）,以表格格式分。
另外，也算做正确树的前序遍大学计大学计算算期期数据数据参考参考到答题纸上，10分）10分）3.abcd-共20分）共20分）
（2）.（i（4）.i+a,key,L,分分，共计50，共计500，13，23是堆。
若不是。
（10分）所示。
阵，写出其（1,3,（3,6,1（6,1,1，还是以元基于从0确。
遍历输出序列算算机科机科学学据结构据结构期期考答案考答案，并注明题-*+ni=x）ai=x;,key,mabfabfabfm+1,H）;cdgcdgcdgb、e、f、c、d、g；中序遍历输出序列为：
e、f、b、a、c、g、d；画出该树的后序二叉穿线树。
（10分）4.给定如下组合：
，解答下列问题：
（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，将其合并成升序升序排列的单链表，并返回新链表的表头指针。
要求利用原表的结点数据空间。
typedefstructLintd;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-dd）q=h1;h1=h1-next;elseq=h2;h2=h2-next;04321101005030102060043210432110100503010206004321初始初始0432111004321210100432131010200432141010203004321初始初始0432104321初始初始04321110043210432104321110043212101004321043210432121010043213101020043210432104321043213101020043214101020300432104321043210432104321410102030313556479122138313556479122138tail-next=q;tail=q;if（h1=NULL）tail-next=h2;elsetail-next=h1;returnh;2、编写算法，返回二叉树中序遍历的第一个结点；typedefstructppintd;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江西师范大学计算机科学技术专业09-10第1学期数据结构期末考试试题B课程代号：
262208注意事项：
请将答案全部写到答题纸上，并注明题号！
一、填空题（每小题2分，共10分）一、填空题（每小题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分）二、程序填空（每小题10分，共20分）1、以下代码实现折半检索，L、H刻画在数组a中检索的范围。
（10分）BS（inta,intkey,intL,intH）intm;if（LH）return-1；m=
（1）;if（am=key）returnm;if（amkey）return
（2）;if（aml=NULL）vo三、综合三、综合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小题10分分12，10，1分）的稀疏矩阵（10分）叉树的后序g、d、c、a叉穿线树。
25，23，散列函数为a存储各元12法，针对右每每小题10小题10分分序序排列的带头链表的表头（4&pre-;pree（Btreeeturn;6）（L）;（R）;分分，共计50，共计503，23，14阵，写出其对遍历输出序a；中序遍（10分）45，35，为H（key）=元素的位置示34右图画出构分分，共20，共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降降序序排列的4310060434310060typedefstructLintd;structL*next;LinkL;LinkL*mergeList（LinkL*h1,LinkL*h2）/*补充完整补充完整*/2、编写算法，返回二叉树中序遍历的最后一个结点；typedefstructppintd;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-1009-10第第号：
262208项：
请将答案题（每小题（每小题题止性/或有穷b-cd5填空（每填空（每小小L+H）/2-ltag=1解答题（1解答题（1输入键值27，22，3右子树大于二叉排序树。
稀疏矩阵，（1,2,12）,（1,建议无论是以始的下标刻画知某棵二叉树d、c、a；中、d；画出该江江西师范西师范第第11学期学期案全部写到题题2分，共2分，共穷性5.|i-j|小小题10分，题10分，
（2）.BS（;（5-2题每-2题每题题12，10，133，按照左于根的规则。
（10分）写出其对应,3,9）,（3,1,-3以表格格式画上述矩阵树的后序遍中序遍历输该树的后序大学计大学计算算期期数据数据参考参考到答题纸上，10分）10分）2.O（lo|b共20分）共20分）a,key,L,5）.pre-题题5分，35分，3-，23，14，左子树小于则，画出其应的三元组3）,（3,6,14）,式，还是以元阵，也算做正遍历输出序列输出序列为序二叉穿线树算算机科机科学学据结构据结构期期考答案考答案，并注明题ogn）3.,m-1）;（-r=p;（6-5每题15每题100组表示。
（1,（4,3,24）,（5元素对格式正确。
列为：
f、e：
e、f、b树。
（10分学学技术专技术专期末考试期末考试题号！
（r+n-f）3）.BS（a,6）.pre=00分，共计分，共计0分）5,2,18）,（6式，都可以给、b、）eee业业试试题试试题BB%n,key,m=t;40分）40分）6,1,15）,（6给满分。
另abfeabfeabfem+1,H）;6,4,-7）另外，基于cdgcdgcdg4.S=15，10，25，23，45，35，17，27，22，33依次按散列方式存入数组a中，其中散列函数为H（key）=key%10，冲突处理的方法是线性探测再散列。
将下面数组a存储各元素的位置示意图填写完整。
（10分）0123456789数组a102722233315254535175.使用Prim算法，针对右图画出构造最小生成树的过程图示（10分）四、算法设计题（每小题10分，共20分）四、算法设计题（每小题10分，共20分）1、给定键值按升序升序排列的带头结点的单链表h1和h2，将其合并成降序降序排列的单链表，并返回新链表的表头指针。
要求利用原表的结点数据空间。
typedefstructLintd;structL*next;LinkL;LinkL*mergeList（LinkL*h1,LinkL*h2）LinkL*h,*q;h=h1;h1=h1-next;h2=h2-next;h-next=NULL;while（h1!
=NULL&h2!
=NULL）if（h1-dd）q=h1;h1=h1-next;elseq=h2;h2=h2-next;q-next=h-next;h-next=q;while（h1!
=NULL）q=h1;h1=h1-next;q-next=h-next;h-next=q;while（h2!
=NULL）q=h2;h2=h2-next;q-next=h-next;h-next=q;returnh;04321101005030102060043210432110100503010206004321初始初始0432111004321410102030043212103004321310203004321初始初始04321初始初始043211100432104321043211100432141010203004321043210432104321043214101020300432121030043210432121030043213102030043210432131020302、编写算法，返回二叉树中序遍历的最后一个结点；typedefstructppintd;structpp*l,*r;Btree;Btree*InLastNode（Btree*bt）Btree*p;if（bt=NULL）return;p=bt;while（p-R!
=NULL）p=p-R;returnp;
升级会员 