2023年数据结构导论串讲笔记.docVIP

1）已知出栈序列，写出也许的入栈序列并分析操作过程。

2）已知入栈序列，写出也许的出栈序列并分析操作过程。

[2023/1]如下图所示，输入元素为（A，B，C），在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有也许的输入序列。

输出端

输出端

输入端

栈

ABC

【分析】A，B，C三个字符排成的序列可以有：ABC、ACB、BAC、BCA、CAB、CBA六种，按堆栈操作的先进后出（或后进先出）的原则，只有输入序列为BCA时，输出无法得到ABC。由于输入序列为BCA时，要想先输出A，必须BCA均入栈，但这样只能得到序列ACB。其余五种输入序列都可在输出端得到序列ABC。

【解答】ABC、ACB、BAC、CAB、CBA

2．队列的操作

分析顺序队中元素入队出队操作及队列的状态。（考过）

[2023/10]设有一顺序队列sq，容量为5，初始状态时sq．front=sq．rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理。

d，e，b入队

d，e出队

i，j入队

b出队

n，o，p入队

【解答】队列及其头尾指针的状态变化情况如下图所示

Sq.front

Sq.front

Sq.rear

b

e

d

Sq.front

Sq.rear

b

Sq.front

Sq.rear

j

b

i

Sq.front

Sq.rear

j

i

Sq.front

Sq.rear

（a）初态（b）d，e，b入队（c）d，e出队（d）i，j入队（e）b出队

第5步操作无法进行，因队列已满。

3．二叉树的存储结构

给出一棵二叉树，画出二叉链表达意图及顺序存储示意图。（[2023/10][2023/10][2023/10]考过）

[2023/10]画出下列二叉树的二叉链表表达图。

B

B

E

D

F

H

G

A

C

B

【解答】二叉树的二叉链表表达

B

B

∧

∧

A

D

∧

C

G

∧

∧

F

H

∧

∧

E

∧

∧

给出二叉树的顺序存储示意图，画出二叉树。（[2023/1]考过）

[2023/1]已知某二叉树的顺序存储结构如下所示，试画出该二叉树。

A

B

C

D

∧

∧

∧

∧

E

∧

∧

∧

∧

∧

∧

∧

∧

F

G

【分析】按照给出的顺序存储结构，先绘制出一棵涉及空结点的完全二叉树，然后去掉空结点就是所求的二叉树。

【解答】所求二叉树如下图

A

A

C

B

D

E

G

F

4．二叉树的遍历

1）给出一棵二叉树，写出对该二叉树进行先根遍历、中根遍历及后根遍历的序列。（[2023/10][2023/1][2023/10]考过）

[2023/10]对于如下图所示二叉树，分别写出其先根遍历、中根遍历和后根遍历的结点访问序列。

B

B

E

D

F

A

C

B

【分析】根据二叉树三种遍历方法的原理，很容易写出该二叉树的先根遍历、中根遍历和后根遍历的结点访问序

【解答】先根遍历的结点访问序：A，B，D，E，F，C

中根遍历的结点访问序：B，F，E，D，A，C

后根遍历的结点访问序：F，E，D，B，C，A

2）给出一棵二叉树的先根遍历和中根遍历序列，恢复二叉树，写出后根遍历的序列。（[2023/10]考过）

[2023/10]现有某二叉树，按先根遍历的序列为ABDEFCGH，按中根遍历的序列为DEFBGHCA，试画出此二叉树。

【分析】由先根遍历和中根遍历恢复二叉树的方法：在先根序列中拟定根结点（最前面那个结点一定是根结点），然后根据根结点在中根序列中的位置分出根结点的左、右子树（根结点前面的那些结点为根结点的左子树上的结点，根结点后面的那些结点为根结点的右子树上的结点）。恢复该二叉树的任何一棵子树的过程仍然遵循这个原则。

【解答】二叉树如下图所示

B

B

C

D

AK

G

H

F

E

3）给出一棵二叉树的后根遍历和中根遍历序列，恢复二叉树，写出先根遍历的序列。（未考过，但也许考注意第四章的考核知识点的讲解）

5．树的存储结构

1）给出一棵树，画出该树的双亲表达法、孩子链表表达法、带双亲的孩子链表表达法及孩子兄弟链表表达法的示意图。（[2023/4]考过）

2）给出一棵树的某一种存储结构的示意图，画出相应的树。（未考过）

6．树的遍历

给出一棵树，写出对该树进行先根遍历、后根遍历及层次遍历的序列。（未考过）

7．二叉树与树、林的互相转换

1）将一棵二叉树转换为树。（未考过）

2）将一棵树转换为二叉树。（未考过）

3）将林转换为一棵二叉树。（未考过）

4）将二叉树转换为林。（未考过）

8．够造哈夫曼树

给出一组权值，构造一棵哈夫曼树