《数据结构期末复习题2.doc》由会员分享，可在线阅读，更多相关《数据结构期末复习题2.doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、温习题2一、选择题1.下述次序段中语句的频度是。s=0;for(i=1;im;i+)for(j=0;jnext=p-next；p-next=s；p-next-prior=s；s-prior=p；B.p-next=s；s-next=p-next；p-next-prior=s；s-prior=p；C.s-next=p-next；s-prior=p;p-next-prior=s；p-next=s；D.p-next-prior=s；p-next=s；s-next=p-next；s-prior=p；3.设栈的初始形态为空，元素1、2、3、4、5、6顺次入栈，失掉的出栈序列是2,4,3,6,5,1,那么栈
2、的容量至多是。A2B3C4D64.曾经明白二维数组A610，每个数组元素占4个存储单位，假定按行优先次序寄存数组元素a35的存储地点是1000，假定a00是该数组的首元素，那么a00的存储地点是。A860B864C868D8725.一棵完整二叉树中有128个叶子节点，那么该树起码有个结点。A.255B.254C.253D.2566.曾经明白二叉树的前序遍历序列是abdgcefh，中序遍历序列是dgbaechf，它的后序遍历序列是。AbdgcefhaB.gdbehfcaCbdgechfaDgdbecfha7.对以以下列图进展拓扑排序，准确的拓扑序列是。Av1，v2，v3，v4，v5，v6，v7B
3、v1，v2，v4，v3，v6，v5，v7Cv1，v2，v4，v3，v5，v7，v6Dv1，v2，v3，v4，v5，v6，v78、对记载序列(314，298，508，123，486，145)顺次按个位跟十位进展两趟基数排序之后所得后果为_。A314，298，508，123，486，145B123，314，145，486，298，508C123，145，298，314，486，586D508，314，123，145，486，2989.以下二叉树中，不均衡的二叉树是。10、在给出的四棵二叉树中，只要()满意一个小顶堆的外形。二、填空题1.在如以下列图的链表中，假定在指针p所指的结点之后拔出数据域值接
4、踵为a跟b的两个结点，那么可用以下两个语句完成该操纵，它们顺次是_跟_。2.曾经明白狭义表C=(a，b)，(c，(d，(e)，f)，那么：tail(tail(head(C)=_。3.运用一个20个元素的数组存储轮回行列，假如采用罕用一个元素空间的办法来区不轮回行列的队空跟队满，商定队头指针front即是队尾指针rear时表现队空。假定为front=5，rear=18，那么行列中的元素个数为_；假如行列中拔出2个元素，那么rear的值为。4.设有下三角矩阵A=8 0004200657013911紧缩存储到一维数组Fm中，m为数组长度，0元素不存储，那么m为，a00是二维数组首元素，元素a32按行
5、优先次序寄存到Fk2中，k2值为。5.对长度为31的有序次序表进展二分查寻，在各记载的查寻概率均相称的状况下，查寻胜利时所需进展的要害字比拟次数的均匀值为_，查寻第10个元素需求比拟次数为。三、运用题1、设形式串t=abaabacababa，试求出t的next跟nextval函数值。2由字符集s，t，a，e，i及其在电文中呈现的频度构建的哈夫曼树如以下列图。曾经明白某段电文的哈夫曼编码为101100000111，请依照该哈夫曼树进展译码，写出本来的电文。3.设散列长度为9，散列函数为H(k)=kmod9，给出要害字序列：23，45，14，17，9，29，37，18，25，41，33，采纳链地点
6、法处理抵触。(1)请画出散列表；(2)盘算在等概率状况下，查寻胜利的均匀查寻长度。4、应用Dijkstra算法，求图中极点V0到别的各极点的最短途径，写出求解进程。V0C10100V4V1B3050106020V3V25、曾经明白3阶B-树如以下列图。曾经明白3阶B-树如以下列图，画出将要害字10、78、110、120顺次拔出之后的B-树。四、次序浏览题1.以下函数的功用是，将两个递增有序单链表La跟Lb进展兼并，请求兼并之后的新单链表不反复的元素同时递增有序。请在以下算法LinkMerge空白处填入适宜内容，使其成为一个完好的算法。voidLinkMerge(LinkListLa,LinkL
7、istLb，LinkList&pc)/本算法的功用是将一切Lb表中存在而La表中不存在的结点拔出到La表中LinkListq;LinkListpa=La-next;LinkListpb=Lb-next;free(Lb);while(pa&pb)if(pa-datadata)(1);pc=pa;pa=pa-next;elseif(pa-datapb-data)pc-next=pb;pc=pb;elsepc-next=pa;pc=pa;pa=pa-next;q=pb;pb=pb-next;(3);if(pa)pc-next=pa;if(pb)(4);2、二叉树采纳二叉链表存储如右图所示：浏览以下算
8、法,并答复以下咨询题：voidSwapBinTreeTBinTrees;ifTs=T-lchild；T-lchild=T-rchild;T-rchild=s；SwapT-lchild；SwapT-rchild；假定用Swap函数履行右图的二叉树，写出履行之后的二叉树。3、以下算法实如今二叉排序树拔出一个结点key，在算法空白地位填写恰当的内容使算法完好。BinTreeInsert(BinTreet,intkey)BinTreep=t;BinTrees,f;while(p!=NULL)f=p;if(key=p-key)returnt;if(1)p=p-lchild;elsep=p-rchild;
9、s=(2);s-key=key;s-lchild=NULL;s-rchild=NULL;if(t=NULL)returns;/新节点为二叉排序树的根if(keykey)(3);elsef-rchild=s;returnt;4.对以下函数填空，完成以带头结点的单链表h为存储构造的直截了当选择排序。voidSelectSort(LinkListh)LinkListp，q，m；inttemp；p=h-next；while(p!=NULL)q=p-next；m=p；while(q!=NULL)if(m-keyq-key)；if(p!=m)temp=p-key；p-key=m-key；m-key=temp；五、编程题1、 给出一个带表头的单链表L，L的每个结点中寄存一个整数。现给定一个阈值K，将L分红两三个子表L1、L2跟L3，此中L1中寄存L中一切要害字值年夜于K的结点，L2中寄存L中一切要害字值即是K的结点，L3中寄存L中一切要害字值小于K的结点。试编程完成那个进程。2、编写算法：采纳非递归算法求二叉树的深度。