四川大学数据结构期终复习

A）E、G、F、A、C、D、B B）E、A、G、C、F、B、D C）E、A、C、B、D、G、F D）E、G、A、C、D、F、B （7）该二叉树有（ ）个叶子。

A）3 B）2 C）5 D）4 （8）该二叉树的按层遍历的序列为（ ）。

A）E、G、F、A、C、D、B B）E、A、C、B、D、G、F C）E、A、G、C、F、B、D D）E、G、A、C、D、F、B （9）下面的二叉树中，（ ）不是完全二叉树。

（10）设有关键码序列(q,g,m,z,a)，（ ）序列是从上述序列出发建的小根堆的结果。

A）a,g ,m,q,z B）a,g,m,z,q C）g,m,q,a,z D）g, m, a,q,z 三、（本题8分）

设有一个输入数据的序列是{ 46, 25, 78, 62, 12, 80 }，试画出从空树起，逐个输入各个数据而生成的二叉排序树。

四、（本题8分）

给定一个关键字序列｛24，19，32，43，38，6，13，22｝，请写出快速排序第一趟的结果；堆排序时所建的初始堆；然后回答上述两种排序方法中哪一种方法使用的辅助空间最小，在最坏情况下哪种方法的时间复杂度最差？

五、（本题8分）

设二维数组A[0:10,-5:0]，按行优先顺序存储，每个元素占4个单元，A[0][-5]的存储地址为1000，则A[9][-2]的存储地址为多少？

六、（本题8分）

用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。

七、（本题8分）

请说明对一棵二叉树进行前序、中序和后序遍历，其叶结点的相对次序是否会发生改变？为什么？

九、（本题9分）

已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI 十、（本题15分）

已知二叉排序树采用二叉链表存储结构，根结点的指针为T，请写出递归算法，从小到大输出该二叉排序树中所有关键字值≥K的结点的关键字的值。

一、单项选择题（每小题 2 分，共20分） （1）B （2）C （3）A （4）B （6）C （7）A （8）C （9）C 三、（本题8分） 如下图所示：

（5）B （10）B

四、（本题8分）

快速排序的第一趟结果为｛22,19,13,6,24,38,43,12｝；堆排序时所建立的初始大顶堆如所图所示：

两种排序方法所需辅助空间：堆是O(1)，快速排序是O(logn)，可见堆排序所需辅助空间较少；在最坏情况下两种排序方法所需时间：堆是O(nlogn)，快速排序是O(n2)，所以，可见快速排序时间复杂度最差。

?

注意：快速排序的平均时排序速度最快，但在最坏情况下不一定比其他排序方法快。

五、（本题8分）

依题意A的起始地址为1000，则有：

Loc(9,-2)=1000+[(9-0)*(0-(-5)+1)+(-2-(-5))]*4=1228。 六、（本题8分）

先画出该二叉树的树形结构。对其进行后序遍历得到后序序列为：HIDJKEBLFGCA。

七、（本题8分）

二叉树任两个中叶结点必在某结点的左/右子树中，三种遍历方法对左右子树的遍历都是按左子树在前、右子树在后的顺序进行遍历的。所以在三种遍历序列中叶结点的相对次序是不会发生改变的。

九、（本题9分）

先由先序序列的第一个结点确定二叉树的根结点，再由根结点在中序序列中左侧部分为左子树结点，在右侧部分为右子树结点，再由先序序列的第一个结点确定根结点的左右孩子结点，由类似的方法可确定其他结点，如下图所示。

十、（本题15分）

由于二叉排序树是中序有序的，因此对二叉排序树采用中序遍历依次输出大于等于K的结点即可。

C语言版测试程序见exam4\\10c，具体算当如下：

void DisplayKey(BiTree T,KeyType K) // 从小到大输出该二叉排序树中所有关键字值≥K的结点的关键字的值 { if(T) { DisplayKey(T->lchild,K); //输出左子树 if(T->data.key>=K) cout<data.key<<\ \//输出满足条件的关键值 DisplayKey(T->rchild,K); //输出右子树 } }

一、单项选择题（每小题 2 分，共20分） （1）队列的特点是（ ）。

A）先进后出 B）先进先出 C）任意位置进出 D）前面都不正确 （2）有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（ ）遍分配与收集。

A）n B）d C）r D）n - d

（3）在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ ）。

A）都不相同 B）完全相同 C）先序和中序相同，而与后序不同 D）中序和后序相同，而与先序不同 （4）限定在一端加入和删除元素的线性表称为（ ）。

A）双向链表 B）单向链表 C）栈 D）队列 （5）快速排序执行一遍之后，已经到位的元素个数是（ ）。

A）1 B）3 C）n D）n

42（6）设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。

A）m-n-1 B）n+1 C）m-n+1 D）m-n

（7）设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为（ ）。

A）12 B）13 C）14 D）15 （8）下面关于广义表的叙述中，不正确的是（ ）。

A）广义表可以是一个多层次的结构 B）广义表至少有一个元素 C）广义表可以被其他广义表所共享 D）广义表可以是一个递归表

（9）设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点，下列关系式不正确的是（ ）。

A）f>=c B）c>f C）f=2k+1-a D）c>sk-1

（10）从L=((apple,pear),(orange,banana))中，取出banana元素的表达式为（ ）。

A）head(tail(L)) B）head(head(tail(L))) C）tail(head(tail(L))) D）head(tail(head(tail(L)))) 四、（每小题4分，共8分）

判断以下序列是否是小根堆? 如果不是，将它调整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }

（2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 六、（每小题2分，共8分）

设有12个数据25,40,33,47,12,66,72,87,94,22,5,58，它们存储在散列表中，利用线性探测再散列处理冲突，取散列函数为H(key)=key % 13。

（1）顺次将各个数据散列到表中，并同时列出各元素的比较次数。 （2）计算查找成功的平均查找次数。 八、（本题8分）

已知一棵树边的结点为：

{(I,M),(I,N),(E,I),(B,E),(B,D),(C,B),(G,J),(G,K),(A,G),(A,F),(H,L),(A,H),(C,A)} 试画出这棵树，并回答下列问题： （1）哪个是根结点？ （2）哪些是叶子结点？ （3）树的深度是多少？ 九、（本题9分）

给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)。写出用下列算法从小到大排序时第一趟结束时的序列。

（1）希尔排序（第一趟排序的增量为5） （2）快速排序（选第一个记录为枢轴） 十、（本题15分）

编写复制一棵二叉树的非递归算法。

一、单项选择题（每小题 2 分，共20分） （1）B （2）B （3）B （4）C （5）A （6）D （7）C （8）B （9）B （10）D