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

第页数据结构必过复习测试附答案1.32.以下（）方法可用于求无向图的连通分量。A、遍历B、拓扑排序C、Dijkstra算法D、Prim算法【正确答案】：A解析：

从图中某个顶点出发进行遍历，可将与该顶点相连通的所有顶点全部访问，也就找到了该顶点所在的连通分量。2.1.线性表是具有n个（）的有限序列。A、表元素B、字符C、数据元素D、数据项【正确答案】：C解析：

线性表是具有n（n≥0）个数据元素的有限序列，本题答案为C。3.27.n个顶点的连通图的生成树有（）个顶点。A、n-1B、nC、n+1D、不确定【正确答案】：B4.次探测。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。5.8.顺序表具有随机存取特性，指的是（）。A、查找值为x的元素与顺序表中元素个数n无关B、查找值为x的元素与顺序表中元素个数n有关C、查找序号为i的元素与顺序表中元素个数n无关D、查找序号为i的元素与顺序表中元素个数n有关【正确答案】：C解析：

一种存储结构具有随机存取特性指的是，对于给定的序号i，在O(1)时间内找到对应元素值。6.的数据结构为（）。A、数组B、树C、图D、线性表【正确答案】：B7.26.树最适合用来表示（）。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据【正确答案】：C8.结点。A、1+2b+3cB、a+2b+3cC、2b+3cD、1+b+2c【正确答案】：D9.14.对于不带权无向图的邻接矩阵来说，()_。A、第i行上、第i列上非零元素总数等于顶点i的度数B、矩阵中的非零元素个数等于图中的边数C、第i行上的非零元素个数和第i列的非零元素个数一定相等D、邻接矩阵中非全零行的行数等于图中的顶点数【正确答案】：C解析：

无向图的邻接矩阵是一个对称矩阵。【正确答案】：为C。10.树。若遍历后的结点序列为3,1,7,5,6,2,4，则其遍历方式是（）。A、LRNB、NRLC、RLND、RNL【正确答案】：D11.26.给定一个足够大的空栈，有4个元素的进栈次序为A、B、C、D，则以C、D开头的出栈序列的个数为（）。A、1B、2C、3D、4【正确答案】：A解析：

若出栈序列为CD…，则A、B、C进栈，C出栈，D进栈，D出栈，此后只有B出栈和A出栈一种情况，所以这样的出栈序列只有CDBA一个。12.≤i≤m）。一个结点的子树个数为该结点的次数（或度）。A、有0个或1个B、有0个或多个C、有且只有1个D、有1个或1个以上【正确答案】：A13.15.在一个双链表中，删除p所指结点（非首、尾结点）的操作是()。A、p.prior.next=p.next;p.next.prior=p.priorB、p.prior=p.prior.prior;p.prior.prior=pC、p.next.prior=p;p.next=p.next.nextD、p.next=p.prior.prior;p.prior=p.prior.prior【正确答案】：A解析：

在双链表中删除结点p的过程如图A.24所示，访问两步（顺序可以任意），答案为A。14.移方式是（）。A、i=next[j]B、i不变C、j不变D、j=next[j]【正确答案】：B解析：

在KMP算法中，当tj≠si时，i位置不改变。15.（）。A、冒泡排序B、希尔排序C、归并排序D、基数排序【正确答案】：A16.19.下面关于串的叙述中，正确的是（）。A、串是一种特殊的线性表B、串中元素只能是字母C、空串就是空白串D、串的长度必须大于零【正确答案】：A17.14.数据结构通常采用二元组表示：B=(D,R)，其中D表示（）的集合。A、数据项B、数据元素C、数据元素关系D、数据类型【正确答案】：B解析：

二元组(D,R)是数据逻辑结构的一种通用描述方法，其中D是数据元素的集合，R是数据元素关系的集合，在D上可以多种关系，每个关系用序偶来表示。18.58.以下关于排序的叙述中正确的是（）。A、稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率较高B、对同一个顺序表使用不同的排序方法进行排序，得到的排序结果可能不同C、排序方法都是在顺序表上实现的，在链表上无法实现排序方法D、在顺序表上实现的排序方法在链表上也可以实现【正确答案】：B解析：

稳定的排序方法的效率不一定都比不稳定的排序方法高。有些排序方法既可以上顺序表上实现，也可以在链表上实现，但不是所有的排序方法都如此。由于排序方法具有不同的稳定性，所以对同一个顺序表使用不同的排序方法进行排序，得到的排序结果可能不同。19.16.设一棵哈夫曼树中有1999个结点，该哈夫曼树用于对（）个字符进行编码。A、999B、998C、1000D、1001【正确答案】：C20.36.以下叙述中错误的是（）。A、图的遍历是从给定的初始点出发访问每个顶点且每个顶点仅访问一次B、图的深度优先遍历适合无向图C、图的深度优先遍历不适合有向图D、图的深度优先遍历是一个递归过程【正确答案】：C解析：

图的深度优先遍历算法既适合无向图也适合有向图的遍历。21.8.一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（）特性。A、顺序存储B、随机存取C、输入输出D、以上都不对【正确答案】：B解析：

稀疏矩阵采用三元组或者十字链表压缩后均不再具有随机存取特性。22.38.以下关于二叉树遍历的说法中，错误的是（）。A、一棵二叉树中，若每个结点最多只有左孩子，没有右孩子，则先序和后序序列相同B、一棵二叉树中，若每个结点最多只有左孩子，没有右孩子，则中序和后序序列相同C、一棵二叉树中，若每个结点最多只有左孩子，没有右孩子，则先序和层次序列相同D、一棵二叉树中，若每个结点最多只有右孩子，没有左孩子，则先序和中序序列相同【正确答案】：A23.20.关于串的的叙述，不正确的是（）。A、串是字符的有限序列B、空串是由空格构成的串C、替换是串的一种重要运算D、串既可以采用顺序存储，也可以采用链式存储【正确答案】：B24.32.以下关于二叉树的说法中正确的是（）。A、二叉树就是度为2的树B、二叉树中不存在度大于2的结点C、二叉树就是有序树D、二叉树中每个结点的度都为2【正确答案】：B25.排序确定A、外排序所花时间=内排序时间+外存信息读写时间+内部归并所花时间B、外排序并不涉及文件的读写操作C、外排序完全可以由内排序来替代【正确答案】：B解析：

外排序过程主要分为两个阶段：生成初始归并段和对初始归并段进行归并，这两个步骤中都涉及文件的读写操作。26.果是_（）__。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。27.22.对于AOE网的关键路径，以下叙述（）是正确的。A、任何一个关键活动提前完成，则整个工程一定会提前完成B、完成整个工程的最短时间是从源点到汇点的最短路径长度C、一个AOE网的关键路径一定是唯一的D、任何一个活动持续时间的改变可能影响关键路径的改变【正确答案】：D解析：

AOE网中的关键路径是从源点到汇点的最长路径，其长度为完成整个工程的最短时间。一个AOE网可能存在多条关键路径，若提前完成所有关键路径都包含的关键活动则整个工程一定会提前完成，但改变任何一个活动的持续时间可能影响关键路径的改变（因为此时关键路径可能发生改变）。答案：为D。28.操作是（）。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。29.28.在含有n个结点的二叉排序树中查找某关键字的结点时，最多进行（）次比较。A、n/2B、log2nC、log2n+1D、n【正确答案】：D解析：

n个结点的二叉排序树的高度可能为n。30.是（）的集合。A、序偶B、序列C、数据结构D、数据类型【正确答案】：A解析：

二元组(D,R)是数据逻辑结构的一种通用描述方法，其中D是数据元素的集合，R是数据元素关系的集合，在D上可以多种关系，每个关系用序偶来表示。31.叉树根结点的右子树上的结点个数是（）。A、16B、15C、7D、17【正确答案】：B32.28.设有一棵哈夫曼树的结点总数为35，则该哈夫曼树共有（）个叶子结点。A、18B、20C、35D、30【正确答案】：A33.11.顺序表和链表相比存储密度较大，这是因为()。A、顺序表的存储空间是预先分配的B、顺序表不需要增加指针来表示元素之间的逻辑关系C、链表中所有结点的地址是连续的D、顺序表中所有元素的存储地址是不连续的【正确答案】：B解析：

由于顺序表中逻辑上相邻的两个元素在物理上也相邻，不需要增加指针来表示元素之间的逻辑关系，所以存储密度为1，而链表的存储密度总是小于1。答案为B。34.队头元素的前一个位置，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。35.的A、采用拉链法解决冲突时容易引起堆积现象B、以上都不对【正确答案】：B解析：

若哈希地址为0～m-1，序号为i（0≤i≤m-1）的单链表中的结点个数可能有多个，这样查找到任何一个关键字的结点的时间可能不同。拉链法解决冲突时不会出现堆积现象。【正确答案】：为B。36.19.数据结构通常采用二元组表示：B=(D,R)，其中R表示（）的集合。A、数据项B、数据元素C、数据元素关系D、数据类型【正确答案】：C解析：

二元组(D,R)是数据逻辑结构的一种通用描述方法，其中D是数据元素的集合，R是数据元素关系的集合，在D上可以多种关系，每个关系用序偶来表示。37.采用败者树进行，则总的关键字比较次数是（）（用时间复杂度表示）。A、log2m(u-1)(k-1)B、log2m(u-1)(k-1)/log2kC、log2m(u-1)D、log2m(k-1)【正确答案】：C38.22.查找效率低的数据结构是（）。A、有序顺序表B、二叉排序树C、堆D、二叉平衡树【正确答案】：C解析：

堆查找的时间复杂度为O(n)，所以效率最低。39.25.二叉排序中，最大关键字结点的（）。A、没有左孩子结点B、没有右孩子结点C、一定没有左右孩子结点D、一定存在左右孩子结点【正确答案】：B解析：

在二叉排序中，最大关键字结点是中序序列的最后结点，即根结点的最右下结点。40.37.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（）。A、直接插入和快速B、冒泡和快速C、简单选择和直接插入D、简单选择和冒泡【正确答案】：C解析：

简单选择和直接插入肯定要进行n-1趟排序，冒泡排序为1～n-1趟，快速排序为log2n～n-141.51.以下排序方法中，稳定的排序方法是（）。A、快速排序B、堆排序C、希尔排序D、基数排序【正确答案】：D解析：

基数排序是一种稳定的排序方法。42.24.静态查找表和动态查找表的区别是（）。A、它们的逻辑结构相同B、施加其上的操作不同C、所包含的数据元素的类型不同D、存储实现不同【正确答案】：B解析：

由是否支持修改运算（或操作）来确定存放数据元素的表是静态查找表还是动态查找表。43.13.数据结构的研究内容不涉及（）。A、数据如何组织B、数据如何存储C、数据运算如何实现D、算法用什么语言来描述【正确答案】：D解析：

数据结构涉及三方面的内容：数据的逻辑结构（对应选项A），数据的存储结构（对应选项B）和运算（运算包括运算描述和运算实现，后者对应选项C）。44.5.线性表的顺序存储结构是一种（）。（1≤i≤n）的存储地址为LOC(a0)+i×sizeof(ElemType)，也就是说，对于给定的序号i，在O(1)的A、随机存取的存储结构B、顺序存取的存储结构C、索引存取的存储结构D、散列存取的存储结构【正确答案】：A解析：

若含有n个元素的线性表a采用顺序表存储，每个元素的类型为ElemType，则第i个元素ai时间内找到该元素值，这是一种随机存取的存储结构。而顺序存取是一种读写方式，不是存储方式，有别于顺序存储。45.25.设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是（）。A、5、1、2、3、4B、4、5、1、3、2C、4、3、1、2、5D、3、2、1、5、4【正确答案】：D解析：

只有选项D是合法输出序列，其操作是：1进栈，2进栈，3进栈，3出栈，2出栈，1出栈，4进栈，5进栈，5出栈，4出栈。46.22.数据结构课程中讨论的数据一般具有内在的联系，这是指（）。A、数据和数据之间存在一种或多种特定关系B、数据元素和数据元素之间存在一种或多种特定关系C、数据项和数据项之间存在一种或多种特定关系D、同一数据中的所有数据元素值之间存在一种或多种特定关系【正确答案】：B解析：

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。47.6.算法的平均时间复杂度取决于（）。A、问题的规模B、待处理数据的初始状态C、A和BD、计算机的配【正确答案】：A解析：

算法的时间复杂度分为最好、最坏和平均时间复杂度，最好和最坏时间复杂度是考虑若干种实例得到的结果，与初始状态有关，而平均时间复杂度是考虑所有实例的结果，与初始状态无关。答案为A。48.20.顺序查找法适合于存储结构为（）的线性表。A、哈希存储B、顺序存储或链式存储C、压缩存储D、索引存储【正确答案】：B解析：

顺序查找可以从前向后或从后向前依次查找，既适合于顺序存储结构也适合于链式存储结构。49.16.哈希表中出现的哈希冲突是指()。A、两个元素具有相同的序号B、两个元素的关键字不同，而其他属性相同C、数据元素过多D、两个元素的关键字不同，而对应的哈希函数值相同【正确答案】：D解析：

哈希冲突也称为同义词冲突，是指两个元素的关键字不同，而对应的哈希函数值相同。【正确答案】：为D。50.10.由权值分别为9、2、7、5的4个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_()。A、23B、44C、37D、27【正确答案】：B51.≤i≤m）。一个结点的子树个数为该结点的次数（或度）。A、互不相交B、允许相交C、允许叶结点相交D、允许树枝结点相交【正确答案】：A52.4.以下算法的时间复杂度为()。deffun(n):i,s=0,0whiles<=n:i+=1s+=iA、O(n)B、O(√nn)C、O(nloD、2n)E、O(loF、2n)【正确答案】：B解析：

设while循环执行的次数为m，i从0开始，每次循环增加1，则s=1+2+…+m=m(m+1)/2≤n，可以推出m=O(n)。答案为B。53.18.高度为h（h>0）的满二叉树对应的森林由（）棵树构成。A、1B、loC、2hD、h/2E、h【正确答案】：D54.55.下列排序方法中，辅助空间为O(n)的是（）。A、希尔选择B、冒泡排序C、堆排序D、归并排序【正确答案】：D解析：

这几种排序方法中只有归并排序的空间复杂度为O(n)，其余几种排序方法的空间复杂度为O(1)。55.23.计算机所处理的数据一般具备某种内在联系，这是指（）。A、数据和数据之间存在某种关系B、元素和元素之间存在某种关系C、元素内部具有某种结构D、数据项和数据项之间存在某种关系【正确答案】：B解析：

数据结构中讨论的数据是由数据元素构成的，这些数据元素之间存在某种关系。56.33.哈希查找方法一般适用于（）情况下的查找。A、查找表为链表B、查找表为有序表C、关键字集合比地址集合大得多D、关键字集合与地址集合之间存在对应关系【正确答案】：D解析：

关键字集合与地址集合之间存在对应关系时，通过哈希函数表示这种关系，这样查找以计算哈希函数而不是比较的方式进行查找。57.个数是()_。A、10B、nC、5D、2【正确答案】：A解析：

基数排序中队列的个数仅与基数相关，这里基数为10。【正确答案】：为A。58.速排序Ⅳ.二路归并排序A、仅ⅠB、仅Ⅰ、ⅡC、仅Ⅰ、ⅢD、仅Ⅱ、Ⅳ【正确答案】：B解析：

当初始数据基本正序时，直接插入排序和起泡排序的时间复杂度为O(n)。【正确答案】：为B。59.11.最不适合用作链队的链表是（）。A、只带头结点指针的非循环双链表B、只带队首结点指针的循环双链表C、只带队尾结点指针的循环双链表D、以上都不适合【正确答案】：A解析：

只带头结点指针的非循环双链表作为链队时，队头在首部，队尾在尾部，进队和出队操作的时间均为O(1)。【正确答案】：为A。60.10.某算法的空间复杂度为O(1)，则()。A、该算法执行不需要任何辅助空间B、该算法执行所需辅助空间大小与问题规模n无关C、该算法执行不需要任何空间D、该算法执行所需全部空间大小与问题规模n无关【正确答案】：B解析：

一个算法的空间复杂度为O(1)，只能说明其辅助空间大小与问题规模n无关，并不是说该算法不需要空间。答案为B。61.23.若一个具有n个顶点和e条边的无向图是一个森林（n>e），则该森林必有（）棵树。A、eB、nC、n-eD、1【正确答案】：C解析：

设该森林有m棵树，结点个数分别为n1、n2、…、nm，则总顶点数n=n1+n2+…+nm，第i棵树的边数=ni-1，总边数=(n1-1)+(n2-1)+…+(nm-1)=n-m=e，所以m=n-e。62.26.用n个关键字构造的一棵二叉排序树，经过i次关键字比较成功找到的元素个数最多为（）。A、iB、2iC、2i-1D、2i-1【正确答案】：C解析：

二叉排序树中第i层最多有2i-1个结点。63.是()。A、存在，且唯一B、存在、且不唯一C、存在，可能不唯一D、无法确定是否存在【正确答案】：C解析：

这样的有向图中只有顶点i到顶点j（i<j）可能有边，而顶点j到顶点i一定没有边，也就是说这样的有向图中一定没有回路，所以可以产生拓扑序列，但拓扑序列不一定唯一。【正确答案】：为C。64.25.n个顶点的连通图的生成树有（）条边。A、nB、n-1C、n+1D、不确定【正确答案】：B65.叉排序树，若希望高度最小，则应该选择哪个序列插入（）。A、45，24，53，12，37，96，30B、37，24，12，30，53，45，96C、12，24，30，37，45，53，96D、30，24，12，37，45，96，53【正确答案】：B解析：

4个选项对应的关键字序列构造的4棵二叉排序树如图A.32所示，T2是一棵高度为3的满二叉树，高度最小。【正确答案】：为B。66.有序段。A、1B、2C、3D、5【正确答案】：C解析：

产生的有序段是{4,5}，{2,3}，{1}，共3个有序段。67.5.一棵高度为h的非空平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有()个结点。A、2h-1-1B、2h-1C、2h-1+1D、2h-1【正确答案】：D68.个数是（）。A、10B、nC、5D、2【正确答案】：A解析：

基数排序中建立队列个数等于进制数。69.值为()。A、一定是2B、一定是1C、不可能是1D、以上都不对【正确答案】：C解析：

若出栈序列中p1=3，说明1、2先进栈，次栈顶为2，此时可以出栈2（p2=2），或者4进栈再出栈（p2=4），或者4、5进栈再出栈5（p2=5），…，总之p2可能是除了1外的其他整数。【正确答案】：为C。70.47.有n个十进制整数进行基数排序，其中最大的整数为5位，则基数排序的趟数是（）。A、10B、nC、5D、2【正确答案】：C解析：

基数排序的趟数是最大的关键字的位数。48、48.有n个十进制整数进行基数排序，其中最大的整数为5位，则基数排序过程中临时建立的队数71.53.就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是（）。A、堆排序<快速排序<归并排序A、堆排序<归并排序<快速排序B、堆排序>归并排序>快速排序C、堆排序>快速排序>归并排序【正确答案】：A解析：

归并排序的空间复杂度为O(n)，快速排序的空间复杂度为O(log2n)，堆排序的空间复杂度为O(1)。72.18.在一棵m阶B树中删除一个关键字会引起合并，则该结点原有（）个关键字。A、1B、m/2C、m/2-1D、m/2+1【正确答案】：C解析：

在一棵m阶B树中每个内部结点的关键字个数为m/2-1～m-1，删除一个关键字会引起合并，则该结点中关键字个数一定是最少的情况。【正确答案】：为C。73.16.在数据结构中，与所使用的计算机无关的是数据的（）结构。A、逻辑B、存储C、逻辑和存储D、物理【正确答案】：A解析：

逻辑结构与存储结构无关，也就是与使用的计算机无关。74.27.设有13个权值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（）个结点。A、13B、12C、26D、25【正确答案】：D75.21.采用顺序查找方法查找长度为n的线性表时，成功查找的平均查找长度为（）。A、nB、n/2C、(n+1)/2D、(n-1)/2【正确答案】：C解析：

解：顺序查找时，元素ai需i次比较，成功查找的平均查找长度=(1+2+…+n)/n=(n+1)/2。76.1.两个字符串相等的条件是（）。A、串的长度相等B、含有相同的字符集C、都是非空串D、串的长度相等且对应的字符相同【正确答案】：D77.60.内排序方法的稳定性是指（）。A、该排序算法不允许有相同关键字的元素B、该排序算法允许有相同关键字的元素C、平均时间为O(nlog2n)的排序方法D、以上都不对【正确答案】：D78.59.以下不属于内排序方法的是（）。A、二路归并排序B、拓扑排序C、堆排序D、直接插入排序【正确答案】：B解析：

拓扑排序是一种产生拓扑序列的方法，不属内排序方法。79.19.一个链队中，由front和rear分别指向队头和队尾结点，它不具有的功能是()。A、可以实现元素进队操作B、可以由队头指针和队尾指针直接求出队列中的元素个数C、可以实现元素出队操作D、可以由队头指针和队尾指针确定队列为空【正确答案】：B解析：

链队（由front和rear分别指向队头和队尾结点）中不能直接由front和rear求出队列中的元素个数。【正确答案】：为B。80.≤i≤m）。一个结点的子树个数为该结点的（）。A、权B、维数C、次数（或度）D、序【正确答案】：C81.1.以下关于有向图的说法中，正确的是（）。A、强连通图是任何顶点到其他所有顶点都有边B、完全有向图一定是强连通图C、有向图中任一顶点的入度等于出度D、有向图边集的子集和顶点集的子集可构成原有向图的子图【正确答案】：B解析：

完全有向图中任意两个顶点之间都有一条边，一定是强连通图。【正确答案】：为B。82.19.哈希查找方法一般适用于（）情况下的查找。A、查找表为链表B、查找表为有序表C、关键字集合比地址集合大得多D、关键字集合与地址集合之间存在着某种对应关系。【正确答案】：D解析：

哈希表通过哈希函数和冲突解决函数确定存储地址的，适合关键字集合与地址集合之间存在着某种对应关系的数据集的存储与查找。【正确答案】：为D。83.17.在含有n（n>2）个数据结点的数据结构中，开始结点是指（）的结点。A、没有前趋结点B、含有一个或多个前趋结点C、没有后继结点D、含有一个或多个后继结点【正确答案】：A解析：

开始结点是没有任何前趋结点的。84.种要求的排序方法是（）。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。85.17.如图7.1（a）所示的二叉树B是由森林T转换而来的二叉树，那么森林T有（）个叶子结点。A、4B、5C、6D、7【正确答案】：C86.21.线索二叉树中的线索是指（）。A、左孩子B、右孩子C、指针D、标识【正确答案】：C87.9.以下数据结构中元素之间为非线性关系的是()。A、栈B、队列C、线性表D、以上都不是【正确答案】：D解析：

栈、队列和线性表中元素之间的逻辑关系均为线性关系。答案为D。88.10.设有100个元素的有序顺序表，采用折半查找方法，不成功时最大的比较次数是（）。A、25B、50C、10D、7【正确答案】：D解析：

不成功时最大比较次数为log2(n+1)=log2101=7。【正确答案】：为D。89.32.将10个元素散列到大小为10000的哈希表中，（）产生冲突。A、一定会B、一定不会C、仍可能会D、以上都不对【正确答案】：C解析：

无论装填因子大还是小，哈希表仍可能发生冲突。90.42.冒泡排序最少元素移动的次数是（）。A、1B、nC、3n(n-1)/2【正确答案】：A91.35.图的遍历是指（）。A、访问图的所有顶点B、以某种次序访问图的所有顶点C、从一个顶点出发访问图中所有顶点且每个顶点只能访问一次D、从一个顶点出发访问图中所有顶点但每个顶点可以访问多次【正确答案】：C解析：

图的遍历是从给定的初始点出发访问每个顶点且每个顶点仅访问一次。92.7.二分查找和二叉排序树查找的时间性能（）。A、完全相同B、有时不同C、完全不同D、数量级都是O(loE、2n)【正确答案】：B解析：

问题规模为n时，二分查找的时间复杂度为O(log2n)，而二叉排序树查找与树高相关，介于O(log2n)～O(n)，所以二分查找和二叉排序树查找的时间性能不是完全相同，也不是完全不同，只能说有时不同。【正确答案】：为B。93.12.以下关于哈希查找的叙述中正确的是()_。A、哈希查找中不需要任何关键字的比较B、采用拉链法解决冲突时，查找每个元素的时间是相同的C、哈希表在查找成功时的平均查找长度仅仅与表长有关D、哈希表的装填因子等于表中填入的元素个数除以哈希表的长度【正确答案】：D解析：

装填因子等于表中填入的元素个数n除以哈希表的长度m。【正确答案】：为D。94.56.下列排序方法中，（）在一趟结束后不一定能选出一个元素放在其最终位置上。A、简单选择排序B、冒泡排序C、归并排序D、堆排序【正确答案】：C解析：

因为归并排序每趟并不一定产生全局有序区。95.31.在一个图中，每个顶点的前趋顶点和后继顶点数可以有（）。A、1个B、2个C、任意多个D、0个【正确答案】：C解析：

图中顶点之间是多对多的相邻关系。96.前一位置，r指向队尾元素），元素x出队的操作是（）;x=qu.data[qu.f]。A、qu.r+=1B、qu.r=(qu.r+1)%NC、qu.f+=1D、qu.f=(qu.f+1)%N【正确答案】：D解析：

这里f指向队首元素的前一位置，r指向队尾元素，所以出队操作先循环移动f。【正确答案】：为D。97.11.设目标串为s，模式串为t，在KMP模式匹配中，next[4]=2的含义是()。A、表示t4字符前面最多有2个字符和开头的2个字符相同B、表示s4字符前面最多有2个字符和开头的2个字符相同C、表示目标串匹配失败的位置是i=4D、表示模式串匹配失败的位置是j=2【正确答案】：A解析：

KMP算法中next数组表示模式串t的部分匹配信息，next[4]=2表示字符t4前面最多有2个字符和t开头的2个字符相同。【正确答案】：为A。98.16.串是一种特殊的线性表，其特殊性体现在（）。A、可以顺序存储B、数据元素是单个字符C、可以链接存储D、数据元素可以是多个字符【正确答案】：B99.20.中缀表达式“2*(3+4)-1”的后缀表达式是（）。A、2341*+-B、234+*1–C、234*+1–D、-+*2341【正确答案】：B解析：

对于每个选项按后缀表达式方式求解，看是否与中缀表达式“2*(3+4)-1”的计算顺序一致。【正确答案】：为B。100.）个虚段。A、uB、k-uC、k-1-uD、u-1【正确答案】：C1.子。A、正确B、错误【正确答案】：A解析：

二叉排序树的任意一棵子树也是二叉排序树。2.5.树中元素之间是多对多的关系。A、正确B、错误【正确答案】：B3.22.内排序过程在数据量很大时就变成了外排序过程。A、正确B、错误【正确答案】：B4.23.从时间性能看，堆排序总是优于简单选择排序。A、正确B、错误【正确答案】：A解析：

堆排序的最好、最坏和平均时间复杂度均为O(nlog2n)，而简单选择排序的最好、最坏和平均时间复杂度均为O(n2)。5.7.线性表的存储结构大小与线性表中元素类型有关。A、正确B、错误【正确答案】：A解析：

线性表的存储结构大小等于线性表中所有元素存储空间之和，而线性表中元素类型不同，每个元素所占用的存储空间大小也可能不同。6.干块，每块中的数据个数必须相同A、正确B、错误【正确答案】：B解析：

分块查找的数据组织方式为：数据表+索引表，数据表分块，块间有序，块内无序。【正确答案】：为B。7.17.栈具有先进后出的特点，其中数据的逻辑结构是任意的。A、正确B、错误【正确答案】：B解析：

栈具有先进后出的特点，其中数据的逻辑结构一定是线性结构，不能是树形结构或图形结构。8.5.队列是一种对进队、出队操作的次序做了限制的线性表。A、正确B、错误【正确答案】：B解析：

只要队列不满就可以进行进队操作，只要队列不空就可以进行出队操作，并不规定进队列、出队列操作的次序。9.34.直接插入排序、冒泡排序和简单选择排序在最好情况下的时间复杂度均为O(n)。A、正确B、错误【正确答案】：B解析：

直接插入排序和冒泡排序在最好情况下的时间复杂度均为O(n)。10.8.数据的运算就是指基本运算，只能对数据实施基本运算。A、正确B、错误【正确答案】：B解析：

数据的基本运算只是数据运算的一部分，它是常用的数据运算，但并非就是数据运算的全部，也可以对数据实施非基本运算。11.17.影响外排序的时间因素主要是内存与外存交换信息的次数。A、正确B、错误【正确答案】：A12.25.简单选择排序是一种不稳定的排序方法。A、正确B、错误【正确答案】：A13.19.外排序中没有关键字比较。A、正确B、错误【正确答案】：B解析：

外排序中需要关键字比较。14.成树。A、正确B、错误【正确答案】：B解析：

这样的子图不一定是连通的。15.1.一种逻辑结构的数据只有一种对应的存储结构。A、正确B、错误【正确答案】：B16.14.非空二叉树的后序序列的最后一个结点一定是叶子结点。A、正确B、错误【正确答案】：A17.3.非线性结构中，每个元素最多只有一个前趋元素。A、正确B、错误【正确答案】：B解析：

非线性结构中，每个元素可能有多个前趋元素。18.7.n个元素进队的顺序和出队的顺序总是一致的。A、正确B、错误【正确答案】：A解析：

后进队的元素后出队，先进队的元素先出队。19.13.哈希表发生冲突是由于选取的解决冲突的方法不当造成的。A、正确B、错误【正确答案】：B解析：

哈希表发生冲突是由于选取的哈希函数不合适造成的。20.5.顺序查找法适用于存储结构为顺序或链式存储的线性表。A、正确B、错误【正确答案】：A21.9.栈和队列都是限制存取端的线性表。A、正确B、错误【正确答案】：A解析：

栈和队列中元素的逻辑关系都是线性关系，仅限制在端点进行插入和删除操作。22.15.为了提高外排序的速度，在外排序中必须选用最快的内排序算法。A、正确B、错误【正确答案】：B解析：

外排序的第二阶段只能采用归并排序算法。23.8.线性表的逻辑顺序总与其物理顺序一致。A、正确B、错误【正确答案】：B解析：

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

如果顶点j到顶点k有路径，则顶点i有一条通过顶点j到达顶点k的路径，与题中条件矛盾。25.16.通常外排序采用多路归并排序方法，实际上也可以用其他内排序方法代替归并排序方法。A、正确B、错误【正确答案】：B26.1.顺序队采用数组存放队中元素，数组具有随机存取特性，所以顺序队中可以随机存取元素。A、正确B、错误【正确答案】：B解析：

顺序队采用数组存放队中元素，尽管数组具有随机存取特性，但队列的操作特性是顺序存取，只能存取两端的元素。27.10.图是一种结点之间无层次关系的线性结构。A、正确B、错误【正确答案】：B解析：

图是一种非线性结构。28.16.非空二叉树的中序序列的第一个结点一定是叶子结点。A、正确B、错误【正确答案】：B29.11.图的深度优先遍历算法仅对无向图适用。A、正确B、错误【正确答案】：B解析：

图的深度优先遍历算法对无向图和有向图都适用。30.43.内排序方法要求数据一定以顺序表方式存储。A、正确B、错误【正确答案】：B解析：

有些内排序方法也适合数据采用链表方式存储的情况。31.18.非空二叉树的先序序列的最后一个结点一定是叶子结点。A、正确B、错误【正确答案】：A32.2.给定一棵树T，可以找到唯一的一棵二叉树B与之对应。A、正确B、错误【正确答案】：A33.要(100-1)×3×1=297次关键字比较。73、12.减少初始归并段的个数，可以使外排序的时间缩短。A、正确B、错误【正确答案】：A34.8.一个图中的简单路径是指该路径上的边不重复出现。A、正确B、错误【正确答案】：B解析：

一个图中的简单路径是指该路径上的顶点不重复出现。35.5.置换-选择排序算法的作用是由一个无序文件生成一个全部有序的文件。A、正确B、错误【正确答案】：B36.9.二叉树中每个度为2的结点的两棵子树都是有序的。A、正确B、错误【正确答案】：A37.1.线性表中所有元素的数据类型必须相同。A、正确B、错误【正确答案】：A解析：

线性表中所有元素具有相同性质，在设计存储结构时，它们对应的数据类型也必然相同。38.26.n个元素采用简单选择排序进行排序，关键字比较的次数总是n(n-1)/2。A、正确B、错误【正确答案】：A39.24.简单选择排序中，每趟产生的有序区中所有元素在以后的排序中不再改变位置。A、正确B、错误【正确答案】：A40.15.栈和线性表是两种不同的数据结构，它们的数据元素的逻辑关系也不同。A、正确B、错误【正确答案】：B解析：

栈和线性表是两种不同的数据结构，但它们的数据元素的逻辑关系都是线性关系。41.2.数据的逻辑结构与各数据元素在计算机中如何存储有关。A、正确B、错误【正确答案】：B解析：

数据的逻辑结构与存储结构无关。42.列是不可能相同的。A、正确B、错误【正确答案】：B解析：

图的两种遍历序列可能相同。43.44.所有内排序算法中的比较次数与初始元素序列的排列无关。A、正确B、错误【正确答案】：B44.27.简单选择排序在初始数据正序时，其时间复杂度为O(n)。A、正确B、错误【正确答案】：B45.11.哈希冲突是指同一个关键字对应多个不同的哈希地址。A、正确B、错误【正确答案】：B解析：

哈希冲突是指多个不同一个关键字对应相同的哈希地址。46.29.冒泡排序在最好情况下元素移动的次数为0。A、正确B、错误【正确答案】：A解析：

冒泡排序在初始数据正序时元素移动的次数为0。91、30.冒泡排序中，关键字比较的次数与初始数据序列有关，而元素移动的次数与初始数据序列无47.37.基数排序只适用于以数字为关键字的情况，不适用以字符串为关键字的情况。A、正确B、错误【正确答案】：B48.变为…,R[j],…,R[i],…，则该排序算法是稳定的。A、正确B、错误【正确答案】：B解析：

该排序算法是不稳定的。108、1.等有8个长度为2、5、3、10、4、7、9、18的初始归并段，采用3路归并，在其最佳归并树中49.间复杂度的主要因素。正确错误A、正确B、错误【正确答案】：B解析：

影响算法时间复杂度的主要因素是移动元素的次数和关键字比较的次数。50.1.k路最佳归并树在外排序中的作用是产生初始归并段。A、正确B、错误【正确答案】：B51.42.二路归并排序算法的时间复杂度与初始数据序列的顺序无关。A、正确B、错误【正确答案】：A52.36.基数排序与初始数据中关键字的大小无关。A、正确B、错误【正确答案】：B解析：

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

只要队列不满就可以进行进队操作，只要队列不空就可以进行出队操作，并不规定进队列、出队列操作的次数。54.12.n（n>2）个结点的二叉树中至少有一个度为2的结点。A、正确B、错误【正确答案】：B55.13.二叉树就是度为2的有序树。A、正确B、错误【正确答案】：B56.14.在外排序过程中，一个记录的读入内存的次数和写到外存的次数必定相等。A、正确B、错误【正确答案】：A57.6.哈夫曼树中没有度为1的结点。A、正确B、错误【正确答案】：A58.40.二路归并排序算法是稳定的。A、正确B、错误【正确答案】：A59.8.哈夫曼树中结点个数可以偶数也可以是奇数。A、正确B、错误【正确答案】：B60.12.有向图的遍历不可采用广度优先遍历方法。A、正确B、错误【正确答案】：B解析：

广度优先遍历算法适合于有向图和无向图。49、13.图的深度优先遍历算法和广度优先遍历算法是两种不同的算法，所以任何图的这两种遍历序61.13.空栈是指栈中元素没有赋值。A、正确B、错误【正确答案】：B解析：

空栈是指栈中没有元素。62.7.哈夫曼树是带权路径长度最短的二叉树，权值越大的结点离根结点越远。A、正确B、错误【正确答案】：B63.18.栈的定义不涉及数据的逻辑结构。A、正确B、错误【正确答案】：B解析：

栈的定义不涉及数据的存储结构，栈中数据元素的逻辑关系属于线性关系，所以栈的定义涉及64.序的时间。A、正确B、错误【正确答案】：B解析：

主要取决于内外存数据交换的次数。65.7.n个顶点的无向图至多有n(n-1)条边。A、正确B、错误【正确答案】：B解析：

n个顶点的无向图至多有n(n-1)/2条边。66.3.对于不同的存储结构，应采用不同的查找方法。A、正确B、错误【正确答案】：A67.7.采用多路平衡归并方法可以减少初始归并段的个数。A、正确B、错误【正确答案】：B解析：

采用多路平衡归并方法可以减少归并的趟数。68.4.在队空间大小为n的循环队列中，最多只能进行n次进队操作。A、正确B、错误【正确答案】：B解析：

在循环队列中，元素出队后，其位置空了出来，可以让其他元素进队，所以理论上讲可以进队任意次。69.12.哈希表中所有的哈希地址是连续的。A、正确B、错误【正确答案】：A70.径。A、正确B、错误【正确答案】：A解析：

顶点i和顶点j属一个连通分量，而顶点k属另一个连通分量，所以顶点i到顶点k没有路径。71.6.线性表的长度是线性表占用的存储空间的大小。A、正确B、错误【正确答案】：B解析：

线性表的长度是指表中元素个数，属逻辑结构的概念，与线性表占用的存储空间大小无关。72.个比较的方法选取最小记录，则总共需要396次关键字比较。A、正确B、错误【正确答案】：A解析：

归并趟数s=log55=1，5个记录选取最小记录需比较4次，所以总共需要(100-1)×4×1=396次关键字比较。73.数据的逻辑结构。50、19.栈是一种特殊的线性表，其特殊之处在于栈的存储结构比较特殊。A、正确B、错误【正确答案】：B解析：

栈是一种特殊的线性表，其特殊之处在于对线性表的操作做了限制。74.5.一个连通图的生成树是唯一的。A、正确B、错误【正确答案】：B解析：

一个连通图的生成树可能有多棵。75.39.n个元素采用二路归并排序算法，总的趟数为n。A、正确B、错误【正确答案】：B解析：

n个元素采用二路归并排序算法，总的趟数为log2n。76.9.数据对象就是一组任意数据元素的集合。A、正确B、错误【正确答案】：B解析：

数据对象是指具有相同性质的有限个数据元素的集合。77.9.k路平衡归并中，败者树的主要作用是减少归并的趟数。A、正确B、错误【正确答案】：B解析：

败者树的主要作用是加速从k个记录中选取最小记录，并不能减少归并的趟数。78.2.对于无向图生成树，从同一顶点出发所得到的生成树一定是相同的。A、正确B、错误【正确答案】：B解析：

无向图的生成树可能有多棵，从同一顶点出发所得到的生成树也不一定相同。79.45.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。A、正确B、错误【正确答案】：B80.17.由二叉树某种遍历方式产生的结果是一个线性序列。A、正确B、错误【正确答案】：A81.查找、折半查找和分块查找。A、正确B、错误【正确答案】：B解析：

在顺序存储的物理介质如磁带上，只能进行顺序查找，即便文件有序，也不能进行折半查找。82.9.线性表的顺序存储结构优于链式存储结构。A、正确B、错误【正确答案】：B解析：

线性表的顺序存储结构和链式存储结构各有优缺点。83.录，则总共需要396次关键字比较。A、正确B、错误【正确答案】：B解析：

归并趟数s=log55=1，采用败者树时，5个记录选取最小记录需比较log25=3次，所以总共需84.6.置换-选择排序算法的作用是由一个无序文件生成若干个有序的子文件。A、正确B、错误【正确答案】：A85.20.k路最佳归并树一定是一棵k路平衡树。A、正确B、错误【正确答案】：B解析：

k路最佳归并树不一定是一棵k路平衡树。86.16.栈和队列都是线性表，只是在插入和删除时受到了一些限制。A、正确B、错误【正确答案】：A解析：

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

线性表是有限个相同性