复习数据结构习题解答

习题解答

1．空格串是由 空格 组成的串，空串是 不含任何字符 的串，因此空格串和空串不是一个概念。

2．从整体上看，数据在存储器内有两种存放的方式：一是集中存放 在一个连续的 内存存储区中；一是利用存储器中的零星区域， 分散地存放在 内存的各个地方。 3．如果一棵满二叉树的深度为6，那么它共有 63 个结点，有 32 个叶结

3．限定插入和删除操作只能在一端进行的线性表，被称为是 栈 。

4．在数据结构中，把n（n≥0）棵互不相交的树的集合称为 森林 。树中一个结点的子树中的任何结点，都被称作是该结点的 子孙 结点。

5．在一个n阶方阵A中，若所有元素都有性质：aij = aji (1≤i, j≤ n)，就称其为 对称 矩阵。

6．在有向图中，把从顶点vi到顶点vj的弧记为 < vi，vj > ，而把从顶点vj到顶点vi的弧记为 < vj，vi > ，这是两条不同的弧。

7．如果查找只是为了得知是否成功或获取相应的记录信息，并不去改变查找表的内容，那么这种查找称为 静态 查找；如果查找过程会伴随着对数据元素的变更，那么这种查找称为 动态 查找。

8. 前序遍历序和中序遍序列相同的二叉树为树中的任何一个节点无左孩子

1.若已知一个栈的输入序列为 1 ,2, 3 ,...n ,其输出序列为 p1,p2,p3,....pn。若p1=n,则pi为

＿n-i+1＿＿＿。 2.循环队列用数组a[m]存放其元素值,已知尾指针是rear,元素个数是qlen,则当前队列中的首指针为(Max+Sq->rear-sq->qlen)%max ＿＿＿＿。

3.按照二叉树的定义,具有3个结点的二叉树有＿5＿＿＿种。

4.从逻辑关系上讲,数据结构主要分为两大类,它们是＿＿＿＿和＿＿＿＿。

5. 在有向图中，把从顶点vi到顶点vj的弧记为 < vi，vj > ，而把从顶点vj到顶点vi的弧记为 < vj，vi > ，这是两条不同的弧。

6.已知完全二叉树的第八层有8个结点,则其叶子结点数是＿＿＿＿。

7．在数据结构中，把n（n≥0）棵互不相交的树的集合称为 森林 ，树中一个结点的子树中的任何结点，都被称作是该结点的 子孙 结点。

8．在一个具有4个顶点的无向图中，要连通全部顶点，，至少需要 3 条边。

9．对关键字序列22、86、19、49、12、30、65、35、18做一趟排序后，得到的结果是18、12、19、22、49、30、65、35、86。因此，可以认为采用的排序方法是 快速排序 。

10．在一个n阶方阵A中，若所有元素都有性质：aij = aji (1≤i, j≤ n)，就称其为 对称 矩阵。

11．如果查找只是为了得知是否成功或获取相应的记录信息，并不去改变查找表的内容，那么这种查找称为 静态 查找；如果查找过程会伴随着对数据元素的变更，那么这种查找称为 动态 查找。

答案 ：1、n-i+1 2、(Max+Sq->rear-sq->qlen)%max

3、5 4、线性关系和非线性关系 5、< vi，vj >、 < vj，vi > 6、68

- 1 -

习题解答

7、森林、子孙 8 、3 9、快速排序 10、对称 11、静态、动态

1. 前序遍历序和中序遍序列相同的二叉树为 2. 无向图G用邻接矩阵A{1...n，1...n}存储。其第i列的所有非零元素个数等于顶点i的 。 3. 由带权为３，９，６，２，５的５个叶子结点构成一棵哈夫曼树，则其带权路径长度为＿＿．

4. 设有有空栈，栈顶指针指向100H（十六进制），现有输入序列为1，2，3，4，经过Push，Push，Pop，Push，Pop，Push，Push后，输出序列为 。 5. 在一棵树中， 结点没有前驱结点。

6. 具有有结点的完全二叉树的深度为 。

7.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，需 次比较可检索成功。

8．空格串是由 空格 组成的串，空串是 不含任何字符 的串，因此空格串和空串不是一个概念。

9．若经过某种排序之后，那些有相同关键字值的记录间的相对位置保持不变，那么称这种排序方法是 稳定 的。

10．线性表中数据元素的个数n称为线性表的 长度 11．所谓“数组”，是指n（n>1)个具有 相同 类型的数据的有序集合。

12．在具有n个数据结点的循环队列中，队满时共有 n-1 个数据元素。

13．在无向图中，若从顶点vi到顶点vj之间有 路径 存在，则称vi与vj是连通的。

14．在一个n阶方阵A中，若所有元素都有性质：aij = aji (1≤i, j≤ n)，就称其为 对称 矩阵。

答案：1.树中的任何一个节点无左孩子 2.度 3. 55 4. 5，4，1或2,3, 5，4，1 5. 根 6.7 7. 2 8. 空格、不含任何字符

9. 稳定 10. 长度 11. 相同 12. n-1 13．路径 14.对称

1．线性表中数据元素的个数n称为线性表的 长度

2．结点数为7的二叉树的高度最矮是 5 ，最高是 7。

3．字符串中任意多个 连续 字符所组成的子序列，被称作是这个串的“子串”，这个字符串本身则称为“主串”。 4．树中除根结点外，其他结点有且只有 一个 前驱结点，但可以有 零个或多个 后继结点。 5．所谓“数组”，是指n（n>1)个具有 相同 类型的数据的有序集合。 6．在具有n个数据结点的循环队列中，队满时共有 n-1 个数据元素。 7．在一个具有4个顶点的无向图中，要连通全部顶点，，至少需要 3 条边。

8．若经过某种排序之后，那些有相同关键字值的记录间的相对位置保持不变，那么称这种排序方法是 稳定 的。

9．在数据结构中，把n（n≥0）棵互不相交的树的集合称为 森林 。树中一个结点的子树中的任何结点，都被称作是该结点的 子孙 结点。 10． 选择 排序方法是从未排序的序列中挑选出元素，然后将其依次放入排好序的序列的一端。

11．从整体上看，数据在存储器内有两种存放的方式：一是集中存放 在一个连续的 内存存储区中；一是利用存储器中的零星区域， 分散地存放在 内存的各个地方。

- 2 -

习题解答

1． 线性表中数据元素的个数n称为线性表的 长度 。 2．队列中，允许进行删除的一端称为 队首 。

3．结点数为7的二叉树的高度最矮是 3 ，最高是 7 。

4．将一棵完全二叉树按层次进行编号。那么，对编号为i的结点，如果有左孩子，则左孩子的编号应该是 2i ；如果有右孩子，则右孩子的编号应该是 2i+1 。

5．空格串是由 空格 组成的串，空串是 不含任何字符 的串，因此空格串和空串不是一个概念。

6．对于一个无向图，其邻接矩阵中第i行（或第i列）里非零或非∞元素的个数，正好是第i个顶点vi的 度 。

7．在无向图中，若顶点vi和vj之间有一条边（vi，vj）存在，那么则称顶点vi和vj互为 邻接 点。

8．在无向图中，若从顶点vi到顶点vj之间有 路径 存在，则称vi与vj是连通的。

9．在一个n阶方阵A中，若所有元素都有性质：aij = aji (1≤i, j≤ n)，就称其为 对称 矩阵。

10． 选择 排序方法是从未排序的序列中挑选出元素，然后将其依次放入排好序的序列的一端。

11．如果操作顺序是先让字母A、B、C进栈，做两次出栈；再让字母D、E、F进栈，做一次出栈；最后让字母G进栈，做三次出栈。最终这个堆栈从栈顶到栈底的余留元素应该是 DA 。

二、选择

1．若一个栈的进栈序列是1、2、3、4，那么要求出栈序列为3、2、1、4时，进、出栈操作的顺序应该是 A 。（注：所给顺序中，I表示进栈操作，O表示出栈操作） A．IIIOOOIO B．IOIOIOIO C．IIOOIOIO D．IOIIIOOO 2．在所给的4棵二叉树中， C 不是完全二叉树。

3．在一棵二叉树中，第5层上的结点数最多是 C 个。 A．8 B．15 C．16 D．32

4．在长度为n的顺序表中，往其第i个元素（1≤i≤n）之前插入一个新的元素时，需要往后移动 B 个元素。

A．n-i B．n-i+1 C．n-i-1 D．i

5．用某种排序方法对序列：24、84、21、47、16、28、66、35、20进行排序，序列的变化情况为：

24，84，21，47，16，28，66，35，20 20，16，21，24，47，28，66，35，84 16，20，21，24，35，28，47，66，84 16，20，21，24，28，35，47，66，84

C．快速排序

D．选择排序

那么，这里采用的排序方法是 C 。 A．直接插入排序 B．冒泡排序

6．采用顺序查找法查找长度为n的线性表时，其平均查找长度为 C 。

- 3 -

习题解答

A．n B．n/2

C．(n+1)/2 D．(n-1)/2

7． D 是图状关系的特例。 A．只有线性关系 C．线性关系和树型关系都不 8．有下面的算法段：

B．只有树型关系 D．线性关系和树型关系都

for (i=0; i其时间复杂度为 B 。

2

A．O(1) B．O(n) C．O(log2n) D．O(n) 9．下面，对非空线性表特点的论述， C 是正确的。

A．所有结点有且只有一个直接前驱 B．所有结点有且只有一个直接后继

C．每个结点至多只有一个直接前驱，至多只有一个直接后继

D．结点间是按照1对多的邻接关系来维系其逻辑关系的

10．一个栈的元素进栈序列是a、b、c、d、e，那么下面的 C 不能做为一个出栈序列。 A．e、d、c、b、a B．d、e、c、b、a

C．d、c、e、a、b

D．a、b、c、d、e

1．在计算递归函数时,如不使用递归过程,则一般情况下必须借助于＿＿＿＿数据结构。 (A)队列 (B)广义表 (C)二叉树 (D) 栈 2. 一个队列的输入序列是a d c b，则队列的输出序列是＿＿＿＿。

(A) a d c b (B)b c d a (C)d c b a (D) c b a d

3．有32个结点的完全二叉树的深度为＿＿＿＿ （根的层次为1）。 （A）8 （B）7 (C)6 (D)5 4．一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列是＿＿＿＿。

（A）2 3 4 1 5 （B）5 4 2 3 1 (C)2 3 1 4 5 (D) 1 5 4 3 2 5.数组a[5][6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续单元中，则元素a[2][5] 的地址为＿＿＿＿

（A）1175 (B)1180 (C)1205 (D)1210 6．串的模式匹配是指＿＿＿＿。

（A）判断两个串是否相等 （C）找某字符在主串中第一次出现的位置

（B）对两个串比较大小 （D）找某子串在主串中第一次出现的第一个字符位置 7. ．对关键字序列：46、79、56、38、40、84采用快速排序方法。若以46为枢轴，那么一次划分后的结果应该是 D 。

A．38，40，46，79，56，84 C．40，38，46，79，84，56 8. 栈操作的原则是＿＿＿＿ 。

（A）先进先出 （B）后进先出 （C）只能进行插入 （D）只能进行删除 9．将一棵有50个结点的完全二叉树按层编号，那么编号为25的结点是 B 。

A．无左、右孩子

B．有左孩子，无右孩子 D．有左、有孩子

C．有右孩子，无左孩子

B．38，40，46，84，56，79

D．40，38，46，56，79，84

10．在长度为n的顺序表中，往其第i个元素（1≤i≤n）之前插入一个新的元素时，需要往后移动 B 个元素。

- 4 -

习题解答

A．n-i B．n-i+1 C．n-i-1 D．i 1、D 2、A 3、C 4、B 5、B 6、D 7、D 8、B 9 、B 10 B

1.在无向图中，定义顶点Vi与Vj之间的路径为从Vi到达Vj的 一个 。 （A ）顶点序列 （B） 边序列 （C ） 权值总和 （D）边的条数

2. 设键字序列为３，７，６，９，８，１，４，５，２，则对它们进行排序的最小交换次数是＿＿.

（Ａ）８ （Ｂ）７ （Ｃ）６√ （Ｄ）９

3．如果只想到1024个元素组成的序列中前5个最小元素，那么用（ ）方法最快。 （A ）起泡排序 （B）快速排序 （C ）堆排序 （D）直接选择排序

4．设有一个栈，元素的进栈顺序为Ａ，Ｂ，Ｃ，Ｄ，Ｅ，＿是不可能的出栈序列．

（Ａ）ＡＢＣＤＥ （B）B C D E A （Ｃ）ＥＡＢＣＤ （Ｄ）ＥＤＣＢＡ

5. 一个具有n个顶点的无向图中，要连通全部顶点至少需要 条边。

(A)n (B)n+1 (C)n/2 (D)n-1 6.串的逻辑结构与 的逻辑结构不同。

（A）线性表 (B) 栈 (C)队列 (D)树

7. 已知8个元素（34，76，45，18，26，，92，65），按照依次插入结点的方法生成一棵

二叉排序树，该树的深度为 。

(A)4 (B)5 (C)6 (D)7

8. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0 的结点个数为_________.

(A) 4 (B)5 (C)6 (D)7

9．若一个栈的进栈序列是1、2、3、4，那么要求出栈序列为3、2、1、4时，进、出栈操作的顺序应该是 A 。（注：所给顺序中，I表示进栈操作，O表示出栈操作）

A．IIIOOOIO

B．IOIOIOIO

C．IIOOIOIO

D．IOIIIOOO

10．在所给的4棵二叉树中， C 不是完全二叉树。

1. （A ）2. （Ｃ） 3. （D） 4. （Ｃ）5. （D ）6.（ D ）7. （B ）8. （C） 9. （A ） 10.（Ｃ）

1．有下面的算法段：

for (i=0; iB．O(n) C．O(log2n) D．O(n)

2

其时间复杂度为 B 。

A．O(1)

2．下面，对非空线性表特点的论述， C 是正确的。 A．所有结点有且只有一个直接前驱

- 5 -

习题解答

B．所有结点有且只有一个直接后继

C．每个结点至多只有一个直接前驱，至多只有一个直接后继

D．结点间是按照1对多的邻接关系来维系其逻辑关系的

3．将一棵有50个结点的完全二叉树按层编号，那么编号为25的结点是 B 。 A．无左、右孩子 B．有左孩子，无右孩子 C．有右孩子，无左孩子 D．有左、有孩子

4．一棵二叉树度2的结点数为7，度1的结点数为6。那么它的叶结点数是 C 。 A．6 B．7 C．8 D．9

5．对于一个有向完全图来说，它的每个不同顶点对之间，都存在有两条弧。因此，有n个顶点的有向完全图包含有 A 条边。

A．n(n-1)

B．n(n+1)

C．n(n-1)/2

6．从待排序序列中依次取出元素与已排好序的序列里的元素进行比较，并存放到已排序序列的正确位置上，这种排序方法是 A 。 A．直接插入排序 B．交换排序

C．冒泡排序

D．选择排序

7．下列说法中，正确的是 A 。 A．树的先序遍历序列与其对应的二叉树的先序遍历序列相同

B．树的先序遍历序列与其对应的二叉树的后序遍历序列相同 C．树的后序遍历序列与其对应的二叉树的先序遍历序列相同 D．树的后序遍历序列与其对应的二叉树的后序遍历序列相同

8．当两个元素出现逆序时就交换它们的位置，这种排序方法是 C 。 A．直接插入排序 B．冒泡排序 C．交换排序 D．选择排序 9．在对线性表进行折半查找时，要求线性表必须 B 。 A．以顺序方式存储

B．以顺序方式存储，且结点按关键字有序排列 C．以链式方式存储 D．以链式方式存储，且结点按关键字有序排列

10．从链栈中删除一个结点时，操作顺序应该是 A 。

A．先保存被删结点的值，再修改栈顶指针 B．先修改栈顶指针，再保存被删结点的值 C．无须修改栈顶指针的值 D．谁先谁后没有关系

1．链栈与顺序栈相比，一个较为明显的优点是 D 。 A．通常不会出现栈空的情形 B．插入操作更加便利 C．删除操作更加便利 D．通常不会出现栈满的情形 2．在一个无向图中，所有顶点的度数之和，是其所有边数之和的 C 倍。

A．1/2

B．1

C．2

D．4

3．对关键字序列：46、79、56、38、40、84采用快速排序方法。若以46为枢轴，那么一次划分后的结果应该是 D 。

A．38，40，46，79，56，84 C．40，38，46，79，84，56

B．38，40，46，84，56，79 D．40，38，46，56，79，84

4． D 是图状关系的特例。 A．只有线性关系

C．线性关系和树型关系都不

B．只有树型关系 D．线性关系和树型关系都

- 6 -

习题解答

5．在长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要往前移动 A 个元素。 A．n-i B．n-i+1 C．n-i-1 D．i 6．在一个循环顺序队列里，队首指针Cq_front总是指向 B 。 A．队首元素 B．队首元素的前一个队位 C．任意位置 D．队首元素的后一个队位 7．深度为6的二叉树，最多可以有 A 个结点。 A．63 B． C．127

D．128

8．设有一个5阶上三角矩阵A，将其元素按列优先顺序存放在一维数组B中。已知每个元素占用2个存储单元，B[1]的地址是100。那么A[3][4]的地址是 A 。

A．116

B．118

C．120

D．122

9．在对线性表进行折半查找时，要求线性表必须 B 。

A．以顺序方式存储

B．以顺序方式存储，且结点按关键字有序排列 C．以链式方式存储

D．以链式方式存储，且结点按关键字有序排列

10．将一棵有50个结点的完全二叉树按层编号，那么编号为25的结点是 B 。

A．无左、右孩子 B．有左孩子，无右孩子 C．有右孩子，无左孩子 D．有左、有孩子

11．当线性表的数据元素个数基本稳定、很少进行插入和删除操作，但却要求以最快的速度存取表中的元素时，我们应该对该表采用 顺序 存储结构。

四、应用

1．若元素进栈的序列是1、2、3、„、n，有一个出栈序列的第1个元素是n。那么，这个出栈序列的第i个元素是什么？

答：由于栈具有“先进后出”的特性，因此只有将1、2、3、„、n依次都进栈后，出

栈序列的第1个元素才能是n。所以，在这个出栈序列里，第个i元素应该是n-i+1。 2．有人说，有一棵结点数为n>1的二叉树，只包含有一个叶结点。这可能吗？如果可能的话，这样一棵二叉树应该是个什么样子呢？

答：这是完全可能的，这种二叉树是从根结点开始只有左子树，或只有右子树的单支二叉

树，如图所示。

3．权值序列为：10、16、20、6、30、24，请用图示来表达构造一棵哈夫曼树的全过程。

答：构造这棵哈夫曼树的全过程如下所示。

- 7 -

习题解答

4．已知一棵树的孩子链表表示法如图6-24所示，试画出该树。

图6-24 一棵树的孩子链表表示法

答：该树形状如下图所示。

5．有如图7-23所示的一个无向图，给出它的邻接矩阵以及从顶点v1出发的深度优先遍历序列。

- 8 -

习题解答

答：它的邻接矩阵如图所示。从顶点v1出发的深度优先遍历序列为：

v1->v2->v4->v5->v7->v6->v3

注意，该序列是不唯一的。

6．有两个关键字序列：3、10、12、22、36、18、28、40和5、8、11、15、23、20、32、7。试问谁是堆，谁不是堆？把不是堆的序列通过筛选将它调整为一个堆。

答：依照序列的顺序，画出对应的完全二叉树如(a)和(b)所示。可以看出，(a)是一个堆，

(b)则不是，因为结点7破坏了堆的性质。为此，先将7和15对换，如图(c)所示；然

后再将7和8对换，如图(d)所示。这时，序列2就被调整为是一个堆了。

1．对于树的各种遍历，哪一种遍历是（1）首先访问树的根结点？（2）位于最左边的结点最先访问？（3）根结点最后访问？（4）最右边的结点最后访问？ 答：（1）层次遍历和先序遍历总是首先访问树的根结点；（2）后序遍历总是最先访问位于树最左边的结点；（3）后序遍历总是最后访问树的根结点；（4）前序遍历总是最后访问树的最右边的结点。

2．试述栈与队列各自具有什么样的逻辑特点？它们之间又有什么共同点？ 答：对于栈来说，由于只能在栈顶处进行插入和删除操作，这就使得数据元素到达栈（即往栈里插入元素）的顺序与数据元素离开栈（即从栈里删除元素）的顺序恰好相反。所以，堆栈的逻辑特点是后进先出（LIFO），或先进后出（FILO）。而对队列来说，插入在一端进行，删除在另一端进行，这就使得数据元素到达队列（即往队列里插入元素）的顺序与数据元素离开队列（即从队列里删除元素）的顺序是完全一致的。所以，队列的逻辑特点是先进先出（FIFO）或后进后出（LILO）。它们之间的共同之处是插入和删除只能在表的端点处进行（要知道，对于线性表，可以在表的任何位置处插入和删除）。

3．设有6个元素a1、a2、a3、a4、a5、a6，它们以此顺序依次进栈。假定要求它们的出栈顺序是a4、a3、a2、a6、a5、a1，那么应该如何安排push和pop操作序列？ 答：所需的push和pop操作序列如下：

push，push，push，push，pop，pop，pop，push，push，pop，pop，pop

4．有两个关键字序列：3、10、12、22、36、18、28、40和5、8、11、15、23、20、32、7。试问谁是堆，谁不是堆？把不是堆的序列通过筛选将它调整为一个堆。

答：依照序列的顺序，画出对应的完全二叉树如(a)和(b)所示。可以看出，(a)是一个堆，

(b)则不是，因为结点7破坏了堆的性质。为此，先将7和15对换，如图(c)所示；然

- 9 -

习题解答

后再将7和8对换，如图(d)所示。这时，序列2就被调整为是一个堆了。

5．给出如图6-27所示树的先序遍历序列和后序遍历序列。

答：该树的先序遍历序列为：A-B-E-F-K-L-M-C-G-D-H-I-J；该树的后序遍历序列是：

E-K-M-L-F-B-G-C-H-I-J-D-A。

6．有人说，有一棵结点数为n>1的二叉树，只包含有一个叶结点。这可能吗？如果可能的话，这样一棵二叉树应该是个什么样子呢？ 答：这是完全可能的，这种二叉树是从根结点开始只有左子树，或只有右子树的单支二叉树，如图所示。

1.已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造出该二叉树。（5分）

参及评分标准：

- 10 -

习题解答

A B H C E I D F J k

G

2. 已知图如下：

答案：

B E A F C D (1)试求图的邻接矩阵表示。

(2)试求图的邻接表表示。 答：(1)邻接矩阵表示：

A B C D E F ------------------------ A |0 1 1 0 0 0 B |0 0 1 0 0 1 C |0 0 0 1 0 0 D |0 0 0 0 0 1 E |0 0 0 1 0 1 F |0 0 0 0 0 0 (2)邻接表表示：

A ·->B ·->C ^ B ·->C ·->F ^ C ·->D ^

- 11 -

习题解答

D ·->F ^ E ·->D ·->F ^

F ^

3. 权值序列为：10、16、20、6、30、24，请用图示来表达构造一棵哈夫曼树的全过程。

答：构造这棵哈夫曼树的全过程如下所示。

4.已知稀疏矩阵A[100][100],它的非零元素为A[2][4]=56,A[67][23]=8,A[22][34]=-29, A[45][45]=67。请写出它的压缩三元组表TA。

0 1 2

0 100 100 4

1 2 4 56 2 22 34 -29 3 45 45 67 4 67 23 8

5 .一组记录的关键字为（50，80，55，40，42，85），则利用堆排序的方法建立初始堆是什

么？。

参及评分： (40，42，55，80，50，85)

6.一组记录的关键字为（90，80，55，40，42，85），则利用快速排序的方法，以第1个记录为基准得到的一次划分结果是什么？ 参及评分：（85，80，55，40，42，90）

1. 已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。

中序序列：c,b,d,e,a,g,I,h,j,f

- 12 -

习题解答

前序序列：a,b,c,d,e,f,g,h,I,j 参及评分：c e d b I j h g f a

2. 已知一图如下，则从顶点a出发按深度优先搜索遍历和广度优先搜索遍历则可以得到的顶点序列。

a b c e f d

深度优先搜索遍历参及评分 ： a-＞b-＞e-＞d-f＞-＞c(5分) 广度优先搜索遍历参及评分 ： a-＞b-＞e-＞c-＞d-＞f(5分) 3. 已知稀疏矩阵A[100][100],它的非零元素为

A[10][4]=56,A[67][23]=8,A[22][34]=-29, A[45][45]=67。请写出它的压缩三元组表TA。

I j v

10 4 56 22 34 -29 45 45 67 67 23 8

4.设有一个顺序栈S，元素s1, s2 ,s3 ,s4 , s5，s6依次进栈，如果6个元素的出栈顺序为s2, s3 ,s4 s6 ,s5 ,s1,则顺序栈的容量至少应为多少？

答案 ： 3 5 .一组记录的关键字为（45，80，55，40，42，85），则利用堆排序的方法建立初始堆（堆

顶为最小值时）是什么？。

答案： (85,80,55,40,42,45)

6.一组记录的关键字为（45，80，55，40，42，85），则利用快速排序的方法，以第1个记录为基准得到的一次划分结果是什么？ 答案：（42,40,45,55,80,85）

- 13 -

习题解答

1．已知无向连通网的邻接矩阵如下所示，试画出该无向连通网以及所对应的最小生

树。

答：无向连通网以及所对应的最小生成树如图(a)、(b)所示。

2．有关键字序列：20、10、30、15、25、5、35、12、27，请一步步画出构造二叉查找树的过程。

答：构造二叉查找树的过程如下：

3．分别写出如图5-32所示二叉树的先序、中序、后序遍历序列。

- 14 -

习题解答

图5-32 二叉树示例

答：先序遍历序列为：A-B-C-D-F-G-H-E，中序遍历序列为：B-A-D-G-F-H-C-E，后序遍历序

列为：B-G-H-F-D-E-C-A。

4．一个稀疏矩阵如图4-35所示。试问，它对应的三元组表是什么？

图4-35 稀疏矩阵示例

答：它所对应的三元组表如下。

5． 请画出由3个结点构成的所有二叉树，它们的高度分别是多少？

答：大小为3的不同的二叉树共有5种，如下图所示。

其中，4棵树的高度为2，1棵树的高度为1。

6．有两个关键字序列：3、10、12、22、36、18、28、40和5、8、11、15、23、20、32、7。试问谁是堆，谁不是堆？把不是堆的序列通过筛选将它调整为一个堆。 答：依照序列的顺序，画出对应的完全二叉树如(a)和(b)所示。可以看出，(a)是一个堆，

(b)则不是，因为结点7破坏了堆的性质。为此，先将7和15对换，如图(c)所示；然后再将7和8对换，如图(d)所示。这时，序列2就被调整为是一个堆了。

- 15 -