资源描述
数据结构典型习题数据结构典型习题知博书店v1、下面程序段的时间复杂度为（、下面程序段的时间复杂度为（）for(inti=0;im;i+)for(intj=0;jn;j+)aij=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)答案：Cv设设n为正整数为正整数,分析下列各程序段中加下划线的语句的程序分析下列各程序段中加下划线的语句的程序步数。步数。for(inti=1;i=n;i+)for(intj=1;j=n;j+)cij=0.0;for(intk=1;k=n;k+)cij=cij+aik*bkj;（2）x=0;y=0;for(inti=1;i=n;i+)for(intj=1;j=i;j+)for(intk=1;k=j;k+)x=x+y;(3)inti=1,j=1;while(i=n&jnext-next和和rear,查找时间都是查找时间都是O(1)。若用头指针来表示该链表，则查找终端结若用头指针来表示该链表，则查找终端结点的时间为点的时间为O(n)。v在单链表、双链表和单循环链表中，若仅知道指针在单链表、双链表和单循环链表中，若仅知道指针p指向某指向某结点，不知道头指针，能否将结点结点，不知道头指针，能否将结点*p从相应的链表中删去从相应的链表中删去?若可以，其时间复杂度各为多少若可以，其时间复杂度各为多少?答：我们分别讨论三种链表的情况。答：我们分别讨论三种链表的情况。1.单链表。当我们知道指针单链表。当我们知道指针p指向某结点时，能够根据该指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法指针找到其直接后继，但是由于不知道其头指针，所以无法访问到访问到p指针指向的结点的直接前趋。因此无法删去该结点。指针指向的结点的直接前趋。因此无法删去该结点。2.双链表。由于这样的链表提供双向链接，因此根据已知双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为点。其时间复杂度为O(1)。3.单循环链表。根据已知结点位置，我们可以直接得到其单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置后相邻的结点位置(直接后继直接后继)，又因为是循环链表，所以我，又因为是循环链表，所以我们可以通过查找，得到们可以通过查找，得到p结点的直接前趋。因此可以删去结点的直接前趋。因此可以删去p所所指结点。其时间复杂度应为指结点。其时间复杂度应为O(n)。v下述算法的功能是什么下述算法的功能是什么?LinkListDemo(LinkListL)/L是无头结点单链表是无头结点单链表ListNode*Q,*P;if(L&L-next)Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;returnL;/Demo答：将开始结点摘下链接到终端结点之后成为新的终端结点，答：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指而原来的第二个结点成为新的开始结点，返回新链表的头指针。针。v链栈中为何不设置头结点链栈中为何不设置头结点?答：链栈不需要在头部附加头结点，因为栈都答：链栈不需要在头部附加头结点，因为栈都是在尾部进行操作的，如果加了头结点，等是在尾部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可算法更复杂，所以只要有链表的头指针就可以了。以了。v循环队列的优点是什么循环队列的优点是什么?如何判别它的空和满如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的答：循环队列的优点是：它可以克服顺序队列的“假假溢出溢出”现象，能够使存储队列的向量空间得到充分现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的的利用。判别循环队列的“空空”或或“满满”不能以头不能以头尾指针是否相等来确定，一般是通过以下几种方法：尾指针是否相等来确定，一般是通过以下几种方法：一是另设一变量来区别队列的空和满。二是少用一个一是另设一变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。还可以得到队列中元素的个数。v设数组设数组datam作为循环队列作为循环队列SQ的存储空间，的存储空间，front为队头指为队头指针，针，rear为队尾指针，则执行出队操作后其头指针为队尾指针，则执行出队操作后其头指针front值为值为（）Afront=front+1Bfront=(front+1)%(m-1)Cfront=(front-1)%mDfront=(front+1)%mDv设长度为设长度为n的链队用单循环链表表示，若设头的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何指针，则入队出队操作的时间为何?若只设若只设尾指针呢尾指针呢?答：当只设头指针时，出队的时间为答：当只设头指针时，出队的时间为1，而入队，而入队的时间需要的时间需要n，因为每次入队均需从头指针开，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍就是头指针所指元素，所以出队时不需要遍历整个队列。历整个队列。v在一个带头结点的单循环链表中，在一个带头结点的单循环链表中，p指向尾结指向尾结点的直接前驱，则指向头结点的指针点的直接前驱，则指向头结点的指针head可可用用p表示为表示为head=_。vpnextnextv数组用来表示一个循环队列，为数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计的位置，假定队列中元素的个数小于，计算队列中元素的公式为算队列中元素的公式为（）（）rf;（）（）（nfr）%n;（）（）nrf;（）（）（nrf）%nDv为了提高内存的利用效率，减少溢出机会，为了提高内存的利用效率，减少溢出机会，可以让两个栈共享一段连续内存空间，应如可以让两个栈共享一段连续内存空间，应如何设置两个栈？何设置两个栈？v栈底分别设在内存的两端栈底分别设在内存的两端v设有编号为设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。的车站，具体写出这四辆列车开出车站的所有可能的顺序。v全进之后再出情况，只有全进之后再出情况，只有1种：种：4，3，2，1v进进3个之后再出的情况，有个之后再出的情况，有3种，种，3,4,2,13,2,4,13,2,1,4v进进2个之后再出的情况，有个之后再出的情况，有4种，种，2,4,3,12,3,4,12,1,3,42,1,4,3v进进1个之后再出的情况，有个之后再出的情况，有5种，种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3v设有一个顺序栈设有一个顺序栈S，元素，元素s1，s2，s3，s4，s5，s6依次进栈，如果依次进栈，如果6个元素的出栈顺个元素的出栈顺序为序为s2，s3，s4，s6，s5，s1，则顺序，则顺序栈的容量至少应为多少？栈的容量至少应为多少？v3v指出下述程序段的功能是什么指出下述程序段的功能是什么?vvoidDemo1(SeqStack*S)inti;arr64;n=0;while(!StackEmpty(S)arrn+=Pop(S);for(i=0,in;i+)Push(S,arr);答：程序段的功能是将一栈中的元素按反序重新排列，答：程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在到栈顶。此栈中元素个数限制在64个以内。个以内。vSeqStackS1,S2,tmp;DataTypex;./假设栈假设栈tmp和和S2已做过初始化已做过初始化while(!StackEmpty(&S1)x=Pop(&S1);Push(&tmp,x);while(!StackEmpty(&tmp)x=Pop(&tmp);Push(&S1,x);Push(&S2,x);答：程序段的功能是利用答：程序段的功能是利用tmp栈将一个非空栈的所有元素按原样复制到一个栈将一个非空栈的所有元素按原样复制到一个空栈当中去。空栈当中去。vvoidDemo2(SeqStack*S,intm)/设设DataType为为int型型SeqStackT;inti;InitStack(&T);while(!StackEmpty(S)if(i=Pop(S)!=m)Push(&T,i);while(!StackEmpty(&T)i=Pop(&T);Push(S,i);答：程序段的功能是将一个非空栈中值等于答：程序段的功能是将一个非空栈中值等于m的元素的元素全部删去全部删去。vvoidDemo3(CirQueue*Q)/设设DataType为为int型型intx;SeqStackS;InitStack(&S);while(!QueueEmpty(Q)x=DeQueue(Q);Push(&S,x);while(!StackEmpty(&s)x=Pop(&S);EnQueue(Q,x);/Demo3答：程序段的功能是将一个循环队列反向排列，原来答：程序段的功能是将一个循环队列反向排列，原来的队头变成队尾，原来的队尾变成队头。的队头变成队尾，原来的队尾变成队头。vCirQueueQ1,Q2;/设设DataType为为int型型intx,i,m=0;./设设Q1已有内容，已有内容，Q2已初始化过已初始化过while(!QueueEmpty(&Q1)x=DeQueue(&Q1);EnQueue(&Q2,x);m+;for(i=0;ileft=NULL B.t-ltag=1 vC.t-ltag=1且t-left=NULL D.以上都不对v二叉树按某种顺序线索化后，任意结点均有指向其前驱和后二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索，这种说法（继的线索，这种说法（）vA.正确正确B.错误错误 v用二叉链表法存储包含用二叉链表法存储包含n个结点的二叉树，结点的个结点的二叉树，结点的2n个指个指针区域中有针区域中有n+1个为空指针。个为空指针。vA.正确正确B.错误错误BBAv二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）v A.正确 B.错误 v设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）v A.2h B.2h-1 C 2h+1 D h+1ABv某二叉树的前序遍历节点访问顺序是，中序遍历访问顺序是，则其后序遍历的节点访问顺序是vvvv vDv按照二叉树的定义，具有个节点的二叉树有种v v一棵二叉树如图所示，其中序遍历是vvvv CdabcBv在一非空二叉树的中序遍历序列中，根节点的右边v只有右子树上的所有节点v只有右子树上的部分节点v只有左子树的部分节点v只有左子树上的所有节点v任何一棵二叉树的叶子节点在先序，中序和后序遍历序列中的相对次序 v不发生改变发生改变v不能确定以上都不对AAv如果某二叉树的前序是，中序是，那么后序为vvv设n，m为一棵二叉树上的两个节点，在中序遍历是，n在m前面的条件是 v A n在m右方 B n是m祖先vC n在m左方 D n是m子孙C C v.线索二叉树是一种 结构。vA逻辑 B 逻辑和存储vC 物理 D 线性一棵度为一棵度为2的树与一棵二叉树有何区别？的树与一棵二叉树有何区别？Cv在一个图中，所有顶点的度数之和等于所有在一个图中，所有顶点的度数之和等于所有边数的（）倍。边数的（）倍。va.1/2b.1c.2d.4v在一个有向图中，所有顶点的入度之和等于在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。所有顶点的出度之和的（）倍。va.1/2b.1c.2d.4CBv一个有一个有n个顶点的无向图最多有（）条边。个顶点的无向图最多有（）条边。va.nb.n(n-1)c.n(n-1)/2d.2nv在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边v a.n b.n+1 c.n-1 d.n-2 CCv对于一个具有个顶点的无向图，若采用邻对于一个具有个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）接矩阵表示，则该矩阵的大小是（）va.nb.(n-1)2c.n-1d.n 2v对于一个具有对于一个具有n个顶点和个顶点和e条边的无向图，若条边的无向图，若采用邻接表表示，则表头向量的大小为（），采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（）。所有邻接表中的结点总数是（）。v1：a.nb.n+1c.n-1dn+ev2:a.e/2b.ec.2ed.n+e DACv已知一个图如图所示，若从顶点已知一个图如图所示，若从顶点a出发按深度出发按深度搜索法进行遍历，则可能得到的一种顶点序搜索法进行遍历，则可能得到的一种顶点序列为（）按广度搜索法进行遍历，则可能得列为（）按广度搜索法进行遍历，则可能得到的一种顶点序列为（）到的一种顶点序列为（）vA.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,bvAa,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,bacefbdDBv已知一有向图的邻接表存储结构如图所示。已知一有向图的邻接表存储结构如图所示。v根据有向图的深度优先遍历算法，从顶点根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）出发，所得到的顶点序列是（）va.v1,v2,v3,v5.v4b.v1,v2,v3,v4,v5vc.v1,v3,v4,v5,v2d.v1,v4,v3,v5,v2123453244524Cv已知一有向图的邻接表存储结构如图所示。已知一有向图的邻接表存储结构如图所示。v根据有向图的广度优先遍历算法，从顶点根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）出发，所得到的顶点序列是（）va.v1,v2,v3,v4,v5b.v1,v3,v2,v4,v5vc.v1,v2,v3,v5,v4dv1,v4,v3,v5,v2123453244524Bv采用邻接表存储的图的深度优先遍历算法类采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）似于二叉树的（）va先序遍历先序遍历b中序遍历中序遍历vc后序遍历后序遍历d按层遍历按层遍历v采取邻接表存储的图的广度优先遍历算法类采取邻接表存储的图的广度优先遍历算法类似于二叉树的（）似于二叉树的（）va先序遍历先序遍历b中序遍历中序遍历vc后续遍历后续遍历d按层遍历按层遍历 ADv用邻接表表示图进行广度优先遍历时，通常用邻接表表示图进行广度优先遍历时，通常是采用是采用来实现算法的。来实现算法的。vA栈栈B.队列队列C.树树D.图图 v用邻接表表示图进行深度优先遍历时，通常用邻接表表示图进行深度优先遍历时，通常是采用是采用来实现算法的。来实现算法的。vA栈栈B.队列队列C.树树D.图图BAv判定一个有向图是否存在回路除了可以利用拓扑排判定一个有向图是否存在回路除了可以利用拓扑排序方法之外，还可以利用（）序方法之外，还可以利用（）va求关键路径的方法求关键路径的方法vb求最短路径的求最短路径的dijkstra方法方法vC广度优先遍历法广度优先遍历法vd深度优先遍历法深度优先遍历法v任何一个无向连通图的最小生成树（任何一个无向连通图的最小生成树（）vA只有一棵只有一棵B.一棵或多棵一棵或多棵vC.一定有多棵一定有多棵D.可能不存在可能不存在 DAv在无权图在无权图G的邻接矩阵的邻接矩阵A中，若（中，若（vi,vj）或）或属于图属于图G的边集合，则对应元素的边集合，则对应元素Aij等于（）否则等于（）等于（）否则等于（）v已知一个图用邻接矩阵表示，计算第已知一个图用邻接矩阵表示，计算第i个结点个结点的入度的方法是的入度的方法是_删除所有从第删除所有从第i个结点出发的边的方法是个结点出发的边的方法是_10第第i列非零元素之和列非零元素之和 将矩阵第将矩阵第i行全部置为零行全部置为零 v如果如果n个顶点的图是一个环，则它有个顶点的图是一个环，则它有_棵棵生成树。生成树。vn个顶点个顶点e条边的图，若采用邻接矩阵存储，条边的图，若采用邻接矩阵存储，则空间复杂度为则空间复杂度为_。vn个顶点个顶点e条边的图，若采用邻接表存储，则条边的图，若采用邻接表存储，则空间复杂度为空间复杂度为。v设有一稀疏图设有一稀疏图G，则，则G采用采用存储较省存储较省空间。空间。v设有一稠密图设有一稠密图G，则，则G采用采用存储较省存储较省空间。空间。nO(n2)O(n+e)邻接表邻接表邻接矩阵邻接矩阵v用用Dijkstra算法求某一顶点到其余各顶点间的算法求某一顶点到其余各顶点间的最短路径是按路径长度最短路径是按路径长度的次序来得到的次序来得到最短路径的。最短路径的。v拓扑排序算法是通过重复选择具有拓扑排序算法是通过重复选择具有个个前驱顶点的过程来完成的前驱顶点的过程来完成的 递增递增0v在数据的存放无规律而言的线性表中进行检索的最在数据的存放无规律而言的线性表中进行检索的最佳方法是佳方法是_v顺序查找法适合于存储结构为（）的线性表顺序查找法适合于存储结构为（）的线性表 a散列存储 b顺序存储或链接存储 c压缩存储 d索引存储 对线性表进行二分查找时，要求线性表必须（）va以顺序方式存储 b 以链接方式存储 vc以顺序方式存储，且结点按关键字有序排序vd以链接方式存储，且结点按关键字有序排序顺序查找顺序查找 bCv采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）va.n b.n/2 c(n+1)/2 d.(n-1)/2 v采用二分法查找长度为n的线性表时，每个元素的平均查找长度为（）va.O(n2)b O(nlog2n)c O(n)d O(log2n)v二分法查找和二叉排序树的时间性能（）va 相同 b不相同 Cdbv有一个有序表为(n=13)1,3,9,12,32,41,45,62,75,77,82,95,100,当二分查找值82为的结点时（）次比较后查找成功 va 1 b 2 c 4 d 8 v设哈希表长m14，哈希函数H（key）key11。表中已有4个结点：vaddr（15）4 addr（38）5vaddr（61）6 addr（84）7v其余地址为空,如用二次探测再散列处理冲突，关键字为49的结点的地址是（）va 8 b3 c5 d9Cdv有一个长度为12的有序表，按二分查找发对该表进行查找，在表内个元素等概率情况下查找成功所需的平均比较次数为（）va 35/12 b 37/12 c 39/12 d 43/12 v顺序查找法的平均查找长度为（）；二分查找法的平均查找长度（）;分块查找法（以顺序查找确定块）的平均查找长度（）;分块查找法（以二分法查找确定块）的平均查找长度（）b(n+1)/2(n+1)*log2(n+1)/n-1(s+2s+n)/2slog(n/s+1)+s/2v在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 v在分块查找法首先查找（）再查找相应的（）v在散列函数（key）=key%p中p应取（）v假设在有序线性表A1.20上进行二分查找，则比较一次查找成功的结点数为(),则比较二次查找成功的结点数为（），则比较三次查找成功的结点数为（）则比较4次查找成功的结点数为（）则比较5次查找成功的结点数为（）平均查找长度为（）哈希表查找法 索引 块 素数 1个 2个 4个 8个 5个 3.7 v在散列存储中，装填因子的值越大则存取元素时发生冲突的可能性就（）值越小则（）v 折半查找有序表（折半查找有序表（4，6，10，12，20，30，50，70，88，100）（）（n=10）。若查找表）。若查找表中元素中元素58，则它将依次与表中，则它将依次与表中比较大比较大小，查找结果是失败。小，查找结果是失败。vA20，70，30，50B30，88，70，50C20，50D30，88，50 越大 越小Av要进行线性查找，则线性表要进行线性查找，则线性表A；要进行二分查找，则线性；要进行二分查找，则线性表表B；要进行散列查找，则线性表；要进行散列查找，则线性表C。v某顺序存储的表格，其中有某顺序存储的表格，其中有90000个元素，已按关键项的值个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为查找时，平均比较次数约为D，最大比较次数为，最大比较次数为E。v供选择的答案：供选择的答案：vAC：必须以顺序方式存储必须以顺序方式存储必须以链表方式存储必须以链表方式存储必须以散列方式存储必须以散列方式存储v既可以以顺序方式，也可以以链表方式存储既可以以顺序方式，也可以以链表方式存储v必须以顺序方式存储且数据元素已按值递增或递减的次序必须以顺序方式存储且数据元素已按值递增或递减的次序排好排好v必须以链表方式存储且数据元素已按值递增或递减的次序必须以链表方式存储且数据元素已按值递增或递减的次序排好排好vD，E：25000300004500090000v答案：答案：A=B=C=DE v在二叉排序树中，每个结点的关键码值在二叉排序树中，每个结点的关键码值A，B一棵二叉排序，即可一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是结构上的特点是C。v供选择的答案供选择的答案vA：比左子树所有结点的关键码值大，比右子树所有结点的关键码值比左子树所有结点的关键码值大，比右子树所有结点的关键码值小小v比左子树所有结点的关键码值小，比右子树所有结点的关键码值大比左子树所有结点的关键码值小，比右子树所有结点的关键码值大v比左右子树的所有结点的关键码值都大比左右子树的所有结点的关键码值都大v与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系大小关系vB:前序遍历前序遍历中序（对称）遍历中序（对称）遍历后序遍历后序遍历层次遍历层次遍历vC：除最下二层可以不满外，其余都是充满的除最下二层可以不满外，其余都是充满的除最下一层可除最下一层可以不满外，其余都是充满的以不满外，其余都是充满的v每个结点的左右子树的高度之差的绝对值不大于每个结点的左右子树的高度之差的绝对值不大于1最下层的叶最下层的叶子必须在最左边子必须在最左边v答案：答案：ABCv散列法存储的基本思想是根据散列法存储的基本思想是根据A来决定来决定B，冲突指的，冲突指的是是C，处理冲突的两类主要方法是，处理冲突的两类主要方法是D。v供选择的答案供选择的答案vA，B：存储地址存储地址元素的符号元素的符号元素个数元素个数关键码值关键码值非码属性非码属性平均检索长度平均检索长度负载因子负载因子散列表空间散列表空间vC:两个元素具有相同序号两个元素具有相同序号两个元素的关键码两个元素的关键码值不同，而非码属性相同值不同，而非码属性相同v不同关键码值对应到相同的存储地址不同关键码值对应到相同的存储地址负载因子过大负载因子过大数据元素过多数据元素过多vD：线性探查法和双散列函数法线性探查法和双散列函数法建溢出区法和不建溢出区法和不建溢出区法建溢出区法v除余法和折叠法除余法和折叠法链地址法和开放定址法链地址法和开放定址法v答案：答案：ABCD v大多数排序算法都有两个基本的操作：大多数排序算法都有两个基本的操作：和和_v在堆排序和快速排序中，若初始记录接近正在堆排序和快速排序中，若初始记录接近正序或反序，则选用序或反序，则选用堆排序堆排序；若初始记录基；若初始记录基本无序，则最好选用本无序，则最好选用快速排序快速排序 v对于对于n个记录的集合进行冒泡排序，在最坏的个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是情况下所需要的时间是O(n2)。若对其进。若对其进行快速排序，在最坏的情况下所需要的时间行快速排序，在最坏的情况下所需要的时间是是O(n2)比较比较移动移动v在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是vA.希尔排序 B.起泡排序 C.插入排序 D.选择排序 v设有1000个无序的元素，希望用最快的速度挑选出其中十个最大的元素，最好选用 什么排序法。vA.起泡排序 B.快速排序 C.堆排序 D.基数排序 v在待排序的元素序列基本有序的前提下，效率最高的排序方法是vA.插入排序 B.选择排序 C.快速排序 D.归并排序 DCAv一组记录的排序码是（46，79，56，38，40，84），利用堆排序的方法建立的初始堆为vA.79,46,56,38,40,80vB.84,79,56,38,40,46vC.84,79,56,46,40,38vD.84,56,79,40,46,38 Bv一组记录的关键码是（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为vA.38,40,46,56,79,84vB.40,38,46,79,56,84vC.40,38,46,56,79,84vD.40,38,46,84,56,79vCv一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中又五个长度为二的有序表，按归并排序的方法对该序列进行一次归并后的结果为vA.16 25 35 48 23 40 79 82 36 72vB.16 25 35 48 79 82 23 36 40 72vC.16 25 48 3579 82 23 36 40 72vD.16 25 35 48 79 23 36 40 72 82 vAv排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为vA.希尔排序 B.起泡排序 C.插入排序 D.选择排序v排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端方法，称为vA.希尔排序 B.归并排序 C.插入排序 D.快速排序CDv下述几种排序方法中，平均查找长度最小的是vA插入排序 B选择排序 C 快速排序 D 归并排序 v下列几种排序方法中，要求内存量最大的是vA插入排序 B选择排序 C 快速排序 D 归并排序v快速排序方法在 情况下不利于发挥其长处vA要排序的数据量太大vB要排序的数据中含有太多多个相同值vC要排序的数据已基本有序vD要排序的数据个数为奇数CDCv在堆排序中、快速排序和归并排序中，若只从存储空间考虑，则应首先选取（）方法，其次选取（）方法，最后选取（）方法；若只从平均情况下最快考虑，则应选取（）方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取（）方法。v在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是（），需要内存容量最多的是（）。堆排序 快速排序 归并排序 快速排序 堆排序 快速排序 基数排序 v在堆排序和快速排序中，若原始记录接近正序或反序，则选用（），若原始记录无序，则最好选用（）。v在插入和选择排序中，若初始数据基本正序，则选用（）；若初始数据基本反序，则选用（）。v对n个元素的序列进行起泡排序时，最少的比较次数是（）。堆排序 快速排序 插入排序 选择排序 n-1
展开阅读全文