数据结构---清华大学模拟试题二答案

一．单项选择题（2分/题）

1．一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其空链域数为（）。

A.0      B.1         C.2      D.不确定

2．设图G采用邻接表存储，则拓扑排序算法的时间复杂度是（）。

A.O(n)          B.O(n+e)         C.O(n2)      D.O(n*e)

3．下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是（）。

A.堆排序          B.冒泡排序       C.快速排序       D.SHELL排序

4．已知数据表A中每个元素距其最终位置不远，则采用（）排序算法最节省时间。

A.堆排序          B.插入排序          C.快速排序          D.直接选择排序

5．串是（）。

A.不少于一个字母的序列          B. 任意个字母的序列

C.不少于一个字符的序列           D.有限个字符的序列

二．判断题（1分/题）

1.（）若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai =n-i+1。(i=1,2,...,n)

2.（）二叉树中的叶子结点就是二叉树中没有左右子树的结点。

3.（）一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。

4.（）删除二叉排序树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。

5.（）线性表就是顺序表。

6.（）若一棵树中某结点的度为1，则该结点仅有一棵子树。

7.（）所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。

8.（）AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。

9.（）若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。

10.（）在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。 

11.（）对B-树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在非叶结点的最下层。

12.（）若一个连通无向图的以顶点1为起点的深度遍历序列唯一，则可唯一确定该图。

13.（）若一个有向图的以顶点1为起点的深度遍历序列唯一，则可唯一确定该图。

14.（）在数据表基本有序时，冒泡排序算法的时间复杂度一定接近O(n)。

15.（）设指针p指向单链表中的一个结点，则语句序列u:=p^.next; u:=u^.next将删除一个结点。

三．填空题（2分/题）

1．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数是（129）。

2．已知栈的输入序列为1,2,3,...,n，输出序列为a1, a2, a3,..., an，符合a2=n的输出序列共有（n-1）种。

3．已知数组A[1..10,1..10]为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续内存单元中，则元素A[5，6]对应的地址为（1095）。

4．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是（log2i=log2j）。

5．在按关键字递增的数组A[1..20]中，按折半查找方法进行查找时，查找长度为5的元素个数是（5）。

四．应用题（5分/题）

1．一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该二叉树。

              先序序列：   B   F   ICEH   G；

              中序序列：D   KFIA   EJC   ；

              后序序列：   K   FBHJ   G   A

      先序序列：ABDFKICEHJG；

      中序序列：DBKFIAHEJCG；

      后序序列：DKIFBHJEGCA

                                         A

                    B                                      C

          D                 F                    E               G

                       K           I        H          J

2．已知哈希表地址空间为0..14，哈希函数为H(k)=k mod 13，采用线性探测法处理冲突。将下面各数依次存入该散列表中，并求出在等概率下的平均查找长度和失败的查找长度。

          240,29,345,1,100,20,21,35,3,208,78,99,45,350

               0   1   2   3   4   5   6   7   8   9   10  11   12  13   14

                 0    1   2    3   4   5   6     7     8      9   10 11 12 13 14

               208 78 350 29  3      240 345 1 100 20 21 35 99 45

                 0    0   12  3   3        6     7     7      9    7   8   9   8   6

            ASLs=43/14          ASLf=105/13

3．对下面的递归算法，写出调用p(4)的执行结果。

PROC  p(w:integer);

if w>0 then

      [  write(w);

          p(w-1);

          p(w-1)

      ]

ENDP; {p}

      4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

4．一棵排序二叉树结构如下，各结点的值从小到大依次为1~8，请标出各结点的值。

6

8

1

7

5

3

4

2

5．60

求出下图中顶点1到其余各顶点的最短路径。

30             20           15

4

3

2

1

4

3

2

1

10              3            6        3 

10    15      3    16    6        3        6

8

7

6

5

8

7

6

5

7             8             10

7             8             10

五．算法设计题（10分/题）

1．已知T为一棵二叉排序树。

（1）设计算法按递减次序打印各结点的值。

（2）设计算法以产生一个序列，要求该序列满足：依次将这些元素插入到初值为空的二叉排序树中所得的结果与原二叉排序树相同。

算法思想：（1）按“右根左”遍历

                    （2）先序遍历

2．已知一棵二叉树按顺序方式存储在数组A[1..n]中，设计算法求出下标分别为i和j的两个结点的最近公共祖先结点。

算法思想：沿i、j分别上溯查找公共结点。

3．已知数组A[1..n]的元素类型为整型，设计算法将其调整为左右两部分，使得左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n)。

算法思想：利用快速排序的思想。

4．设计算法判断有向图G是否是一棵以v为根的有向树。

      可以使用以下几个函数调用：

firstadj(G,v)—返回图G中顶点v的第一个邻接点，若不存在返回0

nextadj(G,v,w)—返回图G中顶点v的邻接点中处于w之后的邻接点，若不存在返回0

nodes(G)—返回图G中的顶点数

      算法思想：从v出发深度优先搜索，若可遍历到图中所有顶点且遍历过的顶点不会再次访问则是；否则不是。