数据结构必过复习测试卷附答案

第页数据结构必过复习测试卷附答案1.接表更省空间Ⅲ.若有向图中存在拓扑序列，则该图不存在回路A、仅ⅡB、仅Ⅰ、ⅡC、仅ⅢD、仅Ⅰ、Ⅲ【正确答案】：C解析：

只有简单回路才是起始顶点和终止顶点相同的简单路径。存储稀疏图，用邻接表比邻接矩阵更省空间。若有向图中存在拓扑序列（包含全部顶点），则该图不存在回路。【正确答案】：为C。2.35.图的遍历是指（）。A、访问图的所有顶点B、以某种次序访问图的所有顶点C、从一个顶点出发访问图中所有顶点且每个顶点只能访问一次D、从一个顶点出发访问图中所有顶点但每个顶点可以访问多次【正确答案】：C解析：

图的遍历是从给定的初始点出发访问每个顶点且每个顶点仅访问一次。3.果是_（）__。A、0，1，2，3，4B、0，1，2，4，3C、0，1，3，4，2D、0，1，4，2，3【正确答案】：A解析：

直接从顶点0出发进行深度优先遍历，得到的DFS序列为0，1，2，3，4。【正确答案】：为A。4.15.一棵含有n个结点的线索二叉树中，其线索个数为（）。A、2nB、n-1C、n+1D、n【正确答案】：C5.14.由n个无序的元素创建一个有序单链表的算法的时间复杂度是（）。A、O(nlog2n)B、O(n)C、O(1)D、以上都不对【正确答案】：A解析：

创建有序单链表需要排序，而排序的可以采用时间复杂度为O(nlog2n)的算法。6.29.对于采用置换-选择算法产生的归并段，以下含有3个初始归并段的组是（）有序段。A、{5,6,10}，{7,8,2}，{9,5}B、{3,6,12}，{1,2,3}，{5,14}C、{5,6,10}，{7,12,15}，{2,9}D、{7,8,12}，{1,4,6}，{9,12}【正确答案】：C解析：

采用置换-选择算法产生的归并段一定是有序段，选项A错误。而前一个归并段的最后一个关键字一定大于下一个归并段的第一个关键字，选项B、D错误。7.21.线索二叉树中的线索是指（）。A、左孩子B、右孩子C、指针D、标识【正确答案】：C8.=1，则pi（1≤i≤n-1）的值是()。A、n-i+1B、n-iC、iD、有多种可能【正确答案】：A解析：

当pn=1时，进栈序列是p1、p2、p3、…、1，由输出序列可知，p1、p2、p3、…、pn依次进栈，然后依次出栈，即pn-1=2，pn-2=3，…，p1=n，也就是说pi=n-i+1。【正确答案】：为A。9.排序确定A、外排序所花时间=内排序时间+外存信息读写时间+内部归并所花时间B、外排序并不涉及文件的读写操作C、外排序完全可以由内排序来替代【正确答案】：B解析：

外排序过程主要分为两个阶段：生成初始归并段和对初始归并段进行归并，这两个步骤中都涉及文件的读写操作。10.17.设有100个元素的有序表，用折半查找时，不成功时最大的比较次数是（）。A、25B、50C、10D、7【正确答案】：D解析：

不成功时最大的比较次数=log2(n+1)=7。【正确答案】：为D。11.10.某算法的空间复杂度为O(1)，则()。A、该算法执行不需要任何辅助空间B、该算法执行所需辅助空间大小与问题规模n无关C、该算法执行不需要任何空间D、该算法执行所需全部空间大小与问题规模n无关【正确答案】：B解析：

一个算法的空间复杂度为O(1)，只能说明其辅助空间大小与问题规模n无关，并不是说该算法不需要空间。答案为B。12.收集后得到的关键字序列是（）。A、007，110，119，114，911，120，122B、007，110，119，114，911，122，120C、007，110，911，114，119，120，122D、110，120，911，122，114，007，119【正确答案】：C解析：

这里基数排序的第一趟排序是按照个位数字来排序的，第二趟排序是按然十位数字的大小进行排序的。【正确答案】：为C。13.9.以下数据结构中元素之间为非线性关系的是()。A、栈B、队列C、线性表D、以上都不是【正确答案】：D解析：

栈、队列和线性表中元素之间的逻辑关系均为线性关系。答案为D。14.32.以下（）方法可用于求无向图的连通分量。A、遍历B、拓扑排序C、Dijkstra算法D、Prim算法【正确答案】：A解析：

从图中某个顶点出发进行遍历，可将与该顶点相连通的所有顶点全部访问，也就找到了该顶点所在的连通分量。15.到一维数组B[0..m]中，则A[5][8]元素在B中的位置k是（）。A、10B、37C、45D、60【正确答案】：B解析：

A[5][8]属于上三角部分的元素，A[5][8]前面存放的元素个数计算是，第1行有10个，第2行有9个，…，第4行有7个，在第5行中有A[5..7]计3个元素，共10+9+8+7+3=37，由于B的起始下标从0开始，所以k=37。16.13.对含有n个元素的顺序表采用顺序查找方法，不成功时的比较次数是()。A、1B、nC、n-1D、n+1E、4F、5G、6H、7【正确答案】：B解析：

不成功时的比较次数总是n。【正确答案】：为B。14、14.含有20个结点的AVL树的最大高度是()。【正确答案】：C设Nh表示高度为h的平衡二叉树中含有的最少结点数，有N1=1，N2=2，Nh=Nh-1+Nh-2+1，求出N6=20。【正确答案】：为C。17.35.m个初始归并进行k路平衡归并时，所需趟数（）。A、logkmB、logkm+1C、logk(m+1)D、logmk【正确答案】：A18.6.（）方法可以判断一个有向图是否存在回路。A、求最小生成树B、拓扑排序C、求关键路径D、求最短路径【正确答案】：B解析：

可以采用深度优先遍历和拓扑排序来判断一个有向图是否存在回路，若一个有向图能够成功进行拓扑排序，即拓扑排序时产生所有顶点的拓扑序列，则该有向图中一定没有回路。【正确答案】：为B。19.24.数据结构是具有（）的数据元素的集合。A、性质相同B、相同物理结构C、相互关系D、数据项【正确答案】：C20.45.以下（）方法在数据基本有序时效率最好。A、快速排序B、冒泡排序C、堆排序D、希尔排序【正确答案】：B21.18.以下关于有向图的说法中，正确的是()。A、强连通图中任何顶点到其他所有顶点都有边B、完全有向图一定是强连通图C、有向图中任一顶点的入度等于出度D、有向图边集的子集和顶点集的子集可构成原有向图的子图【正确答案】：B解析：

强连通图是任何顶点到其他所有顶点都有路径而不一定有边。完全有向图中任意两个顶点之间都存在一条边，则一定是强连通图。有向图中任一顶点的入度不一定等于出度。一个有向图边集的子集和顶点集的子集不一定构成一个图。【正确答案】：为B。22.28.设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的输出序列不可能是（）。A,B,C,DB、D,C,B,AC、A,C,D,BD,A,B,C【正确答案】：D解析：

可以简单地推算，容易得出D，A，B，C是不可能的，因为D先出来，说明A，B，C，D均在栈中，在栈中顺序应为D，C，B，A，出栈的顺序只能是D，C，B，A，如图3.3所示。所以本题【正确答案】：为D。23.21.采用顺序查找方法查找长度为n的线性表时，成功查找的平均查找长度为（）。A、nB、n/2C、(n+1)/2D、(n-1)/2【正确答案】：C解析：

解：顺序查找时，元素ai需i次比较，成功查找的平均查找长度=(1+2+…+n)/n=(n+1)/2。24.16.设一棵哈夫曼树中有1999个结点，该哈夫曼树用于对（）个字符进行编码。A、999B、998C、1000D、1001【正确答案】：C25.拓扑序列中，若顶点a在顶点b之前，则图中必有一条边<a，b>A、仅ⅠB、仅Ⅰ、ⅢC、仅Ⅱ、ⅢD、Ⅰ、Ⅱ和ⅢE、图的遍历是从给定的初始点出发访问每个顶点且每个顶点仅访问一次F、图的深度优先遍历适合无向图G、图的深度优先遍历不适合有向图H、图的深度优先遍历是一个递归过程【正确答案】：A解析：

在一个有向图的拓扑序列中，若顶点a在顶点b之前，图中不一定有边<a，b>。【正确答案】：为A。10、10.以下叙述中错误的是（）。【正确答案】：C图的深度优先遍历适合无向图和有向图。【正确答案】：为C。26.34.采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）算法。A、先序遍历B、中序遍历C、后序遍历D、层次遍历【正确答案】：A解析：

当图变为二叉树时，深度优先遍历过程是访问起点（类似于访问根结点），访问起点的相邻点，再访问起点的相邻点的相邻点（类似于访问左子树），…，回溯回来时再访问起点的下一个相邻点（类似于访问右子树）。27.1.以下关于有向图的说法中，正确的是（）。A、强连通图是任何顶点到其他所有顶点都有边B、完全有向图一定是强连通图C、有向图中任一顶点的入度等于出度D、有向图边集的子集和顶点集的子集可构成原有向图的子图【正确答案】：B解析：

完全有向图中任意两个顶点之间都有一条边，一定是强连通图。【正确答案】：为B。28.树。若遍历后的结点序列为3,1,7,5,6,2,4，则其遍历方式是（）。A、LRNB、NRLC、RLND、RNL【正确答案】：D29.13.设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为a、b、c、d，将森林F转换为一颗二叉树B，则二叉树B中根结点的左子树上的结点个数是()。A、a-1B、aC、a+b+cD、b+c+d【正确答案】：A30.61.内排序方法的稳定性是指（）。A、经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变B、经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变C、排序算法的性能与被排序元素的数量关系不大D、排序算法的性能与被排序元素的数量关系密切【正确答案】：A31.34.以下关于二叉树的说法中正确的是（）。A、二叉树中每个结点的度均为2B、二叉树中至少有一个结点的度为2C、二叉树中每个结点的度可以小于2D、二叉树中至少有一个结点【正确答案】：C32.8.在（）_中将会用到栈结构。A、递归调用B、图深度优先遍历C、表达式求值D、以上场景都有【正确答案】：D解析：

在递归调用、图的深度优先遍历和表达式求值中均使用栈。【正确答案】：为D。33.储地址为100，则A[2][3]的存储地址是（）。A、122B、126C、114D、116【正确答案】：A解析：

A[2][3]前面有3列，每列3个元素，计9个元素，在列3中前面有2个元素，这样的存储方式中，A[2][3]前面共存储11个元素。LOC(A[2][3])=LOC(A[0][0])+11×2=122。【正确答案】：为A。34.8.关于m阶B树说法错误的是（）。A、m阶B树是一棵平衡的m叉树B树中的查找无论是否成功都必须找到最下层结点C、根结点最多含有m棵子树D、根结点至少含有2棵子树【正确答案】：B解析：

B树中成功的查找会落在某个内部结点中，失败的查找会落在某个外部结点中。【正确答案】：为B。35.8.一棵高度为h、结点个数为n的m（m≥3）次树中，其分支数是（）。A、nhB、n+hC、n-1D、h-1【正确答案】：C36.1.若某非空二叉树的中序序列和后序序列正好相反，则该二叉树的形态是（）。A、只有一个根结点B、所有分支结点都有左右孩子C、所有结点没有左子树D、所有结点没有右子树【正确答案】：C37.55.下列排序方法中，辅助空间为O(n)的是（）。A、希尔选择B、冒泡排序C、堆排序D、归并排序【正确答案】：D解析：

这几种排序方法中只有归并排序的空间复杂度为O(n)，其余几种排序方法的空间复杂度为O(1)。38.23.设栈的输入序列是1、2、3、4，则（）不可能是其出栈序列。A、1、2、4、3B、2、1、3、4C、4、3、1、2D、3、2、1、4【正确答案】：C解析：

当出栈序列的第一个元素为4时，只有唯一的出栈序列4、3、2、1，不可能有4、3、1、2的出栈序列。本题【正确答案】：为C。39.2.以下算法的时间复杂度为()。deffun(n):i=1whilei<=n:i=i*3A、O(n)B、O(n2)C、O(nloD、2n)E、O(loF、2n)【正确答案】：D解析：

设while循环的次数为m，i从1开始每循环一次按3倍递增，有i=3m≤n，m≤log3n=O(log2n)。答案为D。40.19.哈希查找方法一般适用于（）情况下的查找。A、查找表为链表B、查找表为有序表C、关键字集合比地址集合大得多D、关键字集合与地址集合之间存在着某种对应关系。【正确答案】：D解析：

哈希表通过哈希函数和冲突解决函数确定存储地址的，适合关键字集合与地址集合之间存在着某种对应关系的数据集的存储与查找。【正确答案】：为D。41.57.初始数据序列中有两个相同关键字的元素，通过不稳定的排序方法排序后，（）。A、这两个元素的前后位置不发生变化B、这两个元素的前后位置一定发生变化C、这两个元素的位置不发生变化D、这两个元素的前后位置可能发生变化【正确答案】：D42.的排序方法是（）。A、简单选择排序B、快速排序C、冒泡排序D、直接插入排序【正确答案】：A解析：

从数据排列次序的变化过程看到，每一趟都从无序区中选一个最小的元素归位。43.11.以下算法的时间复杂度为（）。deffun(n):i=1whilei<=n:i+=1A、O(n)B、O(√nn)C、O(nloD、2n)E、O(loF、2n)【正确答案】：A解析：

设while循环的次数为m，则有2m<=n，m<=n/2=O(n)。答案为A。44.10.将10阶对称矩阵A压缩存储到一维数组B中，则数组B的长度最少为_()。A、100B、40C、80D、55【正确答案】：D解析：

n阶对称矩阵压缩存储时需要存储的元素个数=n(n+1)/2，n=10时结果为55。45.排序，需要分配和收集()趟。A、3B、4C、5D、8【正确答案】：A解析：

这组关键字中最长的位数是3，所以采用基数排序方法时需要进行3趟分配和收集过程。【正确答案】：为A。46.20.中缀表达式“2*(3+4)-1”的后缀表达式是（）。A、2341*+-B、234+*1–C、234*+1–D、-+*2341【正确答案】：B解析：

对于每个选项按后缀表达式方式求解，看是否与中缀表达式“2*(3+4)-1”的计算顺序一致。【正确答案】：为B。47.11.对于有n个顶点的带权连通图，它的最小生成树是指图中任意一个（）。A、由n-1条权值最小的边构成的子图B、由n-l条权值之和最小的边构成的子图C、由n个顶点构成的极大连通子图D、由n个顶点构成的极小连通子图，且边的权值之和最小【正确答案】：D解析：

最小生成树是图中所有顶点构成的极小连通子图，且边的权值之和最小。【正确答案】：为D。题型：48.5.线性表的顺序存储结构是一种（）。（1≤i≤n）的存储地址为LOC(a0)+i×sizeof(ElemType)，也就是说，对于给定的序号i，在O(1)的A、随机存取的存储结构B、顺序存取的存储结构C、索引存取的存储结构D、散列存取的存储结构【正确答案】：A解析：

若含有n个元素的线性表a采用顺序表存储，每个元素的类型为ElemType，则第i个元素ai时间内找到该元素值，这是一种随机存取的存储结构。而顺序存取是一种读写方式，不是存储方式，有别于顺序存储。49.4.以下最适合用作链队的不带头结点的链表是（）。A、只带首结点指针的循环单链表B、只带尾结点指针的单链表C、只带首结点指针的单链表D、只带尾结点指针的循环单链表【正确答案】：D解析：

只带尾结点指针的循环单链表的进队操作和出队操作时间复杂度为O(1)。【正确答案】：为D。50.30.栈的“先进后出”特性是指（）。A、最后进栈的元素总是最先出栈B、当同时进行进栈和出栈操作时，总是进栈优先C、每当有出栈操作时，总要先进行一次进栈操作D、每次出栈的元素总是最先进栈的元素【正确答案】：A51.44.以下稳定的排序方法是（）。A、直接插入排序和快速排序B、直接插入排序和冒泡排序C、简单选择排序和归并排序D、归并排序和冒泡排序【正确答案】：B52.1.某递归算法的时间递推式如下：T(1)=1T(n)=T(n/2)+n当n>1则，T(n)=（）。A、O(1)B、O(loC、2n)D、O(n)E、O(n2)【正确答案】：C解析：

不妨设n=2k，有k=log2n，T(n)=T(n/21)+n=[T(n/22)+n/2]+n=T(n/22)+(1+1/2)n=…=T(n/2k)+(1+1/2+…+1/2k-1)n=2n+1=O(n)。答案为C。53.4.下面关于哈夫曼树的说法，不正确的是()。A、对应于一组权值构造出的哈夫曼树可能不唯一B、哈夫曼树具有最小带权路径长度C、哈夫曼树中没有度为1的结点D、哈夫曼树中除了度为2的结点外，还有度为1的结点和叶结点【正确答案】：D54.到'*'时，运算数栈（从栈顶到栈底次序）为（）。A、861B、581C、321D、361【正确答案】：C解析：

算术表达式“1+6/(8-5)*3”的后缀表达式是“1685-/3*+”，在求值时，遇到后缀表达式的'*'时，前面已进行了-和/运算，运算数栈中从栈顶到栈底次序为321。【正确答案】：为C。55.18.有一个非空循环双链表，在结点p之前插入结点q的操作是()。A、p.prior=q;q.next=p;p.prior.next=q;q.prior=p.prior;B、p.prior=q;p.prior.next=q;q.next=p;q.prior=p.prior;C、q.next=p;q.prior=p.prior;p.prior=q;p.prior.next=q;D、q.next=p;q.prior=p.prior;p.prior.next=q;p.prior=q;【正确答案】：D56.操作是（）。A、top+=1;s[top]=x;B、s[top]=x;top+=1C、top-=1;s[top]=x;D、s[top]=x;top-=1【正确答案】：C解析：

数组s的下标为0～n-1，top的初始值为n，将s[n-1]一端作为栈底，进栈中元素向s[0]一端生长。在第一个元素x进栈时，先执行top-=1，这样top指向s的有效下标，再执行s[top]=x。【正确答案】：为C。57.23.由m个初始归并段构建的k阶最佳归并树中，度为k的结点个数是（）。A、(m-1)/kB、m/kC、(m-1)/(k-1)D、无法确定【正确答案】：C解析：

设树中结点个数为n，n0=m，n-1=knk，n=n0+nk，所以有knk=m+nk-1，则nk=(m-1)/(k-1)。58.26.k阶最佳归并树是一棵（）。A、k阶平衡树B、平衡二叉树C、k阶哈夫曼树D、以上都不对【正确答案】：C解析：

k阶最佳归并树是一棵k阶哈夫曼树，不一定是k阶平衡树。59.是()。A、存在，且唯一B、存在、且不唯一C、存在，可能不唯一D、无法确定是否存在【正确答案】：C解析：

这样的有向图中只有顶点i到顶点j（i<j）可能有边，而顶点j到顶点i一定没有边，也就是说这样的有向图中一定没有回路，所以可以产生拓扑序列，但拓扑序列不一定唯一。【正确答案】：为C。60.队头元素的前一个位置，rear指向队尾元素的位置），则其元素个数为（）。A、rear-frontB、rear-front-1C、(rear-front)％N+1D、(rear-front+N)％N【正确答案】：D解析：

在非循环队列中rear总是跑在front的前面，其元素个数=rear-front，在循环队列中rear可能比front多跑一圈，所以其元素个数=(rear-front+N)％N。【正确答案】：为D。61.31.哈希查找的基本思想是根据（）来决定元素的存储地址。A、元素的序号B、元素个数C、关键字值D、非关键字属性值【正确答案】：C62.22.数据结构课程中讨论的数据一般具有内在的联系，这是指（）。A、数据和数据之间存在一种或多种特定关系B、数据元素和数据元素之间存在一种或多种特定关系C、数据项和数据项之间存在一种或多种特定关系D、同一数据中的所有数据元素值之间存在一种或多种特定关系【正确答案】：B解析：

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。63.30.n个记录采用置换-选择算法产生m个有序段，m和n的关系是（）。A、m与n成正比B、m与n成反比C、m=log2nD、以上都不对【正确答案】：D解析：

如w=1时，记录序列{1,2,3,4,5}产生一个有序段，而{5,4,3,2,1}产生5个有序段，所以一般来讲，m与数据序列、内存工作区可容纳的记录个数w和n都有关，但并不是A、B、C选项所指的直接关系。64.42.冒泡排序最少元素移动的次数是（）。A、1B、nC、3n(n-1)/2【正确答案】：A65.的数据结构为（）。A、数组B、树C、图D、线性表【正确答案】：B66.种要求的排序方法是（）。A、先按k1值进行直接插入排序，再按k2值进行简单选择排序B、先按k2值进行直接插入排序，再按k1值进行简单选择排序C、先按k1值进行简单选择排序，再按k2值进行直接插入排序D、先按k2值进行简单选择排序，再按k1值进行直接插入排序【正确答案】：D解析：

从题中看出，k1数据项较k2数据项的权重，结合基数排序的情况，如在对若干两位的十进制数进行基数递增排序时，十位数较个位数权重，所以先按个位数排序，再按十位数排序，否则结果是错误的，因此应先按k2数据项排序，再按k1数据项排序。再考虑排序算法的稳定性，简单选择排序是不稳定的，直接插入排序是稳定的，如果对k1数据项采用不稳定的排序方法，则可能出现相同k1值、k2值不同的元素改变相对次序，即可能出现k1值相同、k2大的在前小的在后，这显然不符合题意，所以应对最后的k1采用稳定的排序方法。综合起来应该先按k2值进行简单选择排序，再按k1值进行插入排序。本题【正确答案】：为D。67.时，()。A、仅修改队头指针B、仅修改队尾指针C、队头、队尾指针一定都会修改D、队头、队尾指针可能都会修改【正确答案】：D解析：

当原链队为空时进队操作会修改队头、队尾指针，当原链队不空时进队操作仅修改队尾指针。【正确答案】：为D。68.29.在一个无向图中，所有顶点的度之和等于边数的（）倍。A、1/2B、1C、2D、4【正确答案】：C解析：

在无向图中，一条边计入两个顶点的度数。69.8.顺序表具有随机存取特性，指的是（）。A、查找值为x的元素与顺序表中元素个数n无关B、查找值为x的元素与顺序表中元素个数n有关C、查找序号为i的元素与顺序表中元素个数n无关D、查找序号为i的元素与顺序表中元素个数n有关【正确答案】：C解析：

一种存储结构具有随机存取特性指的是，对于给定的序号i，在O(1)时间内找到对应元素值。70.11.最不适合用作链队的链表是（）。A、只带头结点指针的非循环双链表B、只带队首结点指针的循环双链表C、只带队尾结点指针的循环双链表D、以上都不适合【正确答案】：A解析：

只带头结点指针的非循环双链表作为链队时，队头在首部，队尾在尾部，进队和出队操作的时间均为O(1)。【正确答案】：为A。71.19.下面关于串的叙述中，正确的是（）。A、串是一种特殊的线性表B、串中元素只能是字母C、空串就是空白串D、串的长度必须大于零【正确答案】：A72.5.一棵高度为h的非空平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有()个结点。A、2h-1-1B、2h-1C、2h-1+1D、2h-1【正确答案】：D73.7.一个顺序表所占用存储空间的大小与（）无关。A、顺序表长度B、顺序表中元素的数据类型C、顺序表中元素各数据项的数据类型D、顺序表中各元素的存放次序【正确答案】：D解析：

对于含有n个元素类型为ElemType的顺序表，所占用存储空间的大小为n×sizeof(ElemType)，与各元素的存放次序无关。74.29.对于栈操作数据的原则是（）。A、先进先出B、后进先出C、后进后出D、不分顺序【正确答案】：B解析：

栈操作数据的原则是先进后出或后进先出。75.24.由m个初始归并段构建的k阶最佳归并树中，总共有（）个结点。A、(mk-1)/kB、(mk-1)/(k-1)C、mk/(k-1)D、无法确定【正确答案】：B解析：

设树中结点个数为n，n0=m，n-1=knk，n=n0+nk，所以有knk=m+nk-1，则nk=(m-1)/(k-1)。n=n0+nk=m+(m-1)/(k-1)=(mk-1)/(k-1)。76.12.在长度为n（n≥1）的循环双链表L中，在尾结点之后插入一个新结点的时间复杂度为()。A、O(n2)B、O(n)C、O(1)D、O(nlog2n)【正确答案】：C解析：

循环双链表可以O(1)时间找到尾结点p，再在结点p的后面插入新结点s，时间也是O(1)。答案为C。77.20.关于串的的叙述，不正确的是（）。A、串是字符的有限序列B、空串是由空格构成的串C、替换是串的一种重要运算D、串既可以采用顺序存储，也可以采用链式存储【正确答案】：B78.23.计算机所处理的数据一般具备某种内在联系，这是指（）。A、数据和数据之间存在某种关系B、元素和元素之间存在某种关系C、元素内部具有某种结构D、数据项和数据项之间存在某种关系【正确答案】：B解析：

数据结构中讨论的数据是由数据元素构成的，这些数据元素之间存在某种关系。79.3，4}，下一步选取的目标顶点可能是（）。A、顶点2B、顶点3C、顶点4D、顶点7【正确答案】：D解析：

Dijkstra算法求出源点到某个顶点的最短路径并添加到S中后，后面不再以它作为目标顶点。【正确答案】：为D。80.36.以下叙述中错误的是（）。A、图的遍历是从给定的初始点出发访问每个顶点且每个顶点仅访问一次B、图的深度优先遍历适合无向图C、图的深度优先遍历不适合有向图D、图的深度优先遍历是一个递归过程【正确答案】：C解析：

图的深度优先遍历算法既适合无向图也适合有向图的遍历。81.取。A、{(1，4)，(3，4)，(3，5)，(2，5)}B、{(1，5)，(2，4)，(3，5)}C、{(1，2)，(2，3)，(3，1)}D、{(1，4)，(3，5)，(2，5)，(3，4)}【正确答案】：C解析：

采用Prim算法求最小生成树时，U={1，2，3}，V-U={4，5，…}，候选边只能是这两个顶点集之间的边。【正确答案】：为C。82.12.若串str="Software"，其子串的数目是（）。A、8B、9C、36D、37【正确答案】：D83.50.以下排序方法中，（）不需要进行关键字的比较。A、快速排序B、归并排序C、基数排序D、堆排序【正确答案】：C解析：

在本章介绍的各种排序方法中，基数排序是唯一不基于关键字比较的排序方法。84.14.设s表示串"abcd"，s1表示串"123"，则执行语句s2=InsStr(s,2,s1)后，s2串为（）。A、"123abcd"B、"a123bcd"C、"ab123cd"D、"abc123d"【正确答案】：B85.16.以下排序方法中，()在初始序列已基本有序的情况下，排序效率最高。A、二路归并排序B、快速排序C、直接插入排序D、堆排序【正确答案】：C解析：

二路归并排序和堆排序的效率用初始序列分布无关，而在初始序列已基本有序的情况下快速排序的效率最差。【正确答案】：为C。86.20.顺序查找法适合于存储结构为（）的线性表。A、哈希存储B、顺序存储或链式存储C、压缩存储D、索引存储【正确答案】：B解析：

顺序查找可以从前向后或从后向前依次查找，既适合于顺序存储结构也适合于链式存储结构。87.26.数据结构是指（）的集合以及它们之间的关系。A、数据元素B、计算方法C、逻辑存储D、数据映像【正确答案】：A解析：

数据结构中讨论的数据是由数据元素构成的，这些数据元素之间存在某种关系，数据结构课程中主要讨论相邻关系。88.32.以下关于二叉树的说法中正确的是（）。A、二叉树就是度为2的树B、二叉树中不存在度大于2的结点C、二叉树就是有序树D、二叉树中每个结点的度都为2【正确答案】：B89.12.设有5个元素进栈序列是a、b、c、d、e，其输出序列是c、e、d、b、a，则该栈的容量至少是（）。A、1B、2C、3D、4【正确答案】：D解析：

对应的操作是abc进栈，栈为（a，b，c），c出栈，de进栈，栈为（a，b，d，e），e出栈，d出栈，b出栈，a出栈。栈中最多4个元素。【正确答案】：为D。90.22.以下排序方法中，（）不需要进行关键字的比较。A、快速排序B、归并排序C、基数排序[].堆排序D、以上都不对【正确答案】：C解析：

在各种内排序方法中基数排序不需要关键字比较。【正确答案】：为C。91.21.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。A、数据元素具有同一特点B、不仅数据元素所包含的数据项个数相同，而且对应数据项的类型要一致C、每个数据元素值都相同D、数据元素所包含的数据项的个数要相等【正确答案】：B解析：

因为只有同一类型的数据元素才能归类到同一种结构中，另外在计算机存储器中表示数据元素时，必须为它们定义相同的数据类型。92.33.以下关于二叉树的说法中正确的是（）。A、二叉树中度为0的结点个数等于度为2的结点个数加1B、二叉树中结点个数必大于0C、完全二叉树中任何结点的度为0或2D、二叉树的度为2【正确答案】：A93.≤i≤m）。一个结点的子树个数为该结点的（）。A、权B、维数C、次数（或度）D、序【正确答案】：C94.17.以下（）是"abcd321ABCD"串的子串。A、abcdB、321ABC、"abcABC"D、"21AB"【正确答案】：D95.5.一个有向无环图G的拓扑序列为…，vi，…，vj，…，则不可能出现的情形是()。A、G中有边<vi，vj>B、G中有一条从vi到vj的路径C、G中没有边<vi，vj>D、G中有一条从vj到vi的路径【正确答案】：D解析：

拓扑序列为…，vi，…，vj，…，则vi到vj有边或者路径，如果存在从vj到vi的路径，则存在回路。【正确答案】：为D。96.2.两个栈采用顺序存储结构时，共享同一个数组空间的好处是（）。A、减少存取时间，降低下溢出发生的机率B、节省存储空间，降低上溢出发生的机率C、减少存取时间，降低上溢出发生的机率D、节省存储空间，降低下溢出发生的机率【正确答案】：B解析：

两个栈构成共享栈，元素进栈时迎面生长，这样可节省存储空间，降低上溢出发生的机率。答案：为B。97.次探测。A、k-1B、kC、k+1D、k(k+1)/2【正确答案】：D解析：

最少探测的情况是，第一个同义词放在哈希表ha[d]位置，探测1次，第2个同义词放在哈希表ha[d+1]位置，探测2次，以此类推，第k个同义词放在哈希表ha[d+k-1]位置，探测k次，总的探测次数=1+2+…+k=k(k+1)/2。【正确答案】：为D。98.4.关于线性表的正确说法是（）。A、每个元素都有一个前趋和一个后继元素B、线性表中至少有一个元素C、表中元素的排序顺序必须是由小到大或由大到小D、除第一个元素和最后一个元素外，其余每个元素有且仅有一个前趋和一个后继元素【正确答案】：D解析：

线性表属典型的线性结构。99.22.对于AOE网的关键路径，以下叙述（）是正确的。A、任何一个关键活动提前完成，则整个工程一定会提前完成B、完成整个工程的最短时间是从源点到汇点的最短路径长度C、一个AOE网的关键路径一定是唯一的D、任何一个活动持续时间的改变可能影响关键路径的改变【正确答案】：D解析：

AOE网中的关键路径是从源点到汇点的最长路径，其长度为完成整个工程的最短时间。一个AOE网可能存在多条关键路径，若提前完成所有关键路径都包含的关键活动则整个工程一定会提前完成，但改变任何一个活动的持续时间可能影响关键路径的改变（因为此时关键路径可能发生改变）。答案：为D。100.16.在含有n个结点的单链表中查找第i个结点的平均时间复杂度是()。A、O(log2n)B、O(1)C、O(n2)D、O(n)【正确答案】：D解析：

单链表不具有随机存取特性，查找第i个结点的平均时间复杂度是O(n)。答案为D。1.5.队列是一种对进队、出队操作的次序做了限制的线性表。A、正确B、错误【正确答案】：B解析：

只要队列不满就可以进行进队操作，只要队列不空就可以进行出队操作，并不规定进队列、出队列操作的次序。2.11.图的深度优先遍历算法仅对无向图适用。A、正确B、错误【正确答案】：B解析：

图的深度优先遍历算法对无向图和有向图都适用。3.5.顺序查找法适用于存储结构为顺序或链式存储的线性表。A、正确B、错误【正确答案】：A4.39.n个元素采用二路归并排序算法，总的趟数为n。A、正确B、错误【正确答案】：B解析：

n个元素采用二路归并排序算法，总的趟数为log2n。5.5.线性表中每个元素都有一个前趋元素和一个后继元素。A、正确B、错误【正确答案】：B解析：

开始元素没有前趋元素，终端元素没有后继元素。6.9.k路平衡归并中，败者树的主要作用是减少归并的趟数。A、正确B、错误【正确答案】：B解析：

败者树的主要作用是加速从k个记录中选取最小记录，并不能减少归并的趟数。7.7.采用多路平衡归并方法可以减少初始归并段的个数。A、正确B、错误【正确答案】：B解析：

采用多路平衡归并方法可以减少归并的趟数。8.13.空栈是指栈中元素没有赋值。A、正确B、错误【正确答案】：B解析：

空栈是指栈中没有元素。9.5.一个连通图的生成树是唯一的。A、正确B、错误【正确答案】：B解析：

一个连通图的生成树可能有多棵。10.9.数据对象就是一组任意数据元素的集合。A、正确B、错误【正确答案】：B解析：

数据对象是指具有相同性质的有限个数据元素的集合。11.径。A、正确B、错误【正确答案】：A解析：

顶点i和顶点j属一个连通分量，而顶点k属另一个连通分量，所以顶点i到顶点k没有路径。12.25.简单选择排序是一种不稳定的排序方法。A、正确B、错误【正确答案】：A13.14.非空二叉树的后序序列的最后一个结点一定是叶子结点。A、正确B、错误【正确答案】：A14.序的时间。A、正确B、错误【正确答案】：B解析：

主要取决于内外存数据交换的次数。15.15.任何一个图，一旦指定源点，其深度优先遍历序列是唯一的。A、正确B、错误【正确答案】：B解析：

图的深度优先遍历序列不一定是唯一的。16.29.冒泡排序在最好情况下元素移动的次数为0。A、正确B、错误【正确答案】：A解析：

冒泡排序在初始数据正序时元素移动的次数为0。91、30.冒泡排序中，关键字比较的次数与初始数据序列有关，而元素移动的次数与初始数据序列无17.12.有向图的遍历不可采用广度优先遍历方法。A、正确B、错误【正确答案】：B解析：

广度优先遍历算法适合于有向图和无向图。49、13.图的深度优先遍历算法和广度优先遍历算法是两种不同的算法，所以任何图的这两种遍历序18.5.树中元素之间是多对多的关系。A、正确B、错误【正确答案】：B19.18.非空二叉树的先序序列的最后一个结点一定是叶子结点。A、正确B、错误【正确答案】：A20.36.基数排序与初始数据中关键字的大小无关。A、正确B、错误【正确答案】：B解析：

基数排序与初始数据中关键字的位数有关，也就与关键字的大小有关。21.6.队列是一种对进队、出队操作的次数做了限制的线性表。A、正确B、错误【正确答案】：B解析：

只要队列不满就可以进行进队操作，只要队列不空就可以进行出队操作，并不规定进队列、出队列操作的次数。22.12.相同的n个元素的不同序列通过一个栈一定不会得到相同的出栈序列。A、正确B、错误【正确答案】：B解析：

相同的n个元素的不同序列通过一个栈可能会得到相同的出栈序列。例如，进栈序列1、2、3和23.37.基数排序只适用于以数字为关键字的情况，不适用以字符串为关键字的情况。A、正确B、错误【正确答案】：B24.42.二路归并排序算法的时间复杂度与初始数据序列的顺序无关。A、正确B、错误【正确答案】：A25.9.栈和队列都是限制存取端的线性表。A、正确B、错误【正确答案】：A解析：

栈和队列中元素的逻辑关系都是线性关系，仅限制在端点进行插入和删除操作。26.14.图的遍历就是访问图中所有顶点。A、正确B、错误【正确答案】：B解析：

图的遍历是指以某种顺序访问图中所有顶点，且每个顶点仅访问一次。27.23.从时间性能看，堆排序总是优于简单选择排序。A、正确B、错误【正确答案】：A解析：

堆排序的最好、最坏和平均时间复杂度均为O(nlog2n)，而简单选择排序的最好、最坏和平均时间复杂度均为O(n2)。28.7.在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小。A、正确B、错误【正确答案】：A29.45.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。A、正确B、错误【正确答案】：B30.后移动。A、正确B、错误【正确答案】：B31.7.哈夫曼树是带权路径长度最短的二叉树，权值越大的结点离根结点越远。A、正确B、错误【正确答案】：B32.41.对于不同的初始数据序列，二路归并排序算法中关键字比较次数有所不同。A、正确B、错误【正确答案】：A解析：

二路归并排序算法的时间复杂度与初始数据序列的顺序无关，但关键字比较次数是相关的。33.44.所有内排序算法中的比较次数与初始元素序列的排列无关。A、正确B、错误【正确答案】：B34.16.通常外排序采用多路归并排序方法，实际上也可以用其他内排序方法代替归并排序方法。A、正确B、错误【正确答案】：B35.子。A、正确B、错误【正确答案】：A解析：

二叉排序树的任意一棵子树也是二叉排序树。36.径。A、正确B、错误【正确答案】：A解析：

如果顶点j到顶点k有路径，则顶点i有一条通过顶点j到达顶点k的路径，与题中条件矛盾。37.干块，每块中的数据个数必须相同A、正确B、错误【正确答案】：B解析：

分块查找的数据组织方式为：数据表+索引表，数据表分块，块间有序，块内无序。【正确答案】：为B。38.19.外排序中没有关键字比较。A、正确B、错误【正确答案】：B解析：

外排序中需要关键字比较。39.1.顺序队采用数组存放队中元素，数组具有随机存取特性，所以顺序队中可以随机存取元素。A、正确B、错误【正确答案】：B解析：

顺序队采用数组存放队中元素，尽管数组具有随机存取特性，但队列的操作特性是顺序存取，只能存取两端的元素。40.8.哈夫曼树中结点个数可以偶数也可以是奇数。A、正确B、错误【正确答案】：B41.2.对于无向图生成树，从同一顶点出发所得到的生成树一定是相同的。A、正确B、错误【正确答案】：B解析：

无向图的生成树可能有多棵，从同一顶点出发所得到的生成树也不一定相同。42.17.由二叉树某种遍历方式产生的结果是一个线性序列。A、正确B、错误【正确答案】：A43.2.给定一棵树T，可以找到唯一的一棵二叉树B与之对应。A、正确B、错误【正确答案】：A44.10.图是一种结点之间无层次关系的线性结构。A、正确B、错误【正确答案】：B解析：

图是一种非线性结构。45.11.哈希冲突是指同一个关键字对应多个不同的哈希地址。A、正确B、错误【正确答案】：B解析：

哈希冲突是指多个不同一个关键字对应相同的哈希地址。46.1.给定一棵树T，将其转换成二叉树B后，它们的结点个数相同。A、正确B、错误【正确答案】：A47.3.对于无向图生成树，其深度优先生成树和广度优先生成树一定不相同。A、正确B、错误【正确答案】：B解析：

不一定，如果一个无向图的生成树唯一，从同一顶点出发构造的深度优先生成树和广度优先生成树也是相同的。48.16.非空二叉树的中序序列的第一个结点一定是叶子结点。A、正确B、错误【正确答案】：B49.1.一种逻辑结构的数据只有一种对应的存储结构。A、正确B、错误【正确答案】：B50.20.k路最佳归并树一定是一棵k路平衡树。A、正确B、错误【正确答案】：B解析：

k路最佳归并树不一定是一棵k路平衡树。51.11.有n个不同的元素通过一个栈，产生的所有出栈序列恰好构成这n个元素的全排列。A、正确B、错误【正确答案】：B52.2.顺序查找方法只能从顺序表的前端向后端查找。A、正确B、错误【正确答案】：B解析：

顺序查找方法可以从顺序表的前端向后端查找，也可以从顺序表的后端向前端查找。53.5.置换-选择排序算法的作用是由一个无序文件生成一个全部有序的文件。A、正确B、错误【正确答案】：B54.43.内排序方法要求数据一定以顺序表方式存储。A、正确B、错误【正确答案】：B解析：

有些内排序方法也适合数据采用链表方式存储的情况。55.31.冒泡排序在最好情况下的时间复杂度也是O(n2)。A、正确B、错误【正确答案】：B解析：

冒泡排序在最好情况下的时间复杂度为O(n)。56.数据的逻辑结构。50、19.栈是一种特殊的线性表，其特殊之处在于栈的存储结构比较特殊。A、正确B、错误【正确答案】：B解析：

栈是一种特殊的线性表，其特殊之处在于对线性表的操作做了限制。57.6.数据的运算描述是定义在数据的逻辑结构上的。A、正确B、错误【正确答案】：A解析：

数据的运算描述是定义在数据的逻辑结构上的，而数据运算的具体实现与存储结构相关联。58.26.n个元素采用简单选择排序进行排序，关键字比较的次数总是n(n-1)/2。A、正确B、错误【正确答案】：A59.8.线性表的逻辑顺序总与其物理顺序一致。A、正确B、错误【正确答案】：B解析：

当线性表采用链式存储结构时，其逻辑顺序与物理顺序可能不一致。60.关。A、正确B、错误【正确答案】：B解析：

关键字比较的次数与元素移动的次数都与初始数据序列有关。61.4.在一个含有n（n≥1）个元素的线性表中，所有元素值不能相同。A、正确B、错误【正确答案】：B解析：

在线性表中允许存在元素值相同的元素，但它们的位置是不同。62.22.内排序过程在数据量很大时就变成了外排序过程。A、正确B、错误【正确答案】：B63.35.基数排序与初始数据的次序无关。A、正确B、错误【正确答案】：A64.7.n个元素进队的顺序和出队的顺序总是一致的。A、正确B、错误【正确答案】：A解析：

后进队的元素后出队，先进队的元素先出队。65.6.置换-选择排序算法的作用是由一个无序文件生成若干个有序的子文件。A、正确B、错误【正确答案】：A66.9.线性表的顺序存储结构优于链式存储结构。A、正确B、错误【正确答案】：B解析：

线性表的顺序存储结构和链式存储结构各有优缺点。67.6.哈夫曼树中没有度为1的结点。A、正确B、错误【正确答案】：A68.3.在队空间大小为n的非循环队列中，最多只能进行n次进队操作。A、正确B、错误【正确答案】：A解析：

在非循环队列，元素进队时队尾指针递增，当到达最大下标时不能再进队，所以总计只能进队n次。69.1.k路最佳归并树在外排序中的作用是产生初始归并段。A、正确B、错误【正确答案】：B70.成树。A、正确B、错误【正确答案】：B解析：

这样的子图不一定是连通的。71.值。A、正确B、错误【正确答案】：A72.17.影响外排序的时间因素主要是内存与外存交换信息的次数。A、正确B、错误【正确答案】：A73.个比较的方法选取最小记录，则总共需要396次关键字比较。A、正确B、错误【正确答案】：A解析：

归并趟数s=log55=1，5个记录选取最小记录需比较4次，所以总共需要(100-1)×4×1=396次关键字比较。74.17.栈具有先进后出的特点，其中数据的逻辑结构是任意的。A、正确B、错误【正确答案】：B解析：

栈具有先进后出的特点，其中数据的逻辑结构一定是线性结构，不能是树形结构或图形结构。75.34.直接插入排序、冒泡排序和简单选择排序在最好情况下的时间复杂度均为O(n)。A、正确B、错误【正确答案】：B解析：

直接插入排序和冒泡排序在最好情况下的时间复杂度均为O(n)。76.12.n（n>2）个结点的二叉树中至少有一个度为2的结点。A、正确B、错误【正确答案】：B77.16.栈和队列都是线性表，只是在插入和删除时受到了一些限制。A、正确B、错误【正确答案】：A解析：

栈和队列中元素都呈现线性关系，但它们插入和删除操作有别于线性表。78.2.线性表中的结点按前趋、后继关系可以排成一个线性序列。A、正确B、错误【正确答案】：A解析：

线性表是有限个相同性质的元素的序列。79.24.简单选择排序中，每趟产生的有序区中所有元素在以后的排序中不再改变位置。A、正确B、错误【正确答案】：A80.6.线性表的长度是线性表占用的存储空间的大小。A、正确B、错误【正确答案】：B解析：

线性表的长度是指表中元素个数，属逻辑结构的概念，与线性表占用的存储空间大小无关。81.14.栈是一种特殊的线性表，线性表的所有运算都可以施加在栈上。A、正确B、错误【正确答案】：B解析：

栈是一种特殊的线性表，其特殊之处在于对线性表的插入和删除操作做了限制，所以不能将线性表的所有运算都施加在栈上。82.14.在外排序过程中，一个记录的读入内存的次数和写到外存的次数必定相等。A、正确B、错误【正确答案】：A83.1.线性表中所有元素的数据类型必须相同。A、正确B、错误【正确答案】：A解析：

线性表中所有元素具有相同性质，在设计存储结构时，它们对应的数据类型也必然相同。84.列是不可能相同的。A、正确B、错误【正确答案】：B解析：

图的两种遍历序列可能相同。85.录，则总共需要396次关键字比较。A、正确B、错误【正确答案】：B解析：

归并趟数s=log55=1，采用败者树时，5个记录选取最小记录需比较log25=3次，所以总共需86.间复杂度的主要因素