数据结构练习题含答案_第1页
数据结构练习题含答案_第2页
数据结构练习题含答案_第3页
数据结构练习题含答案_第4页
数据结构练习题含答案_第5页
免费预览已结束,剩余15页可下载查看

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、数据结构练习题习题1绪论1.1单项选择题1.数据结构是一门研究非数值计算的程序设计问题中的运算等的课程.,数据元素的、数据信息在计算机中的以及一组相关2.合.3.4.5.1.2A.操作对象A.存储结构B.计算方法B.关系逻辑结构运算数据Z构DS(DataStruct)可以被形式地定义为DS=D,D.数据映象D.算法R,其中D是的有限集合,R是D上的有限集A.算法A.操作数据元素映象C.数据操作C.存储D.数据对象D.关系在数据结构中,从逻辑上可以把数据结构分成A.动态结构和静态结构C.线性结构和非线性结构算法分析的目的是oB.紧凑结构和非紧凑结构D.内部结构和外部结构,算法分析的两个主要方面是

2、A.C.A.C.找出数据结构的合理性分析算法的效率以求改良空间复杂性和时间复杂性可读性和文档性I计算机算法指的是A.C.A.C.填空题D.B.D.B.研究算法中的输入和输出的关系分析算法的易懂性和文档性正确性和简明性数据复杂性和程序复杂性,它必具备输入、 输出和等五个特性.计算方法B.解决问题的有限运算序列可行性、可移植性和可扩充性确定性、有穷性和稳定性将正确的答案填在相应的空中1.数据逻辑结构包括、2.在线性结构中,第一个结点结点,其余每个结点有且只有3.在树形结构中,树根结点没有点,其余每个结点的直接后续结点可以4.5.6.7.8.9.D.B.D.排序方法调度方法可行性、确定性和有穷性易读

3、性、稳定性和平安性三种类型,树形结构和图形结构合称为前驱结点,其余每个结点有且只有个后续结点.结点,其余每个结点有且只有在图形结构中,每个结点的前驱结点数和后续结点数可以个前驱结点;最后一个结点个直接前驱结点,叶子结点没有后续线性结构中元素之间存在算法的五个重要特性是分析下面算法(程序段)for(i=0;in;i+)for(j=0;jn;j+)Aij=0;分析下面算法(程序段)for(i=0;in;i+)for(j=0;ji;j+)Aij=0;分析下面算法(程序段)s=0;for(i=0;in;i+)for(j=0;jn;j+)for(k=0;kn;k+)s=s+Bijk;sum=s;关系,树

4、形结构中元素之间存在关系,图形结构中元素之间存在关系.,给出最大语句频度,给出最大语句频度,给出最大语句频度,该算法的时间复杂度是,该算法的时间复杂度是,该算法的时间复杂度是10.分析下面算法程序段i=s=0;给出最大语句频度,该算法的时间复杂度是while(sn)i+;s+=i;s=s+i11.分析下面算法(程序段)给出最大语句频度,该算法的时间复杂度是i=1;while(inext=NULLC.head-next=headD.head!=NULL8.带头结点的单链表head为空的判定条件是.A.head=NULLB.head-next=NULLC.head-next=headD.head!

5、=NULL9.非空的循环单链表head的尾结点(由p所指向)满足.A.p-next=NULLB.p=NULLC.p-next=headD.p=head10.在双向循环链表的p所指结点之后插入s所指结点白操作是.A. p-right=s;s-left=p;p-right-left=s;s-right=p-right;B. p-right=s;p-right-left=s;s-left=p;s-right=p-right;C. s-left=p;s-right=p-right;p-right=s;p-right-left=s;D. s-left=p;s-right=p-right;p-right-

6、left=s;p-right=s;11.在一个单链表中,q所指结点是p所指结点的前驱结点,假设在q和p之间插入s结点,那么执行.A. s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;B. q-next=s;s-next=p;C.p-next=s;s-next=q;12.在一个单链表中,假设p所指结点不是最后结点,在p之后插入s所指结点,那么执行.A.s-next=p;p-next=s;B.s-next=p-next;p-next=s;C. s-next=p-next;p=s;C.p-next=s;s-next=p;13.在一个单链表中,假设删除p

7、所指结点的后续结点,那么执行.A.p-next=p-next-next;B.p=p-next;p-next=p-next-next;C.p-next=p-next;D.p=p-next-next;14.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比拟个结点.A.nB.n/2C.(n-1)/2D.(n+1)/215.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是.A.O(1)B.O(n)C.O(n2)D.O(nlog2n)16.给定有n个元素的向量,建立一个有序单链表的时间复杂度是_.A.0(1)B.O(n)C.O(n2)D.O(n*log

8、2n)2.2填空题(将正确的答案填在相应的空中)1 .单链表可以做的链接存储表示.2.在双链表中,每个菽有两个指针域,一个指向,另一个指向.3.在一个单链表中p所指结点之前插入一个s(值为e)所指结点时,可执行如下操作:q=head;while(q-next!=p)q=q-next;s=newNode;s-data=e;q-next=;/填空s-next=;/填空4.在一个单链表中删除p所指结点的后继结点时,应执行以下操作:q=p-next;p-next=/填空delete;/填空5.在一个单链表中p所指结点之后插入一个s所指结点时,应执行s-next=和p-next=的操作.6.对于一个具有

9、n个结点的单链表,在p所指结点后插入一个新结点的时间复杂度是;在给定值为x的结点后插入一个新结点的时间复杂度是.2.3算法设计题:1.设顺序表va中的数据元数递增有序.试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性.StatusInsert_SqList(SqList&va,intx)if(va.length+1maxsize)returnERROR;va.length+;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;returnOK;2.试写一算法,实现顺序表的就地逆置,即利用原表的存储空

10、间将线性表(ai,az,an)逆置为(an,an-v,a1).voidreverse(inta,intsize)inti,j,tmp;for(i=0,j=size-1;inext;while(q!=L&q-datanext;while(q!=L&q-datanext;free(r);if(p!=q)p-next=q;4.试写一算法,实现单链表的就地逆置(要求在原链表上进行).voidconverse(NODEPTRL)NODEPTRp,q;p=L-next;q=p-next;L-next=NULL;while(p)/*对于当前结点p,用头插法将结点p插入到头结点之后*/p-next=L-nex

11、t;L-next=p;p=q;q=q-next;习题答案2.11.B2.A,C3.B4.D5.C6.A7.A8.B9. C10.D11.B12.B13.A14.D15.B16.C2.21.线性结表2.前驱结点、后继结点3.s,p4.q-next,q3.1单项选择题1.一个栈的入栈序列a,b,c,d,e,那么栈的不可能的输出序列是.A.edcbaB.decbaC.dceabD.abcde2.假设一个栈的入栈序列是1,2,3,n,其输出序列为p1,p2,p3,pn,假设p1=n,那么pi为.A.iB.n=iC.n-i+1D.不确定3.栈结构通常采用的两种存储结构是.A.顺序存储结构和链式存储结构B

12、.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构4.判定一个顺序栈ST最多元素为m.为空的条件是.A.top!=0B.top=0C.top!=m0D.top=m0-15.判定一个顺序栈ST最多元素为m.为栈满白条件是.A.top!=0B.top=0C.top!=m0D.top=m0-16.栈的特点是,队列的特点是.A.先进先出B.先进后出7 .向一个栈顶指针为HS的链栈中插入一个s所指结点时,那么执行_.不带空的头结点A.HSnext=s;B.snext=HSnext;HSnext=s;C.snext=HS;HS=s;D.snext=HS;HS=HSnext;8.从一

13、个栈顶指针为HS的链栈中删除一个结点时,用x保存被删结点的值,那么执行.不带空的头结点A.x=HS;HS=HSnext;B.x=HSdata;C.HS=HSnext;x=HSdata;D.x=HSdata;HS=HSnext;9.一个队列的数据入列序列是1,2,3,4,那么队列的出队时输出序列是.A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,110.判定一个循环队列QU最多元素为mO为空的条件是.A.rear-front=m0B.rear-front-1=m0C.front=rearD.front=rear+111 .判定一个循环队列QU最多元素为m0,m0=Maxsi

14、ze-1为满队列的条件是.A. rear-front+Maxsize%Maxsize=m0B. rear-front-1=m0C. front=rearD. front=rear+112.循环队列用数组A0,m-1存放其元素值,其头尾指针分别是front和rear,那么当前队列中的元素个数是A. rear-front+m%mB. rear-front+1C.rear-front-1D.rear-front13.栈和队列的共同点是.A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点14 2填空题将正确的答案填在相应的空中1 .向量、栈和队列都是结构,可以在向量的位置插

15、入和删除元素;对于栈只能在插入和删除元素; 对于队列只能在插入元素和删除元素.2.向一个长度为n的向量的第i个元素1Wiwn+1之前插入一个元素时,需向后移动个元素.3.向一个长度为n的向量中删除第i个元素1wiwn时,需向前移动个元素.5. p-next,s6. O(1),O习题3栈和队列习题答案3.11.C2.C3.A4.B5.D6.BA7.C8.B9.C10.C11.A12.A13.C3.21.线性、任何、栈顶、队尾、队首2.n-i+13.n-i4. n-1习题6树和二叉树4.1单项选择题1 .由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法.A.正确B.错误2.假定

16、在一棵二叉树中,双分支结点数为15,单分支结点数为30个,那么叶子结点数为个.A.15B.16C.17D.473.根据二叉树的定义,具有3个结点的不同形状的二叉树有种.A.3B.4C.5D.64.根据二叉树的定义,具有3个不同数据结点的不同的二叉树有种.A.5B.6C.30D.325.深度为5的二叉树至多有个结点.A.16B.32C.31D.106.设高度为h的二叉树上只有度为0和度为2的结点,那么此类二叉树中所包含的结点数至少为.A.2hB.2h-1C.2h+1D.h+17.对一个满二叉树,m个树叶,n个结点,深度为h,那么.A.n=h+mB.h+m=2nC.m=h-1D.n=2h-18.任

17、何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序.A.不发生改变B.发生改变C.不能确定D.以上都不对9.如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后序为.A.uwvtsB. vwutsC.wuvtsD.wutsv10.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法.A.正确B.错误11.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,那么其后序遍历的结点访问顺序是.A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca12.在一非空二叉树的中序遍历序列中

18、,根结点的右边A.只有右子树上的所有结点B.只有右子树上的局部结点C.只有左子树上的局部结点D.只有左子树上的所有结点13.如图6.1所示二叉树的中序遍历序列是.A.abcdgefB.dfebagcC.dbaefcgD.defbagcabcdefgh15.设a,b为一棵二叉树上的两个结点,在中序遍历时,A.a在b的右方B.a在b的左方C. a是b的祖先D.a是b的子孙16.某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是.A.acbedB.decabC.deabcD.cedba17.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最正确方案是二叉树采用存储结

19、构.A.二叉链表B.广义表存储结构C.三叉链表D.顺序存储结构18.如图6.3所示的4棵二叉树,不是完全二叉树.D.a在b前的条件是4.在具有n个单元的循环队列中,队满时共有个元素.二叉树如图6.2所示,其中序遍历的嘿甲abdgcefhB.dgbaechfC:gdbehfca图6.320.在线索化二叉树中,t所指结点没有左子树的充要条件是.A.tleft=NULLB.tltag=1C.tltag=1且tleft=NULLD.以上都不对21.二叉树按某种顺序线索化后,任一结点均有指向其前驱和后续的线索,这种说法.A.B.错误22.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值

20、、小于其右孩子的值.这种说法A.正确B.错误23.具有五层结点的二叉平衡树至少有个结点.A.10B.12C.15D.1724.树的根本遍历策略可分为先根遍历和后根遍历;二叉树的根本遍历策略可分为先序遍历、中序遍历和后序遍历.这里,我们把由树转化得到的二叉树叫做这棵数对应的二叉树.结论是正确的.A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对25.树最适合用来表示.A.有序数据元素B.C.元素之间具有分支层次关系的数据6.2填空题(将正确的答案填在相应的空中)1 .有一

21、棵松口图6.5所示,答复下面的问题:这棵树的根结点是;这棵树的叶子结点是;结点k3的度是;这棵树的度是;这棵树的深度是;(6)结点k3的子女是;结点k3的父结点是2.指出树和二叉树的三个主要差异、._;3.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基的是O4一棵二叉树的结点数据采用顺序存储结构,存储于数组t中,如图6.6所示,5.深度为k的完全二叉树至少有一个结点.至多有个结点,假设按自上而下,从左到右次序给结点编号(从始),那么编号最小的叶子结点的编号是.6.在一棵二叉树中,度为零的结点的个数为n0,度为2的结点的个数为n2,那么有色=.7 .一棵二叉树的第i(i1)层最

22、多有个结点;一棵有n(n0)个结点的满二叉树共有个叶子和端结点.8.结点最少的树为,结点最少的二叉树为.(A)(B)(C)(D)正确无序数据元素D.元素之间无联系的数据个非终那么该二叉树的链接表示形式为图6.6一棵二叉树的顺序存储数组t使用0-7的二进制表示形式是另一种编码方案.对于上述实例,比拟两种方案的优缺点.9.试编写算法,对一棵以孩子-兄弟链表表示的树统计叶子的个数.假设一棵序序列为ABCDEFGHIJK请画出该树.习题答案6.11.B2.B3.C4.C5.C11.D2.A13.B14.B19.B20.B21.B22.B6.A15.B23.B7.D16.D24.A8.A9.C10.A1

23、7.C18.C25.C6.21.2.k1k2,k5,k7,k4(4)343.树的结点个数至少为1(不同教材规定不同),而二树中结点的最大度数没有限制,而二叉树结点的最树的结点无左、右之分,而二叉树的结点有左、右树可采用孩子-兄弟链表(二叉链表)做存储结构,决树的有关问题.4.5. 26. n7. 28.如图6.9所示k-1、2k-12+1i-12log2.+1-122k-2+1logn+1_1只有一个结点的树;空的二叉树5;如图6.10所示叉树的结点个数可以为0;大度数为2;之分;目的并利用二叉树的已有算法解种不同形态的二叉树可以得到这一遍历结果,这些二叉树分别是0=(k-1)nI+17.假设

24、用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)0.32,0.03,0.21,0.10二叉树的先序序列为EBADCFHGIK价口中9 .现有按中序遍历二叉树的结果为abc,问有10 .由如图6.7所示的二叉树,答复以下问题:其中序遍历序列为;其前序遍历序列为;其后序遍历序列为;6.3简做题1.根据二叉树的定义,具有三个结点的二叉树有5种不同的形态,请将它们分别画出.2.假设一棵二叉树的先序序列为EBADCFHGIKJ口中序序列为ABCDEFGHIJK请画出该树.3.由如图6.7所示的二叉树,答复以下问题:(1)画出该二叉树的中序线索二叉树;(2)画出该二叉树的后序线索二叉树;(3)

25、画出该二叉树对应的森林.4.一棵树如图6.8所示,转化为一棵二叉树,5.以数据集4,5,6,7,10,12,18为结点权值,画出构造Huffman树的每一步图示,计算其带权路径长度为.6.一棵含有N个结点的k叉树,可能到达的最大深度和最小深度各为多少?7.证实:一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系:8.4算法设计题1.编写按层次顺序(同一层自左至右)遍历二叉树的算法.2.试编写算法,对一棵二叉树,统计叶子的个数.3.试编写算法,对一棵二叉树根结点不变,将左、右子树进行交换,树中每个结点的左、右子树进行交换.组成,字母在电文中出现的频率分别为0.07,0.19,0.0

26、2,0.06,O试为这八个字母设计哈夫曼编码.图6.7一棵二叉树、abdgcefhi、gdbeihfca、图6.11,图6.15一棵树的孩子兄弟表5.画出构造Huffman树如图6.16所示,计算其带权路径长度为.6.一棵含有N个结点的k叉树,可能到达的最大深度h=N-k+1最小深度各为:logkN+1.二叉树如图6.12所示.图6.11树形5种2.3.中序线索二叉树如图6.13左所示;后序NULLb蹩18613和后序线索树该二叉树转换后白的森林如图6.14所示.卜.图6.8的呼我化为-NULLF线索二叉树如图6.13右所示;CG图6.12对应的森林6.146.3图6.16Huffman树10

27、.dgbaechif1.5种,7.1单项选择题1 .在一个图中,所有顶点的度数之和等于所有边数的倍.A.1/2B.1C.2D.42.任何一个无向连通图的最小生成树.A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的倍.A.1/2B.1C.2D.44.一个有n个顶点的无向图最多有条边.A.nB.n(n-1)C.n(n-1)/2D.2n5.具有4个顶点的无向完全图有条边.A.6B.12C.16D.206.具有6个顶点的无向图至少应有条边才能保证是一个连通图.A.5B.6C.7D.87.在一个具有n个顶点的无向图中,要连通全部顶点至

28、少需要条边.A.nB.n+1C.n-1D.n/28.对于一个具有n个顶点的无向图,假设采用邻接矩阵表示,那么该矩阵的大小是一A.nB.(n-1)2C.n-1D.n29 .对于一个具有n个顶点和e条边的无向图,假设采用邻接表表示,那么表头向量的大小为总数是.1A.nB.n+1C.n-1D.n+e2A.e/2B.eC.2eD.n+e10.一个图如图7.1所示,假设从顶点a出发按深度搜索法进行遍历,那么可能得到;按宽度搜索法进行遍历,那么可能得到的一种顶点序列B.e,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b图7.1一个无向图11 .一有向图的邻接表存储结构如图7.2所示

29、.根据有向图的深度优先遍历算法,从顶点习题7图;所有邻接表中的接点D.a,c,f,d,e,b的一种顶点序列为为.A.a,b,e,c,d,fv1出发,所得到的顶点序列是C.a,e,b,c,f,dA.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2根据有向图的宽度优先遍历算法,从顶点v1出发,所得到的顶点序列是.A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v212.采用邻接表存储的图的深度优先遍历算法类似于二叉树的.A.先序遍历B.中序遍历C.

30、后序遍历D.按层遍历13.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的.A.先序遍历B.中序遍历C.后序遍历D.按层遍历14.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用.A.求关键路径的方法B.求最短路径的Dijkstra方法C.宽度优先遍历算法D.深度优先遍历算法15.关键路径是事件结点网络中.A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长的回路D.最短的回路16.下面不正确的说法是.(1)在AOE网中,减小一个关键活动上的权值后,整个工期也就相应减小;(2)AOER工程工期为关键活动上的权之和;(3)在关键路径上的活动都是关键活动,而关键活动也必在

31、关键路径上.A.(1)B.(2)C.(3)D.(1)、(2)17.用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印出相应的顶点,那么输出的顶点序列是A.逆拓朴有序的B.拓朴有序的C.无序的18.在图7.3所示的拓朴排列的结果序列为.A.125634B.516234C.123456D.52163419.一个有n个顶点的无连通阳电所包含的连通分量个数为一.A.0B.1C.nD.n+120.对于一个有向图,假设一个顶点的入度为k1,、出度为k2,那么对应邻接表中该顶点单链表中的结点数为.A.k1B.k2C.k1-k2D.k1+k221.对于一个有向图,假设一个顶点的入度为k1,、出度为k2,

32、那么对应逆邻接表中该顶点单链表中的结点数为.A.k1B.k2C.k1-k2D.k1+k27.2填空题(将正确的答案填在相应俄空中)1 .n个顶点的连通图至少条边.2.在无权图G的邻接矩阵A中,假设(vi,vj)或vvi,vj属于图G的边集合,那么对应元素Aij等于,否那么等于3.在无向图G的邻接矩阵A中,假设A皿等于1,那么Aji等于.4.图G的邻接表如图7.4所示,其从顶点v1出发的深度有限搜索序列为,其从顶点v1出发的宽度优先搜索序列为.5.一个有向图的邻接矩阵表示,计算第i个结点的入度的方法是6.一个图的邻接矩阵表示,删除所有从第i个结点出发的边的方法是7.如果含n个顶点的图形成一个环,

33、那么它有棵生成树.8 .一个非连通无向图,共有28条边,那么该图至少有个顶点.9 .遍历图的过程实质上是.BFS遍历图的时间复杂度为,DFS遍历图的时间复杂度为,两者不同之处在于,反映在数据结构上的差异是.10 .一个图的表示法是唯一的,而表示法是不唯一的.11 .有向图中的结点前驱后继关系的特征是.12 .假设无向图G的顶点度数最小值大于等于时,G至少有一条回路.13.根据图的存储结构进行某种次序的遍历,得到的顶点序列是的.7.3综合题1.如图7.5所示的有向图,请给出该图的(1)(2)(3)(4)(5)每个顶点的入/出度;邻接距阵;邻接表;逆邻接表;强连通分量.2.请用克鲁斯卡尔和普里姆两

34、种算法分别为图(1)7.6、图7.7构造最小生成树:图7.64.请用图示说明图7.9从顶点a到其余各顶点之间的最短路径.5.AOE网有9个结点:V1,V2,V3,V4,V5,V6,V7,V8,V9,其邻接矩阵如下:(1)请画出该AOE图.(2)计算完成整个方案需要的时间.(3)求出该AOE网的关键路径.OC645OCOCOCOCOC工工工工1工工工工工工工工1工工工工工工工工工2工工工工工工工工工971工工工工工工工工4工工工工工工工工工2工工工工工工工工4工工工工工工工工工习题答案7.n8.99.对每个顶点查找其邻接点的过程;O(e)(e为图中的边数);O(e);遍历图的顺序不同;DFS采用

35、栈存储访问过的结点,BFS采用队列存储访问过的结点.10.邻接矩阵邻接表11 .一个结点可能有假设干个前驱,也可能有假设干个后继12.213.唯一7.31.7.11.C2.B3.B4.C5.A8.D9.AC10.DB11.CB12.A13.D16.A17.A18.B19.B20.B7.21.n-12.1;03.14.v1,v2,v3,v6,v5,v4;v1,v2,v5,v4,v3,v65.求矩阵第i列非零元素之和6.将矩阵第i行全部置为零6.A14.D21.A7.C15.A15(2)完成整个方案需要18天.关键路径为:(V1,V2,V5,V7,V9)和(V1,V2,V5,V8,V9,)习题8查

36、找8.1单项选择题1.顺序查找法适合于存储结构为的线性表.A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储2.对线性表进行二分查找时,要求线性表必须.A.以顺序方式存储B.以链接方式存储C.以顺序方式存储,且结点按关键字有序排序D.以链接方式存储,且结点按关键字有序排序3.采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为A.nB.n/2C.(n+1)/2D.(n-1)/24.采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为3.5151263423645.(1)该AO的为:A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)5.二分查找和

37、二叉排序树的时间性能.A.相同B.不相同6.有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100,当二分查找值82为的结点时,次比较后查找成功.A.1B.2C.4D.87.设哈希表长m=14,哈希函数H(key尸key%11.表中已有4个结点:addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7如用二次探测再散列处理冲突,关键字为49的结点的地址是.A.8B.3C.5D.98.有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比拟次数为.A.35/12B.37/12C.39/12D

38、.43/129.对于静态表的顺序查找法,假设在表头设置岗哨,那么正确的查找方式为.A.从第0个元素往后查找该数据元素B.从第1个元素往后查找该数据元素C.从第n个元素往开始前查找该数据元素D.与查找顺序无关10.解决散列法中出现的冲突问题常采用的方法是.A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法11 .采用线性探测法解决冲突问题,所产生的一系列后继散列地址.A.必须大于等于原散列地址B.必须小于等于原散列地址C.可以大于或小于但不能等于原散列地址D.地址大小没有具体限制12.对于查找表的查找过程

39、中,假设被查找的数据元素不存在,那么把该数据元素插入到集合中.这种方式主要适合于.A.静态查找表B.动态查找表C.静态查找表与动态查找表D两种表都不适合13.散列表的平均查找长度.A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关而与表的长度有关D.与处理冲突方法无关而与表的长度无关8.2填空题(将正确的答案填在相应的空中)1.顺序查找法的平均查找长度为;折半查找法的平均查找长度为;哈希表查找法采用链接法处理冲突时的平均查找长度为.2.在各种查找方法中,平均查找长度与结点个数n无关的查找方法是.3.折半查找的存储结构仅限于,且是.4 .假设在有序

40、线性表A1.20上进行折半查找,那么比拟一次查找成功的结点数为,那么比拟二次查找成功的结点数为,那么比拟三次查找成功的结点数为,那么比拟四次查找成功的结点数为,那么比拟五次查找成功的结点数为,平均查找长度为.5.对于长度为n的线性表,假设进行顺序查找,那么时间复杂度为;假设采用折半法查找,那么时间复杂度为;6 .有序表为(12,18,24,35,47,50,62,83,90,115,134),当用折半查找90时,需进行次查找可确定成功;查找47时,需进行次查找成功;查找100时,需进行次查找才能确定不成功.7.二叉排序树的查找长度不仅与有关,也与二叉排序树的有关.8.一个无序序列可以通过构造一

41、棵树而变成一个有序树,构造树的过程即为对无序序列进行排序的过程.9.平衡二叉排序树上任一结点的平衡因子只可能是、_或.10.法构造的哈希函数肯定不会发生冲突.11.在散列函数H(key)=key%p中,p应取.12.在散列存储中,装填因子的值越大,MT;的值越小,那么.8.3综合练习题1 .画出对长度为10的有序表进行折半查找的判定树,并求其等概率时查找成功的平均查找长度.4.选取哈稀函数H(k)=(3k)MOD1.用开放定址法处理冲突,di=i(7k)MOD0+1)(I=1,2,3,).试在0-10的散列地址空间中对关键字序列(22,41,53,46,30,13,01,67)造哈希表,并求等

42、概率情况下查找成功时的平均查找长度.5 .一组关键字49,38,65,97,76,13,27,44,82,35,50,画出由此生成的二叉排序树,注意边插入边平衡.习题答案8.11.B2.C3.C4.D5.B6.C7.D8.B9.C10.D11.C12.B13.C8.21.(n+1)/2、(n+1)*log2(n+1)/n-1、1+(为装填因子)2.哈希表查找法3.顺序存储结构、有序的4.1、2、4、8、5、3.7(依题意,构造一棵有序二叉树,共12个结点,第一层1个结点,第二层2个结点,第三层4个结点,第四层5个结点,贝U:ASL=(1*1+2*2+3*4+4*5)/12=37/12)5.O(

43、n)、O(log2n)6.2、4、37.结点个数n、生成过程8.二叉排序树9.0、1、-110.直接定址11 .素数12.存取元素时发生冲突的可能性就越大、存取元素时发生冲突的可能性就越小习题9排序9.1单项选择题1 .在所有排序方法中,关键字比拟的次数与记录的初始排列次序无关的是.A.希尔排序B.起泡排序C.插入排序D.选择排序2.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好选用排序法.A.起泡排序B.快速排序C.堆排序D.基数排序3.在待排序的元素序列根本有序的前提下,效率最高的排序方法是A.插入排序B.选择排序C.快速排序D.归并排序4.一组记录的排序码为

44、(46, 79,56,38,40,84),那么利用堆排序的方法建立的初始堆为一.A.79,46,56,38,40, 80B. 3846,56,79,40,84,C.84,79,56,46,40, 38D. 8456,79,40,46,385.一组记录的关键码为(46, 79,56,38,40,84),那么利用快速排序的方法,以桁 个记录为基准得到的一次划分结果为OA.38,40,46,56,79, 84B. 4038,46,79,56,84C.40,38,46,56,79, 84D. 4038,46,84,56,796.一组记录的排序码为(25, .48, 16,35,79,_82, 23,40,36,72),其中含有5个长度为2的后序表,按归并排序的方法对该序列进彳 L 趟归并后的结果为OA.16,25,35,48,23, 40,79,82,36,72B.16,25,35,48,79, 82,23,36,40,72C.16,25,48,35,79, 82,23,36,40,72D.16,25,35,48,79, 23,36,40,72,827 .排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比拟,将其放入已排序序列的正确位置上的

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论