06-09数据结构真题及答案

06数据结构（50分）

一、单选题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码

填写在题干后面的括号内。每小题1分，共10分）

1.数据的基本单位是（ ）

A.数据项 B.数据类型 C.数据对象 D.数据元素

2.若频繁的对线性表进行插入和删除操作，则该线性表应该采用_______存储结构。（ ）

A.顺序 B.链式 C.散列 D.任意

3.若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的出栈次序是（ ）

A.7，5，3，9 B.9，7，5，3 C.7，5，9，3 D.9，5，7，3

4.下面的说法中，正确的是（ ）

A.字符串的长度指串中包含的字母的个数 B.字符串的长度指串中包含的不同字符的个数

C.一个字符串不能说是其自身的一个子串 D.若T包含在S中，则T一定是S的一个子串

5.广义表（（a，b），（c，d））的表尾是（ ）

A.d B.c，d C.（c，d） D.（（c，d））

6.n个顶点的连通图，其生成树有_______条边。（ ）

A.n-1 B.n C.n+1 D.不确定

7.若一棵二叉树有8个度为2的结点，则该二叉树的叶节点个数为（ ）

A.7 B.8 C.9 D.不确定

8.在有n个节点的二叉链表中有_______个空链域。（ ）

A.n+1 B.n C.n-1 D.不确定

9.在等概率的情况下，采用顺序插查找法查找长度为n的线性表，平均查找长度为（ ）

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

10.下列排序方法中，排序的比较次数与序列的初始排列状态无关的是（ ）

A.选择排序 B.插入排序 C.冒泡排序 D.快速排序

二、填空题（本大题共10小题，每小题1分，共10分）

1.假定一个顺序队列的队首和队尾分别为f和r，则判断队空的条件为__________________。

2.在顺序存储的线性表中插入或删除一个元素平均约移动表中__________________的元素。

3.设有一个二维数组A[5][4]，按行序优先存储，A[0][0]的存储地址是10，每个数组元素占

2个字节，则A[3][2]的存储地址是______________。

4.深度为k的二叉树至多有______________个结点。（k≥1）

5.在有n个结点，e条边的有向图的邻接表中有_________________个表结点。

6.对一棵二叉树进行___________遍历时，得到的结点序列是一个关键字的有序序列。

7.在一个图中，所有顶点的度数之和是边数的____________倍。

8.若有序表（15，21，33，46，58，80，87）中折半查找元素33时，与关键字比较

________次查找成功。

9.设哈希表长m=14，哈希函数H(key)=key MOD 11。表中已有4个元素：

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

15 38 61 84

1

如果用二次探测再散列处理冲突，关键字为49的记录的存储位置是______________。

10.具有n个顶点的无向完全图，有____________________条边。

三、判断题（本大题共5小题，每小题1分，共5分）

1.算法在执行时，对同样的输入可以得到不同的结果。（ ）

2.线性表的链式存储结构的内存单元地址一定不连续。（ ）

3.队列允许插入的一段成为队尾，允许删除的一端称为队头。（ ）

4.拓扑排序是内部排序。（ ）

5.树转换成二叉树，其根结点的右子树一定为空。（ ）

四、综合应用题（本大题共3小题，每小题5分，共15分）

1.画出具有三个结点的二叉树的所有形态（不考虑数据信息的组合情况）。（5分）

2.写出下图的邻接矩阵，并写出其从V1出发的深度优先搜索遍历序列（5分）

V1

V4 V3 V2

V5

3.将下图所示的树转换成二叉树，并写出该二叉树的先序遍历序列。（5分）

B

F

C D

A

E

G

五、算法设计（本大题共1小题，共10分）

1.已知线性表采用链式存储结构，结点类型定义如下，试编写一个算法，在带头结点的单

链表L中，删除所有值为x的结点。

typedef struct LNode

2

{ElemType data;

struct LNode *next;

}LNode,*Linklist;

07数据结构（50分）

一、单项选择题（10分，每题1分）

1.按二叉树的定义，具有3个结点的二叉树有________种。（ ）

A.3 B.4 C.5 D.6

2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若

p1=n，则pi为（ ）

A.i B.n=i C.n-i+q D.不确定

3.下面结论________是正切的。（ ）

A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B. 树的后根遍历序列与其对应的二叉树的先序遍历序列相同

C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同

D.以上都不对

4.评价一个算法时间性能的主要标准是（ ）

A.算法易于调试 B.算法易于理解

C.算法的稳定性和正确性 D.算法的时间复杂度

5.线性表的顺序存储结构是一种__________的存储结构。（ ）

A.随机存取 B.顺序存取 C.索引存取 D.散列存取

6.在顺序表中，只要知道__________，就可在相同时间内求出任一结点的存储地址。（ ）

A.基地址 B.结点大小 C.向量大小 D.基地址和结点大小

7.在中序线索二叉树中，若某结点有右孩子，则该结点的直接后继是（ ）

A.左子树的最右下结点 B.右子树的最右下结点

C.左子树的最左下结点 D.右子树耳朵最左下结点

8.一个栈的入栈序列是abcde，则栈的不可能输出序列是（ ）

9.广义表是线性表的推广，它们之间的区别在于（ ）

A.能否使用子表 B.能否使用原子项 C.表的长度 D.是否能为空

10.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点的个数是（ ）

A.9 B.11 C.12 D.不确定

二、填空题（每空1分，共10分）

1.顺序表中逻辑上相邻的元素的物理位置_____________________。

2.在分块查找方法中，首先查找索引表，然后再用顺序查找方法查找相应的

______________。

3.分配排序的两个基本过程是_______________________。

3

4.在拓扑排序中，拓扑序列的第一个顶点必定是_________________为0的顶点。

5.有n个结点的二叉链表中。其中空的指针域为__________________________。

6.有向图的邻接表表示适于求顶点的____________________。

7.有向图的邻接矩阵表示中，第i____________________上非零元素的个数为顶点vi的入度。

8.在树的_________________表示法中，求指定结点的双亲或祖先十分方便，但是求指定结

点的孩子或其他后代可能要遍历整个数组。

9.由五个分别带权值为9,2,3,5,14的叶子结点构成一棵哈夫曼树，该树的带权路径长度为

____________________。

10.具有n个顶点的有向图最多有________________条边。

三、填空题（30分）

1.写出头插法建立单链表的算法（5分）

2.求单源最短路径（从源点0开始），要求写出过程。（5分）

2

50

10

20

3

60

1

10

30

0

100

4

3.已知某二叉树的中序遍历序列：dfaechi

后序遍历序列：fdbehica

（1） 请构造出该二叉树；（3分）

（2） 写出前序遍历序列；（2分）

4.设查找的关键字序列{15,4,30,41,11,22,1}。画出对应的二叉排序树。（5分）

5.写出图的广度优先搜索算法（用邻接表存储）（5分）

6.线性表的关键字集合：

{19,14,23,01,68,20,84,27,55,11,10,79}已知散列函数为：H（k）=k%13，采用拉链法处理冲

突，并设计出链表结构。（5分）

08数据结构（50分）

一、单项选择题（10分，每题1分）

1.若一个栈的输入序列为1，2，3，…，n，输出序列的第一个元素是i，则第i个输出元素

是（）

A．i-j-1 B.i-j C.j-i+1 D.不确定的

2.循环队列存储在数组]中，则入队的操作为（）

4

=rear+1 =(rear+1)mod(m-1)

=(rear+1)mod m =(rear+1)mod(m+1)

3.二维数组A的每个元素是由6个字符组成的串，其行下表i=0，1，…，8，列下表

j=1,2，…，10。若A按行序为主序存储，元素A[8][5]的起始地址与当A按列序为主序存

储时的元素_________的起始地址相同。（设每个字符占一个字节）（）

A.A[8][5] B.A[3][10] C.A[5][8] D.A[0][9]

4.下面说法不正确的是（）

A.广义表的表头总是一个广义表 B.广义表的表尾总是一个广义表

C.广义表难以用顺序存储结构 D.广义表可以是一个多层次的结构

5.算术表达式A+B*C-D/E转为前缀表达式后为（）

A.-A*C/DE B.-A+B*CD/E C.-+ABC/DE D.-+A*BC/DE

6.有n个叶子的哈夫曼树的结点总数为（）

A.不确定 B.2n C.2n+1 D.2n-1

7. 若X是中序线索二叉树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）

A.X的双亲 B.X的右子树中最左的结点

C.X的左子树中最右结点 D.X的左子树中最右叶结点

8.无向图G=（V，E），其中V={a，b，c，d，e，f}，E={{a，b}，{a，e}，{a，c}，{b，e}，

{c，f}，{f，d}，{e，d}}，对该图进行广度优先遍历，得到的顶点序列正确的是（ ）

A.a，b，e，c，d，f B.a，c，f，e，b，d

C.a，e，b，c，f，d D.a，e，d，f，c，b

9.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要

进行_________探测。（ ）

A.k-1次 B.k次 C.k+1次 D.k（k+1）/2次

10.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数

据初始特性影响的是（ ）

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

二、填空题（5分，每题1分）

1.在有序表A[1..12]中，采用折半查找算法查等于A[12]的元素，所比较的元素下标依次为

_____________________________。

2.求图的最小生成树有两种算法，________________ 算法适合于求稀疏图的最小生成树。

3.一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为_____________。

4.在单链表L中，指针p所指结点有后继结点的条件是________________________。

5.一个深度为k，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依次

对结点编号，则编号是i的结点所在的层次号是_______________________（跟所在的层次

号规定为1层）。

三、判断题（5分，每题1分）

1.链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结

构中效率高。 （ ）

5

2.对一棵二叉树进行层次遍历时，应借助于一个栈。 （ ）

3.将一棵树转成二叉树，跟节点没有左子树。 （ ）

4.一个有向图的邻接表和逆邻接表中结点的个数可能不等。 （ ）

5.在待排序数据有序的情况下，快速排序效果好。 （ ）

四、应用题（20分，每题5分）

1.用集合{46，88，45，39，70，58，101，10，66，34}建立一棵二叉排序树，画出该树，

并求在等概率情况下的平均查找长度。

2.设一组关键字{9，01，23，14，55，20，84，27}，采用哈希函数：H（key）=key

mod 7和二次探测再散列法解决冲突，对该关键字序列构造表长为10的哈希表。

3.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07、0.19、

0.02、0.06、0.32、0.03、0.21、0.10，试为这8个数字设计哈夫曼编码。

4.用普里姆算法构造下图的一棵最小生成树，并给出选点顺序。（以①为起点）

1

18

23

12

15

20

2

6

7

5

5

4

7

6

8

4

3

25

10

五、算法设计题（10分）

编写一个算法来交换单链表中指针P所指接点与其后继结点，HEAD是该链表的头结点，P

指向该链表中的某一结点。

山东省2008年普通高等教育专升本统一考试

数据结构（50分）

一、单项选择题（10分，每题1分）

1. 【答案】D

【解析】栈的基本性质是后进先出，本题中，在输出序列第一个元素是i时，只能确定1-

i-1这些元素的输出的先后次序，但是不能确定出第i个元素具体输出哪个元素。

2. 【答案】D

【解析】在循环队列中，rear指针指示队尾，本题中存储数组实质上为A[m+1]。所以，入

队列的操作应该是修改rear=(rear+1)%(m+1),答案Ｃ是错误的。

3. 【答案】B

【解析】本题中二维数组属于9行10列。所以，首先确定以行序为主序的存储中，A[8][5]

在所有元素排列中的位置为第85位，同样的确定以列序为主序的第85个存储元素的元素

应该为A[3][10]。

4. 【答案】A

6

【解析】构成广义表的数据元素可以是单个元素，也可以是广义表。广义表的表头就是广

义表中的第一个元素，可以是单个元素，也可以是子表。选项B、C、D都是正确的。

5. 【答案】D

【解析】在算数表达式的前缀表达式实质上就是运算符写在两个运算数的前面，当然在实

现转换时，要考虑运算数的相对位置不变，而且考虑运算的优先级问题。当然，也可以采

用二叉树表示出算数表达式，这样，前序遍历顺序即为前缀表达式（波兰式），后序遍历即

位后缀表达式（逆波兰式），本题答案选D。

6. 【答案】D

【解析】哈夫曼树的特点是没有度为1的结点，根据二叉树的性质3，n0=n2+1，所以，具

有n个叶子结点的二叉树具有n-1个度为２的结点，因此，答案选Ｄ。

7. 【答案】C

【解析】因为在中序线索二叉树中，结点X有左子树，所以，该结点前驱在左子树中，左

子树中最右的结点是子树中最后一个遍历的结点，该结点可能为叶子结点，也可能是度为

1的结点（即有左孩子）。

8. 【答案】A

a

c

f

b

e

d

【解析】根据本题无向图的定义，可以图G如右图所示：

根据广度优先遍历的算法思想，可以确定A是正确的，选项B、C、D都是错误的。

9. 【答案】D

【解析】采取线性探测法存储这k个同义词，则第一个关键字可以直接存储，其余的k-1

个元素中，理想的情况下，第１个元素探测１次可以存储，第２个元素探测２次才能存储，

以此类推，因此，至少需要探测的次数为k(k+1)/2。

10. 【答案】B

【解析】直接插入排序的算法思想是从第2到最后一个元素，依次插入到前面的有序序列

中，因此，每趟执行结束，不能确定出一个元素最终的位置；快速排序的每趟可以确定出

枢轴元素的最终位置，而且，当元素基本有序时，其排序性能会降低，所以选B。选项C、

D能符合第一条要求，但是其时间性能跟待排元素的序列无关。

二、填空题（本大题共10小题，每小题1分，共10分）

1. 【答案】6、9、11、12

【解析】根据有序表的折半查找的mid的取值为(low+high)/2，可以确定判定树的形态如下，

6

3

1

2

4

5

7

810

9

11

12

查找下标为12的元素时，先后要与下标为：6、9、11、

7

12四个元素进行比较。

2．【答案】克鲁斯卡尔（Kruskal）

【解析】求解最小生成树的算法主要有两种，普里姆算法（Prim）时间复杂度为O（n2）,

与网中的边数无关，因此适合于求边稠密的网的最小生成树；而克鲁斯卡尔（Kruskal）算

法时间复杂度为O（eloge），因此，适合于求边稀疏的网的最小生成树。

3. 【答案】2

【解析】左子树为空，则根结点没有前驱，左孩子指针域为空，另外，根结点右子树中最

后一个结点没有后继，右孩子指针域也为空，所以，该二叉树中空链域的个数为2。

4. 【答案】p->next!=NULL（或文字说明“指针P所指结点的指针域不等于NULL”）

【解析】在单链表L中，指针p所指结点有后继，前提是指针P所指结点的指针域不等于

NULL，如果指针域默认为next，则可以表示为“p->next!=NULL” 。（注：NULL一定是

大写）

５．【答案】



log

2

i



1

【解析】深度为K的结点已经构成完全二叉树，所以前i个结点也为完全二叉树，所以根

据性质4可以确定第i个结点的深度为



三、判断题（5分，每题1分）

1．【答案】√

【解析】链式存储结构的线性表的优点就在于实现插入和删除操作时，不需要大量元素的

移动，因此，比顺序存储结构中实现插入删除操作效率高。

2．【答案】×

【解析】实现二叉树的按层遍历时，应借助于一个队列作为辅助结构。

3．【答案】√

【解析】树转换为二叉树是依据的孩子兄弟表示法这种存储结构，树根没有兄弟，所以，

一棵树转换成二叉树，对应二叉树根结点没有左子树。

4．【答案】×

【解析】有向图的邻接表中结点的个数与逆邻接表中结点的个数是相等的，都等于图中所

有顶点的入度和（或出度和）的值。

5．【答案】×

【解析】就平均时间而言，快速排序目前被认为是最好的一种内部排序方法，但是，当待

排序列基本有序时，快速排序将蜕化为冒泡排序，因此，排序效果反而降低。

四、综合应用题（本大题共3小题，每小题5分，共15分）

1．答：根据结点画出二叉排序的过程如图所示：

log

2

i



1

。

8

46

46

8845

46

88

39

45

46

88

39

45

46

88

7039

45

46

88

70

58

46

45

39

58

70

88

101

10

39

58

45

46

88

70

101

10

39

58

45

46

46

88

45

70101

39

10

66

34

66

58

70101

88

等概率情况下，平均查找长度为：（5*2+4*2+3*3+2*2+1*1）/10=3.2

2．答：根据哈希函数和处理冲突的方法为二次探测再散列，构造哈希表如图所示：

0

14

1

1

2

9

3

23

4

84

5

27

6

55

7

20

89

【解析】注意关键字的顺序,9%7=2; 1%7=1; 23%7=2,冲突,但是(2+12)%10=3;14%7=0;

55%7=6;20%7=6,冲突,但是(6+12)%10=7;84%7=0,冲突,但是(0+12)%10=1,已经占用,由于函数

值已经是0了，在这里不能再试探-12,因此(0+22)%10=4,所以84存储在下标4的单元格内。

最后27%7=6，冲突，(6+12)%10=7，仍然冲突，（6-12)%10=5，所以27存储在下标5的单

元格内。

3．答：根据每个字符出现的频率，我们可以求解哈夫曼树，为方便求解，不妨将频率变为

整数，则权值分别为：7，19，2，6，32，3，21，10，由此构造哈夫曼如图：

0

60

0

28

0

11

0

5

0

2

1

3

1

6

0

7

1

17

1

10

1

32

0

19

100

1

40

1

21

由此可以设定每个字符的哈夫曼编码：0.02：00000； 0.03:00001; 0.06:0001;

0.07:0010; 0.1:0011; 0.32:01; 0.19:10; 0.21:11。

4.答:根据普里姆算法构造最小生成树,如下图所示:

9

1

4

6

7

6

1

4

6

7

6

1

4

18

2

6

7

1

4

18

2

5

3

7

6

1

4

6

18

8

2

5

3

6

18

4

5

64

12

8

6

12

4

6

7

5

3

五、算法设计（本大题共１小题，共10分）

答：Linklist exchange(Linklist &head,Linklist p)

{ q=head->next;

pre=head; //初始化q、pre指针，当q指针移动到与P指针相等时，则pre指针正好指向前

驱结点;

while(q!=NULL&&q!=p) {pre=q;q=q->next;}

if(p->next==NULL) printf(“p无后继结点n”);

else { q=p->next; //利用q、pre、p三个指针联合实现当前结点与前驱结点的交换;

pre->next=q;

p->next=q->next;

q->next=p;

}

}

山东省2007年普通高等教育专升本统一考试

计算机科学与技术专业综合二试卷参考答案

数据结构（50分）

一、单选题（每小题1分，共10分，）

1. 【答案】C

【解析】具有三个结点的二叉树的形态共有5种，而具有三个结点的树的形态是2种。

2. 【答案】C

【解析】若输出的第一个元素为n，则所有元素均已经入栈，所以出栈顺序即为元素的逆

序排列，因此，输出的第i个元素的值为n-i+1。

3. 【答案】A

【解析】根据树与二叉树的相互转换数关系，以及树及二叉树的遍历顺序，有以下结论：

（1）树的先根遍历顺序与对应二叉树的先序遍历顺序相同；（2）树的后根遍历顺序与对

应二叉树的中序遍历顺序相同。

4. 【答案】D

【解析】算法的时间性能的评价主要使用算法的时间复杂度，算法的空间性能的评价主要

采用空间复杂度。

5. 【答案】A

【解析】线性表的顺序存储结构要求分配连续的存储空间，因此，可以实现数据元素的顺

10

序存取以及随机存取。但元素的插入和删除需要涉及大量元素的移动；而线性表的链式存

储方便于元素的插入与删除，但是不能实现随机存取，只能进行顺序存取。

6. 【答案】D

【解析】顺序表要求存储空间是连续，所以，只要知道基地址，知道每个元素所占的字节

数，就可以求每个元素的存储起始地址。

7. 【答案】D

【解析】在中序线索二叉树中，若某结点有右子树，则在访问完该结点后要访问右子树中

最左边的结点，所以答案选D。

8. 【答案】C

【解析】栈的基本性质是后进先出，在入栈序列为abcde，出栈的第一个元素为d时，则

已经入栈，所以，此时“abc”三个元素的出栈序列中，一定是cba的顺序，而不能出现

cab的顺序，所以选项C是错误的。

9. 【答案】A

【解析】构成广义表的数据元素可以单个元素，也可以是由若干个元素所组成的子表。广

义表属于特殊的线性表，特殊的地方在于广义表的元素中能否使用子表。

10. 【答案】B

【解析】根据二叉树的基本性质3，对于任意一棵二叉树，满足度为0的结点为度为2的

结点数加1。所以，答案选B

二、填空题（本大题共10小题，每小题1分，共10分）

1. 【答案】一定相邻

【解析】顺序表采用连续存储空间作为元素的存储结构，所以，逻辑上相邻的数据元的物

理存储空间也一定相邻。

2．【答案】块

【解析】在索引顺序表中，将所有的关键字进行分块，块与块之间关键字大小有序，在每

个块内部元素排列无序，可以把每个组中最大元素值作为该组的索引加入到索引表中排列，

所以，索引表中元素排列是有序的，因此，在查找元素时，先查找索引表，获得查找元素

所在组后，再使用顺序查找去查找相应的块。

3. 【答案】分配和收集

【解析】分配法排序属于一种典型的多关键字排序，分配排序的基本思想是排序过程无须

比较关键字，而是通过“分配”和“收集”过程来实现排序。

4. 【答案】入度

【解析】拓扑排序每次都选择没有前驱的结点进行输出，其中结点没有前驱，即入度为0。

5．【答案】n+1

【解析】二叉链表中，每个结点有2个指针域，具有n个结点的二叉链表一共有2n个指针

域，其中，除根结点外，每个结点需要一个指针来指向，所以空的指针域的个数为n+1。

6.【答案】出度

【解析】有向图的邻接表是指:所有顶点建立顶点结点，以每个顶点为弧尾的所有弧对应的

另外一个顶点序号构成表结点链接形成的单链表。所以，通过计数每个单链表中表结点的

11

个数，可以计算每个顶点的出度。

7．【答案】列

【解析】有向图的邻接矩阵的特点是，通过求解每一行上1的个数，可以求解每个顶点的

出度；通过求解每一列上1的个数，可以求解每个顶点的出度。无向图的邻接矩阵属于对

称矩阵，每个顶点的度即为行或列上1的个个数。

8.【答案】双亲

【解析】树的表示方法一共有三种，双亲表示法、孩子表示法以及孩子兄弟表示法。其中

双亲表示法为每个树中元素建立一个结点，包括存储数据元素本身，以及该结点的双亲结

点的存储下标，所以，该存储方法可以很容易的求解结点的双亲以及祖先，但是求解结点

的孩子及后代需要遍历整个数组。

9．【答案】67。

33

1914

109

5

23

5

【解析】。图为五个权值形成的哈夫曼树，树的带权路径长度为：

(2+3)*4+5*3+9*2+14*1=67

10. 【答案】n(n-1)

【解析】在有n个顶点的有向完全图中，从每个顶点出去的弧有n-1条，所以总弧数为

n(n-1)。

四、综合题（30分，每题5分）

1．答：viod creat(Linklist &L)

{ L=(Linklist)malloc(sizeof(Lnode));

L->next=NULL;

for(i=n;i>0;i++)

{ p=(Linklist)malloc(sizeof(Lnode));

scanf(&p->data);

p->next=L->next;

L->next=p;

}

} 注意：除了使用头插法，还有尾插法，可以查阅资料写出算法。

2．答：

12

1

求顶点0其余各顶点的最短路径

10

(0,1)

/ / /

2 ∞ 60

(0,1,2)

50

(0,3,2)

/

/

3 30

(0,3)

30

(0,3)

100

(0,4)

3

/

4 100

(0,4)

90 60

(0,3,4) (0,3,2,4)

2 添加

顶点

1

3．答：根据（1）中序遍历的特点：左子树、根、右子树的遍历顺序；（2）后序遍历的特

点：左子树、右子树、根；（3）二叉树的每棵子树也符合该特性。所以，该二叉树的构造

过程为:

a

a

b

dfb

echi

d

dfehi

fh

ei

a

b

c

c

由此可得到二叉树的前序遍历顺序为：abdfceih

4．答：根据二叉排序树的定义，创建过程如下图：

15

15

44304304

11

30

41

151515

41

15

15

4

1122

30

4

41

11122

41

30

5. 答：

该邻接表的结构描述如下：

#define VERTEX_MAX 100

typedef struct node

{int adjvex;

struct node *next;

}Edgenode; //表结点的类型定义

13