总复习(题目).ppt

总复习题（题目）,一、填空题1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的_和_的学科。2.数据结构研究数据的逻辑结构、_及数据的运算与实现。_是数据不可分割的最小单位。3.通常设计一个“好”的算法应考虑达到以下四个目标：正确性、可读性、_和_。,关系,操作,存储结构,数据项,健壮性,效率与低存储量需求,4.下面程序段的时间复杂度是_。for(i=0;inext=s。,O(m*n),线性结构,图状结构,s-next=p-next;,7.在一个单链表中删除p所指结点时，应执行以下操作：q=p-next;p-data=p-next-data;p-next=_;free(q);8.对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是_；在给定值为x的结点后插入一个新结点的时间复杂度是_。9.栈是一种具有_特性的线性表，队列是一种具有_特性的线性表。,O(1),q-next,O(n),后进先出,先进先出,10.顺序队列在实现时，通常将数组看成是一个首尾相连的环，这样做的目的是为避免产生_现象。判断一个循环队列队满的条件是_（设Q.front代表队头静态指针，Q.rear代表队尾指针，M代表该循环队列的空间大小）,假溢出,(Q.rear+1)%m=Q.front,11.有串s1=ABCDEFG，s2=PQRST，假设函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2),subs(s1,len(s2),2)的结果串是。12.空串是_，其长度等于_。,BCDEFEF,零个字符的串,0,13.二维数组M的成员是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到6，列下标j的范围从0到7，则存放M至少需要_个字节，A的第5列和第5行共占_个字节,若M按行优先方式存储，元素M45的起始地址与当M按列优先方式存储时_的起始地址一致。14.已知一棵二叉树的先序遍历序列是eadcbjfghi，中序遍历序列是abcdjefhgi，那么它的后序遍历序列是。,224,M25,bcjdahigfe,56,15.遍历二叉树的结果为abc，问有_种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是_。,5,16.3个结点可以构成_棵不同形状的树，可以构成_棵不同形状的二叉树。具有32个结点的完全二叉树的深度为_。深度为6的满二叉树所含结点个数为_。17.设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B。已知T1,T2,T3的结点数分别为n1，n2和n3，则二叉树B的左子树中有_个结点，二叉树B的右子树中有_个结点。,2,5,6,63,n1-1,n2+n3,18.一棵二叉树的第i(i1)层最多有_个结点；一棵深度为k的满二叉树共有_个结点、共有_个叶子和_个非终端结点。19.n个结点的二叉树中如果有m个树叶，则一定有_个度为1的结点。20.一个有n个顶点的无向图最多有_条边，至少应有_条边才能确保是一个连通图。21.深度为10的完全二叉树至多有个结点，至少有_个结点。,2i-1,n(n-1)/2,n-1,2k-1,2k-1,2k-1-1,n-2m+1,1023,29-1+1=512,22.已知一个的有向图的邻接矩阵表示，计算第i个结点的入度的方法是_。删除所有从第i个结点出发的弧的方法是_。23.网G的邻接矩阵A=0358，306456028420顶点V4的度为，（V1，V4）的权为_。,将矩阵第i行全部置为0,求矩阵第i列非0元素之和,3,8,24.在各种查找方法中，平均查找长度与结点个数n无关的查法方法是_。25.在堆排序和快速排序中，若原始记录接近正序或反序，则选用_，若原始记录无序，则最好选用_。26.在插入和选择排序中，若初始数据基本正序，则选用_；若初始数据基本反序，则选用_。27.对n个元素的序列进行起泡排序时，最少的比较次数是_。,哈希表查找法,堆排序,快速排序,插入排序,选择排序,n-1,28.在一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为_。查找不成功所需的平均比较次数为_。29.从稳定性能来看，堆排序是_的，简单选择排序是的。,37/12,稳定,不稳定,49/13,二、选择题1.数据结构在计算机内存中的是_。A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系2.下面程序段的时间渐近复杂度为_。i=1；while(inext=nullB.head=nullC.head!=nullD.headnext=“null”,C,A,5.线性表的链式存储有利于_运算的实现。A.插入B.读元素C.查找D.定位6.设一个栈的输入序列为A,B,C,D,借助一个栈所得到的输出序列不可能是_A.A,B,C,DB.D,C,B,AC.A,C,D,BD.D,A,B,C7.经过以下队列运算后，队头的值是_InitQueue(qu);enQueue(qu,a);enQueue(qu,b);enQueue(qu,c);deQueue(qu)A.aB.bC.1D.0,D,A,B,8.设循环队列中数组的下标是0N-1，其头尾指针分别为f和r，则其元素个数为。A.r-fB.r-f-1C.（r-f）%N+1D.（r-f+N）%N9.若已知一个栈的入栈序列是1，2，3，n,其输出序列为p1,p2,p3,，pn,若p1=n,则pi为_。AiBn-iCn-i+1D不确定,D,C,10.线性表采用链式结构存储时，其地址_。A连续与否都可以B部分地址必须是连续的C一定是不连续的D必须是连续的11.对一个有82个结点的完全二叉树中结点按层次编号，则41号结点的双亲序号和它的孩子情况为_。A20，无左孩子B21，无右孩子C21，有左孩子D20，无右孩子,A,D,12.在高度为h的完全二叉树，。A.度为0的结点都在第h层上B.第i(1ih)层上结点都是度为2的结点C.不存在度为1的结点D.第i（1ih-1）层上有2i-1个结点13.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的先序遍历序列是_。AacbedBdecabCdeabcDcedba,D,D,14.如果T2是由有序树T1转换而来的二叉树，那么对T1中结点的后序遍历就是对T2中结点的。A.先序遍历B.中序遍历C.后序遍历D.层次遍历15.深度为k的完全二叉树，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是。A.2k-1B.2k-1C.2k-1+1D.2k-2+1,B,D,16.如果在表示树的孩子兄弟链中有6个空的左指针域，7个空的右指针域，5个结点左、右指针域都为空，则该树中叶的个数_。A.有7个B.有6个C.有5个D.不能确定17.在有n0个叶子结点的哈夫曼树中共有_个结点。A.n0B.2n0C.n01D.2n01,B,D,18.已知有向图如下图所示，它的拓扑序列是。A.V1，V2，V3，V4，V5，V6B.V1，V2，V3，V5，V4，V6C.V1，V2，V5，V4，V3，V6D.V1，V2，V5，V6，V3，V4,C,19.在一个无向图中，所有顶点的度之和等于边数的倍。A.1/2B.1C.2D.420.若表示一项工程的AOE网中存在环，则_。A网中没有度为0的结点B工程需要延期C可以估算工程完成所必须的最短时间D该工程不能顺利进行,C,D,21.已知一个图如下图所示，若从顶点a出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为；按广度优先搜索法进行遍历，则可能得到的一种顶点序列为。A.abecdfB.acfebdC.aebcfdD.aedfcbA.abcedfB.abcefdC.aebcfdD.acfdeb,D,B,22.有向图G=（V，A），其中V=a,b,c,d,e,A=,对该图进行拓扑排序，下面序列中哪一个不是拓扑序列_。A.a,d,c,b,eB.d,a,b,c,eC.a,b,d,c,eD.a,b,c,d,e23.关键路径是事件结点网络中_A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长的回路D.最短的回路,D,A,24.采用邻接表存储的图的广度优先搜索遍历算法类似于二叉树的_。A.中序遍历B.先序遍历C.后序遍历D.按层遍历25.依次将待排序列中的元素和有序子序列合并为新的有序子序列的排序方法是。A.插入排序B.快速排序C.冒泡排序D.堆排序26.下述几种排序方法中，要求内存量最大的是_。A插入排序B选择排序C快速排序D归并排序,D,A,D,27.以下序列不是堆的是。A.(100，85，98，77，80，60，82，40，20，10，66）B.（100，98，85，82，80，77，66，60，40，20，10）C.（10，20，40，60，66，77，80，82，85，98，100）D.（100，85，40，77，80，60，66，98，82，10，20）,D,三、分析解答题1.假设二维数组A77（行列下标的范围从0到6)每个元素用相邻的6个字节存储，存储器按字节编址。已知A的基地址为100，则1）存放A至少需要多少个字节？2）按行存储，元素a14的第一个字节的地址？3）按列存储，元素a47的第一个字节的地址？4)又设该二维数组为对称矩阵，则存储该数组需多少字节？压缩存储此数组又需多少字节？,答：(1)占用776=294个字节。(2)100+(71+4)*6=166(3)100+(77+4)*6=418,Loc(i,j)=Loc(0,0)+(b2*i+j)*L,Loc(i,j)=Loc(0,0)+(b1*j+i)*L,答：(4)存储此数组需：7*7*6294字节。压缩存储此数组需：（n(n+1)/2）*6=(7*8)/2*6=168字节,2.设有一个二维数组Amn，采用以行序为主序的存储方式，假设A00存放位置在200(10)，A22存放位置在240(10)，每个元素占一个空间，问A35(10)存放在什么位置？数组A的第1行和第m-1行一共占多少空间？（脚注(10)表示用10进制表示）,答：设Aij存放在起始地址为Loc(i,j)。Loc(2,2)=Loc(0,0)+2*n+2n=(240-2-200)/2=19Loc(3,5)=200+3*19+5=262A的第1行和第m-1行一共有19*238个元素，占38个空间。,3.若现有某商场的销售情况统计表，对该表经常做插入删除工作，请问建此表时最佳方案采用顺序存储结构还是链式存储结构？为什么？若采用单链表存储此销售情况统计表，其结点结构为：已知P指向此表中的一个结点，若要在P之前插入一个新结点S，则执行的运算是什么？（用类C语言的语句形式描述）,答：对经常做插入、删除工作，最佳方案应采用链式存储结构。因为：链式存储的线性表在做插入删除操作时不需移动大量的数据，只需修改相应的指针。,datanext,答：S-next=P-next;P-next=S;temp=P-data;P-data=S-data;S-data=temp;,4.对于下图所示的二叉树，请将它转换成森林。,A,B,C,E,D,F,G,H,I,J,K,5.写出如图所示的网的（1）从顶点A出发的深度和广度优先遍历的顶点序列；（2）克鲁斯卡尔算法求最小生成树的过程示意图。,从顶点A出发的深度优先遍历的顶点序列：ABCEFD（答案不唯一）,从顶点A出发的广度优先遍历的顶点序列：ABCDEF（答案不唯一）,6,克鲁斯卡尔算法求最小生成树(1),(2),(3),(4),克鲁斯卡尔算法求最小生成树(5),6.对下图所示的无向网采用prim算法从顶点A开始构造最小生成树。画出最小生成树生成过程，并写出在构造过程中辅助数组中各分量值的变化。,最小生成树生成过程：,B,D,E,C,10,4,5,6,Prim算法构造最小生成树过程中辅助数组中各分量值的变化。,A,B,C,D,7,9,8,A7,A9,A,B,C,D,E,1,0,A,B,C,D,E,B8,B6,3,0,0,A,B,D,C,E,D5,4,0,0,0,A,B,D,E,C,E,B10,D4,D5,2,0,0,0,0,A,B,D,E,C,8.已知AOE网如下，按关键路径算法:（1）找出其关键路径。（2）计算：Ve(V4)、Vl(V4)（3）设弧称为活动a,计算:e(a)和L(a),答:(1)关键路径为:,V1,V6,V5,V7,V8,(2)Ve(V4)=?,Vl(V4)=?,(3)a=e(a)=,Ve(V5),2,4,=12,L(a)=,Vl(V7)-dut(a)=,12,9.画出对长度为10的有序表进行折半查找的判定树，并求出查找关键字等概率时查找成功的平均查找长度和查找不成功时的平均查找长度。,答：查找成功的平均查找长度:(1*1+2*2+4*3+3*4)/10=2.9,5,判定树为:,2,8,1,3,6,9,4,7,10,答：查找不成功的平均查找长度:(5*3+6*4)/11=3.54,10.依据下列关键字序列20，15，19，23，30，40，34，25构成一棵二叉排序树。（1）请画出些二叉排序树。（2）若在二叉排序树中查找，则查找成功与查找不成功的平均查找长度分别是多少？,答：查找成功的平均查找长度:(1*1+2*2+2*3+2*4+1*5)/8=3,20,二叉排序树为:,15,19,23,30,40,34,25,答：查找不成功的平均查找长度:(2*2+2*3+3*4+2*5)/9=3.56,11.设有一组关键字1，13，12，34，38，33，27，22，采用哈希函数H(key)=key%11，请分别采用开放定址法的线性探测再散列和链地址法解决冲突，试在010的散列空间中对该关键字序列构造哈希表，并分别求出查找成功的平均查找长度。,线性探测再散列解决冲突构造的哈希表,1,13,12,34,1,1,比较次数,3,4,38,1,1,33,27,2,8,22,平均查找长度:ASL=21/8,关键字1，13，12，34，38，33，27，22链地址法解决冲突构造哈希表：,平均查找长度:ASL=（41+32+13）/8=13/8,12.已知序列50，17，12，90，89，27，70，65，42，请给出采用希尔排序法（d1=4,d2=2,d3=1）对该序列作升序排列时的每一趟的结果。采用快速排序法以第一个元素为枢轴，对该序列作降序排列时每一趟的结果。,初始态:50,17,12,90,89,27,70,65,42,初始态:50,17,12,90,89,27,70,65,42,d1=4,d2=2,d3=1,89,27,70,90,50,17,12,65,42,89,27,70,90,50,17,12,65,42,89,90,70,65,50,27,12,17,42,90,89,70,65,50,42,27,17,12,快速排序对该序列作降序排列每一趟结果:,50,17,12,90,89,27,70,65,42,初始态:,第一趟:,65,70,89,90,50,27,12,17,42,第二趟:,第三趟:,第四趟:,65,70,89,90,50,27,12,17,42,90,70,89,65,50,42,27,17,12,90,70,89,65,50,42,27,17,12,90,70,89,65,50,42,27,17,12,90,89,70,65,50,42,27,17,12,13.判断以下序列（75，56，28，23，40，38，29，61，35，76，29，100）是否为堆，如果是，是小顶堆还是大顶堆？如果不是，则把它调整为堆（要求记录交换次数最少）。分别对上述无序序列写出执行直接插入排序算法的前4趟升序排序的关键字序列的状态和堆排序算法的前4趟降序排序的关键字序列的状态,序列：75,56,28,23,40,38,29,61,35,76,29,100,不是堆,小顶堆,将此序列调整为小顶堆需交换6次记录，调整为大顶堆需交换7次记录。因此，将此序列应调整为小顶堆。,直接插入升序排序前4趟的状态：,堆排序的降序前4趟的状态：,100,23,28,23,75,堆排序的降序前4趟的状态：,75,29,35,56,76,(2),75,29,29,75,(3),76,29,(3),四、算法填空题1.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成了一个单链表存于计算机中，链表的每个结点指出同样价格的若干台，现在又新到m台价格为h元的电视机入库，单链表存储结构与按此存储结构的算法如下，请填空完成该算法。typedefstructLNodefloatcost;intnum;StructLNode*next;LNode,*LinkList；,voidTvsets(LinkList,p-costnum+=m,t-num=m,t-next=p,思考并练习（1）：若某百货公司仓库中有一批电视机，按其价格从高到低的次序构成了一个单链表存于计算机中，链表的每个结点指出同样价格的若干台，现在又新到m台价格为h元的电视机入库，单链表存储结构与按此存储结构的算法如下，请填空完成该算法。typedefstructLNodefloatcost;intnum;StructLNode*next;LNode,*LinkList；,voidTvsets(LinkList,p-costh,p-num+=m,t-num=m,t-next=p,思考并练习（2）：某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个带头结点的单链表存入计算机中，链表的每个结点指出同样价格的若干台，现在又新到m台价格为h元的电视机入库，补充完成以下仓库电视机链表增加电视机的算法。链表结点结构：typedefstructnodefloatprice；/*价格域*/intnum；/*数量域*/structnode*next；Linklist；,linklist*insert(linklist*head,intm,floath)/已知head为带头结点的单链表linklist*q,*s;q=head；while(q-next!=null,q=q-next;,(linklist*)malloc(sizeof(linklist),s-next=q-next,2.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成了一个单链表存于计算机中，链表的每个结点指出同样价格的若干台，现在要清理库存，将价格为h元的电视机清出库，单链表的存储结构与按此存储结构的算法如下，请填空完成该算法。typedefstructLNodefloatcost;intnum;StructLNode*next;LNode,*LinkList；,VoidDELTvsets(LinkList,p-cost!=h,free(p),q-next=p-next,3.假定单链表L中已存放部分候选人的得票信息（结点类型定义如下），下面算法实现当读入一张有效选票(x为候选人编号)后，对当前得票情况进行统计，请将算法空白处补充完整。typedefstructlinknodeintnumber;/候选人编号intpiaoshu;/当前得票数structlinknode*next;linknode,*linklist;,voidTongji(linklistL,intx)linklistp,q,s;p=L-next;q=;while(p)if(p-number!=x)q=p;p=p-next;else;break;if(!p)s=(l