Java程序员面试分类真题13

Java程序员面试分类真题13一、单项选择题1.

若输入序列已经是排好序的，下列排序算法中，速度最快的是______。A.插入排序B.Shell排序C.归并排序D.快速排序正确答案：A[解（江南博哥）析]对于选项A，插入排序一遍扫描即可。

对于选项B，Shell排序虽不需要交换数据，但也要进行几次插入排序。

对于选项C，归并排序虽不需要交换数据，但也要进行logn次合并。

对于选项D，快速排序在数列有序的情况下效率是最低的。

通过上面的分析可知，如果序列已经排好序，那么，此时插入排序算法速度最快。所以，选项A正确。

2.

现有个数约为50K的数列需要进行从小到大排序，数列特征是基本逆序(多数数字从大到小，个别乱序)，以下排序算法中，在事先不了解数列特征的情况下性能大概率最优(不考虑空间限制)的是______。A.冒泡排序B.堆排序C.选择排序D.快速排序正确答案：B[解析]由于排序元素个数为50K，数据量大，所以，冒泡、选择、插入等排序算法基本不适用，所以，选项A与选项C错误。由于数列特性基本逆序，而快速排序的最差情况就是基本逆序或者基本有序的情况，所以，选项D错误。根据排除法可知，堆排序是最为合理的排序方法，所以，选项B正确。

所以，本题的答案为B。

3.

下面排序算法中，初始数据集的排列顺序对算法的性能无影响的是______。A.堆排序B.插入排序C.冒泡排序D.快速排序正确答案：A[解析]对于选项A，堆排序的过程如下：构造最大堆，从而得到最大的元素，将最大的元素与最后一个元素交换(即取出最大的元素)，然后对以根结点为首的、除最后一个元素之外的n-1个元素进行一次构造堆操作，由堆的性质可知，经过该次操作后得到的堆仍为最大堆，所以，可以继续将根结点与第n-1个结点交换，取出第二大元素……重复上述操作，直到依次取出第n-1大元素即完成了排序。所以，堆排序的时间复杂度一直都是O(nlogn)，它是一种不稳定的排序算法。所以，初始数据集的排列顺序对算法的性能无影响。因此，选项A正确。

对于选项B，插入排序的平均时间复杂度为O(n^2)，在序列初始有序的情况下，其时间复杂度为O(n)，它是一种稳定的排序算法。因此，选项B错误。

对于选项C，冒泡排序的平均时间复杂度为O(n^2)，在序列初始有序的情况下，增加交换标志flag可将时间复杂度降到O(n)，它是一种稳定的排序算法。因此，选项C错误。

对于选项D，快速排序与主元的选择有关，如果选择子序列左侧第一个元素比较，那么第一个元素最好是大小居中的，以使得分成的两个子数组长度大致相等，性能才能最佳，否则，在序列初始有序的情况下，时间复杂度可能会退化到O(n^2)，它是一种不稳定的排序算法。因此，选项D错误。

所以，本题的答案为A。

4.

假设某文件经内排序后得到100个初始归并段(初始顺串)，若使用多路归并排序算法，且要求三趟归并完成排序，问归并路数最少为______。A.8B.7C.6D.5正确答案：D[解析]本题首先要弄懂归并排序的思路。m个元素k路归并的归并次数s=logk(m)，当m=100，s=3时，代入公式，logk(100)＜=3，即k^3＞=100，所以，k值最小为5，选项D正确。

5.

快速排序在已经有序的情况下效率最差，此时其时间复杂度为______。A.O(nlogn)B.O(n^2)C.O(n^1.5)D.O(n^2logn)正确答案：B

6.

在排序方法中，从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为______。A.归并排序B.希尔排序C.插入排序D.选择排序正确答案：C

7.

对一个已经排好序的数组进行查找，时间复杂度为______。A.O(n)B.O(logn)C.O(nlogn)D.O(1)正确答案：B[解析]通常，对一个有序数组进行查找的最好方法为二分查找法。

二分查找的过程如下(假设表中元素是按升序排列)：首先，将表中间位置记录的关键字与查找关键字比较，如果两者值相等，则查找成功；否则，利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字的值大于查找关键字的值，则进一步查找前一子表，否则，进一步查找后一子表。重复以上过程，直到找到满足条件的记录，查找成功，或直到子表不存在为止，此时查找不成功。

例如，对于数组{1，2，3，4，5，6，7，8，9}，当需要查找元素6时，如果用二分查找的算法执行，其顺序如下：

1)第一步查找中间元素，即5，由于5＜6，所以，6必然在5之后的数组元素中，那么就在{6，7，8，9}中查找。

2)寻找{6，7，8，9}的中位数，为7，7＞6，所以，6应该在7左边的数组元素中，那么只剩下6，即找到了。

本题中，数组序列共11个数据元素，第一次比较下标为10/2=5的元素32。第二次比较下标为4/2=2的元素15，得到要查找的数。

通过以上的分析可知，二分查找的时间复杂度为O(logn)。所以，选项B正确。

8.

对有序数组{2、11、15、19、30、32、61、72、88、90、96}进行二分查找，则成功找到数值15需要比较______次。A.2B.3C.4D.5正确答案：A

9.

一个文件包含了200个记录，若采用分块查找法，每块长度为4，则平均查找长度为______。A.30B.28C.29D.32正确答案：B[解析]分块查找是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，对块内结点没有排序要求，因此，它特别适合于结点动态变化的情况。

对于分块查找的平均查找长度，通常由两部分组成，一个是对索引表进行查找的平均查找长度，一个是对块内结点进行查找的平均查找长度。假设线性表中共有n个结点，分成大小相等的b块，每块有s=n/b个结点。假定查找索引表采用顺序查找，只考虑查找成功的情况，并假定对每个结点的查找概率是相等的，则其平均查找长度ASL=(b+1)/2+(s+1)/2；假设索引表中采用折半查找，则其平均查找长度ASL=(s+1)/2+log2(b+1)-1。

本题中，s=200/4=50，b=4，所以，其平均查找长度ASL=(200/4+4)/2+1=28，选项B正确。

所以，本题答案为B。

引申：有一个2000项的表，采用等分区间顺序查找的分块查找法，问：

1)每块的理想长度是多少?

2)分成多少块最为理想?

3)平均查找长度是多少?

4)若每块是20，ASL是多少?求详解。

分块查找的平均查找长度包括索引表和分块内的两部分之和，即索引表+块中。

假设线性表长n，均匀分成m块，每块中记录个数s，则(其中符号表示上取整)，在等概率查找的前提下，如果约定在索引表中确定关键字所在的分块也是顺序查找，因为顺序查找的平均查找长度为(L+1)/2，则ASL=(n/s+s)/2+1。当s=sqrt(n)时，该和值有极小值：sqrt(n)+1。

因此，如果索引表内也是顺序查找，则每块的理想元素个数是sqrt(2000)，约为44.7，近似为45，同样分块数量也是45，因此，ASL=2*(45+1)/2=46。

如果每块长20，则分块为2000/20=100块，按照上面的结果，则ASL=(100+1)/2+(20+1)/2=61。

10.

设某棵二叉树中有360个结点，则该二叉树的最小高度是______。A.7B.9C.10D.8正确答案：B[解析]本题中的二叉树并没有说明到底是一棵什么类型的二叉树(完全二叉树、满二叉树、普通二叉树还是其他二叉树)，所以，其高度存在不确定性。

定义二叉树中的结点总数为n，当每个结点只有一棵子树的时候，其高度值最大，为n。当该二叉树为完全二叉树时，其高度值最小，为(其中符号表示取下整)，其他情况的二叉树的高度都是介于这两个值之间，即，不大于最大值也不小于最小值。

本题中要想求二叉树的最小高度，那么此时该二叉树为完全二叉树，其对应的高度为。所以，选项B正确。

11.

一棵有12个结点的完全二叉树，其深度为______。A.4B.5C.3D.6正确答案：A

12.

将一棵有100个结点的完全二叉树从根这一层开始，进行广度遍历编号，那么编号最小的叶子结点的编号是______。A.49B.50C.51D.52正确答案：C[解析]在解答本题前，首先需要弄懂一个概念，什么是完全二叉树?所谓完全二叉树是指除树的最后一层外，每一层上的结点数均达到最大值，且在最后一层上只缺少右边的若干结点的二叉树。

通过完全二叉树的定义，可以引出以下两种性质：①对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称为完全二叉树；②一棵二叉树至多只有最下面两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树为完全二叉树。

假设n0是度为0的结点总数(即叶子结点数)，n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0=n2+1，n=n0+n1+n2(其中n为完全二叉树的结点总数)，由上述公式把n2消去得n=2n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能：0或1，由此得到n0=(n+1)/2或n0=n/2，即。可根据完全二叉树的结点总数计算出叶子结点数。

本题中，n的值为100，根据上面的分析可知，n0=50。所以，度为0的结点有50个，度为1的结点有1个，度为2的结点有49个，二叉树前k层最多有2^k-1个结点。所以，100个结点二叉树高度为7，按照广度优先遍历编号，有50个非叶子结点，所以，最小的叶子结点编号为51。

下面给出另外一种求解方法：

100个结点时，二叉树高度为7。

7层包含数据个数为100-(2^6-1)=37。

6层包含数据的编号为32～63，6层中前19个数据包含子树(37/2=18.5)，故最小的叶结点应该为32+19=51。所以，选项C正确。

13.

已知一棵二叉树，如果先序遍历的结点顺序为ADCEFGHB，中序遍历的结点顺序为cDFEGHAB，则后序遍历的结点顺序为______。A.CFHGEBDAB.CDFEGHBAC.FGHCDEBAD.CFHGEDBA正确答案：D[解析]要解答出本题，首先需要对各种遍历方式有一个清晰的认识。可以通过图1来介绍二叉树的三种遍历方式的区别。

图1

二叉树的遍历方式

1)先序遍历：先遍历根结点，再遍历左子树，最后遍历右子树。所以，图1的先序遍历序列是ABDECFG。

2)中序遍历：先遍历左子树，再遍历根结点，最后遍历右子树。所以，图1的中序遍历序列是DBEAFCG。

3)后序遍历：先遍历左子树，再遍历右子树，最后遍历根结点。所以，图1的后序遍历序列是DEBFGCA。

从上面的介绍可以看出，先序遍历序列的第一个结点一定是根结点，因此，本题中可以确定这个二叉树的根结点为A。由中序遍历的特点可以把树分为三部分：根结点A、A的左子树和A的右子树。在中序遍历的序列中，在A结点前面的序列一定是在A的左子树上，在结点A后面的序列一定在A的右子树上。由此可以确定：A的左子树包含的结点为CDFEGH，右子树包含的结点为B(见图2a)。接下来对A的左子树上的结点采用同样的方法进行分析：对于序列CDFEGH，先序遍历的时候先遍历到结点D，因此，结点D是这个子树的根结点；通过对中序遍历进行分析可以把CDFEGH分为三部分：根结点D、D的左子树包含的结点为C、D的右子树上包含的结点为FEGH(见图2b)。然后对FEGH用同样的方法进行分析：在先序遍历的序列中先遍历到的结点为E，因此，根结点为E，通过分析中序遍历的序列，可以把这个序列分成三部分：根结点E、E的左子树上的结点F和E的右子树上的结点GH(见图2c)。最后分析结点GH，在先序遍历序列中先遍历到G，则说明G为根结点，在中序遍历序列中先遍历到结点G，说明H是G右子树上的结点(见图2d)。由此可以发现，通过先序遍历和中序遍历完全确定了二叉树的结构，可以非常容易

图2

二叉树的遍历

所以，本题的答案为D。

14.

有以下二叉树：

对其进行后序遍历的结果是______。A.丙乙丁甲戊己B.甲乙丙丁戊己C.丙丁乙己戊甲D.丙丁己乙戊甲正确答案：C

15.

已知一棵二叉树的前序遍历结果是ACDEFHGB，中序遍历结果是DECALHFBG，那么该二叉树的后序遍历的结果为______。A.HGFEDCBAB.EDCHBGFAC.BGFHEDCAD.EDCBGHFA正确答案：B

16.

某二叉树按中序遍历的序列为SYZ，则该二叉树可能存在______种情况。A.2B.3C.4D.5正确答案：D[解析]由于二叉树的中序遍历序列为SYZ，所以，可以分别以字符S、Y、Z为根构建二叉树。

(1)S为根

此时可以构建2种不同的二叉树。

二叉树结构如图1所示。

图1

S为根的二叉树

(2)Y为根

此时可以构建1种二叉树。

二叉树结构如图2所示。

图2

Y为根的二叉树

(3)Z为根

此时可以构建2种不同的二叉树。

二叉树结构如图3所示。

图3

Z为根的二叉树

所以，一共可以构建2+1+2=5种不同的二叉树。所以，选项D正确。

17.

某棵完全二叉树上有699个结点，则该二叉树的叶子结点数为______。A.349B.350C.188D.187正确答案：B[解析]二叉树有如下性质：对于一棵非空的二叉树，度为0的结点(即叶子结点)总是比度为2的结点多一个，即如果叶子结点(度为0的结点)数为n0，度数为2的结点数为n2，则有n0=n2+1。

对于本题而言，假设度为i的结点的个数为ni，则n0=n2+1，所以，n0+n1+n2=n0+n1+n0-1=699，可以得到n0=(700-n1)/2，显然，n1只能是偶数。由于在完全二叉树中，度为1的结点只有0个或1个两种情况，因此，n1=0，n0=350。所以，叶子结点个数为350，选项B正确。

18.

对于一棵排序二叉树，可以得到有序序列的遍历方式是______遍历。A.前序B.中序C.后序D.都可以正确答案：B[解析]排序二叉树的特点为：对于一个结点而言，所有左子树结点元素的值都小于这个结点元素的值，所有右子树结点的元素的值都大于这个结点元素的值，且左右子树都是排序二叉树。由于中序遍历的顺序为左子树、根、右子树，显然，中序遍历得到的序列是有序的。所以，选项B正确。

19.

最佳二叉搜索树是______。A.关键码个数最少的二叉搜索树B.搜索时平均比较次数最少的二叉搜索树C.所有结点的左子树都为空的二叉搜索树D.所有结点的右子树都为空的二叉搜索树正确答案：B[解析]二叉查找树(BinarySearchTree)又称为二叉搜索树、二叉排序树，它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二又查找树。

二叉搜索树的优点是：树中的元素是有序的，对二叉搜索树的查找类似于二分查找，显然，查找过程中比较的次数越少，效率就越高。显然，选项B正确。

对于选项A，二叉搜索树的好坏与关键码的个数没有直接关系。所以，选项A错误。

对于选项C与选项D，如果所有结点的左孩子(右孩子)都为空，那么查找效率与线性查找相同，都为O(n)。所以，选项C与选项D错误。

20.

若一棵二叉树的前序遍历序列为aebdc，后序遍历序列为bcdea，则根结点的孩子结点______。A.只有eB.有e，bC.有e，cD.不确定正确答案：A[解析]二叉树是每个结点最多有两个子树的树结构，通常子树被称作“左子树”(LeftSubtree)和“右子树”(RightSubtree)。所谓遍历(Traversal)，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。而通常情况下，如果中序遍历未知，则是无法还原出二叉树的。但本题只要求判断根结点的孩子结点，因此，是可以实现的。

二叉树中的前序遍历也叫作先根遍历、先序遍历，遵循的原则为“根左右”，即首先遍历根结点，再遍历根结点的左子树结点，最后遍历根结点的右子树结点。从前序遍历序列可知，结点e紧跟着结点a，可得结论：①结点a为根结点；②当结点e为结点a的右孩子时，结点a有且仅有结点e一个孩子。

二叉树中的后序遍历也叫作后根遍历，遵循的原则为“左右根”，即首先遍历左子树结点，再遍历右子树结点，最后遍历根结点。从后序遍历序列可知，结点e之后紧跟结点a，可得结论：③当结点e为结点a的左孩子时，结点a有且仅有结点e一个孩子。从结论①②③可知根结点的孩子有且仅有e。

通过前序遍历序列和后序遍历序列不能够唯一确定一棵二叉树，本例子存在如图所示的两种情况。

本题的两种情况

但无论是以上哪一种情况，都可以看出根结点的孩子结点只有e。

通过以上分析可知，选项A是正确的。

21.

现有一个包含m个结点的三叉树，即每个结点都有三个指向孩子结点的指针，请问：在这3m个指针中，空指针的个数是______。A.2mB.2m-1C.2m+1D.3m正确答案：C[解析]根据题目意思可知，m个结点共有3m个指针，而除了根结点外，每个结点都有父结点(即需要占用一个父结点的指针)，所以，空指针数为3m-(m-1)=2m+1，选项C正确。

22.

一个具有20个叶子结点的二叉树，它有______个度为2的结点。A.16B.21C.17D.19正确答案：D[解析]度的含义是一个结点所拥有的孩子个数。结点的度为0表示该结点没有孩子结点，也就是说，该结点为叶子结点。结点的度为2表示该结点有两个孩子结点。

在二叉树中，存在这样一个结论：对于任何的一棵二叉树，度为0的结点(就是叶子结点)数总是比度为2的结点数多一个。即假定度为0的结点(就是叶子结点)个数为n0，度为2的结点的个数为n2，那么数值上满足如下计算公式：n0=n2+1。证明过程如下：

假设n1为二叉树T中度为1的结点数，因为二叉树中所有结点的度都小于或等于2，所以，其结点总数为

n=n0+n1+n2

(1)

而二叉树中的分支数，除了根结点外，其余结点都有一个分支进入，设B为分支总数，则n=B+1。由于这些分支是由度为1或2的结点射出的，所以，B=n1+2n2，于是得出如下结论：

n=n1+2n2+1

(2)

由表达式(1)和(2)可得：n0=n2+1。

本题中，由于己知叶子结点数为20，即n0的值为20，所以，n2的值就为19，选项D正确。

23.

一个完全二叉树总共有289个结点，则该二叉树中的叶子结点数为______。A.145B.128C.146D.156正确答案：A[解析]对于任何的一棵二叉树，度为0的结点(就是叶子结点)数总是比度为2的结点数多一个。即假定度为0的结点(就是叶子结点)个数为n0，度为2的结点的个数为n2，那么数值上满足如下计算公式：n0=n2+1。

而在一个完全二叉树中，其左右子树的深度之差不大于1，所以，要么只有一个度为1的结点，要么没有。定义二叉树中所有结点个数为n，度为1的结点数为n1，那么n0+n1+n2=n，而n0=n2+1，所以叶子结点的个数n0=(n+1-n1)/2，其中n1要么为0，要么为1，n=289，只有当n1=0的时候，n+1-n1才能整除2，因此，n1=0，此时n0=(289+1)/2=145。所以，选项A正确。

24.

一棵二叉树有1000个结点，则该二叉树的最小高度是______。A.9B.10C.11D.12正确答案：B

25.

二叉排序树的定义是：①若它的左子树不为空，则左子树所有结点均小于它的根结点的值；②若它的右子树不为空，则右子树所有结点的值均大于根结点的值；③它的左右子树也分别为二叉排序树。下列遍历方式中，能够得到一个递增有序序列的是______。A.前序遍历B.中序遍历C.后序遍历D.广度遍历正确答案：B[解析]如果需要得到的序列为递增序列，按照二叉排序树的定义，应该先访问左子树，再访问根结点，最后访问右子树，根据定义可知，能够得到一个递增有序序列的遍历方式是为中序遍历。所以，选项B正确。

26.

递归式地先序遍历一个有n个结点、深度为d的二叉树，则需要栈空间的大小为______。A.O(n)B.O(d)C.O(logn)D.(nlogn)正确答案：B[解析]本题中，由于没有明确交代二叉树的类型或性质，所以，本题中的二叉树是无法确定类型的，自然而然也就并不一定是平衡的了，也就是说，深度d的值并不一定等于logn，很有可能d的值比logn的值大，而栈空间的大小通常为二叉树的深度，所以，栈的大小应该是O(d)，而不是O(logn)。因此，本题的答案为B。

27.

用关键字序列10、20、30、40、50构造的二叉排序树(二叉查找树)为______。

A．

B．

C．

D．正确答案：D[解析]对于二叉排序树而言，右结点元素的值总是比根结点元素的值大，左结点元素的值总是比根结点元素的值小。本题中，给出的序列是递增的。通过逐一对比可知，只有选项D正确。

28.

具有n个顶点的有向图，所有顶点的出度之和为m，则所有顶点的入度之和为______。A.mB.m+1C.n+1D.2m+1正确答案：A[解析]度指的是与该顶点相关联的边数。在有向图中，度又分为入度(In-degree)和出度(Out-degree)。以某顶点为弧头，终止于该顶点的弧的数目称为该顶点的入度。以某项点为弧尾，起始于该顶点的弧的数目称为该顶点的出度。在某顶点的入度和出度的和称为该顶点的度。

在有向图的邻接表中，从一个顶点出发的弧链接在同一链表中，邻接表中结点的个数恰为图中弧的数目，所以，顶点入度之和为弧数和的一倍。如果为无向图，同一条边有两个结点，分别出现在和它相关的两个顶点的链表中，因此，无向图的邻接表中结点个数为边数的2倍。本题中顶点的出度之和为m，所以，所有顶点的入度之和也为m(一条弧对应一个入度与一个出度)，通过以上分析可知，选项A正确。

29.

具有n个顶点的有向图最多有______条边。A.nB.n(n-1)C.n(n+1)D.n^2正确答案：B[解析]如果图中的每条边都是有方向的，则称为有向图。在一个有向图中，边是由两个顶点组成的有序对，有序对通常用尖括号表示，例如＜vi,vj＞表示一条有向边，其中vi是边的始点，vj是边的终点。在有向图中，＜vi,vj＞和＜vi,vj＞代表两条不同的有向边。

在有向图中，任意两个结点之间都可以形成一对有向边，因此，对于具有n个顶点的有向图，其边的条数为n(n-1)。所以，选项B正确。

30.

n个顶点的强连通图至少有______条边。A.nB.n-1C.n+1D.n(n-1)正确答案：A[解析]n个顶点的强连通图至少有n条边，最多有n(n-1)/2条边。所以，选项A正确。

31.

在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为______。A.sB.s-1C.s+1D.n正确答案：A[解析]在有向图中，所有顶点的入度之和等于出度之和。本题中，所有顶点的出度之和为s，则所有顶点的入度之和也为s。所以，选项A正确。

32.

对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表中该顶点的单链表中的结点数为______。A.k1B.k2C.k1-k2D.k1+k2正确答案：A[解析]在有向图的邻接表中，某顶点链表的结点个数是发出去的弧的数量，也就是出度，反过来说，逆邻接表的某顶点链表的结点个数是进入的弧的数量，也就是入度，所以，选项A正确。

33.

在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情况下不可能出现的是______。A.G中有弧＜vi,vj＞B.G中有一条从vi到vj的路径C.G中没有弧＜vi,vj＞D.G中有一条从vj到vi的路径正确答案：D

34.

判断有向图是否存在回路，最好的方法是______。A.拓扑排序B.求最短路径C.求关键路径D.广度优先遍历正确答案：A[解析]针对有向图是否存在回路的问题，最好的方法就是对有向图构造其顶点的拓扑有序序列，如果有向图的所有顶点可以排出拓扑序列，则该有向图无环路。具体步骤如下：

在求拓扑算法的过程中，最重要的是要维护一个入度为0的顶点的集合，每次从这个集合中取出一个顶点，放入保存拓扑结构结果的列表中，然后从图中删除从这个顶点引出的所有边，在删除这些边后，这个边的另外一个结点，如果入度变成0，则加入到存放入度为0的结点的集合中。依次类推，直到把所有顶点都遍历完成，就求出了拓扑结构。如果在求解的过程中，存放入度为0的集合为空，但是此时图中还有没有遍历的边，则说明图中至少存在一个回路。所以，选项A正确。

35.

无向图G=(V，E)，其中V={a，b，c，d，e，f}，E={＜a，b＞，＜a，e＞，＜a，c＞，＜b，e＞，＜e，f＞，＜f，d＞，＜e，d＞}，对该图进行深度优先排序，得到的顶点序列正确的是______。A.a，b，e，c，d，fB.a，c，f，e，b，dC.a，e，b，c，f，dD.a，e，d，f，c，b正确答案：D[解析]图的深度优先遍历类似于树的前序遍历。假设给定无向图G的初态是所有顶点均未曾被访问过，深度优先遍历过程是这样的：在无向图G中任选一个顶点v为初始出发点(源点)，首先访问源点v，并将其标记为已访问过，然后，依次从源点v出发，搜索源点v的每个相邻结点w。如果结点w未曾被访问过，那么以结点w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。如果此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

本题中，按照上述方法可知，选项D正确。

36.

已知一个无向图(边为正数)中顶点A、B的一条最短路径P，如果把各个边的权重(即相邻两个顶点的距离)变为原来的2倍，那么在新图中，P仍然是A、B之间的最短路径。以上说法______。A.不确定B.正确C.错误正确答案：B[解析]如果从图中某一顶点(源点)到达另一顶点(终点)的路径可能不止一条，有这样一条路径，沿此路径上各边的权值总和(称为路径长度)最小，该路径称为最短路径。

本题中，如果将各条边的权值按从小到大排序，则权值乘以2之后的排序不变，也就是权重的相对关系不变，p仍是最短路径。所以，选项B正确。

37.

一个具有8个顶点的连通无向图，最多有______条边。A.28B.7C.26D.8正确答案：A[解析]所谓连通无向图，指的是对图中任意顶点u、v，都存在路径使u、v连通，即任何两个点都有边相连。本题中，8个点中任选择两个，都可以有一条边，所以，最多有8*7/2=28条边，选项A正确。

所以，本题的答案为A。

结论1：一个有n个顶点的有向强连通图最多有n(n-1)条边，最少有n条边。

强连通图必须从任何一点出发都可以回到原处，每个结点至少要一条出路(单结点除外)，至少有n条边，正好可以组成一个环。

结论2：一个有n个顶点的无向连通图最多有n(n-1)/2条边，最少有n-1条边。

可以通过数学归纳法进行证明。有兴趣的读者可以自行验证。

引申：若一个非连通的无向图最多有28条边，则该无向图至少有多少个顶点?

9个。假设有8个顶点，则8个顶点的无向图最多有28条边且该图为连通图。连通无向图构成条件：边=顶点数*(顶点数-1)/2。顶点数＞=1，所以，该函数存在单调递增的单值反函数，边与顶点为增函数关系。故28条边的连通无向图顶点数最少为8个。

因此，28条边的非连通无向图为9个(加入一个孤立点)。

38.

对于一个具有n个顶点的无向图，若采用邻接表数据结构表示，则存放表头结点的数组大小为______。A.nB.n+1C.n-1D.n+边数正确答案：A[解析]无向图指的是边没有方向的图。采用邻接表表示的无向图，存放表头结点的数组的大小为图的顶点个数。本题中，无向图的顶点个数为n，所以，存放表头结点的数组大小为n，选项A正确。

39.

在一个具有n个顶点的无向图中，要连通全部顶点至少需要______条边。A.nB.n+1C.n-1D.n/2正确答案：C

40.

一个有n个顶点的无向连通图，它所包含的连通分量个数为______。A.0B.1C.nD.n+1正确答案：B

41.

在一个无向图中，若两个顶点之间的路径长度为k，则该路径上的顶点数为______。A.kB.k+1C.k+2D.2k正确答案：B

二、多项选择题1.

二叉树是一种树形结构，每个结点至多有两棵子树，下列一定是二叉树的是______。A.红黑树B.B树C.AVL树D.B+树正确答案：AC[解析]对于选项A，红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。除了具有二叉查找树的一般性质以外，对于任何有效的红黑树，还有如下的额外要求：

1)结点是红色或黑色。

2)根结点是黑色。

3)每个叶子结点(空结点)是黑色的。

4)每个红色结点的两个子结点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色结点)。

5)从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

所以，红黑树是二叉树。所以，选项A正确。

对于选项B，B树是一种平衡的多叉树。所以，选项B不正确。

对于选项C，AVL树是平衡二叉树。所以，选项C正确。

对于选项D，B+树是一种树数据结构，是一个n叉树，每个结点通常有多个孩子，一棵B+树包含根结点、内部结点和叶子结点。根结点可能是一个叶子结点，也可能是一个包含两个或两个以上孩子结点的结点。所以，选项D不正确。

所以，本题的答案为AC。

2.

堆的形状是一棵______。A.完全二叉树B.平衡二叉树C.二叉排序树D.满二叉树正确答案：AB[解析]堆是一种特殊的树形结构，有大顶堆和小顶堆两种。大顶堆(小顶堆)的特点是根结点的值最大(最小)，且根结点的子树也为一个大项堆(小顶堆)。

对于选项A，完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在使用的时候堆是采用数组来存储的，因此，它满足完全二叉树的特点。所以，选项A正确。

对于选项B，平衡二叉树(BalancedBinaryTree)又称为AVL树(有别于AVL算法)，具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两棵子树都是一棵平衡二叉树。由于完全二叉树一定满足平衡二叉树的性质。所以，选项B正确。

对于选项C，排序二叉树有如下性质：

1)若左子树不为空，则左子树上所有结点的值均小于它的根结点的值。

2)若右子树不为空，则右子树上所有结点的值均大于或等于它的根结点的值。

3)左、右子树也分别为二叉排序树。

4)没有键值相等的结点。

显然，堆不满足这个性质。所以，选项C不正确。

对于选项D，满二叉树是指树中除最后一层无任何子结点外，每一层上的所有结点都有两个子结点的二叉树。满二叉树中结点的个数为1，3，7等特殊的数字，而堆中的结点可以是任意的，因此，不能保证堆是个满二叉树。所以，选项D不正确。

所以，本题的答案为AB。

3.

2-3树是一种特殊的树，它满足以下两个条件：

1)每个内部结点有两个或三个子结点。

2)所有的叶子结点到根的路径长度相同。

如果一棵2-3树有9个叶子结点，则它可能有的非叶结点个数为______。A.8B.7C.6D.5E.4正确答案：BE[解析]根据条件2)，叶子结点只能在同一层，根据条件1)，上一层的父结点只能是3个或4个，只能是下图所示的两种结果。

本题的两种结构

所以，本题的答案为BE。

三、填空题1.

程序的局部变量存在于______中，全局变量存在于______中，动态申请数据存在于______中。正确答案：栈，静态区，堆。

2.

设有字母序列{Q，D，F，X，A，P，N，B，Y，M，C，W}，按二路归并方法对该序列进行一趟扫描后的结果为______。正确答案：DQFXAPBNMYCW。[解析]归并排序是利用递归与分治技术将数据序列划分成越来越小的子序列，再对子序列进行排序，最后再用递归法将排好序的子序列合并成越来越大的有序序列。其中，“归”代表的是递归的意思，即递归地将数组折半分离为单个数组，例如数组[2，6，1，0]，会先折半，分为[2，6]和[1，0]两个子数组，然后再折半将数组分离，分为[2]、[6]和[1]、[0]。“并”就是将分开的数据按照从小到大或者从大到小的顺序再放到一个数组中。例如上面的[2]、[6]合并到一个数组中是[2，6]，[1]、[0]合并到一个数组中是[0，1]，然后再将[2，6]和[0，1]合并到一个数组中，即为[0，1，2，6]。

具体而言，归并排序算法的原理如下：对于给定的一组记录(假设共有n个记录)，首先将数组中的元素两两分组，得到n/2(向上取整)个长度为2或1的有序子序列，对每个分组中的元素进行排序，再将其两两归并，反复执行此过程，直到得到一个有序序列为止。

对于本题而言，一趟扫描后的结果为：

3.

设有关键码序列(Q，H，C，Y，Q，A，M，S，R，D，F，X)，按照关键码值递增的次序进行排序，若采用初始步长为4的Shell的排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。正确答案：QACSQFXRHMY、FHCDQAMQRSYX。[解析]希尔排序也称为“缩小增量排序”，它的基本原理如下：首先将待排序的元素分成多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序”后，再对所有元素进行一次直接插入排序。当步长为4时，一趟扫描排序的过程如图所示。

一趟扫描排序过程

快速排序是一种非常高效的排序算法，它采用“分而治之”的思想，把大的拆分为小的，小的再拆分为更小的。其原理如下：对于一组给定的记录，先选取一个分界的元素，然后通过一趟排序后，将原序列分为三部分：数组前半部分、分界元素和数组后半部分。其中数组前半部分的所有记录均比分界元素小，数组后半部分元素均比分界元素大。递归该过程，直到序列中的所有记录均有序为止。

一趟快速排序的实现方法如下：首先确定分界元素pivotkey，接着用两个指针low和high，它们分别指向待排序数组首尾元素。然后从high所指的位置起向前搜索找到第一个小于pivotkey的元素与pivotkey交换，然后从low开始向右搜索找到第一个大于pivotkey的元素与pivotkey交换，重复这两个步骤，直到low==high为止。

根据这个思路可以很容易得到一趟排序后的结果为FHCDQ