数据结构必过复习试题含答案

第页数据结构必过复习试题含答案1.拓扑序列中，若顶点a在顶点b之前，则图中必有一条边<a，b>A、仅ⅠB、仅Ⅰ、ⅢC、仅Ⅱ、ⅢD、Ⅰ、Ⅱ和ⅢE、图的遍历是从给定的初始点出发访问每个顶点且每个顶点仅访问一次F、图的深度优先遍历适合无向图G、图的深度优先遍历不适合有向图H、图的深度优先遍历是一个递归过程【正确答案】：A解析：

在一个有向图的拓扑序列中，若顶点a在顶点b之前，图中不一定有边<a，b>。【正确答案】：为A。10、10.以下叙述中错误的是（）。【正确答案】：C图的深度优先遍历适合无向图和有向图。【正确答案】：为C。2.21.采用顺序查找方法查找长度为n的线性表时，成功查找的平均查找长度为（）。A、nB、n/2C、(n+1)/2D、(n-1)/2【正确答案】：C解析：

解：顺序查找时，元素ai需i次比较，成功查找的平均查找长度=(1+2+…+n)/n=(n+1)/2。3.移方式是（）。A、i=next[j]B、i不变C、j不变D、j=next[j]【正确答案】：B解析：

在KMP算法中，当tj≠si时，i位置不改变。4.4.以下最适合用作链队的不带头结点的链表是（）。A、只带首结点指针的循环单链表B、只带尾结点指针的单链表C、只带首结点指针的单链表D、只带尾结点指针的循环单链表【正确答案】：D解析：

只带尾结点指针的循环单链表的进队操作和出队操作时间复杂度为O(1)。【正确答案】：为D。5.1.若某非空二叉树的中序序列和后序序列正好相反，则该二叉树的形态是（）。A、只有一个根结点B、所有分支结点都有左右孩子C、所有结点没有左子树D、所有结点没有右子树【正确答案】：C6.()来保存这些数据。A、线性表B、队列C、栈D、单链表【正确答案】：B解析：

队列具有先进先出的特点。【正确答案】：为B。7.20.在数据结构中，以下说法中不正确的是（）。A、数据元素是数据的基本单位B、数据项是不可分割的最小可标识单位C、数据可由若干个数据元素构成D、数据项可由若干个数据元素构成【正确答案】：D解析：

数据元素可由若干个数据项构成，而数据项不能再拆分，否则就没有意义了。8.≤i≤m）。一个结点的子树个数为该结点的（）。A、权B、维数C、次数（或度）D、序【正确答案】：C9.值为()。A、一定是2B、一定是1C、不可能是1D、以上都不对【正确答案】：C解析：

若出栈序列中p1=3，说明1、2先进栈，次栈顶为2，此时可以出栈2（p2=2），或者4进栈再出栈（p2=4），或者4、5进栈再出栈5（p2=5），…，总之p2可能是除了1外的其他整数。【正确答案】：为C。10.3，4}，下一步选取的目标顶点可能是（）。A、顶点2B、顶点3C、顶点4D、顶点7【正确答案】：D解析：

Dijkstra算法求出源点到某个顶点的最短路径并添加到S中后，后面不再以它作为目标顶点。【正确答案】：为D。11.13.若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图()。A、是个有根有向图B、是个强连通图C、含有多个入度为0的顶点D、含有顶点数目大于1的强连通分量【正确答案】：D解析：

该图中存在回路，该回路构成一个强连通分量的一部分或全部。【正确答案】：为D。12.()。A、5B、6C、7D、8【正确答案】：D13.27.n个顶点的连通图的生成树有（）个顶点。A、n-1B、nC、n+1D、不确定【正确答案】：B14.45.以下（）方法在数据基本有序时效率最好。A、快速排序B、冒泡排序C、堆排序D、希尔排序【正确答案】：B15.51.以下排序方法中，稳定的排序方法是（）。A、快速排序B、堆排序C、希尔排序D、基数排序【正确答案】：D解析：

基数排序是一种稳定的排序方法。16.8.下面（）算法适合用于构造一个稠密图的最小生成树。A、Dijkstra算法B、Prim算法C、Floyd算法D、Kruskal算法【正确答案】：B解析：

Prim算法和Kruskal算法用于构造一个带权连通图（顶点个数为n，边数为e）的最小生成树，前者的时间复杂度为O(n2)，后者的时间复杂度为O(elog2e)。【正确答案】：为B。17.队头元素的前一个位置，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。18.33.以下关于二叉树的说法中正确的是（）。A、二叉树中度为0的结点个数等于度为2的结点个数加1B、二叉树中结点个数必大于0C、完全二叉树中任何结点的度为0或2D、二叉树的度为2【正确答案】：A19.5.线性表的顺序存储结构是一种（）。（1≤i≤n）的存储地址为LOC(a0)+i×sizeof(ElemType)，也就是说，对于给定的序号i，在O(1)的A、随机存取的存储结构B、顺序存取的存储结构C、索引存取的存储结构D、散列存取的存储结构【正确答案】：A解析：

若含有n个元素的线性表a采用顺序表存储，每个元素的类型为ElemType，则第i个元素ai时间内找到该元素值，这是一种随机存取的存储结构。而顺序存取是一种读写方式，不是存储方式，有别于顺序存储。20.个数据递增排序，最好的时间复杂度为()。A、O(nloB、2n)C、O(nloD、2k)E、O(kloF、2n)G、O(kloH、2k)【正确答案】：B解析：

每个组内k个元素采用基于比较的排序方法排序最好时间复杂度为O(klog2k)，整个元素序列排序的最好时间复杂度为O(klog2k)×n/k=O(nlog2k)。【正确答案】：为B。21.53.就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是（）。A、堆排序<快速排序<归并排序A、堆排序<归并排序<快速排序B、堆排序>归并排序>快速排序C、堆排序>快速排序>归并排序【正确答案】：A解析：

归并排序的空间复杂度为O(n)，快速排序的空间复杂度为O(log2n)，堆排序的空间复杂度为O(1)。22.{0，2，3，4}，下一步选取的目标顶点可能是()。A、顶点2B、顶点3C、顶点4D、顶点7【正确答案】：D解析：

Dijkstra算法执行中，一旦某个顶点v添加到S中，后面不再调整源点到v的最短路径。【正确答案】：为D。23.31.二叉树中所有结点的度之和等于结点数加（）。A、1B、-1C、2【正确答案】：B24.到一维数组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。25.4.采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是()。A、递归次数与初始数据的排列次序无关B、每次划分后，先处理较长的分区可以减少递归次数C、每次划分后，先处理较短的分区可以减少递归次数D、递归次数与每次划分后得到的分区处理顺序无关【正确答案】：D解析：

快速排序将一个无序序列划分为两个无序子序列，这两个无序子序列的排序是独立的，先排序哪一个都可以。【正确答案】：为D。26.17.与单链表相比，双链表的优点之一是()。A、插入、删除操作更简单B、可以进行随机访问C、可以省略表头指针或表尾指针D、访问前后相邻结点更方便【正确答案】：D解析：

单链表只能通过指针向后遍历，而双链表可以通过前后指针双向遍历，所以访问前后相邻结点更方便。答案为D。27.17.设有100个元素的有序表，用折半查找时，不成功时最大的比较次数是（）。A、25B、50C、10D、7【正确答案】：D解析：

不成功时最大的比较次数=log2(n+1)=7。【正确答案】：为D。28.叉排序树，若希望高度最小，则应该选择哪个序列插入（）。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。29.的排序方法是（）。A、简单选择排序B、快速排序C、冒泡排序D、直接插入排序【正确答案】：A解析：

从数据排列次序的变化过程看到，每一趟都从无序区中选一个最小的元素归位。30.14.设s表示串"abcd"，s1表示串"123"，则执行语句s2=InsStr(s,2,s1)后，s2串为（）。A、"123abcd"B、"a123bcd"C、"ab123cd"D、"abc123d"【正确答案】：B31.17.在含有n（n>2）个数据结点的数据结构中，开始结点是指（）的结点。A、没有前趋结点B、含有一个或多个前趋结点C、没有后继结点D、含有一个或多个后继结点【正确答案】：A解析：

开始结点是没有任何前趋结点的。32.35.二叉树若用顺序存储结构表示，则下列4种运算中的（）最容易实现。A、先序遍历二叉树B、中序遍历二叉树C、层次遍历二叉树D、根据结点的值查找其存储位置【正确答案】：C33.≤i≤m）。一个结点的子树个数为该结点的次数（或度）。A、有0个或1个B、有0个或多个C、有且只有1个D、有1个或1个以上【正确答案】：A34.种要求的排序方法是（）。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。35.26.数据结构是指（）的集合以及它们之间的关系。A、数据元素B、计算方法C、逻辑存储D、数据映像【正确答案】：A解析：

数据结构中讨论的数据是由数据元素构成的，这些数据元素之间存在某种关系，数据结构课程中主要讨论相邻关系。36.趟。38、38.在一般情况下，以下排序算法中元素移动次数最少的（）。A、直接插入排序B、冒泡排序C、简单选择排序D、都一样【正确答案】：C解析：

简单选择排序移动元素的次数为0～3(n-1)，在一般情况下，比直接插入排序和冒泡排序移动元素次数要少。37.32.将10个元素散列到大小为10000的哈希表中，（）产生冲突。A、一定会B、一定不会C、仍可能会D、以上都不对【正确答案】：C解析：

无论装填因子大还是小，哈希表仍可能发生冲突。38.13.在长度为n（n≥1）的双链表L中，在p结点之前插入一个新结点s的时间复杂度为（）。A、O(1)B、O(n)C、O(n2)D、O(nlog2n)【正确答案】：A解析：

双链表中给定p结点后，可以直接找到其前驱结点pre，再在pre结点和p结点之间插入结点s。答案为A。39.8.设n是描述问题规模的非负整数，下面程序段的时间复杂度为()。x=1whilex<=n:x=5*xA、O(loB、5n)C、O(n)D、O(nloE、5n)F、O(n5)【正确答案】：A解析：

设while循环的次数为m，x从1开始每次循环按5倍递增，有x=5m≤n，即m≤log5n=O(log5n)。答案为A。40.操作是（）。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。41.69，88）则所采用的排序方法是（）。A、快速排序B、简单选择排序C、直接插入排序D、二路归并排序【正确答案】：A解析：

从元素序列的变化情况看，不可能是简单选择排序（因为前后没有产生全局有序区），不可能是直接插入排序（因为前后没有产生局部有序区），也不可能是二路归并排序。【正确答案】：为A。42.6.在一棵非空二叉树的先序序列和后序序列中，各叶子之间的相对次序关系()。A、不一定相同A、都相同B、都不相同C、互为逆序【正确答案】：B43.18.关于串的叙述，正确的是（）。A、串是含有一个或多个字符的有穷序列B、空串是只含有空格字符的串C、空串是含有零个字符或含有空格字符的串D、串是含有零个或多个字符的有穷序列【正确答案】：D44.4.关于线性表的正确说法是（）。A、每个元素都有一个前趋和一个后继元素B、线性表中至少有一个元素C、表中元素的排序顺序必须是由小到大或由大到小D、除第一个元素和最后一个元素外，其余每个元素有且仅有一个前趋和一个后继元素【正确答案】：D解析：

线性表属典型的线性结构。45.50.以下排序方法中，（）不需要进行关键字的比较。A、快速排序B、归并排序C、基数排序D、堆排序【正确答案】：C解析：

在本章介绍的各种排序方法中，基数排序是唯一不基于关键字比较的排序方法。46.57.初始数据序列中有两个相同关键字的元素，通过不稳定的排序方法排序后，（）。A、这两个元素的前后位置不发生变化B、这两个元素的前后位置一定发生变化C、这两个元素的位置不发生变化D、这两个元素的前后位置可能发生变化【正确答案】：D47.6.在KMP算法中，模式串"ababaabab"的next数组值为（）。A、-1,0,0,1,2,3,1,2,3B、-1,0,0,1,2,1,1,2,3C、-1,0,0,1,2,3,4,1,2D、-1,0,0,1,2,3,1,2,2【正确答案】：A解析：

求模式串"ababaabab"的next数组的过程如表A.1所示。【正确答案】：为A。48.11.对于有n个顶点的带权连通图，它的最小生成树是指图中任意一个（）。A、由n-1条权值最小的边构成的子图B、由n-l条权值之和最小的边构成的子图C、由n个顶点构成的极大连通子图D、由n个顶点构成的极小连通子图，且边的权值之和最小【正确答案】：D解析：

最小生成树是图中所有顶点构成的极小连通子图，且边的权值之和最小。【正确答案】：为D。题型：49.16.哈希表中出现的哈希冲突是指()。A、两个元素具有相同的序号B、两个元素的关键字不同，而其他属性相同C、数据元素过多D、两个元素的关键字不同，而对应的哈希函数值相同【正确答案】：D解析：

哈希冲突也称为同义词冲突，是指两个元素的关键字不同，而对应的哈希函数值相同。【正确答案】：为D。50.24.一个栈的输入序列为1、2、3、4、5，则下列序列中不可能是栈的输出序列的是（）。A、2、3、4、1、5B、5、4、1、3、2C、2、3、1、4、5D、1、5、4、3、2【正确答案】：B解析：

当出栈序列的第一个元素为5时，只有唯一的出栈序列5、4、3、2、1，不可能有5、4、1、3、2的出栈序列。本题【正确答案】：为B。51.22.对于AOE网的关键路径，以下叙述（）是正确的。A、任何一个关键活动提前完成，则整个工程一定会提前完成B、完成整个工程的最短时间是从源点到汇点的最短路径长度C、一个AOE网的关键路径一定是唯一的D、任何一个活动持续时间的改变可能影响关键路径的改变【正确答案】：D解析：

AOE网中的关键路径是从源点到汇点的最长路径，其长度为完成整个工程的最短时间。一个AOE网可能存在多条关键路径，若提前完成所有关键路径都包含的关键活动则整个工程一定会提前完成，但改变任何一个活动的持续时间可能影响关键路径的改变（因为此时关键路径可能发生改变）。答案：为D。52.29.在一个无向图中，所有顶点的度之和等于边数的（）倍。A、1/2B、1C、2D、4【正确答案】：C解析：

在无向图中，一条边计入两个顶点的度数。53.排序确定A、外排序所花时间=内排序时间+外存信息读写时间+内部归并所花时间B、外排序并不涉及文件的读写操作C、外排序完全可以由内排序来替代【正确答案】：B解析：

外排序过程主要分为两个阶段：生成初始归并段和对初始归并段进行归并，这两个步骤中都涉及文件的读写操作。54.56.下列排序方法中，（）在一趟结束后不一定能选出一个元素放在其最终位置上。A、简单选择排序B、冒泡排序C、归并排序D、堆排序【正确答案】：C解析：

因为归并排序每趟并不一定产生全局有序区。55.42.冒泡排序最少元素移动的次数是（）。A、1B、nC、3n(n-1)/2【正确答案】：A56.31.给定一个空栈，若元素10、20、23、13依次进栈，然后有两个数出栈，又有3个数进栈，第一次进栈的元素23现在（）。A、已出栈B、从栈底算起第3个C、处于栈顶D、从栈底算起第4个【正确答案】：A解析：

本题的操作是：元素10、20、23、13依次进栈，然后出栈13和23，再进栈3个元素，第一次进栈的元素23已出栈了。57.15.适合于折半查找的数据组织方式是()。A、以链表存储的线性表B、以顺序表存储的任意线性表C、以链表存储的有序线性表D、以顺序表存储的有序线性表【正确答案】：D解析：

折半查找的元素序列一定是有序的，并且采用具有随机存取特性的存储结构存储。【正确答案】：为D。58.32.以下（）方法可用于求无向图的连通分量。A、遍历B、拓扑排序C、Dijkstra算法D、Prim算法【正确答案】：A解析：

从图中某个顶点出发进行遍历，可将与该顶点相连通的所有顶点全部访问，也就找到了该顶点所在的连通分量。59.14.一棵高度为h（h≥1）的完全二叉树至少有（）个结点。A、2h-1B、2hC、2h+1D、2h-1+1【正确答案】：A60.16.以下排序方法中，()在初始序列已基本有序的情况下，排序效率最高。A、二路归并排序B、快速排序C、直接插入排序D、堆排序【正确答案】：C解析：

二路归并排序和堆排序的效率用初始序列分布无关，而在初始序列已基本有序的情况下快速排序的效率最差。【正确答案】：为C。61.10.将10阶对称矩阵A压缩存储到一维数组B中，则数组B的长度最少为_()。A、100B、40C、80D、55【正确答案】：D解析：

n阶对称矩阵压缩存储时需要存储的元素个数=n(n+1)/2，n=10时结果为55。62.次探测。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。63.26.k阶最佳归并树是一棵（）。A、k阶平衡树B、平衡二叉树C、k阶哈夫曼树D、以上都不对【正确答案】：C解析：

k阶最佳归并树是一棵k阶哈夫曼树，不一定是k阶平衡树。64.28.设有一棵哈夫曼树的结点总数为35，则该哈夫曼树共有（）个叶子结点。A、18B、20C、35D、30【正确答案】：A65.21.设连通图有n个顶点e条边（e，n>0），若满足（），则图中一定有回路。A、e≥nB、e<nC、e=n-1D、2e≥n【正确答案】：A解析：

一个有n个顶点e条边的无向图，若e=n-1时构成一个树图，若en-1则一定存在回路。【正确答案】：为A。66.18.快速排序在()情况下最不利于发挥其长处。A、排序的数据量太大B、排序的数据中含有多个相同值C、排序的数据个数为奇数D、排序的数据已基本有序【正确答案】：D解析：

当排序的数据已基本有序，快速排序的时间复杂度会变为O(n2)。【正确答案】：为D。67.8.一棵高度为h、结点个数为n的m（m≥3）次树中，其分支数是（）。A、nhB、n+hC、n-1D、h-1【正确答案】：C68.3.以下不属于存储结构是()。A、栈B、二叉链C、哈希表D、双链表【正确答案】：A解析：

二叉链是二叉树的一种存储结构，哈希表是一种适合特定数据（关键字与地址之间存在某种关系）快速查找的存储结构，双链表是线性表的一种存储结构，而栈是一种逻辑结构，可以采用顺序栈或者链栈存储。答案为A。69.8.一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（）特性。A、顺序存储B、随机存取C、输入输出D、以上都不对【正确答案】：B解析：

稀疏矩阵采用三元组或者十字链表压缩后均不再具有随机存取特性。70.5.以下数据结构中()属非线性结构。A、栈B、串C、队列D、平衡二叉树【正确答案】：D解析：

栈、队列和串中元素的逻辑关系都是线性关系，平衡二叉树是一种二叉树，而二叉树属于非线性结构。答案为D。71.10.设有100个元素的有序顺序表，采用折半查找方法，不成功时最大的比较次数是（）。A、25B、50C、10D、7【正确答案】：D解析：

不成功时最大比较次数为log2(n+1)=log2101=7。【正确答案】：为D。72.25.n个顶点的连通图的生成树有（）条边。A、nB、n-1C、n+1D、不确定【正确答案】：B73.25.二叉排序中，最大关键字结点的（）。A、没有左孩子结点B、没有右孩子结点C、一定没有左右孩子结点D、一定存在左右孩子结点【正确答案】：B解析：

在二叉排序中，最大关键字结点是中序序列的最后结点，即根结点的最右下结点。74.速排序Ⅳ.二路归并排序A、仅ⅠB、仅Ⅰ、ⅡC、仅Ⅰ、ⅢD、仅Ⅱ、Ⅳ【正确答案】：B解析：

当初始数据基本正序时，直接插入排序和起泡排序的时间复杂度为O(n)。【正确答案】：为B。75.12.数据结构是指（）。A、一种数据类型B、数据的存储结构C、一组性质相同的数据元素的集合D、相互之间存在一种或多种特定关系的数据元素的集合【正确答案】：D解析：

数据结构通常指相互之间存在一种或多种特定关系的数据元素的集合。答案为D。76.（）。A、冒泡排序B、希尔排序C、归并排序D、基数排序【正确答案】：A77.46.冒泡排序最少关键字比较的次数是（）。A、nB、n-1C、3n(n-1)/2【正确答案】：C78.同IV.若v不是T1的叶子结点，则T1与T3相同A、仅I、IIIB、仅I、IVC、仅II、IIID、仅II、IV【正确答案】：C解析：

在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树可能发生变化，不再相同。【正确答案】：为C。79.32.采用败者树进行k路平衡归并的外排序算法中，总的关键字比较次数与k（）。A、成正比B、成反比C、无关D、以上都不对【正确答案】：C解析：

采用败者树进行k路平衡归并的外排序算法中，总的关键字比较次数=(u-1)log2m，其中u为归并的记录个数，m是初始归并段的个数，从而看出与k无关。80.为节俭排序算法，以下算法中是节俭排序算法的有_（）。A、直接插入排序B、简单选择排序C、堆排序D、所有选项都不对【正确答案】：A解析：

直接插入排序中没有同一对元素被比较过两次或以上。【正确答案】：为A。81.31.哈希查找的基本思想是根据（）来决定元素的存储地址。A、元素的序号B、元素个数C、关键字值D、非关键字属性值【正确答案】：C82.37.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（）。A、直接插入和快速B、冒泡和快速C、简单选择和直接插入D、简单选择和冒泡【正确答案】：C解析：

简单选择和直接插入肯定要进行n-1趟排序，冒泡排序为1～n-1趟，快速排序为log2n～n-183.35.m个初始归并进行k路平衡归并时，所需趟数（）。A、logkmB、logkm+1C、logk(m+1)D、logmk【正确答案】：A84.4.数据序列（8，9，10，4，5，6，20，1，2）只能是()算法的两趟排序后的结果。A、简单选择排序B、冒泡排序C、直接插入排序D、堆排序【正确答案】：C解析：

简单选择排序、冒泡排序和堆排序每一趟产生的有序区都是全局有序区，而（8，9，10，4，85.4.下面关于哈夫曼树的说法，不正确的是()。A、对应于一组权值构造出的哈夫曼树可能不唯一B、哈夫曼树具有最小带权路径长度C、哈夫曼树中没有度为1的结点D、哈夫曼树中除了度为2的结点外，还有度为1的结点和叶结点【正确答案】：D86.2.以下序列不是堆的是（）。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解析：

画出各个序列对应的完全二叉树，再对每个分支结点逐个判断。本题【正确答案】：为D。87.36.外排序和内排序的主要区别是（）。A、内排序速度快，而外排序速度慢B、内排序不涉及内、外存数据交换，而外排序涉及内、外存数据交换C、内排序所需内存小，而外排序所需内存大D、内排序的数据量小，而外排序的数据量大【正确答案】：B88.前一位置，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。89.排序后的结果，则该排序算法只能是()。A、冒泡排序B、直接插入排序C、简单选择排序D、二路归并排序【正确答案】：B解析：

从第二趟排序后结果看出，先后没有全局有序区，不可能是冒泡排序和简单选择排序，又发现了并非两两有序，所以不是二路归并排序。【正确答案】：为B。90.27.若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是（）。A、dcebfaB、cbdaefC、bcaefdD、afedcb【正确答案】：D解析：

选项A操作：a进，b进，c进，d进，d出，c出，e进，e出，b出，f进，f出，a出。选项B操作：a进，b进，c进，c出，b出，d进，d出，a出，e进，e出，f进，f出。选项C操作：a进，b进，b出，c进，c出，a出，d进，e进，e出，f进，f出，d出。选项D操作：a进，a出，b进，c进，d进，e进，f进，f出，e出，d出，c出，b出。从中看到，选项D中最后连续出栈5次，不符合要求。本题答案：为D。91.18.在含有n（n>2）个数据结点的数据结构中，终端结点是指（）的结点。A、没有前趋结点B、含有一个或多个前趋结点C、没有后继结点D、含有一个或多个后继结点【正确答案】：C解析：

终端结点是没有任何后继结点的。92.60.内排序方法的稳定性是指（）。A、该排序算法不允许有相同关键字的元素B、该排序算法允许有相同关键字的元素C、平均时间为O(nlog2n)的排序方法D、以上都不对【正确答案】：D93.23.如果一个表既能较快地查找，又能适应动态变化的要求，则可采用（）。A、有序表B、线性表C、哈希表D、二叉平衡树【正确答案】：D解析：

满足这种条件的表为树表，各选项中只有二叉平衡树是一种树表。94.31.在一个图中，每个顶点的前趋顶点和后继顶点数可以有（）。A、1个B、2个C、任意多个D、0个【正确答案】：C解析：

图中顶点之间是多对多的相邻关系。95.20.引入线索二叉树的目的是（）。A、加快查找结点的前趋或后继结点的速度B、为了能在二叉树中方便插入和删除C、为了能方便找到双亲D、使二叉树的遍历结果唯一【正确答案】：A96.29.对于栈操作数据的原则是（）。A、先进先出B、后进先出C、后进后出D、不分顺序【正确答案】：B解析：

栈操作数据的原则是先进后出或后进先出。97.28.在含有n个结点的二叉排序树中查找某关键字的结点时，最多进行（）次比较。A、n/2B、log2nC、log2n+1D、n【正确答案】：D解析：

n个结点的二叉排序树的高度可能为n。98.22.查找效率低的数据结构是（）。A、有序顺序表B、二叉排序树C、堆D、二叉平衡树【正确答案】：C解析：

堆查找的时间复杂度为O(n)，所以效率最低。99.3.以下4个线性表中，最适合采用基数排序的是()。A、10000个实数B、1000个由字母、数字和其他字符组成的字符串C、1000个int类型的整数D、10000个100以内的正整数【正确答案】：D解析：

这里是要求选择最适合基数排序的数据，显然实数序列不如整数序列，含负整数的序列不如仅100.13.设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为a、b、c、d，将森林F转换为一颗二叉树B，则二叉树B中根结点的左子树上的结点个数是()。A、a-1B、aC、a+b+cD、b+c+d【正确答案】：A1.9.二叉树中每个度为2的结点的两棵子树都是有序的。A、正确B、错误【正确答案】：A2.6.线性表的长度是线性表占用的存储空间的大小。A、正确B、错误【正确答案】：B解析：

线性表的长度是指表中元素个数，属逻辑结构的概念，与线性表占用的存储空间大小无关。3.14.在外排序过程中，一个记录的读入内存的次数和写到外存的次数必定相等。A、正确B、错误【正确答案】：A4.45.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。A、正确B、错误【正确答案】：B5.29.冒泡排序在最好情况下元素移动的次数为0。A、正确B、错误【正确答案】：A解析：

冒泡排序在初始数据正序时元素移动的次数为0。91、30.冒泡排序中，关键字比较的次数与初始数据序列有关，而元素移动的次数与初始数据序列无6.后移动。A、正确B、错误【正确答案】：B7.15.栈和线性表是两种不同的数据结构，它们的数据元素的逻辑关系也不同。A、正确B、错误【正确答案】：B解析：

栈和线性表是两种不同的数据结构，但它们的数据元素的逻辑关系都是线性关系。8.9.数据对象就是一组任意数据元素的集合。A、正确B、错误【正确答案】：B解析：

数据对象是指具有相同性质的有限个数据元素的集合。9.20.k路最佳归并树一定是一棵k路平衡树。A、正确B、错误【正确答案】：B解析：

k路最佳归并树不一定是一棵k路平衡树。10.2.线性表中的结点按前趋、后继关系可以排成一个线性序列。A、正确B、错误【正确答案】：A解析：

线性表是有限个相同性质的元素的序列。11.4.在队空间大小为n的循环队列中，最多只能进行n次进队操作。A、正确B、错误【正确答案】：B解析：

在循环队列中，元素出队后，其位置空了出来，可以让其他元素进队，所以理论上讲可以进队任意次。12.15.任何一个图，一旦指定源点，其深度优先遍历序列是唯一的。A、正确B、错误【正确答案】：B解析：

图的深度优先遍历序列不一定是唯一的。13.1.线性表中所有元素的数据类型必须相同。A、正确B、错误【正确答案】：A解析：

线性表中所有元素具有相同性质，在设计存储结构时，它们对应的数据类型也必然相同。14.1.一种逻辑结构的数据只有一种对应的存储结构。A、正确B、错误【正确答案】：B15.17.栈具有先进后出的特点，其中数据的逻辑结构是任意的。A、正确B、错误【正确答案】：B解析：

栈具有先进后出的特点，其中数据的逻辑结构一定是线性结构，不能是树形结构或图形结构。16.16.非空二叉树的中序序列的第一个结点一定是叶子结点。A、正确B、错误【正确答案】：B17.5.树中元素之间是多对多的关系。A、正确B、错误【正确答案】：B18.7.n个元素进队的顺序和出队的顺序总是一致的。A、正确B、错误【正确答案】：A解析：

后进队的元素后出队，先进队的元素先出队。19.6.哈夫曼树中没有度为1的结点。A、正确B、错误【正确答案】：A20.1.给定一棵树T，将其转换成二叉树B后，它们的结点个数相同。A、正确B、错误【正确答案】：A21.5.线性表中每个元素都有一个前趋元素和一个后继元素。A、正确B、错误【正确答案】：B解析：

开始元素没有前趋元素，终端元素没有后继元素。22.数据的逻辑结构。50、19.栈是一种特殊的线性表，其特殊之处在于栈的存储结构比较特殊。A、正确B、错误【正确答案】：B解析：

栈是一种特殊的线性表，其特殊之处在于对线性表的操作做了限制。23.35.基数排序与初始数据的次序无关。A、正确B、错误【正确答案】：A24.子。A、正确B、错误【正确答案】：A解析：

二叉排序树的任意一棵子树也是二叉排序树。25.18.栈的定义不涉及数据的逻辑结构。A、正确B、错误【正确答案】：B解析：

栈的定义不涉及数据的存储结构，栈中数据元素的逻辑关系属于线性关系，所以栈的定义涉及26.4.在一个含有n（n≥1）个元素的线性表中，所有元素值不能相同。A、正确B、错误【正确答案】：B解析：

在线性表中允许存在元素值相同的元素，但它们的位置是不同。27.个比较的方法选取最小记录，则总共需要396次关键字比较。A、正确B、错误【正确答案】：A解析：

归并趟数s=log55=1，5个记录选取最小记录需比较4次，所以总共需要(100-1)×4×1=396次关键字比较。28.25.简单选择排序是一种不稳定的排序方法。A、正确B、错误【正确答案】：A29.2.对于无向图生成树，从同一顶点出发所得到的生成树一定是相同的。A、正确B、错误【正确答案】：B解析：

无向图的生成树可能有多棵，从同一顶点出发所得到的生成树也不一定相同。30.接插入排序。为把所有记录排好序，需做6趟归并排序。A、正确B、错误【正确答案】：B解析：

内排序采用直接插入排序时，可以产生375000/600=625个初始归并段，5路平衡归并排序的趟数=log5625=4。所以需做4趟归并排序。31.树。A、正确B、错误【正确答案】：B解析：

对于二叉排序树，左子树上所有结点的关键字均小于根记录的关键字；右子树上所有结点的关键字均大于根记录的关键字。而不是仅仅与左、右孩子的关键字进行比较。32.14.图的遍历就是访问图中所有顶点。A、正确B、错误【正确答案】：B解析：

图的遍历是指以某种顺序访问图中所有顶点，且每个顶点仅访问一次。33.列是不可能相同的。A、正确B、错误【正确答案】：B解析：

图的两种遍历序列可能相同。34.42.二路归并排序算法的时间复杂度与初始数据序列的顺序无关。A、正确B、错误【正确答案】：A35.17.由二叉树某种遍历方式产生的结果是一个线性序列。A、正确B、错误【正确答案】：A36.1.k路最佳归并树在外排序中的作用是产生初始归并段。A、正确B、错误【正确答案】：B37.14.栈是一种特殊的线性表，线性表的所有运算都可以施加在栈上。A、正确B、错误【正确答案】：B解析：

栈是一种特殊的线性表，其特殊之处在于对线性表的插入和删除操作做了限制，所以不能将线性表的所有运算都施加在栈上。38.2.数据的逻辑结构与各数据元素在计算机中如何存储有关。A、正确B、错误【正确答案】：B解析：

数据的逻辑结构与存储结构无关。39.39.n个元素采用二路归并排序算法，总的趟数为n。A、正确B、错误【正确答案】：B解析：

n个元素采用二路归并排序算法，总的趟数为log2n。40.2.给定一棵树T，可以找到唯一的一棵二叉树B与之对应。A、正确B、错误【正确答案】：A41.31.冒泡排序在最好情况下的时间复杂度也是O(n2)。A、正确B、错误【正确答案】：B解析：

冒泡排序在最好情况下的时间复杂度为O(n)。42.最后一个结点A、正确B、错误【正确答案】：A43.26.n个元素采用简单选择排序进行排序，关键字比较的次数总是n(n-1)/2。A、正确B、错误【正确答案】：A44.5.队列是一种对进队、出队操作的次序做了限制的线性表。A、正确B、错误【正确答案】：B解析：

只要队列不满就可以进行进队操作，只要队列不空就可以进行出队操作，并不规定进队列、出队列操作的次序。45.12.哈希表中所有的哈希地址是连续的。A、正确B、错误【正确答案】：A46.22.内排序过程在数据量很大时就变成了外排序过程。A、正确B、错误【正确答案】：B47.15.为了提高外排序的速度，在外排序中必须选用最快的内排序算法。A、正确B、错误【正确答案】：B解析：

外排序的第二阶段只能采用归并排序算法。48.1.顺序队采用数组存放队中元素，数组具有随机存取特性，所以顺序队中可以随机存取元素。A、正确B、错误【正确答案】：B解析：

顺序队采用数组存放队中元素，尽管数组具有随机存取特性，但队列的操作特性是顺序存取，只能存取两端的元素。49.7.采用多路平衡归并方法可以减少初始归并段的个数。A、正确B、错误【正确答案】：B解析：

采用多路平衡归并方法可以减少归并的趟数。50.3.对于无向图生成树，其深度优先生成树和广度优先生成树一定不相同。A、正确B、错误【正确答案】：B解析：

不一定，如果一个无向图的生成树唯一，从同一顶点出发构造的深度优先生成树和广度优先生成树也是相同的。51.13.二叉树就是度为2的有序树。A、正确B、错误【正确答案】：B52.16.通常外排序采用多路归并排序方法，实际上也可以用其他内排序方法代替归并排序方法。A、正确B、错误【正确答案】：B53.16.栈和队列都是线性表，只是在插入和删除时受到了一些限制。A、正确B、错误【正确答案】：A解析：

栈和队列中元素都呈现线性关系，但它们插入和删除操作有别于线性表。54.9.k路平衡归并中，败者树的主要作用是减少归并的趟数。A、正确B、错误【正确答案】：B解析：

败者树的主要作用是加速从k个记录中选取最小记录，并不能减少归并的趟数。55.13.空栈是指栈中元素没有赋值。A、正确B、错误【正确答案】：B解析：

空栈是指栈中没有元素。56.9.线性表的顺序存储结构优于链式存储结构。A、正确B、错误【正确答案】：B解析：

线性表的顺序存储结构和链式存储结构各有优缺点。57.间复杂度的主要因素。正确错误A、正确B、错误【正确答案】：B解析：

影响算法时间复杂度的主要因素是移动元素的次数和关键字比较的次数。58.19.外排序中没有关键字比较。A、正确B、错误【正确答案】：B解析：

外排序中需要关键字比较。59.10.二叉树是一种特殊的树。A、正确B、错误【正确答案】：B60.37.基数排序只适用于以数字为关键字的情况，不适用以字符串为关键字的情况。A、正确B、错误【正确答案】：B61.成树。A、正确B、错误【正确答案】：B解析：

这样的子图不一定是连通的。62.5.顺序查找法适用于存储结构为顺序或链式存储的线性表。A、正确B、错误【正确答案】：A63.径。A、正确B、错误【正确答案】：A解析：

顶点i和顶点j属一个连通分量，而顶点k属另一个连通分量，所以顶点i到顶点k没有路径。64.11.有n个不同的元素通过一个栈，产生的所有出栈序列恰好构成这n个元素的全排列。A、正确B、错误【正确答案】：B65.8.n个元素通过一个队列，其出队序列是唯一的。A、正确B、错误【正确答案】：A解析：

后进队的元素后出队，先进队的元素先出队，所以出队序列与进队序列相同。66.36.基数排序与初始数据中关键字的大小无关。A、正确B、错误【正确答案】：B解析：

基数排序与初始数据中关键字的位数有关，也就与关键字的大小有关。67.12.相同的n个元素的不同序列通过一个栈一定不会得到相同的出栈序列。A、正确B、错误【正确答案】：B解析：

相同的n个元素的不同序列通过一个栈可能会得到相同的出栈序列。例如，进栈序列1、2、3和68.41.对于不同的初始数据序列，二路归并排序算法中关键字比较次数有所不同。A、正确B、错误【正确答案】：A解析：

二路归并排序算法的时间复杂度与初始数据序列的顺序无关，但关键字比较次数是相关的。69.23.从时间性能看，堆排序总是优于简单选择排序。A、正确B、错误【正确答案】：A解析：

堆排序的最好、最坏和平均时间复杂度均为O(nlog2n)，而简单选择排序的最好、最坏和平均时间复杂度均为O(n2)。70.3.非线性结构中，每个元素最多只有一个前趋元素。A、正确B、错误【正确答案】：B解析：

非线性结构中，每个元素可能有多个前趋元素。71.9.二叉排序树可以是一棵空树。A、正确B、错误【正确答案】：A72.17.影响外排序的时间因素主要是内存与外存交换信息的次数。A、正确B、错误【正确答案】：A73.查找、折半查找和分块查找。A、正确B、错误【正确答案】：B解析：

在顺序存储的物理介质如磁带上，只能进行顺序查找，即便文件有序，也不能进行折半查找。74.3.将二叉树变为线索二叉树的过程称为线索化。A、正确B、错误【正确答案】：A75.关。A、正确B、错误【正确答案】：B解析：

关键字比较的次数与元素移动的次数都与初始数据序列有关。76.6.队列是一种对进队、出队操作的次数做了限制的线性表。A、正确B、错误【正确答案】：B解析：

只要队列不满就可以进行进队操作，只要队列不空就可以进行出队操作，并不规定进队列、出队列操作的次数。77.值。A、正确B、错误【正确答案】：A78.3.对于不同的存储结构，应采用不同的查找方法。A、正确B、错误【正确答案】：A79.径。A、正确B、错误【正确答案】：A解析：

如果顶点j到顶点k有路径，则顶点i有一条通过顶点j到达顶点k的路径，与题中条件矛盾。80.8.一个图中的简单路径是指该路径上的边不重复出现。A、正确B、错误【正确答案】：B解析：

一个图中的简单路径是指该路径上的顶点不重复出现。81.15.非空二叉树的中序序列的最后一个结点一定是叶子结点。A、正确B、错误【正确答案】：B82.13.外排序的k路平衡归并中，采用败者树时，归并效率与k无关。A、正确B、错误【正确答案】：B解析：

外排序的k路平衡归并中，采用败者树时，总的关键字比较次数与k无关。83.33.快速排序、简单选择排序和堆排序都与初始序列次序无关。A、正确B、错误【正确答案】：B解析：

快速排序与初始序列次序无关。84.5.一个连通图的生成树是唯一的。A、正确B、错误【正确答案】：B解析：

一个连通图的生成树可能有多棵。85.24.简单选择排序中，每趟产生的有序区中所有元素在以后的排序中不再改变位置。A、正确B、错误【正确答案】：A86.3.在队空间大小为n的非循环队列中，最多只能进行n次进队操作。A、正确B、错误【正确答案】：A解析：

在非循环队列，元素进队时队尾指针递增，当到达最大下标时不能再进队，所以总计只能进队n次。87.40.二路归并排序算法是稳定的。A、正确B、错误【正确答案】：A88.14.非空二叉树的后序序列的最后一个结点一定是叶子结点。A、正确B、错误【正确答案】：A89.7