数据结构期终复习 下载本文

一、单项选择题(每小题 2 分,共20分) (1)一个 n*n的带状矩阵A=[aij]如下:

?a11?a?21??A???????a12a22a32a23a33?a34?an?2,n?1?an?2,n?2an?1,nan?2,n?1an?1,n?1an,n?1?????? ??an?1,n?ann??将带状区域中的元素aij(|i-j|≤1)按行序为主序存储在一维数组B[3n-2]中,元素aij

在B中的存储位置是( )。

A)i+2j-2 B)2i+j-3 C)3i-j D)i+j+1 (2)一n×n的三角矩阵A=[aij]如下:

?a11?????a12a22?a1n??a2n??

???ann?将三角矩阵中元素aij(i≤j)按行序为主序的顺序存储在一维数组B[n(n+1)/2]中,则aij

在B中的位置是( )。

A)(i-1)(2n+i)/2+i-j B)(i-1)(2n-i+2)/2+j-i C)(i-1)(2n-i)/2+j-i-1 D)(i-1)(2n-i+2)/2+j-i-1

(3)设有一棵度为3的树,其叶结点数为n0,度为1的结点数为n1,度为2的结点数为n2,度为3的结点数为n3,则n0与n1,n2,n3满足关系( )。

A)n0=n2+1 B)n0=n1+2n3+1 C)n0=n2+n3+1 D)n0=n1+n2+n3 (4)G是一个非连通无向图,共有28条边,则该图至少有( )个顶点。

A)6 B)7 C)8 D)9 (5)设图G用邻结表存储,则拓扑排序的时间复杂度为( )。

A)O(n) B)O(n+e) C)O(n2) D)O(n×e) (6)用n个键值构造一棵二叉排序树,最低高度为( )。

A)

n 2

B)n

C)nlog2n

D)?log2n??1

(7)若需在O(nlogn)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是( )。

A)快速排序 B)堆排序 C)归并排序 D)直接插入排序 (8)在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是( )。(北方名校经典试题)

A)直接插入排序 B)起泡排序 C)简单选择排序D)基数排序 (9)一棵有124个叶结点的完全二叉树,最多有( )个结点。

A)247 B)248 C)249 D)250

(10)一个序列中有10000个元素,若只想得到其中前10个最小元素,最

好采用 ( )方法。

B)堆排序 D)二路归并排序

A)快速排序 C)插入排序

二、(本题8分)

要借助栈由输入序列是输入1,2,3,…,n得到的输出序列为p1,p2,p3,…,pn(此输出序列是输入序列经过栈操作后的某个排列),则在输出序列中不可能出现当i

三、(本题8分)

已知某一完全k叉树只有度为k的结点及叶结点,设叶结点数为n0,试求它的树高h。(南方名校经典试题)

四、(本题8分)

试讨论怎样在一棵中序线索二叉树上查找给定结点x在后序序列中的后继。 五、(本题8分)

具有n个关键字的B一树的查找的最大路径长度是多少? 六、(本题8分)

对长度为12的有序表(a1,a2,…,a12)(其中aia12以及ai

八、(本题8分)

(1)设T是具有n个内结点的判断二叉树,I是它的内路径长度,E是它的外路径长度,试利用归纳法证明 E=I+2n,n>0。

(2)利用(1)的结果,试说明,成功查找的平均比较次数s与不成功查找的平均比

)u?1,n>0表示。 较次数u之间的关系,可用公式s?(1?1n提示:判断二叉树只有度为0或度为2的结点;判断二叉树成功查找的比较次数为内

路径长度与内结点数之和,不成功查找的比较次数为外路径长度。

九、(本题9分)

一个深度为h的满m叉树有如下性质:第h层上的结点都是叶结点,其余各层上每个结点有m棵非空子树。问:

(1)第k层有多少个结点?(k≤h) (2)整棵树有多少个结点?

(3)若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,编号为i的结点的双亲结点的编号是什么?编号为i的结点的第j个孩子结点(若存在)的编号是什么?

十、(本题15分)

设散列表的关键字取值范围为0 ~ m-1,n为对散列表的最大插入次数,设计散列表,允许使用以O(m+n)空间,要求查找、插入和删除算法的时间复杂度都是O(1)。

模拟试题(八)参考答案

一、单项选择题(每小题 2 分,共20分) (1)参考答案:B)

(2)【分析】存储位置=n+(n-1)+…+(n-i+2)+i-j=(i-1)(2n-i+2)/2+j-i。 参考答案:B)

(3)【分析】用n表示结点总数,则有:n= n0+n1+n2+n3;

由于除根结点而外,结点与分支一一对应,而分支数= n1+2n2+3n3,即有:n-1= n1+2n2+3n3。

由上面两式可得:n0=n1+2n3+1 参考答案:B)

(4)【分析】本题中由于是非连图,至少有一个顶点与其他顶点不连,这个顶点是孤立点,其他顶点可组成一个连通图,由于8个顶点的完全图共有28条边,所以具体28个顶点的连通图的顶点个数至少为8,这样非连通图至少有9个顶点。

参考答案:D) (5)【分析】对于有n个顶点e条边的有向图,建立各顶点的入度时间复杂度为O(e),建立入度为零的栈的时间复杂度为O(n),在拓扑排序过程中,最多每个顶点进一次栈,入度减1的操作最多总共执行e次,可知总的时间复杂度为O(n+e)

参考答案:B)

(6)【分析】当用n个键值构造一棵二叉排序树是一棵完全二叉树时,高度最低,此时高度为?log2n??1。

参考答案:D)

(7)【分析】快速排序和堆排序都是不稳定的,应排除;归并排序稳定,时间复杂度O(nlogn),满足条件;直接插入排序,时间复杂度为O(n2),排除。

参考答案:C)

(8)【分析】对直接插入排序而言,算法时间复杂度为O(n2),但若待排记录序列为“正序”时,其时间复杂度可提高至O(n)。若待排记录序列按关键字“基本有序”,直接

插入排序的效率就可大大提高,此外由于直接插入排序算法简单,在n值很小时效率也高。

参考答案:A)

(9)【分析】完全二叉树中度为1的结点最多只有1个,由二叉树的度和结点的关

系:

n=n0+n1+n2 (1) n=n1+2n2+1 (2)

由2(1)-(2)得,n=2n0+n1-1=247+n1≤248,所以本题应选择B)。 参考答案:A)

(10)参考答案:B) 二、(本题8分)

【解答】设pj

三、(本题8分)

【解答】设度为k的结点数为nk,结点总数为n,则有如下关系:

n= nk+n0 ①

又由于树中只有n-1条边,所以:

n-1=k×nk ②

由①与②可得:nk=(n0-1) / (k-1),进而有n=

k?n0?1

k?1(k-1)≤kh-1 对于k叉完全树有如下关系:kh-1-1<n×

kh-1≤n×(k-1)<kh,h-1≤logk(n×(k-1))<h,h??logk(n?(k?1))??1 即有:从而:进而:所以:h=?logk(k?n0?1)??1

四、(本题8分)

【解答】由于后序遍历二叉树需要知道的关键是访问当前结点的双亲结点,需要由中序线索树才能得到当前结点的双亲,中序线索树有如下性质:

若x是parent的左孩子,则parent是x的最右子孙的右线索; 若x是parent的右孩子,则parent是x的最左子孙的左线索。 用以上性质能找到x的双亲结点parent。

若x是parent的右孩子,则parent结点就是x的后序序列的后继结点;如下图(1)中结点①的后继是结点②。

若x是parent的左孩子,则:

如果parent的右指针域为线索的话,那么parent就是x的后序序列的后继结点,如下图(2)中结点②的后继是结点③。

否则 parent右子树中最左边第一个左右孩子均为线索的结点,就是 x的后序序列的后继结点。如下图(3)中结点②的后继是结点③。