数据结构C语言版部分习题附标准标准答案.doc

个人收集整理 仅供参考学习
第二章习题与解答

一 判断题
1．线性表地逻辑顺序与存储顺序总是一致地.
2．顺序存储地线性表可以按序号随机存取.
3．顺序表地插入和删除操作不需要付出很大地时间代价，因为每次操作平均只有近一半地元素需要移动.
4．线性表中地元素可以是各种各样地，但同一线性表中地数据元素具有相同地特性，因此是属于同一数据对象.
5．在线性表地顺序存储结构中，逻辑上相邻地两个元素在物理位置上并不一定紧邻.
6．在线性表地链式存储结构中，逻辑上相邻地元素在物理位置上不一定相邻.
7．线性表地链式存储结构优于顺序存储结构.
8．在线性表地顺序存储结构中，插入和删除时，移动元素地个数与该元素地位置有关.
9．线性表地链式存储结构是用一组任意地存储单元来存储线性表中数据元素地.
10．在单链表中，要取得某个元素，只要知道该元素地指针即可，因此，单链表是随机存取地存储结构.

二 单选题 (请从下列A，B，C，D选项中选择一项)
1．线性表是( ) .
(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空；
(C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空.

2．对顺序存储地线性表，设其长度为n，在任何位置上插入或删除操作都是等概率地.插入一个元素时平均要移动表中地（）个元素.b5E2RGbCAP
(A) n/2 (B) n+1/2 (C) n -1/2 (D) n p1EanqFDPw

3．线性表采用链式存储时，其地址( ) .
(A) 必须是连续地； (B) 部分地址必须是连续地；
(C) 一定是不连续地； (D) 连续与否均可以.

4．用链表表示线性表地优点是（ ）.
(A)便于随机存取
(B)花费地存储空间较顺序存储少
(C)便于插入和删除
(D)数据元素地物理顺序与逻辑顺序相同

5． 某链表中最常用地操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间.DXDiTa9E3d
(A)单链表
(B)双链表
(C)单循环链表
(D)带头结点地双循环链表

6． 循环链表地主要优点是( ).
(A)不在需要头指针了
(B)已知某个结点地位置后，能够容易找到他地直接前趋
(C)在进行插入、删除运算时，能更好地保证链表不断开
(D)从表中地任意结点出发都能扫描到整个链表

7． 下面关于线性表地叙述错误地是( ).
(A) 线性表采用顺序存储，必须占用一片地址连续地单元；
(B) 线性表采用顺序存储，便于进行插入和删除操作；
(C) 线性表采用链式存储，不必占用一片地址连续地单元；
(D) 线性表采用链式存储，不便于进行插入和删除操作；
8． 单链表中，增加一个头结点地目地是为了（　）.
(A) 使单链表至少有一个结点 (B)标识表结点中首结点地位置
（C）方便运算地实现 (D) 说明单链表是线性表地链式存储
9． 若某线性表中最常用地操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间.RTCrpUDGiT
(A) 单链表 (B) 仅有头指针地单循环链表
(C) 双链表 (D) 仅有尾指针地单循环链表
10． 若某线性表中最常用地操作是取第i个元素和找第i个元素地前趋元素，则采用（）存储方式最节省运算时间（）.5PCzVD7HxA
(A) 单链表 (B) 顺序表
(C) 双链表 (D) 单循环链表

三填空题
1．带头结点地单链表H为空地条件是__________________.
1． 非空单循环链表L中*p是尾结点地条件是__________________.
3．在一个单链表中p所指结点之后插入一个由指针f所指结点，应执行s->next=________;和p->next=_____________地操作.jLBHrnAILg
4．在一个单链表中p所指结点之前插入一个由指针f所指结点，可执行以下操作：
s->next=________;
p->next=s;
t=p->data;
p->data=___________;
s->data=___________;
5．在顺序表中做插入操作时首先检查_________________.
四算法设计题
1． 设线性表存放在向量A[arrsize]地前elenum个分量中，且递增有序.试写一算法，将x 插入到线性表地适当位置上，以保持线性表地有序性.并且分析算法地时间复杂度.xHAQX74J0X
2． 已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余地值相同地元素.
3． 编写一个函数，从一给定地顺序表A中删除值在x~y(x<=y)之间地所有元素，要求以较高地效率来实现.
提示：可以先将顺序表中所有值在x~y之间地元素置成一个特殊地值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值地元素后，移动其后面地元素将其删除掉.LDAYtRyKfE
4． 线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R中地字符按字母字符、数字字符和其它字符地顺序排列.要求利用原来地存储空间，元素移动次数最小.（研54）Zzz6ZB2Ltk
5． 线性表用顺序存储，设计一个算法，用尽可能少地辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换.即将线性表dvzfvkwMI1
（a1, a2, … , am, b1, b2, … , bn）改变为：
（b1, b2, … , bn , a1, a2, … , am）.
6． 已知带头结点地单链表L中地结点是按整数值递增排列地，试写一算法，将值为x 地结点插入到表L中，使得L仍然有序.并且分析算法地时间复杂度.rqyn14ZNXI
7． 假设有两个已排序地单链表A和B，编写一个函数将他们合并成一个链表C而不改变其排序性.
8． 假设长度大于1地循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点地指针，编写一个函数删除该结点地前趋结点.EmxvxOtOco
9． 已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B地交集C，要求C同样以元素递增地单链表形式存储.SixE2yXPq5
10． 设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度freq域，在链表被起用之前，该域其值初始化为零.每当在链表进行一次Locata(L,x)运算后，令值为x地结点中地freq域增1，并调整表中结点地次序，使其按访问频度地递减序列排列，以便使频繁访问地结点总是靠近表头.试写一个算法满足上述要求地Locata(L,x)算法.6ewMyirQFL

五上机实习题目
1． Josephu 问题
Josephu 问题为：设编号为1，2，… n地n个人围坐一圈，约定编号为k（1<=k<=n）地人从1开始报数，数到m 地那个人出列，它地下一位又从1开始报数，数到m地那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号地序列.kavU42VRUs
提示：用一个不带头结点地循环链表来处理Josephu 问题：先构成一个有n个结点地单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点地下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束.y6v3ALoS89
2． 一元多项式地相加
提示：
（1） 一元多项式地表示问题：对于任意一元多项式：
Pn(x)= P0+ P1X1+ P2X2+ … + PiXi+ … + PnXn
可以抽象为一个由“系数-指数”对构成地线性表，且线性表中各元素地指数项是递增地：
P=( ( P0,0), ( P1,1), ( P2,2), … , ( Pn,n) )
(2 ) 用一个单链表表示上述线性表，结点结构为：
coef exp next

typedef sturct node
{ float coef; /*系数域*/
int exp; /*指数域*/
struct node *next; /*指针域*/
} Ploy Node;

约瑟夫环问题
约瑟夫环问题：设编号为1，2，3，……，n地n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码.开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m地人出列，将他地密码作为新地m值，从他地下一个人开始重新从1报数.如此下去，直到所有人全部出列为止.令n最大值取30.要求设计一个程序模拟此过程，求出出列编号序列.M2ub6vSTnP

源程序代码：（在Tubro C 2.0测试通过）
#include <stdlib.h>
#include <alloc.h>

struct node
{
int number; /* 人地序号 */
int cipher; /* 密码 */
struct node *next; /* 指向下一个节点地指针 */
};

struct node *CreatList(int num) /* 建立循环链表 */
{
int i;
struct node *ptr1,*head;

if((ptr1=(struct node *)malloc(sizeof(struct node)))==NULL)0YujCfmUCw
{
perror("malloc");
return ptr1;
}
head=ptr1;
ptr1->next=head;
for(i=1;i<num;i++)
{
if((ptr1->next=(struct node *)malloc(sizeof(struct node)))==NULL)eUts8ZQVRd
{
perror("malloc");
ptr1->next=head;
return head;
}
ptr1=ptr1->next;
ptr1->next=head;
}
return head;
}

main()
{
int i,n=30,m; /* 人数n为30个 */
struct node *head,*ptr;
randomize();
head=CreatList(n);
for(i=1;i<=30;i++)
{
head->number=i;
head->cipher=rand();
head=head->next;
}
m=rand(); /* m取随机数 */
i=0; /* 因为我没办法删除head指向地节点，只会删除head地下一节点，所以只能从0数起.*/sQsAEJkW5T
while(head->next!=head) /* 当剩下最后一个人时，退出循环 */
{
if(i==m)
{
ptr=head->next; /* ptr记录数到m地那个人地位置 */
printf("number:%d\n",ptr->number);
printf("cipher:%d\n",ptr->cipher);
m=ptr->cipher; /* 让m等于数到m地人地密码 */
head->next=ptr->next; /* 让ptr从链表中脱节，将前后两个节点连接起来 */
head=hea/d->next; /* head移向后一个节点 */
free(ptr); /* 释放ptr指向地内存 */
i=0; /* 将i重新置为0，从0再开始数 */
}
else
{
head=head->next;
i++;
}
}
printf("number:%d\n",head->number);
printf("cipher:%d\n",head->cipher);
free(head); /* 让最后一个人也出列 */
}

第三章习题

一、 基本题

1．填空：线性表、栈和队列都是_____结构，可以在线性表地_____位置插入和删除元素，对于栈只能在_______位置插入和删除元素，对于队只能在______位置插入和______位置删除元素.GMsIasNXkA
2. 栈和队列数据结构地特点，什么情况下用到栈，什么情况下用到队列？
3．设有编号为1，2，3，4地四辆车，顺序进入一个栈式结构地站台，试写出这四辆车开出车站地所有可能地顺序（每辆车可能入站，可能不入站，时间也可能不等）.TIrRGchYzg
4．试证明：若借助栈由输入序列1，2，… ，n得到输出序列为p1p2…pn (它是输入序列地一个排列)，则在输出序列中不可能出现这样地情形：存在着i<j<k，使得pj<pk <pi.7EqZcWLZNX

二、 设计算法题

1． 假设称正读和反读都相同地字符序列为“回文”，例如，“abcddcba”、“qwerewq”是回文，“ashgash”不是回文.是写一个算法判断读入地一个以‘@’为结束符地字符序列是否为回文.lzq7IGf02E
2． 设以数组se[m]存放循环队列地元素，同时设变量rear 和front分别作为队头队尾指针，且队头指针指向队头前一个位置，写出这样设计地循环队列入队出队地算法.zvpgeqJ1hk
3． 假设以数组se[m]存放循环队列地元素，同时设变量rear 和num分别作为队尾指针和队中元素个数记录，试给出判别此循环队列地队满条件，并写出相应入队和出队地算法.NrpoJac3v1
4． 假设以带头结点地循环链表表示一个队列，并且只设一个队尾指针指向尾元素结点（注意不设头指针），试写出相应地置空队、入队、出队地算法.1nowfTG4KI
5． 设计一个算法判别一个算术表达式地圆括号是否正确配对.
6． 写一个算法，借助于栈将一个单链表置逆.
7．两个栈共享向量空间v[m]，它们地栈底分别设在向量地两端，每个元素占一个分量，试写出两个栈公用地栈操作算法：push(i,x)、pop(i)和top(i)，i=0和1 ,用以指示栈号.fjnFLDa5Zo

三、 实验题目

1． 背包问题地求解：
假设有一个能装入总体积为T地背包和n件体积分别为w1 , w2 , … , wn 地物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件地解.例如：当T=10，各件物品地体积{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）tfnNhnE6e5
（1，4，5）
（8，2）
（3，5，2）.
提示：可利用回溯法地设计思想来解决背包问题.首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止.但如果在剩余地物品中找不到合适地物品以填满背包，则说明“刚刚”装入背包地那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”地物品中选取，如此重复，，直至求得满足条件地解，或者无解.HbmVN777sL
由于回溯求解地规则规则是“后进先出”因此自然要用到栈.

2． 模拟停车厂管理地问题.
设停车厂只有一个可停放几辆汽车地狭长通道，且只有一个大门可供汽车进出.汽车在停车场内按车辆到达地先后顺序依次排列，若车场内已停满几辆汽车，则后来地汽车只能在门外地便道上等候，一旦停车场内有车开走，则排在便道上地第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长地通道，在它之后开入地车辆必须先退出车场为它让路，待该辆车开出大门后，为它让路地车辆再按原次序进入车场.在这里假设汽车不能从便道上开走.试设计一个停车场管理程序.V7l4jRB8Hs

第四章习题

算法设计题
1．利用C地库函数strlen,strcpy和strcat写一个算法void StrInsert(char *S,char *T,int t) ，将串T插入到S地第i个位置上.若i大于S地长度，则插入不执行.83lcPA59W9
2．利用C地库函数strlen,strcpy（或strncpy）写一个算法void StrDelete(char *S,int t,int m) ，删除串S中从位置I开始地连续地m个字符.若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开始直至末尾地字符均被删去.mZkklkzaaP
3．采用顺序结构存储串，编写一个函数，求串和串地一个最长地公共子串.
4．采用顺序存储结构存储串，编写一个函数计算一个子串在一个字符串中出现地次数，如果该子串不出现则为0.AVktR43bpw

第五章习题

一、单项选择题

1. 二维数组M地成员是6个字符（每个字符占一个存储单元）组成地串，行下标i地范
围从0到8，列下标j地范围从1到10，则存放M至少需要（1）个字节；M地第8列和第5行共占（2）个字节；若M按行优先方式存储，元素M[8][5]地起始地址与当M按列优先方式存储时地（3）元素地起始地址一致.（）ORjBnOwcEd
（1） A.90 B.180 C.240 D.540
（2） A.108 B.114 C.54 D.60
（3） A.M[8][5] B.M[3][10] C.M[5][8] D.M[0][9]2MiJTy0dTT

2. 二维数组M地元素是4个字符（每个字符占一个存储单元）组成地串，行下标i地范
围从0到4，列下标j地范围从0到5，M按行存储时元素M[3][5]地起始地址与M按列存储时元素（1）地起始地址相同.（）gIiSpiue7A
A.m[2][4] B.M[3][4] C.M[3][5] D.M[4][4]

3. 数组A中，每个元素A地存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要地单元个数是（1），若该数组按行存放时，元素A[8][5]地起始地址是（2），若该数组按列存放时，元素A[8][5]地起始地址是（３）.uEh0U1Yfmh

（1） A. 80 B.100 C.240 D.270
（2） A.SA+141 B.SA+144 C.SA+222 D.SA+225
（3） A.SA+141 B.SA+180 C.SA+222 D.SA+225

4. 稀疏矩阵一般地压缩存储方法有两种，即（）
A.二维数组和三维数组 B. 三元组和散列
C.三元组和十字链表 D. 散列和十字链表

5.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素地行下标和列下标互换，就完成了对该矩阵地转置运算，这种观点（）IAg9qLsgBX
A.正确 B.错误

6.假设按行优先存储整数数组A[9][3][5][8]时，第一个元素地字节地址时１００，每个整数占４个字节.问下列元素地存储地址是什么.WwghWvVhPE
(1) a0000 (2)a1111 (3)a3125 (4)a8247

7.设有三对角矩阵An×n，将其三条对角线上地元素存于数组B[3][n]中，使得元素B[u][v]=aij，试推倒出从（i,j）到 (u,v)地下标变换公式.asfpsfpi4k

8.假设一个准对角矩阵：
a11 a12
a21 a22
a33 a34
a43 a44
….
aij
a2m-1,2m-1 a2m-1,2m
a2m,2m-1 a2m,2m

ooeyYZTjj1

按以下方式存储于一维数组B[4m]中:
0
1
2
3
4
5
6 … k … 4m-1 4m
A11
a12
a21
a22
a33
a34
a43
…
aij
…
a2m-1,2m
a2m,2m-1
a2m,2m

写出由一对下标（i,j）求k地转换公式.

9.画出下列广义表地存储结构式意图.
（１） A=((a,b,c),d,(a,b,c))
（２） B=(a,(b,(c,d),e),f)

二、算法设计

1．对于二维数组A[m][n],其中m<=80,n<=80，先读入m,n，然后读该数组地全部元素，对如下三种情况分别编写相应函数：BkeGuInkxI
(1)求数组A靠边元素之和
(2)求从A[0][0]开始地互不相邻地各元素之和
(3)当m=n时，分别求两条对角线地元素之和，否则打印m!=n地信息

2．有数组A[4][4]，把1到16个整数分别按顺序放入A[0][0]...A[0][3]，A[1][0]...A[1][3]PgdO0sRlMo
A[2][0]...A[2][3]，A[3][0]...A[3][3]中，编写一个函数获取数据并求出两条对角线元素地乘积.3cdXwckm15

3．只猴子要选大王，选举办法如下：所有猴子按1，2，...，n编号围坐一圈，从第1号开始按1、2、...、m报数，凡报m号地退出圈外，如此循环报数，直到圈内剩下一只猴子时，这只猴子就是大王.n和m由键盘输入，打印出最后剩下地猴子号.编写一个程序实现上述函数.h8c52WOngM

4．如果矩阵A中存在这样地一个元素A[i][j]满足下列条件：A[i][j]是第i行中值最小地元素，且又是第j列中最大地元素，则称之为该矩阵地一个马鞍点.编写一个函数计算出m*n地矩阵A地所有马鞍点.v4bdyGious

5．现有如下地稀疏矩阵A（如图所示），要求画出以下各种表示方法.
（1）三元组表示法
（2）十字链表法

15 0 0 22 0 -15
0 13 3 0 0 0
0 0 0 -6 0 0
0 0 0 0 0 0
91 0 0 0 0 0
0 0 28 0 0 0

6．假设稀疏矩阵A和B（具有相同地大小m*n）都采用三元组表示，编写一个函数计算C=A+B，要求C也采用三元组表示.J0bm4qMpJ9

7．假设稀疏矩阵A和B（分别为m*n和n*1矩阵）采用三元组表示，编写一个函数计算C=A*B，要求C也是采用稀疏矩阵地三元组表示.XVauA9grYP

8．假设稀疏矩阵只存放其非0元素地行号、列号和数值，以一维数组顺次存放，行号为-1结束标志.
例如：如图所示地稀疏矩阵M，则存在一维数组D中：
D[0]=1， D[1]=1，D[2]=1，D[3]=1，D[4]=5
D[5]=10，D[6]=3，D[7]=9，D[8]=5，D[9]= -1
M =:

1 0 0 0 10 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

现有两个如上方法存储地稀疏矩阵A和B，它们均为m行n列，分别存放在数组A和B中，编写求矩阵加法C=A+B地算法，C亦放在数组C中.bR9C6TJscw

９．已知A和B为两个n*n阶地对称矩阵，输入时，对称矩阵只输入下三角形元素，按压缩存储方法存入一维数组A和B中，编写一个计算对称矩阵A和B地乘积地函数.pN9LBDdtrd

10．假设L为非递归并且不带共享子表地广义表，设计一个复制广义表L地算法.

同步综合练习及参考答案
（一） 基础知识题
6.1 加设在树中，结点x是结点y地双亲时，用(x,y)来表示树变.已知一棵树边地集合为：{(i,m),(i,n),(b,e),(e,i),(b,d),(a,b),(g,i),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树，并回答下列问题：DJ8T7nHuGT
（1） 哪个是根结点？
（2） 哪些是叶结点？
（3） 哪个是g地双亲？
（4） 哪些是g地祖先？
（5） 哪些是g地孩子？
（6） 哪些是e地子孙？
（7） 哪些是e地兄弟？哪些是f地兄弟？
（8） 结点b和n地层次各是多少？
（9） 树地深度是多少？
（10） 以结点c为根地子树地深度是多少？
（11） 树地度数是多少？
解：
（1） a是根结点.
（2） m,n,j,k,l是叶结点.
（3） c是g地双亲.
（4） a,c是g地祖先.
（5） g地孩子是j,k..
（6） e地子孙是 i,m,n..
（7） e地兄弟是a,f地兄弟是g.
（8） h,b在第五层.
（9） 树地深度为3.
（10） 以C为根地子树地深度为3.
（11） 树地度数为3.
6．2 一棵度为2地有序属于一棵二叉树有何区别？
解：
区别：度为2地树有二个分支，没有左右之分；以可二叉树也有两个分支，但有左右之分，且左右不能交换.
6．3 试分别画出具有3个结点地树和3个结点地二叉树地所有不同形态.
解：
3个结点树形态：
3个结点地二叉树：
6．4已知一棵树为m地树中有n1个度为1地结点，n2个度为2地结点，…nm个度为m地结点，问该书中有多少片叶子？QF81D7bvUA
解：
因为 n1+n2+…+nM+n0+=1+n1+2n2+…+mnM
=>n0+=1+n2+…+(m-1)nM
6.5 一个深度为h地满k叉树有如下性质：第h层上地结点都是叶子结点，其余各层上每个结点都有k棵非空子树.如果按层次顺序（同层自左至右）从未有过开始对全部结点编号，问：4B7a9QFw9h
（1） 各层地结点数目是多少？
（2） 编号为i地结点地双亲结点（若存在）地编号是多少？
（3） 编号为i地结点地第j个孩子结点（若存在）地编号是多少？
（4） 编号为i地结点有右兄弟地条件是什么？其右兄弟地编号是多少？
解：
（1） Ki-1
（2）
（3） Ki+j-1
（4） (i-1)MOD K<>0 ,i+1
6．6 高度为h地完全二叉树至少有多少个结点？至多有多少个结点？
解：
至少有：2h-1，至多有：2h-1
6．7 在具有n个结点地k叉树（k≥2）地k叉树链表表示中，有多少个空指针？
解：
（k-1）n+1个空指针
6．8 假设二叉树包含地结点数据为1，3，7，2，12.
（1） 画出两棵高度最大地二叉树；
（2） 画出两棵完全二叉树，要求每个双亲结点地值大于其孩子结点地值.
6．9 试找出分别满足下面条件地所有二叉树：
（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；
（3）前序序列和后序序列相同；（4）前序、中序、后序序列均相同.
解：
（1） 空二叉树或任一结点均无左子树地非空二叉树
（2） 空二叉树或任一结点均无左子树地非空二叉树
（3） 空二叉树或仅有一个结点地二叉树
（4） 同（3）
6．10 试采用顺序存储方法和链接存储方法分别画出6. 30所示各二叉树地存储结构.
解：①顺序存储：
(a)1 2 φφ 3 φφφφ 4 φφφφφφφφφφ 5
(b)1 φ 2 φφ 3 φφφφφφφ 4 φφφφφφφφφφφφ 5
(c)1 φ 2 φφ 3 4 φφφφ 5 6 φφφφφφφφφφφ 7 8
(d)1 2 3 4 φ 5 6 φ 7 φφφφ 8 9
②连接存储：
6．11 分别写出图6.30所示各二叉树地前序、中序和后序序列.
解：
6．12 若二叉树中个结点地值均不相同，则由二叉树地前序序列和中序序列，或由其后序序列地中序列均能惟一地确定一棵二叉树，但由前序序列和后序序列却不一定能惟一地确定一棵二叉树.ix6iFA8xoX
（1） 已知一棵二叉树地前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树.
（2） 已知一棵二叉树地中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树.
（3） 已知两棵二叉树前序序列和后序序列均为AB和BA，请画出这两棵不同地二叉树.
解：
6．13 对二叉树中结点进行按层次顺序（每一层自左至右）地访问操作称为二叉树地层次遍历，遍历所得到地结点序列称为二叉树地层次序列.现已知一棵二叉树地层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树.wt6qbkCyDE
解：
6．14 试画出图6.30所示各二叉树地前序、中序和后序线索树及相应地线索链表.
解：
（以c为例）
① 前序：1 2 3 5 7 8 6 4
② 前序：1 7 5 8 3 6 2 4
6．15 在何种线索树中，线索对所求指定结点在相应次序下地前趋和后继并无帮助？
解：
在前序线索树中找某一点地前序前趋以及在后序线索树中寻找某一点地后继，线索并无多大帮助.
6．16 对图6.31所示地森林：
（1） 求各树地前序序列和后序序列：
（2） 求森林地前序序列和后序序列：
（3） 将此森林转换为相应地二叉树：
（4） 给出（a）所示树地双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点地祖先，哪些易于求指定结点地后代？Kp5zH46zRk
解：
(1) a b cYl4HdOAA61
前序 ABCDEF GHIJK LMPQRNO
后序 BDEFCA IJKHG QRPMNOL
(2) 前序： ABCDEFGHIGKLMPQRNO
后序： BDEFCAIJKHGQRPMNOL
(3) 二叉树
(4) 1
① 孩子链表表示发：
② 双亲链表表示发：
结点 0 1 2 3 4 5 6
data A B C D E F
parent -1 0 1 1 3 3 3
③ 双亲孩子链表：
④ 孩子兄弟链表表示：
⑤ 易于求祖先：双亲链表面双亲孩子
⑥ 易于求后代：孩子链表双亲孩子
6．17 画出图6.32所示地各二叉树所应地森林
6．18 高度为h地严格二叉树至少有多少个结点？至多有多少个结点？
解：
最多有2n-1 最少有 2n-1
6．19 在什么样地情况下，等长编码是最优地前缀码？
解：
当字符集中地各字符使用频率均匀时.
6．20 下属编码哪一组不是前缀码？
{00，01，10，11}，{0，1，00，11}，{0，10，110，111}
解：
因为前缀码中不可能存在一个元素是另一个地前面部分.所以第二组不是.
6．20 假设用于通信地电子由字符集{a,b,c,d,e,f,g,h}中地字母构成，这8个字母在电文中出现地概率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}ch4PJx4BlI
（1） 为这8个字母设计哈夫曼编码.
（2） 若用三位二进制数（0~7）对这个8个字母进行等长编码，则哈夫曼编码地平均码长是等长编码地百分之几？它使电文总长平均压缩多少？qd3YfhxCzo
解：
①
②哈夫曼编码码长：
4*0.07+2*0.19+5*0.02+4*0.06+5*0.03+2*0.21+4*0.1=2.71E836L11DO5
等长码长： 3
905 平均缩了10%
（二） 算法设计题
6.22 二叉树地遍历算法可写为通用形式.例如，通用地中序遍历为：
void Inorder(BinTree T,void(*Visit)(Datatype x))
{ if (T)
{Inorder(T->lchild,Visit); /*遍历左子树*/
Visit(T->data); /*通过函数指针调用它所指地函数来访问结点*/
Inorder(T->rchild,Visit); /*遍历右子树*/
}
}
其中Visit是一个函数指针，它指向形如void f（DdataType x）地函数.因此我们可以将访问结点地操作写在函数f中，通过调用语句Inorder（root，f）将f地地址传递给Visit，来执行遍历操作.请写一个打印结点地数据地函数，通过调用上述算法来完成书中6.3节地中序遍历.S42ehLvE3M
解：
#include“stdio.h”
#define Null 0
typedef char DataType;
typedef struct no