sum++;
else
s=s+n;
（5）x=66;n=200;
while（n>0）{
if（x>100）{x=x-10;
n=n~l;
}else
x=x+l;
}
4.对于给定的n个元素，可以构造出的逻辑结构有，，,四种。
5.按增长率由小到大的顺序排列下列各函数：
3243
2"°,
（2）n,q）n,q）n,if,ii；,ii!
ii,log2n,n/log2n
习题2
2.1已知L是无头结点的单链表，且p结点既不是第一个结点，也不是最后一个结点,试从下列提供的语句中选出合适的语句序列：
2.3试编写一个计算头结点指针为L的单链表长度的算法。
2.4试编写一个将单循环链表逆置的算法。
2.5已知一顺序表A,其元素值非递减有序排列，编写一个算法，删除顺序表中多余的值相同的元素。
习题3
3.1简述栈和线性表的区别。
简述栈和队列的相同点和不同点。
栈有两种存储方式，其中一种是线性存储，而线性表只有线性存储一种方式,可以说线性存储的栈是只在表尾进行插入和删除操作的线性表。
栈、队列相同点：
同为一种特殊的线性表，不同是：
栈是先进后出，队列是先进先出。
3.2如果进栈的数据元素序列为1、2、3、4、5、6,能否得到4、3、5、6、1、2和1、3、5、4、2、6的出栈序列?
并说明为什么得不到或如何得到。
第一组不可以：
因为最后出栈1、2则2必在1前出栈；
而第二组可以：
1进1出，2、3进3出，4、5进5出4出，2出，6进6出；
3.3利用两个栈模拟一个队列的入队、出队和判断队列空的运算。
两个栈共同一个线表,
baseltopi
出栈
入栈
base2top2
topl=top2时栈为空
3.4写一算法，将一个顺序栈中的元素依次取出，并打印元素值。
#include
#include"malloc.h"
#defineMAXSIZE100
typedefstruct（
intdate[MAXSIZE];
inttop;
Jseqstack;
voidposeqstack（seqstack*s）（
while（s->top!
=-l）
printf（"%d",s->date[s->top-]）;
voidmain（）
inti;
seqstack*s;
s=（seqstack*）malloc（sizeof（seqstack））;
for（i=0;i<6;i++）
s->date[i]=i+10;
s->top=5;
poseqstack（s）;
）
3.5写一算法，将一个非负十进制整数转换成二进制。
#include
#include"malloc.h"
#defineMAXSIZE100
typedefstruct（
intdate[MAXSIZE];
inttop;
Jseqstack;
voidposeqstack（seqstack*s）（
while（s->top!
=-l）
printf（"%d",s->date[s->top—]）;
printf（”\n”）；
}voidmain（）
{
inti=0,n;
seqstack*s;
s=（seqstack*）malloc（sizeof（seqstack））;
scanf（"%d",&n）;
while（n）{
s->date[i++]=n%2;
n=n/2;
）
s->top=i-l;
poseqstack（s）;
}
3.6写一算法，将一个链式队列中的元素依次取出，并打印元素值。
#include
#include"malloc.h"
#defineNULL0
typedefstructnode（
intdate;
structnode*next;
}qnode;
typedefstruct（
qnode*front;
qnode*rear;
}lqueue;
voidqueuetraval（lqueue*s）（
qnode*p;
p=s->front;
p=p->next;
while（p!
=NULL）（
printf（"%d",p->date）;
p=p->next;
voidmain（）
inti=0,n;
Iqueue*q;qnode*p;
q=（lqueue*）malloc（sizeof（lqueue））;
p=（qnode*）malloc（sizeof（qnode））;
p->next=NULL;
q->front=p;
q->rear=p;
for（i=0;i<6;i++）（
p=（qnode*）malloc（sizeof（qnode））;
p->date=i+10;
q->rear->next=p;
q->rear=p;
）
p->next=NULL;
queuetraval（q）;
3.7设有编号为1、2、3、4的4辆车，顺序进入一个栈式结构的站台，试写出这4
辆车开出站台的所有可能的顺序。
法一：
#include
#include"malloc.h"
#defineMAXSIZE50
typedefstruct（
intdate[MAXSIZE];
inttop;
Jseqstack;
voidmain（）
（
intendl,k,i,j,a[50][8]={0},s[50]={0},end=l,begin=0;
a[0][0]=l;s[0]=l;
seqstack*T;
T=（seqstack*）malloc（sizeof（seqstack））;
T->top=-l;
for（j=l;j<8;j++）（
i=begin;
endl=end;
while（iif（s[i]<4&&2*s[i]>j）（
a[i]U]=l；
s[end]=s[i];
s[i]++；
for（k=0;ka[end][k]=a[i][k];
end++;
）
else
if（s[i]==4）begin++;
else（
a[i][j]=l；
s[i]++；
）
i++；
）
）
for（i=0;ik=l;
for（j=0;j<8;j++）
if（a[i][j]）
T->date[++T->top]=k++;
else
printf（"%d",T->date[T->top-]）；
法二：
#include
#include"malloc.h"
#defineMAXSIZE50
typedefstruct（
intdate[MAXSIZE];
inttop;
Jseqstack;
voidpopu（seqstack*m,seqstack*n）（
if（m->top!
=-l）
n->date[++n->top]=m->date[m->top-];
）
voidintravel（seqstack*c）（
inti=0;
while（i<=c->top）
printf（"%d",c->date[i++]）;
voidtravel（seqstack*b）（
intn;
n=b->top;
while（n!
=-l）
printf（"%d",b->date[n-]）；
printf（"\n"）;
）
voidpp（seqstack*a,seqstack*b,seqstack*c）（
int
n=b->top+l;
if（a->top!
=-l）
for（i=0;i<=n;i++）（
for（j=0;jpopu（b,c）;
popu（a,b）;
pp（a,b,c）;
if（a->top==-l）（
intravel（c）;
travel（b）;
popu（b,a）;
for（j=0;jpopu（c,b）;
voidmain（）
（
inti;
seqstack*a,*b,*c;
a=（seqstack*）malloc（sizeof（seqstack））;
b=（seqstack*）malloc（sizeof（seqstack））;
c=（seqstack*）malloc（sizeof（seqstack））;
a->top=-l;b->top=-l;c->top=-l;
for（i=4;i>0;i-）
a->date[++a->top]=i;
pp（a,b,c）;
3.8写一个算法，借助于栈将一个单链表逆置。
#include
#include"malloc.h"
#defineMAXSIZE100
typedefstructnode（
intdate;
structnode*next;
}qnode;
typedefstruct（
intdate[MAXSIZE];
inttop;
Jseqstack;
voidmain（）
（
inti=l;
qnode*head,*p;
seqstack*s;
s=（seqstack*）malloc（sizeof（seqstack））;
s->top=-l;
head=（qnode*）malloc（sizeof（qnode））;
p=head;
for（i=0;i<5;i++）（
p->next=（qnode*）malloc（sizeof（qnode））;
p=p->next;
p->date=i+10;
p->next=NULL;
p=head->next;
while（p!
=NULL）（
s->date[++s->top]=p->date;
p=p->next;
）
p=head->next;
while（s->top!
=-l）（
p->date=s->date[s->top—];
p=p->next;
）
/*打印*/
p=head->next;
do（
printf（"%-4d",p->date）;
p=p->next;
}while（p!
=NULL）;
习题4
4.1空串和空格串有什么区别？
4.2两个字符串相等的充要条件是什么？
4.3串的三种机内表小方法是什么？
4.4设S=*1amastudent*,T=,good,,Q=，worker，。
求：
（l）StrLength（S）
⑵SubString（&Sub,S,8,7）
（3）SubString（&Sub,T,2,1）
（4）Index（S,'a',1）
（5）Index（S,T,1）
⑹Replace（&S,'Student',Q）
（7）Concat（&N,SubString（&V,S,6,2）,Concat（&P,T,SubString（&W,S,7,8）））
4.5设A=,This,,F=fasample1,C='good',D="e',B=”，G='is'。
求：
（1）Coneat（&S,A,Concat（&Z,SubString（&Y,F,2,7）,Concat（&X,B,
SubString（A,3,2））））
（2）Concat（&U,SubString（&X,C,3,1）,D）
（3）Concat（&V,S,Concat（&Z,B,Concat（&Y,F,Concat（&X,B,U））））
⑷StrLength（S）
（5）Index（V,G,1）
（6）Index（U,G,1）
⑺Replace（&F,SubString（&X,F,3,6）,C）
4.6利用C的库函数strlen>strcpy（或strcat）写一个算法voidStrDelete（char*S,inti,intm）,删除串S中从位置i开始连荟的m个字符。
若i^strlen（S）,则没有字符被删除;若i+mNstrlen（S）,则S中从位置i开始直至末尾的字符均被删去.。
4.7采用顺序结构存储串，编写一个函数，求串s和串t的一个最长的公共子串。
提示：
需要采用三重循环来实现。
习题5
1.假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100,每个整数占4个字节。
问下列元素的存储地址是什么？
（1）Qoooo100
（2）ami776（3）3.31251784（4）382474416
2.假设一个准对角矩阵
IlS
。
21。
22
<>33弓34
。
43^44
a2m~\2m\a2m\,2m
a2mOm\a2m^m
、J
按以下方式存储于一维数组B[4m]中：
0123564m~l4m
a11
a12
a2l
a22
%
•••
«ij
写出由一对下标（ij）求k的转换公式。
i+j-l-i%2;
3.现有如下的稀疏矩阵A,要求画出三元组表示法。
r
0
0
0
22
0
、
-15
0
13
3
0
0
0
0
0
0
-6
0
0
A=
0
0
0
0
0
0
91
0
0
0
0
0
0
0
28
0
0
0
i
J
V
1
1
4
22
2
1
6
-15
3
2
2
13
4
2
3
3
5
3
4
-6
6
5
1
91
7
6
3
28
习题6
1.对于如图6-21所示的二叉树，试给出:
（1）它的顺序存储结构示意图。
（2）它的二叉链表存储结构示意图。
（3）它的三叉链表存储结构示意图。
图6-21题1图
2.证明：
在结点数多于1的哈夫曼树中不存在度为1的结点。
3.证明：
若哈夫曼树中有〃个叶结点，则树中共有2〃-1个结点。
4.已知一棵度为m的树中有为个度为1的结点，&个度为2的结点，……，个度为力的结点，问该树中共有多少个叶子结点？
有多少个非终端结点？
5.设高度为A的二叉树上只有度为0和度为2的结点，问该二叉树的结点数可能达到的最人值和最小值。
6.求表达式（a+8*（c-J））-eV的波兰式（前缀式）和逆波兰式（后缀式）。
7.画出和下列已知序列对应的二叉树。
（1）二叉树的先序次序访问序列为：
GFKDAIEBCHJo
（2）二叉树的中序访问次序为：
DIAEKFCJHBG。
8.画出和下列已知序列对应的二叉树。
（1）二叉树的后序次序访问序列为：
CFEGDBJLKIHA,
（2）二叉树的中序访问次序为：
CBEFDGAJIKLH。
9.画出和下列已知序列对应的二叉树。
（1）二叉树的层次序列为：
ABCDEFGHIJ.
（2）二叉树的中序次序为：
DBGEHJACIF。
10.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为7,19,2,6,32,3,21,10。
试为这8个字母设计赫夫曼编码。
使用0〜7的二进制表示形式是另一种编码方案。
对于上述实例，比较两种方案的优缺点。
、
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
B
C
D
E
F
G
H
二、叶子结点多于一，如果存在度为一的结点，则应将孩子结点与双亲结点相联，而将度为一的结点去除。
三、度数为2的结点数为n2,又对于任意一棵二叉树而言，.・.
n=n2+1,・••总数结点数为n2+n=2n-1；
四、叶子结点数为：
n2*l+n3*2+n4*3++nm*（m-l）+l
非终端结点数为：
nl+n2*2+n3*3+nm*m
五、最大值：
2虹1最小值：
2h-l
六、波兰式：
-+a*b-cd/ef逆波兰式：
abcd-*+ef/-
七、先GFKDAIEBCHJ
中DIAEKFCJHBG
G
F
KB
DC
AH
IEJ
八、后CFEGDBJLKIHA
中CBEFDGAJIKLH
EG
F
九、层ABCDEFGHIJ
中DBGEHJACIF
A
B
DE
GH
J
十、1010
00
10000
1001
11
10001
01
1011
用哈夫曼编码之后长度比二进制要短，
而哈夫曼编码却没有二进制编码容易解码。
11.一棵度为2的树与一棵二叉树有何区别?
树与二叉树之间有何区别？
解：
树有多个分枝，而二叉树最多有两个分支;
下标
0
1
2
3
4
5
6
7
8
9
10
11
12
Date
A
B
c
G
F
E
D
I
H
J
K
M
N
Parent
-1
0
0
1
1
2
2
2
4
5
5
6
7
Child13591112
24610
13.画出下图所示的森林经转换后所对应的二叉树，并指出在二叉链表中某结点所对应的森林中结点为叶子结点的条件。
14.将如图所示的二叉树转换成相应的森林。
15.在具有n（n>l）个结点的各棵树中，其中深度最小的那棵树的深度是多少?
它共有多少叶子和非叶子结点?
其中深度最大的那棵树的深度是多少?
它共有多少叶子和非叶子结点？
16.画出和下列已知序列对应的树T：
树的先根访问序列为：
GFKDAIEBCHJ；
树的后根访问序列为：
DIAEKFCJHBGo
17.画出和下列已知序列对应的森林F：
森林的先序访问序列为：
ABCDEFGHIJKL；
森林的中序访问序列为：
CBEFDGAJIKLH。
18.对以孩子一兄弟链表表示的树编写计算树的深度的算法。
#include"iostream"
usingnamespacestd;
inti=0;
typedefstructstu{
chardata;
structstu*lchild;
structstu*rchild;
}NODE;
〃先序初始化。
voidchuo（NODE**q,chars[]）{
NODE*p;
if（s[i]!
=\O'）（
if（s[i]!
=''）{
p=（NODE*）malloc（sizeof（NODE））;p->data=s[i++];
p->lchild=NULL;p->rchild=NULL;
*q=p；
chuo（&p->lchild,s）;
chuo（&p->rchild,s）;
}
else
i++；
intlenpre（NODE*L）{
if（!
L）
return0;
else{
intt,n=0;
while（L）{
t=lenpre（L->lchild）+l;
if（t>n）n=t;
L=L->rchild;
returnn;
voidmain（）{
NODE*L,*p;
chars[81]={"ABCDEGF"};
intn;
//gets（s）;
chuo（&L,s）;
n=lenpre（L）;
cout«n«endl;
习题7
4
V5
1
2
4
A
5
V6
2
5
A
（4）逆邻接表。
序号
vertex
firstedge
0
Vl
2
5
A
1
V2
5
6
A
2
V3
2
A
3
V4
1
3
5
A
4
V5
3
6
A
5
V6
3
A
（5）强连通分量。
序号
vertex
firstedge
0
VO
Vl
V2
A
1
Vl
VO
V3
A
2
V2
VO
V3
A
3
V3
Vl
V2
V4
V5
A
4
V4
V3
V6
A
5
V5
V3
V6
A
6
V6
V4
V5
A
（3）该图的多重邻接表。
⑷从V。
出发的“深度优先”遍历序列。
VOvlv3v2v4v6v5
（5）从vo出发的“广度优先”遍历序列。
Vovlv2v3v4v5v6
3请对下边的无向带权图，
（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树;
abbddedeeffheg
2
3
2
2
3
1
2
1
2
4
2
1
2
4
1
2
1
2
2
3
1
3
（2）写出它的邻接表，并按克鲁斯卡尔算法（cdeffhabbddeeg）求其最小
4对下图所示的带权有向图G,试回答以下问题:
（1）求出G中从结点vl出发按深度优先搜索遍历G所得到结点序列;
V1v2v3v8v5v7v4v6
（2）求出G中从结点vl出发按广度优先搜索遍历G所得的结点序列;
VIv2v4v6v3v5v7v8
5对于下图所示的带权图
（1
升级会员 