一、单项选择题9. 一个文件包含了200个记录,若采用分块查找法,每块长度为4,则平均查找长度为______。
A B C D
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 B C D
B
[解析] 本题中的二叉树并没有说明到底是一棵什么类型的二叉树(完全二叉树、满二叉树、普通二叉树还是其他二叉树),所以,其高度存在不确定性。
定义二叉树中的结点总数为n,当每个结点只有一棵子树的时候,其高度值最大,为n。当该二叉树为完全二叉树时,其高度值最小,为
(其中
符号表示取下整),其他情况的二叉树的高度都是介于这两个值之间,即
,不大于最大值也不小于最小值。
本题中要想求二叉树的最小高度,那么此时该二叉树为完全二叉树,其对应的高度为
。所以,选项B正确。
12. 将一棵有100个结点的完全二叉树从根这一层开始,进行广度遍历编号,那么编号最小的叶子结点的编号是______。
A B C D
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.CFHGEBDA
- B.CDFEGHBA
- C.FGHCDEBA
- D.CFHGEDBA
A B C D
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。
16. 某二叉树按中序遍历的序列为SYZ,则该二叉树可能存在______种情况。
A B C D
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正确。
20. 若一棵二叉树的前序遍历序列为aebdc,后序遍历序列为bcdea,则根结点的孩子结点______。
A B C D
A
[解析] 二叉树是每个结点最多有两个子树的树结构,通常子树被称作“左子树”(Left Subtree)和“右子树”(Right Subtree)。所谓遍历(Traversal),是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。而通常情况下,如果中序遍历未知,则是无法还原出二叉树的。但本题只要求判断根结点的孩子结点,因此,是可以实现的。
二叉树中的前序遍历也叫作先根遍历、先序遍历,遵循的原则为“根左右”,即首先遍历根结点,再遍历根结点的左子树结点,最后遍历根结点的右子树结点。从前序遍历序列可知,结点e紧跟着结点a,可得结论:①结点a为根结点;②当结点e为结点a的右孩子时,结点a有且仅有结点e一个孩子。
二叉树中的后序遍历也叫作后根遍历,遵循的原则为“左右根”,即首先遍历左子树结点,再遍历右子树结点,最后遍历根结点。从后序遍历序列可知,结点e之后紧跟结点a,可得结论:③当结点e为结点a的左孩子时,结点a有且仅有结点e一个孩子。从结论①②③可知根结点的孩子有且仅有e。
通过前序遍历序列和后序遍历序列不能够唯一确定一棵二叉树,本例子存在如图所示的两种情况。
本题的两种情况
但无论是以上哪一种情况,都可以看出根结点的孩子结点只有e。
通过以上分析可知,选项A是正确的。
三、填空题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为止。
根据这个思路可以很容易得到一趟排序后的结果为FHCDQAMQRSYX。
4. 根据访问根结点的次序,二叉树的遍历可以分为三种:前序遍历、 ______和后序遍历。
5. 一个具有3个结点的二叉树可以有______种形态。
5。
[解析] 这5种形态如图所示。
3个结点的二叉树形态
6. 把4000个结点组成一棵二叉树,最小高度是______。
12。
[解析] 要使得二叉树的高度最低,那么就需要把二叉树每一层都排满,即排成一个完全二叉树,高度为k的完全二叉树最多有2^k-1个结点。当k=11时,2^k-1=2047<4000,当k=12时,2^k-1=4095>4000。因此,树的最低高度为12,且最后一层结点的个数为4000-2017=1983。
7. 表达式((A+B)*C-(D-E)*(F+G))的前缀表达式是______。
-*+ABC*-DE+FG。
[解析] 前缀表达式,也称为“波兰式”,指的是不含括号的算术表达式,而且它是将运算符写在前面,操作数写在后面的表达式,例如,前缀表达式-1+2 3,它等价于算术表达式1-(2+3)。
根据以上分析可知,本题的表达式前缀表达式为-*+ABC*-DE+FG。
四、论述题1. 排序都有哪几种方法?用Java语言实现一个插入排序。
常见的排序方法有选择排序、插入排序、冒泡排序、归并排序、快速排序、希尔排序和堆排序等。
下面重点介绍插入排序。对于给定的一组记录,初始时假设第一个记录自成一个有序序列,其余的记录为无序序列。接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直至最后一个记录插入到有序序列中为止。以数组{38,65,97,76,13,27,49}为例,直接插入排序具体步骤如下:
第一步插入38以后,序列为[38] 65 97 76 13 27 49。
第二步插入65以后,序列为[38 65] 97 76 13 27 49。
第三步插入97以后,序列为[38 65 97] 76 13 27 49,,
第四步插入76以后,序列为[38 65 76 97] 13 2749。
第五步插入13以后,序列为[13 38 65 76 97] 27 49。
第六步插入27以后,序列为[13 27 38 65 76 97] 49。
第七步插入49以后,序列为[13 27 38 49 65 76 97]。
程序示例如下:
public class TestSort {
public static void insetxSort(int[]a){
if(a==null || a.length==0)
return;
for(int i=1;i<a.length;i++)
{
//把a[i]插入到a[0~i-1.的有序子列表中
int temp=a[i],j=i;
if(a[j-1]>temp){
while(j>=1&&a[j-1]>temp) {
a[j]=a[j-1];
j--;
}
}
a[j]=temp;
}
}
public static void main(String[]args){
int[]array={7,3,19,40,4,7,1};
insertSort(array);
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
}
}
程序的运行结果为:
1 3 4 7 7 19 40
2. 什么是平衡二叉树?
平衡二叉树(Balanced Binary Tree)又被称为AVL树,它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。