在数据结构的时间复杂度中计算时间复杂度的题目，请问我错了的这几题，应该怎么做？详细过程，谢谢！
点击联系发帖人
时间：2018-06-03 12:54
数据结构时间复杂度计算_百度知道
数据结构时间复杂度计算
3.分析以下算法的时间复杂度，并写出分析过程。void fun(int n) {
for (i = 1; i &= i ++)
for (j = 0; j &=n; j ++) {
while (k &= n) k = k * 5;
}}有具体的过程
我有更好的答案
采纳率：87%
为您推荐：
其他类似问题
您可能关注的内容
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。当前位置： >>
数据结构(第二版)习题答案
（C语言版）
（第 2版）
揭安全 李云清 杨庆红
江西师范大学计算机信息工程学院
联系方式：（习题答案仅供参考）
1.1什么是数据结构？
【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储
于计算机中，并在这些数据上定义了一个运算集合。
1.2数据结构涉及哪几个方面？
【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集
合。
1.3两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不
一样，它们是否可以认作是同一个数据结构？为什么？
【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不
一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，
所以它们是两种不同的数据结构。
1.4线性结构的特点是什么？非线性结构的特点是什么？
【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结
点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元
素之间的关系可以是一对多的或多对多的。
1.5数据结构的存储方式有哪几种？
【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。
1.6算法有哪些特点？它和程序的主要区别是什么？
【答】：算法具有（
1）有穷性（
2）确定性（
3）0个或多个输入（4）1个或多个输出（
5）可
行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。
1.7抽象数据类型的是什么？它有什么特点？
【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。
抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一
个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这
些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本
数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作
的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。
1.8算法的时间复杂度指的是什么？如何表示？
【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的
机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在
同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以
对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算
法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为
n的数据处理问题，用
T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写
O符号表示算法
的时间复杂度，大写
O符号给出了函数
f的一个上限。其它义如下：
定义：f (n)=O (g (n)) 当且仅当存在正的常数
n0，使得对于所有的
f (n) ≤c g(n)。
上述定义表明，函数
f顶多是函数
n0。因此对于足够大的
f 的一个上限（不考虑常数因子
c）。在为函数
f 提供一个上限函数
g 时，通常使用比较
简单的函数形式。比较典型的形式是含有
n的单个项（带一个常数系数）。表
1-1列出了一些
常用的
g函数及其名称。对于表
1-1中的对数函数
logn，没有给出对数基，原因是对于任何大
于
logan =logbn/logba,所以
logbn都有一个相对的乘法系数
1/logba，
其中
a是一个常量。
1-1常用的渐进函数
1.9算法的空间复杂度指的是什么？如何表示？
【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表
示为问题规模的函数，并通过大写O符号表示空间复杂度。
1.10对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度
T(n)。
（1） i++;
（2） for(i=0;i&n;i++)
if (a[i]&x) x=a[i];
（3）for(i=0;i&n;i++)
for(j=0;j&n;j++)
printf(“%d”,i+j);
（4）for (i=1;i&=n-1;i++)
for(j=i+1;j&=n;j++)
if(a[j]&a[j+1]) k=j;
t=a[k]; a[k]=a[i]; a[i]=t;
（5）for(i=0;i&n;i++)
for(j=0;j&n;j++)
{++x;s=s+x;}
【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n）；（5）O（n2）
2章线性表及其顺序存储
2.1选择题
（1）表长为 n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，
插入一个元素所需移动元素的平均个数为（ E ），删除一个元素所需移动元素的平均个数
为（ A ）。
A．（n . 1）/2 B．n C．n + 1 D．n . 1
E．n/2 F．(n + 1)/2 G．(n . 2)/2
（2）设栈 S和队列 Q的初始状态为空，元素 e1、e2、e3、e4、e5和 e6依次通过栈 S，
一个元素出栈后即进入队列 Q，若 6个元素出队的序列为 e2、e4、e3、e6、e5和 e1，则栈 S
的容量至少应该为（ C ）。
A．6 B．4 C．3 D．2
（3）设栈的输入序列为 1、2、3 … n，若输出序列的第一个元素为 n，则第i个输出的元素为
（ B ）。
A．不确定 B．n .
i + 1 C．i D．n .
i
（4）在一个长度为 n的顺序表中删除第 i个元素（ 1& = i& = n）时，需向前移动（ A ）个
元素。
A．n.i B．n .
i +1 C．n .
i . 1 D．i
（5）若长度为 n的线性表采用顺序存储结构存储，在第 i个位置上插入一个新元素的时
间复杂度为（ A ）。
A．O(n) B．O(1) C．O(n2) D．O(n3)
（6）表达式 a*(b+c).d的后缀表达式是（ B ）。
A．abcd*+. B．abc+*d. C．abc*+d. D．.+*abcd
（7）队列是一种特殊的线性表，其特殊性在于（ C ）。
A．插入和删除在表的不同位置执行 B．插入和删除在表的两端位置执行
C．插入和删除分别在表的两端执行 D．插入和删除都在表的某一端执行
（8）栈是一种特殊的线性表，具有（ B）性质。
A．先进先出 B．先进后出 C．后进后出 D．顺序进出
（9）顺序循环队列中（数组的大小为 n），队头指示 front指向队列的第 1个元素，队尾
指示 rear指向队列最后元素的后 1个位置，则循环队列中存放了 n .1个元素，即循环队列满
的条件为（ B ）。
A．(rear + 1)%n = front . 1 B．(rear + 1)%n = front
C．(rear)%n = front D．rear + 1 = front
（10）顺序循环队列中（数组的大小为 6），队头指示 front和队尾指示 rear的值分别为 3
和 0，当从队列中删除 1个元素，再插入 2个元素后， front和 rear的值分别为（ D ）。
A．5和 1 B．2和 4 C．1和 5 D．4和 2
2.2什么是顺序表？什么是栈？什么是队列？
【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表
现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），
因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约
定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具
有先进先出，后进后出的特点。
2.3设计一个算法，求顺序表中值为
x的结点的个数。
【答】：顺序表的存储结构定义如下（文件名
seqlist.h）：
#include &stdio.h&
#define N 100 /*预定义最大的数据域空间
/*假设数据类型为整型
typedef struct {
datatype data[N]; /*此处假设数据元素只包含一个整型的关键字域
/*线性表长度*/
} /*预定义的顺序表类型
countx（L,x）用于求顺序表
x的结点的个数。
int countx(seqlist *L,datatype x)
{ int c=0;
for (i=0;i&L-&i++)
if (L-&data[i]==x) c++;
2.4设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组
a中，倒
置的结果是使得数组
a[0]等于原来的最后一个元素，
a[1] 等于原来的倒数第
2个元
素，…，a的最后一个元素等于原来的第一个元素。
【答】：顺序表的存储结构定义同题
2.3，实现顺序表倒置的算法程序如下：
void verge(seqlist *L)
{int t,i,j;
j=L-&length-1;
while (i&j)
t=L-&data[i];
L-&data[i++]=L-&data[j];
L-&data[j--]=t;
2.5已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为
x的结点，
使顺序表中的结点仍然是从小到大有序。
【答】：顺序表的定义同题
2.3，实现本题要求的算法程序如下：
void insertx(seqlist *L,datatype x)
if (L-&length&N)
{ j=L-&length-1;
while (j&=0 && L-&data[j]&x)
{ L-&data[j+1]=L-&data[j];
L-&data[j+1]=x;
L-&length++;
2.6将下列中缀表达式转换为等价的后缀表达式。
(2) (5-6)/7
(3) 5-6*7*8
(5) 5*(7-6)+8/9
(6) 7*(5-6*8)-9
(7) 5+6*7 后缀表达式：5 6 7*+
(8) (5-6)/7 后缀表达式：5 6-7/
(9) 5-6*7*8后缀表达式：5 6 7*8*-
(10)5*7-8后缀表达式：5 7* 8-
(11)5*(7-6)+8/9后缀表达式：5 7 6-*8 9/+
(12)7*(5-6*8)-9后缀表达式：7 5 6 8*-*9-
2.7循环队列存储在一个数组中，数组大小为
n，队首指针和队尾指针分别为
rear，请
写出求循环队列中当前结点个数的表达式。
【答】：循环队列中当前结点个数的计算公式是：
(n+rear-front)%n
1,2,3,4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果
有
n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。
【答】：
解题思路：栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是
1，2，3，4
全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于
序列中的任何一个数其后面所有比它小的数应该是倒序的，例如
4321是一个有效的出栈序列，
1423不是一个有效的出栈结果（
4后面比它小的两个数
2，3不是倒序）。据此，本题可以通过
算法产生
n个数的全排列，然后将满足出栈规则的序列输出。
产生
n个数的全排列有递归与非递归两种实现算法。
产生全排列的递归算法：
R={r1,r2,…,rn}是要进行排列的
n个元素，Ri=R-{ri}。集合
X中元素的全排列记为
perm(X)。(ri)perm(X)表示在全排列
perm(X)的每一个排列前加上前缀
ri得到的排列。R的全排
列可归纳定义如下：
n=1时，perm(R)=(r)，其中
R中惟一的元素；
当
n&1时，perm(R)由(r1)perm(R1),(r2)perm(R2),…,(rn)perm(Rn)构成。
依此递归定义，可设计产生
perm(R)的递归算法如下：
递归解法：
#include&stdio.h&
int cont=1; /*全局变量，用于记录所有可能的出栈序列个数
void print(int str[],int n);
/*求整数序列
void perm(int str[],int k,int n)
if (k==n-1) print(str,n);
{ for (i=k;i&n;i++)
{temp=str[k]; str[k]=str[i]; str[i]=
perm(str,k+1,n); /*递归调用*/
temp=str[i]; str[i]=str[k]; str[k]=
/*本函数判断整数序列
str[]是否满足进出栈规则,若满足则输出*/
void print(int str[],int n)
{int i,j,k,l,m,flag=1,b[2];
for(i=0;i&n;i++) /*对每个
str[i]判断其后比它小的数是否为降序序列*/
for(j=i+1;j&n&&j++)
if (str[i]&str[j]) {if (m==0) b[m++]=str[j];
else {if (str[j]&b[0]) {flag=0;}
else b[0]=str[j];
if(flag) /*满足出栈规则则输出
str[]中的序列*/
{ printf(& %2d:&,cont++);
for(i=0;i&n;i++)
printf(&%d&,str[i]);
printf(&\n&);
int main()
{int str[100],n,i;
printf(&input a int:&); /*输出排列的元素个数
scanf(&%d&,&n);
for(i=0;i&n;i++) /*初始化排列集合
str[i]=i+1;
printf(&input the result:\n&);
perm(str,0,n);
printf(&\n&);
当参与进出栈的元素个数为
4时，输出的结果如下图所示。
该算法执行的时间复杂度为
O（n!）。随着
n的增大，算法的执行效率非常的低。
非递归解法：（2_7_8.c）
对一组数穷尽所有排列，还可一种更直接的方法，将一个排列看作一个长整数，则所有排
列对应着一组整数，将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按
数列的递增顺序逐一列举每个排列对应的每一个整数，这能更有效地完成排列的穷举。从一个
排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为
1,2,4,6,5,3，并令其对应的长整数为
124653。要寻找比长整数
124653更大的排列，可从该排列
的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中
的
6比它的前一位数字
4大，则说明还有可能对应更大整数的排列。但为顺序从小到大列举出
所有的排列，不能立即调整得太大，如本例中将数字
4交换得到的排列为
126453就
不是排列
124653的下一个排列。为得到排列
124653的下一个排列，应从已考察过的那部分数
字中选出比数字
4大，但又是它们中最小的那一个数字，比如数字
4交换。该数字
也是从后向前考察过程中第一个比
4大的数字，5与
4交换后，得到排列
125643。在前面数字
1，2，5固定的情况下，还应选择对应最小整数的那个排列，为此还需将后面那部分数字的排
列颠倒，如将数字
6，4，3的排列顺序颠倒，得到排列
1,2,5,3,4,6，这才是排列
1，2，4，6，
5，3的下一个排列。按照以上想法可以编写非递归程序实现
n个数的全排列，对满足进出栈
规则的排列则计数并输出。
/*本程序输出
1 2 ... n个序列进栈出栈的序列
#include &stdio.h&
int pl(int n)
{ int a[100]; /*最大处理范围为
int flag=1,flag1=0;
int i,j,k,x,count=0;
rf = fopen(&stack.txt&, &w&) ; /*pl.txt用于存放进出栈序列结果
for (i=1;i&=n;i++) /*初始序列*/
while (flag) /* 还剩余未输出的排列
{ flag1=1; /*判断本次排列是否符合进栈出栈序列
for (i=1;i&=n;i++)
while (j&=n && a[j]&a[i]) j++; /*找
a[i]后第一个比
a[i]小的元素
while (k&=n) /*如果
a[j]后还有比
a[i]小且比
a[j]大的元素,则此排列无效*/
{if ( a[k] &a[i] && a[k]&a[j]) flag1=0;
if (flag1)
{ for (i=1;i&=n;i++) /*输出当前排列
printf(&%4d&,a[i]); fprintf(rf,&%4d&,a[i]);}
printf(&\n&); fprintf(rf,&\n&);
count++; /*计数器加
i=n; /*从后向前找相邻位置后大前小的元素值
while (i&1 && a[i]&a[i-1]) i--;
if (i==1) flag=0; /*未找到则结束
{j=i-1;i=n;/*若找到,则在该位置的后面从右向左找第一个比该元素大的值*/
while (i&j && a[i]&a[j]) i--;
k=a[j]; /*交换两元素的值
a[j]=a[i];
/*对交换后后面的数据由小到大排序
for ( i=k+1;i&=n;i++) /*插入排序*/
while (j&=k && x&a[j]) { a[j+1]=a[j]; j--;}
fclose(rf);
/*返回排列总个数
void main()
{int n,m=0;
printf(&please input n:&); /*输入排列规模
scanf(&%d&,&n);
printf(&\nm=%d&,m); /*输出满足进出栈的排列总个数
程序运行时如果输入
4，则输出的结果如下图所示。
该算法的时间复杂度也是
O(n!)。
结论：如果
n个数按编号由小到大的顺序进栈，进栈的过程中可以出栈，则所有可能的出栈序
列的总数为：
3章线性表的链式存储
3.1选择题
（1）两个有序线性表分别具有 n个元素与 m个元素且 n≤m，现将其归并成一个有序表，
其最少的比较次数是（ A ）。
A．n B．m C．n . 1 D．m + n
（2）非空的循环单链表 head的尾结点（由 p所指向）满足（ C）。
A．p-&next==NULL B．p==NULL C．p-&next==head D．p==head
（3）在带头结点的单链表中查找 x应选择的程序体是（ C ）。
A．node *p=head-& while (p && p-&info!=x) p=p-&
if (p-&info==x) return p else return NULL;
B．node *p= while (p&& p-&info!=x) p=p-&
C．node *p=head-& while (p&&p-&info!=x) p=p-&
D．node *p= while (p-&info!=x) p=p-&
（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。
A．必须是连续的 B．部分地址必须是连续的
C．一定是不连续的 D．连续不连续都可以
（5）在一个具有 n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间
复杂度是（ B ）。
A．O(1) B．O(n) C．O(n2) D．O(nlog2
（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队
尾结点，则在进行删除操作时（ D ）。
A．仅修改队头指针 B．仅修改队尾指针
C．队头、队尾指针都要修改 D．队头,队尾指针都可能要修改
（7）若从键盘输入 n个元素，则建立一个有序单向链表的时间复杂度为（ B ）。
A．O(n) B．O(n2) C．O(n3) D．O(n × log2n)
（8）下面哪个术语与数据的存储结构无关（ D ）。
A．顺序表 B．链表 C．散列表 D．队列
（9）在一个单链表中，若删除 p所指结点的后续结点，则执行（ A ）。
A．p-&next=p-&next-& B．p=p-& p-&next=p-&next-&
C．p-&next=p-& D．p =p-&next-&
（10）在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ B ）。
A．s-&next=p;p-&next=s; B．s-&next=p-&p-&next=s;
C．s-&next=p-&p=s; D．p-&next=s;s-&next=p;
3.2设计一个算法，求一个单链表中的结点个数。
【答】：单链表存储结构定义如下（相关文件： linklist.h）
#include &stdlib.h&
#include &stdio.h&
typedef struct node
struct node *
typedef linknode *
/*尾插法创建带头结点的单链表
linklist creatlinklist()
{ linklist head,r,x,s;
head=r=(linklist)malloc(sizeof(linknode));
printf(&\n请输入一组以
0结束的整数序列：
scanf(&%d&,&x);
{ s=(linklist)malloc(sizeof(linknode));
s-&data=x;
r-&next=s;
scanf(&%d&,&x);
r-&next=NULL;
/*输出带头结点的单链表
void print(linklist head)
printf(&List is:\n&);
{ printf(&%5d&,p-&data);
printf(&\n&);
基于上述结构定义，求单链表中的结点个数的算法程序如下：
int count(linklist head)
linklist p=
3.3设计一个算法，求一个带头结点单链表中的结点个数。
【答】：带头结点的单链表的存储结构定义同题
3.2，实现本题功能的算法程序如下（
#include &linklist.h&
int count(linklist head)
{ int c=0;
linklist p=head-&
main() /*测试函数*/
head=creatlinklist();
print(head);
printf(&\nLength of head is:%d&,count(head));
5个数据时，产生的输出结果如下图所示：
3.4设计一个算法，在一个单链表中值为
y的结点前面插入一个值为
x的结点。即使值为
x的
新结点成为值为
y的结点的前驱结点。
【答】：
#include &linklist.h&
void insert(linklist head,int y,int x)
y的结点前插入一个值为
linklist pre,p,s;
while (p && p-&data!=y)
if (p)/*找到了值为
{ s=(linklist)malloc(sizeof(linknode));
s-&data=x;
s-&next=p;
pre-&next=s;
void main() /*测试程序*/
head=creatlinklist(); /*创建单链表*/
print(head); /*输出单链表*/
printf(&\n请输入
x的值:\n&);
scanf(&%d %d&,&y,&x);
insert(head,y,x);
print(head);
程序的一种运行结果如下图所示：
3.5设计一个算法，判断一个单链表中各个结点值是否有序。
【答】：
#include &linklist.h&
int issorted(linklist head,char c)
c=’a’时判断链表是否为升序，当参数
c=’d’是判断链表是否为降序*/
{ int flag=1;
linklist p=head-&
switch (c)
{case 'a':/*判断带头结点的单链表
head是否为升序
while (p &&p-&next && flag)
{if (p-&data&=p-&next-&data) p=p-&
else flag=0;
case 'd':/*判断带头结点的单链表
head是否为降序
while (p &&p-&next && flag)
{if (p-&data&=p-&next-&data) p=p-&
else flag=0;
int main() /*测试程序*/
head=creatlinklist();
print(head);
if (issorted(head,'a')) printf(&单链表
head是升序排列的！
if (issorted(head,'d')) printf(&单链表
head是降序排列的！
else printf(&单链表
head是无序的！\n&);
程序运行时的三种输出结果如下图所示：
3.6设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。
【答】：
#include &linklist.h&
void verge(linklist head)
{/*本函数的功能是就地倒置带头结点的单链表
linklist p,q;
head-&next=NULL;
while (p) /*每次从原表取一个结点插入到新表的最前面
q-&next=head-&
head-&next=q;
int main() /*测试函数*/
head=creatlinklist(); /*创建单链表*/
print(head); /*输出原单链表
verge(head); /*就地倒置单链表
print(head); /*输出倒置后的单链表
3.7设计一个算法，将一个结点值自然数的单链表拆分为两个单链表，原表中保留值为偶数的
结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。
【答】：
#include &linklist.h&
linklist sprit(linklist head)
{ /*将带头结点的单链表
head中的奇数值结点删除生成新的单链表并返回
linklist L,pre,p,r;
L=r=(linklist)malloc(sizeof(linknode));
r-&next=NULL;
{ if (p-&data%2==1) /*删除奇数值结点
pre-&next=p-&
r-&next=p;
else /*保留偶数值结点
r-&next=NULL; /*置链表结束标记
int main() /*测试函数*/
{linklist head,L;
head=creatlinklist(); /*创建单链表*/
print(head); /*输出原单链表
L=sprit(head); /*分裂单链表
printf(&\n原单链表为
print(head); /*输出倒置后的单链表
printf(&\n分裂所得奇数单链表为
本程序的一组测试情况如下图所示。
3.8设计一个算法，对一个有序的单链表，删除所有值大于
y的结点。
【答】：
#include &linklist.h&
void deletedata(linklist head,datatype x,datatype y)
{ /*删除带头结点单链表中所有结点值大于
linklist pre=head,p,q;
p=head-& /*初始化*/
while (p && p-&data&=x) /*找第
x的结点位置
while (p && p-&data&=y) /*找第
q=pre-& /*删除大于
pre-&next=p;
while (pre!=p) /*释放被删除结点所占用的空间
void main() /*测试函数*/
{ linklist head,L;
datatype x,y;
head=creatlinklist(); /*创建单链表*/
print(head); /*输出原单链表
printf(&\n请输入要删除的数据区间
scanf(&%d%d&,&x,&y);
deletedata(head,x,y);
print(head); /*输出删除后的单链表
3.9设计一个算法，在双链表中值为
y的结点前面插入一个值为
x的新结点。即使值为
x的新
结点成为值为
y的结点的前驱结点。
【答】：
首先定义双链表的数据结构，相关文件
dlink.h，内容如下：
/*预定义的数据类型
typedef struct dlink_node{ /*双链表结点定义
struct dlink_node *llink,*
typedef dnode* /*双链表结点指针类型定义
/*尾插法创建带头结点的双链表
dlinklist creatdlinklist(void)
{ dlinklist head,r,s;
head=r=(dlinklist) malloc(sizeof(dnode)); /*建立双链表的头结点
head-&llink=head-&rlink=NULL;
printf(&\n请输入双链表的内容：（整数序列，以
0结束）\n&);
scanf(&%d&,&x);
while (x) /*输入结点值信息，以
{ s=(dlinklist ) malloc(sizeof(dnode));
s-&data=x;
s-&rlink=r-& /*将新结点
s插入到双链表链尾*/
s-&llink=r;
r-&rlink=s;
scanf(&%d&,&x);
/*输出双链表的内容
void print(dlinklist head)
printf(&\n双链表的内容是：
{ printf(&%5d&,p-&data);
本题的求解程序如下：
#include &stdio.h&
#include &dlink.h&
void insertxaty(dlinklist head,datatype y,datatype x)
{ dlinklist s,p;
/*首先在双链表中找
y所在的结点，然后在
y前面插入新结点*/
while (p && p-&data!=y)
if (!p) printf(&\n双链表中不存在值为
y的结点,无法插入新结点!\n&);
else /*插入值为
{ s=(dlinklist)malloc(sizeof(dnode));
s-&data=x;
s-&rlink=p;
s-&llink=p-&
p-&llink-&rlink=s;
p-&llink=s;
void main() /*测试函数*/
datatype x,y;
head=creatdlinklist();
print(head);
printf(&\n请输入要输入的位置结点值
scanf(&%d&,&y);
printf(&\n请输入要输入的结点值
scanf(&%d&,&x);
insertxaty(head,y,x);/*在值为
y的结点前插入值为
print(head);/*输出新的双链表
本程序的一组测试情况如下图所示。
3.10设计一个算法，从右向左打印一个双链表中各个结点的值。
【答】：
本题的双链表定义同题
3.9，实现从右向左打印双链表的各个结点的值可以用递归程序实
现如下：
#include &stdio.h&
#include &dlink.h&
void vprint(dlinklist head)
{ /*递归方法从右向左打印双链表的值
if (head-&rlink)
{vprint(head-&rlink);
printf(&%5d&,head-&rlink-&data);
void main() /*测试函数*/
head=creatdlinklist();
print(head);
printf(&\n从右向左打印的双链表的内容是
vprint(head);
本程序的一组测试情况如下图所示。
3.11设计一个算法，将一个双链表改建成一个循环双链表。
【答】：
#include &stdio.h&
#include &dlink.h&
/*将一个双链表改成循环双链表
void dlinktocdlink(dlinklist head)
while (r-&rlink) /*寻找尾结点*/
head-&llink=r;
void printcdlink(dlinklist head)
{ /*打印双链表
while (p!=head)
{printf(&%5d&,p-&data);
int main() /*测试函数*/
head=creatdlinklist();
dlinktocdlink(head);
printf(&\n循环双链表的内容是：
printcdlink(head);
4章字符串、数组和特殊矩阵
4.1稀疏矩阵常用的压缩存储方法有（ 三元组顺序存储 ）和（十字链表 ）两种。
4.2设有一个 10 × 10的对称矩阵 A采用压缩方式进行存储，存储时以按行优先的顺序存
储其下三角阵，假设其起始元素 a00的地址为 1，每个数据元素占 2个字节，则 a65的地址为
（ 53 ）。
4.3若串 S =“software”，其子串的数目为（ 36 ）。
4.4常对数组进行的两种基本操作为（ 访问数据元素 ）和（ 修改数组元素 ）。
4.5 要计算一个数组所占空间的大小，必须已知（数组各维数）和（每个元素占用的空
间）。
4.6对于半带宽为 b的带状矩阵，它的特点是：对于矩阵元素 aij，若它满足（|i-j|&b），
则 aij = 0。
4.7字符串是一种特殊的线性表，其特殊性体现在（ 该线性表的元素类型为字符 ）。
4.8试编写一个函数，实现在顺序存储方式下字符串的 strcompare（S1，S2）运算。
【答】：
#include &stdio.h&
#include &string.h&
#define MAXSIZE 100
typedef struct{
char str[MAXSIZE];
/* 函数 strcompare()的功能是：当 s1&s2时返回 1，当 s1==s2时返回 0，当 s1&s2时返回-1*/
int strcompare(seqstring s1,seqstring s2)
{ int i,m=0,
len=s1.length&s2.length ?s1.length:s2.
for(i=0;i&=i++)
if(s1.str[i]&s2.str[i])
else if(s1.str[i]&s2.str[i])
int main()
{ seqstring s1,s2;
printf(&input char to s1:\n&);
gets(s1.str);
s1.length=strlen(s1.str);
printf(&input char to s2:\n&);
gets(s2.str);
s2.length=strlen(s2.str);
m=strcompare(s1,s2);
if(m==1) printf(&s1&s2\n&);
else if(m==-1) printf(&s2&s1\n&);
else if(m==0) printf(&s1=s2\n&);
4.9试编写一个函数，实现在顺序存储方式下字符串的
replace（S，T1，T2）运算。
【参考程序
/*本程序用来在顺序存储下用快速匹配模式实现在字符串
T2替换所有
T1出现的可
能*/
#include&malloc.h&
#include&string.h&
#include&stdio.h&
# define maxsize 100
typedef struct{
char str[maxsize];
next[]函数
void getnext(seqstring*p,int next[])
next[0]=-1;
while(i&p-&length)
if(j==-1||p-&str[i]==p-&str[j])
{++i;++j;next[i]=j;}
j=next[j];
//快速模式匹配算法
int kmp(seqstring*t,seqstring*p,int next[],int temppos)
i=temppos,j=0;
while (i&t-&length && j&p-&length)
if(j==-1||t-&str[i]==p-&str[j])
{i++; j++;}
else j=next[j];
if (j==p-&length) return (i-p-&length);
else return(-1);
//替换函数
void takeplace(seqstring*S,seqstring*T1,seqstring*T2)
int next[maxsize],temppos=0,pos,i;
int lent1,lent2;
lent1=strlen(T1-&str); //求
lent2=strlen(T2-&str); //求
getnext(T1,next);//求
next[]向量
pos=kmp(S,T1,next,temppos); //快速模式匹配
temppos=pos+T1-&
if (pos!=-1) //匹配成功
if (lent1&lent2) //T1串长度大于
for (i=i&S-&i++) //前移
S-&str[i-lent1+lent2]=S-&str[i];
for(i=0;i&T2-&i++) //替换
S-&str[pos+i]=T2-&str[i];
S-&length-=lent1-lent2; //修改长度
if (lent2&lent1) //T2串长度大于
for (i=S-&length-1;i&=i--) //后移留空
S-&str[i+lent2-lent1]=S-&str[i];
for(i=0;i&T2-&i++) //替换
S-&str[pos+i]=T2-&str[i];
S-&length+=lent2-lent1; //修改长度
else //T1长度与
T2长度相等
{ for(i=0;i&T2-&i++)
S-&str[pos+i]=T2-&str[i];
temppos=pos+T2-& //修改下一次模式匹配的起点位置
}while(pos!=-1);
S-&str[S-&length]='\0';
int main()
{ seqstring*S,*T1,*T2;
printf(&\n\n本程序用来实现字符串替换，将
T1所有出现\nThis program
is used for characters batch takeing place,The T1 characters batch will take place all the T2's
appearances in characters batch S: \n\n&);
printf(&请输入
S中的字符(plese input characters batch S:)\n&);
S=(seqstring*)malloc(sizeof(seqstring));
T1=(seqstring*)malloc(sizeof(seqstring));
T2=(seqstring*)malloc(sizeof(seqstring));
scanf(&%s&,S-&str);
S-&length=strlen(S-&str);
printf(&输入要被替换的串
(input T1):\n&);
scanf(&%s&,T1-&str);
T1-&length=strlen(T1-&str);
printf(&输入替换串
(input T2):\n&);
scanf(&%s&,T2-&str);
T2-&length=strlen(T2-&str);
takeplace(S,T1,T2);
printf(&替换后的字符串为：\n&);
printf(&%s\n&,S-&str);
【参考程序
#include&stdio.h&
#define MAXSIZE 100
typedef struct{
char str[MAXSIZE];
void getnext(seqstring p,int next[]) //求模式的
next[0]=-1;
while(i&p.length)
{if(j==-1||p.str[i]==p.str[j])
{++i;++j;next[i]=j;}
else j=next[j];
void replace(seqstring *s,seqstring t1,seqstring t2,int next[])
{int i,j,k,c,m;
i=0;j=0;k=0;
while(i&s-&length)
while(i&s-&length&&j&t1.length)
{if(j==-1||s-&str[i]==t1.str[j])
{i++; j++;}
else j=next[j];
if(j==t1.length) //匹配成功
if(t1.length==t2.length) //两串长度相等直接替换
for(k=0;k&t2.k++)
s-&str[c+k]=t2.str[k];
else if(t1.length&t2.length)
{ for(m=s-&length-1;m&i-1;m--)
s-&str[t2.length-t1.length+m]=s-&str[m]; //后移留空
for(k=0;k&t2.k++)
s-&str[c+k]=t2.str[k];
s-&length=s-&length-t1.length+t2.
s-&str[s-&length]='\0';
{ for(m=i-1;m&s-&m++) //前移
s-&str[m-t1.length+t2.length]=s-&str[m];
for(k=0;k&t2.k++)
s-&str[c+k]=t2.str[k];
s-&length=s-&length-t1.length+t2.
s-&str[s-&length]='\0';
i=i+t2.length-t1.
int main()
{ int next[MAXSIZE];
seqstring s,t1,t2;
printf(&Input string s:&); //输入主串
gets(s.str);
printf(&\nInput string t1:&); //输入模式串
gets(t1.str);
printf(&\nInput string t2:&); //输入拟替换的串
gets(t2.str);
s.length=strlen(s.str);
t1.length=strlen(t1.str);
t2.length=strlen(t2.str);
getnext(t1,next);
replace(&s,t1,t2,next);
puts(s.str);
4.10试编写一个函数，实现在链式存储方式下字符串的
strcompare（S1，S2）运算。
【参考程序】：
/*建立字符串链式存储结构文件
linkstring.h*/
#include &stdio.h&
#include &stdlib.h&
typedef struct node
struct node *
typedef linkstrnode *
/*---------------------------------------*/
/* 尾插法建立单链表 */
/*---------------------------------------*/
void strcreate(linkstring *S)
linkstrnode *p,*r;
*S=NULL; r=NULL;
while ((ch=getchar())!='\n')
{ p=(linkstrnode *)malloc(sizeof(linkstrnode));
p-&data= /*产生新结点*/
if (*S==NULL) /*新结点插入空表
{ *S=p; r=p;}
else {r-&next=p;
if (r!=NULL) r-&next=NULL; /*处理表尾结点指针域
/*---------------------------------------------*/
/*输出单链表的内容 */
/*---------------------------------------------*/
void print(linkstring head)
linkstrnode *p;
{printf(&%c--&&,p-&data);
printf(&\n&);
#include “linkstring.h”
int strcompare(linkstrnode*S1,linkstrnode*S2)
while(S1&&S2)
{ if(S1-&data&S2-&data)
else if(S1-&data&S2-&data)
return -1;
if(S1) return 1;
else if(S2) return -1;
int main()
linkstring s1,s2;
printf(&\nPlease input s1:&);
strcreate(&s1); /*建立字符串
print(s1);
printf(&\nPlease input s2:&);
strcreate(&s2); /*建立字符串
print(s2);
k=strcompare(s1,s2);
if (k==1) printf(&s1&s2&);
if (k==-1)printf(&s1&s2&);
printf(&s1==s2&);
4.11试编写一个函数，实现在链式存储方式下字符串的
replace（S，T1，T2）运算。
/*题目：链式存储方式下字符串的
replace(S,T1,T2）运算*/
【参考程序】：
#include &linkstring.h&
/*单链表拷贝函数
linkstring copy(linkstring head)
{ linkstring L=NULL,r=NULL,s,p;
{s=(linkstring)malloc(sizeof(linkstrnode));
s-&data=p-&
if (L==NULL) L=r=s;
{r-&next=s;
if (r!=NULL) r-&next=NULL;
/*------------------------------------------------*/
/* 在字符串
/*------------------------------------------------*/
linkstring replace(linkstring S,linkstring T1,linkstring T2)
{linkstring p,q,r,s,pre,temp,
int flag=1;
if (S==NULL|| T1==NULL ) return S; /*若
T1为空,则原串不变*/
pos=S; /*pos表示可能的
S中的起始位置*/
while (pos && flag) /*flag表示
while ( p&&q ) /*从
pos开始找子串
{ if (p-&data==q-&data)
{ p=p-&q=q-&}
if (q!=NULL) flag=0; /*未找到子串
{ flag=1; /*找到了子串
while (r!=p) /*首先删除子串
p指向删除串
T1的下一个结点*/
if (T2!=NULL) /*T2不为空*/
{ temp=r=copy(T2); /*复制一个
while (r-&next!=NULL) /*找
temp串的尾结点*/
r-&next=p;
if (pre==NULL) /*如果
S= /*新串成为链首
else /*T1不是链首串
pre-&next=
pos=p; /*从
p开始继续找子串
T2子串为空
{ if (pre==NULL) /*T1为链首串
pre-&next=p;
int main()
{linkstring S,T1,T2;
printf(&\nPlease input S:&);
strcreate(&S); /*建立字符串
printf(&\nPlease input T1:&);
strcreate(&T1); /*建立字符串
print(T1);
printf(&\nPlease input T2:&);
strcreate(&T2); /*建立字符串
print(T2);
S=replace(S,T1,T2);
printf(&\nThe result is:\n&);
4.12已知如下字符串，求它们的
next数组值：
（1）“bbdcfbbdac”
（2）“aaaaaaa”
【答】：-1012345
（3）“babbabab”
4.13已知正文
t =“ababbaabaa”，模式
p =“aab”，试使用
KMP快速模式匹配算法寻找
t中首次出现的起始位置，给出具体的匹配过程分析。
【答】：模式
next向量如下表所示：
第一趟匹配：
0 1 2 3 4 5 6 7 8 9
a b a b b a a b a a
i=1，j=1，匹配失败，此时
next[1]=0，即下一趟匹配从
i=1，j=0开始；
第二趟匹配：
0 1 2 3 4 5 6 7 8 9
a b a b b a a b a a
i=1，j=0，匹配失败，此时
j=next[0]=-1，下一趟匹配从
i=2，j=0开始；
第三趟匹配：
0 1 2 3 4 5 6 7 8 9
a b a b b a a b a a
i=3，j=1，匹配失败，此时
j=next[1]=0，下一趟匹配从
i=3，j=0开始；
第四趟匹配：
0 1 2 3 4 5 6 7 8 9
a b a b b a a b a a
i=3，j=0，匹配失败，此时
j=next[0]=-1，下一趟匹配从
i=4，j=0开始；
第五趟匹配：
0 1 2 3 4 5 6 7 8 9
a b a b b a a b a a
i=4，j=0，匹配失败，此时
j=next[0]=-1，下一趟匹配从
i=5，j=0开始；
第五趟匹配：
0 1 2 3 4 5 6 7 8 9
a b a b b a a b a a
i=8，j=3，匹配完成，表明匹配成功的位置是：
4.14已知三维数组
A[3][2][4]，数组首地址为
100，每个元素占用
1个存储单元，分别计
算数组元素
A[0][1][2]在按行优先和按列优先存储方式下的地址。
【答】：
A[0][1][2]按行优先方式在内存的存储地址为：
100+0*8+1*4+2=106
A[0][1][2]按列优先方式在内存的储储地址为：
100+2*6+1*3+0*8=115
4.15已知两个稀疏矩阵
B，其行数和列数均对应相等，编写一个函数，计算
B
之和，假设稀疏矩阵采用三元组表示。
【参考程序
#include&stdio.h&
typedef struct {
int data[100][100];
int m,n; /*分别存放稀疏矩阵的行数、列数和非零元素的个数
typedef int spmatrix[100][3]; //三元组存储结构
void add(spmatrix a,spmatrix b,spmatrix c) //基于三元组结构的矩阵相加算法
{int i,j,k,t,r;
while(i&=a[0][2]&&j&=b[0][2])
{if(a[i][0]&b[j][0]||(a[i][0]==b[j][0]&&a[i][1]&b[j][1]))
c[k][0]=a[i][0];
c[k][1]=a[i][1];
c[k][2]=a[i][2];
if(a[i][0]&b[j][0]||(a[i][0]==b[j][0]&&a[i][1]&b[j][1]))
c[k][0]=b[j][0];
c[k][1]=b[j][1];
c[k][2]=b[j][2];
if(a[i][0]==b[j][0]&&(a[i][1]==b[j][1]) )
c[k][0]=a[i][0];
c[k][1]=a[i][1];
c[k][2]=a[i][2]+b[j][2];
if (c[k][2]!=0 ) k++; /*如果相加的和不为
0,则生成一个有效项
while(j&=b[0][2])
{ c[k][0]=b[j][0];
c[k][1]=b[j][1];
c[k][2]=b[j][2];
while(i&=a[0][2])
c[k][0]=a[i][0];
c[k][1]=a[i][1];
c[k][2]=a[i][2];
c[0][0]=a[0][0];
c[0][1]=a[0][1];
c[0][2]=k-1;
compressmatrix将普通矩阵存储转换为三元组存储结构
void compressmatrix(matrix *A , spmatrix B)
for ( i=0; i&A-&m; i++)
for (j=0;j&A-&n; j++)
if (A-&data[i][j] !=0)
{ B[k][0]=i;
B[k][1]=j;
B[k][2]=A-&data[i][j];
B[0][0]=A-&m;
B[0][1]=A-&n;
B[0][2]=k-1;
printf(&the spmatrix is:\n&);
while(i&=B[0][2])
{ printf(&%d%5d%5d\n&,B[i][0],B[i][1],B[i][2]);
void creat(int r,int w,matrix *s)
printf(&input numbers:\n&);
for(i=0;i&r;i++)
for(j=0;j&w;j++)
scanf(&%d&,&data);
s-&data[i][j]=
printf(&the array is:\n&);
for(i=0;i&r;i++)
{ for(j=0;j&w;j++)
printf(&%5d&,s-&data[i][j]);
printf(&\n&);
int main()
{matrix p,q;
spmatrix a,b,c;
int r,w,i;
printf(&input r,w:&); /*输入行和列*/
scanf(&%d%d&,&r,&w);
creat(r,w,&p);
creat(r,w,&q);
compressmatrix(&p,a);
compressmatrix(&q,b);
add(a,b,c);
printf(&the spmatrix c is:\n&);
while(i&=c[0][2])
{ printf(&%d%5d%5d\n&,c[i][0],c[i][1],c[i][2]);
程序运行时先输入矩阵的行和列，然后按普通矩阵格式输入矩阵值，一组程序测试用例运
行结果如下图：
【参考程序
#include &stdio.h&
#include &malloc.h&
#define MAX 100
typedef struct{
int data[MAX][3];
matrix *Input(matrix *A)
{ int i,j;
A = (matrix*)malloc(sizeof(matrix));
scanf(&%d%d%d&,&A-&m,&A-&n,&A-&value);
A-&data[0][0] = A-&m;
A-&data[0][1] = A-&n;
A-&data[0][2] = A-&
for(i = 1;i &= A-&i ++)
for(j = 0;j & 3; j ++)
scanf(&%d&,&A-&data[i][j]);
void Output(matrix *A)
{ int i,j;
printf(&************************************\n&);
for(i = 0;i &= A-&i ++)
for(j = 0;j & 3;j ++)
printf(&%d &,A-&data[i][j]);
printf(&\n&);
printf(&************************************\n&);
matrix *addmatrix(matrix *A,matrix *B,matrix *C)
{ int i = 1,j =1,k = 1;
C = (matrix*)malloc(sizeof(matrix));
while(i &= A-&value && j &= B-&value)
if(A-&data[i][0] == B-&data[j][0])
if(A-&data[i][1] == B-&data[j][1])
C-&data[k][0] = A-&data[i][0];
C-&data[k][1] = A-&data[i][1];
C-&data[k][2] = A-&data[i][2] + B-&data[j][2];
if(C-&data[k][2] != 0) k ++;
else if(A-&data[i][1] & B-&data[j][1])
C-&data[k][0] = A-&data[i][0];
C-&data[k][1] = A-&data[i][1];
C-&data[k][2] = A-&data[i][2];
C-&data[k][0] = B-&data[j][0];
C-&data[k][1] = B-&data[j][1];
C-&data[k][2] = B-&data[j][2];
else if(A-&data[i][0] & B-&data[j][0])
C-&data[k][0] = A-&data[i][0];
C-&data[k][1] = A-&data[i][1];
C-&data[k][2] = A-&data[i][2];
C-&data[k][0] = B-&data[j][0];
C-&data[k][1] = B-&data[j][1];
C-&data[k][2] = B-&data[j][2];
while(i &= A-&value)
C-&data[k][0] = A-&data[i][0];
C-&data[k][1] = A-&data[i][1];
C-&data[k][2] = A-&data[i][2];
while(j &= B-&value)
C-&data[k][0] = B-&data[j][0];
C-&data[k][1] = B-&data[j][1];
C-&data[k][2] = B-&data[j][2];
C-&data[0][0] = (A-&data[0][0]&=B-&data[0][0])?A-&data[0][0]:B-&data[0][0];
C-&data[0][1] = (A-&data[0][1]&=B-&data[0][1])?A-&data[0][1]:B-&data[0][1];
C-&data[0][2] = k-1;
C-&value = k-1;
int main()
matrix * A = NULL,*B = NULL,*C = NULL;
printf(&提示：请按三元组格式输入矩阵内容。
printf(&Input A matrix:\n&);
A = Input(A);
printf(&Input B matrix:\n&);
B = Input(B);
C = addmatrix(A,B,C);
Output(C);
程序运行时按照三元组的格式输入矩阵信息，程序运行结果如下图所示：
4.16写出两个稀疏矩阵相乘的算法，计算：
Cpn = Apm .Bmn
其中，A、B和
C都采用三元组表示法存储。
【答】：
#include &stdio.h&
#include &malloc.h&
#define MAX 100
typedef struct{
int data[MAX][3];
matrix *Input(matrix *A)
{ int i,j;
A = (matrix*)malloc(sizeof(matrix));
scanf(&%d%d%d&,&A-&m,&A-&n,&A-&value);
A-&data[0][0] = A-&m;
A-&data[0][1] = A-&n;
A-&data[0][2] = A-&
for(i = 1;i &= A-&i ++)
for(j = 0;j & 3; j ++)
scanf(&%d&,&A-&data[i][j]);
void Output(matrix *A)
printf(&*******************************\n&);
for(i = 0;i &= A-&i ++)
for(j = 0;j & 3;j ++)
printf(&%d &,A-&data[i][j]);
printf(&\n&);
printf(&*******************************\n&);
/* 基于三元组存储结构的矩阵相乘算法
matrix *MulMatrix(matrix *A,matrix *B,matrix *C)
{ int i ,j ,k ,r=1,p,q,s;
C = (matrix*)malloc(sizeof(matrix));
C-&m=A-&m;
C-&n=B-&n;
C-&data[0][0]=C-&m;
C-&data[0][1]=C-&n;
for (i=0;i&C-&m;i++)
for (j=0;j&C-&n;j++)
for (k=0;k&A-&n;k++)
while (p&=A-&value)
if (A-&data[p][0]==i&&A-&data[p][1]==k)
while (q&=B-&value)
if (B-&data[q][0]==k&&B-&data[q][1]==j)
if (p&=A-&value && q&=B-&value)
s=s+A-&data[p][2]*B-&data[q][2];
{ C-&data[r][0]=i;
C-&data[r][1]=j;
C-&data[r][2]=s;
C-&data[0][2]=r-1;
C-&value=r-1;
int main()
matrix * A = NULL,*B = NULL,*C = NULL;
printf(&提示：请按三元组格式输入矩阵内容。
printf(&Input A matrix:\n&);
A = Input(A);
printf(&Input B matrix:\n&);
B = Input(B);
C = MulMatrix(A,B,C);
Output(C);
程序运行时，要求按照三元组的格式输入矩阵信息。
5.1试述递归程序设计的特点。
【答】：
（1）具备递归出口。递归出口定义了递归的终止条件，当程序的执行使它得到满足时，
递归执行过程便终止。有些问题的递归程序可能存在几个递归出口。
（2）在不满足递归出口的情况下，根据所求解问题的性质，将原问题分解成若干子问题，
子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合
成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。
5.2试简述简单递归程序向非递归程序转换的方法。
【答】：简单递归程序转换为非递归程序可以采用算法设计中的递推技术。递归方法与递
推方法共同采用的分划技术，为使用递推技术解决递归问题奠定了基础。由于简单递归问题求
解过程中无需回溯，因而要转换成非递归方式实现完全可以使用递推技术。为了使用自底向上
的递推方式来解决递归问题，利用子问题已有的解构造规模较大子问题的解，进而构造原问题
的解，必须建立原问题与子问题解之间的递推关系，然后定义若干变量用于记录求解过程中递
推关系的每个子问题的解；程序的执行便是根据递推关系，不断修改这些变量的值，使之成为
更大子问题的解的过程；当得到原问题解时，递推过程便可结束了。
5.3 试简述复杂递归程序向非递归程序转换的方法，并说明栈在复杂递归程序转换成非
递归程序的过程中所起的作用。
【答】：复杂递归问题在求解的过程中无法保证求解动作一直向前，需要设置一些回溯点，
当求解无法进行下去或当前处理的工作已经完成时，必须退回到所设置的回溯点，继续问题的
求解。因此，在使用非递归方式实现一个复杂递归问题的算法时，经常使用栈来记录和管理所
设置的回溯点。
5.4试给出例题
Fact(5)的执行过程分析。
【答】：Fact(5)的执行过程如下图所示：
2 + … + anxn
5.5已知多项式
pn(x) = a0 + a1x + a2x的系数按顺序存储在数组
a中，试：
（1）编写一个递归函数，求
n阶多项式的值；
（2）编写一个非递归函数，求
n阶多项式的值。
【答】：
#include &stdio.h&
#include &math.h&
#include &stdlib.h&
double pnx1(double a[],int n,double x) //（1）递归函数
{ if (n==0) return a[0];
return pnx1(a,n-1,x)+a[n]*pow(x,n);
double pnx2(double a[],int n,double x) //（2）非递归迭代函数
for (i=n-1;i&=0;i--)
t=a[i]+t*x;
int main()
{ double *a,x,p;
printf(&请输入
scanf(&%d%lf&,&n,&x);
a=(double*)malloc((n+1)*sizeof(double));
printf(&请输入
%d项系数：
for (i=0;i&=n;i++)
scanf(&%lf&,&a[i]);
p=pnx1(a,n,x);
printf(&%f\n&,p);
p=pnx2(a,n,x);
printf(“%f\n”,p);
5.6已知两个一维整型数组
b，分别采用递归和非递归方式编写函数，求两个数组的
内积（数组的内积等于两个数组对应元素相乘后再相加所得到的结果）。
【答】：
#include &iostream&
long sum1(int a[],int b[],int n) //非递归函数
for (i=0;i&n;i++)
s+=a[i]*b[i];
long sum2(int a[],int b[],int n) //递归函数
return a[0]*b[0];
return sum2(a,b,n-1)+a[n-1]*b[n-1];
int main()
int i,n,*a,*b;
cout&&&输入数组的长度
a=new int [n];
b=new int [n];
cout&&&请输入数组
for (i=0;i&5;i++)
cin&&a[i];
cout&&&请输入数组
for (i=0;i&5;i++)
cin&&b[i];
s=sum1(a,b,5);
cout&&&非递归计算的和
s=sum2(a,b,5);
cout&&&递归计算的和
delete []a;
delete []b;
Ackerman函数
Ack(m，n)值的递归函数，
Ackerman函数在
n ≥ 0时的
定义为：
Ack(0，n)=n+1;
Ack(m，0)=Ack(m.1，1);
Ack(m，n)=Ack(m.1，Ack(m，n.1)) n&0且
// 输入 m,和 n的值，计算
#include &stdio.h&
int Ack (int m,int n)
{ if (m == 0)
{ return n + 1;
else if (n == 0)
{ return Ack (m - 1,1);
{ return Ack (m - 1,Ack (m,n - 1));
int main ()
printf (&Please input m n\n&);
scanf (&%d%d&,&m,&n);
printf (&Ack (m,n) = %d\n&,Ack (m,n));
已知多项式
Fn(x)的定义如下：
2xFn.1( ) .
2( n .1) Fn.2 xn &1
试写出计算
Fn(x)值的递归函数。
【答】：
// 输入 n，x 计算
#include &stdio.h&
// 为了符合递归函数的表达这里将
x作为参数传递，在实际运用中建议使用全局变量。
// C++中也可以传递引用
int Function (int n,const int &x)
int Function (int n,int x)
{ if (n == 0)
{ return 1;
else if (n == 1)
{ return 2 *
{ return 2 * x * Function (n - 1,x) - 2 * (n - 1) * Function (n - 2,x);
int main ()
printf (&input n,x:\n&);
scanf (&%d%d&,&n,&x);
printf (&F(x) = %d\n&,Function (n,x));
Hanoi塔问题：设有
3个分别命名为
Z的塔座，在塔座
X上从上到下放有
n个直径各不相同、编号依次为
1，2，3，…，n的圆盘（直径大的圆盘在下，直径小的圆盘在上），
现要求将
n个圆盘移至塔座
Z上，并仍然按同样的顺序叠放，且圆盘移动时必须遵循以
下规则：
（1）每次只能移动一个圆盘；
（2）圆盘可以插在塔座
Z中任何一个塔座上；
（3）任何时候都不能将一个大的圆盘压在一个小的圆盘之上。
试编写一个递归程序实现该问题。
【答】：
#include &stdio.h&
void Hanoi(int n,char x,char y,char z)
printf(&%c--&%c\n&,x,z);
Hanoi(n-1,x,z,y);
printf(&%c--&%c\n&,x,z);
Hanoi(n-1,y,x,z);
int main()
printf(&请输入盘子个数：
scanf(&%d&,&n);
Hanoi(n,'X','Y','Z');
5.10八皇后问题：在一个
8×8格的国际象棋棋盘上放上
8个皇后，使其不能相互攻击，
即任何两个皇后不能处于棋盘的同一行、同一列和同一斜线上。试编写一个函数实现八皇后问
题。
【答】：
解法一：（程序
place.cpp）
解向量：(x1，x2，…，xn)
显约束：xi=1，2，…，n
1）不同列：xi≠xj
2）不处于同一正、反对角线：
|i-j|≠|xi-xj|
#include &stdio.h&
#include &math.h&
#define n 8
int x[n+1]={0}; //x[i]的含义表示第
int sum=0; //sum用于记录
n后问题的所有解
void print(); //输出
n后问题的解
int Place(int k) //检测第
k行的皇后放置是否符后规则
{ for (int j=1;j&k;j++)
if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
void Backtrack(int t) //放置
n后问题的第
{ if (t&n) { sum++;
print(); //输出一种解方案
getchar();
for (int i=1;i&=n;i++)
{ x[t]=i; //试探在第
if (Place(t)) Backtrack(t+1);
void print() //输出
n后问题的解
printf(&%d皇后问题的第
%d种解为:\n&,n,sum);
for (i=1;i&=n;i++)
printf(&%d:%d\n&,i,x[i]);
int main()
Backtrack(1);
解法二：
程序思想：
用
3个数组分别存放
8列，15个左对角线和
15个右对角线的值
,同时用一个
8元素大小的
数组记录下放置的皇后的位置。
初始时将三个数组全部标记为
0。
一，从第一行开始，从左向右开始查找。当找到第一个能够放下棋子的点
x,y（其对应的
列，左对角，右对角全部为
0）后，将此棋子所对应的列，左对角，右对角全部设置为
1，然
后继续放置下一行――x + 1行（调用自身的子函数）。
二，当其子函数执行完毕后，将放在
x,y上的点拿起，然后将这点对应的列，左对角，右
对角元素全部置
0，然后继续在此行的
y后查找能放置的点。
三，如果当前要放置的棋子为第
9个棋子的时候，打印结果。
5_10.c（递归法）
5_10_byStack.c (用栈回溯法
/*****************************************************/
/*八皇后问题递归解法 */
/*****************************************************/
#include&stdio.h&
int left[16],right[16],row[9],queen[9],count=0; /*分别用来存放左对角线和右对角线的使用
,row数组记录行数的棋子摆放情况，未使用的话就赋予
0，使用的话就赋予
/*row 的数组用来存放列的使用情况，当第
m列被使用的时候在
row[n]=m*/
queen数组用来专门存放当前皇后的摆放情况*/
int prin()/*打印出皇后的放置情况
printf(& The %d th&,count);
for(m=1;m&=8;m++)
printf(& %d&,queen[m]);
printf(&\n&);
int kaiserin(int line)/*line表示当前放棋子的列数,第一次放的时候为
{/*本变量用来记录当前行放子的列数
for(i=1;i&=8;i++)
if((row[i]||left[i+line-1]||right[8-i+line])==0)/*看当前的列是否可以放
row[i]=1;left[i+line-1]=1;
right[8-i+line]=1;queen[line]=i;
if(line==8)/*如果当前找到第
8行了，说明找成功了，打印
kaiserin(line+1);/*找到了，但是还没找完，将这点放上，然后尝试下一列
left[i+line-1]=0;row[i]=0;
right[8-i+line]=0;queen[line]=0;
/*不管找到没找到，重新初始化当前放子的点，开始右移放子
void init()/*将三个数组进行初始化
for(i=1;i&16;i++)
left[i]=right[i]=0;
for(i=1;i&9;i++)
queen[i]=row[i]=0;
int main()
kaiserin(1);
/********************************************/
/*八皇后问题回溯法 */
/********************************************/
#include&stdio.h&
#define max 10
typedef struct{/*用来存放回溯点的信息，
row用来存放回溯点所放的行数，line用来存放所放
的列数*/
int left[16],right[16],row[9],queen[9],count=0;/*分别用来存放左对角线和右对角线的使用情
况,row数组记录行数的棋子摆放情况，未使用的话就赋予
0，使用的话就赋予
/*row 的数组用来存放列的使用情况，当第
m列被使用的时候在
row[n]=m*/
queen数组用来专门存放当前皇后的摆放情况*/
void print() /*打印出皇后的放置情况
printf(&The %d th&,count);
for(m=1;m&=8;m++)
printf(& %d&,queen[m]);
printf(&\n&);
void init()/*将三个数组进行初始化
for(i=1;i&16;i++)
queen[i]=left[i]=right[i]=0;
for(i=1;i&9;i++)
int kaiserin()
{ node back[max];
int opline=1,oprow=1,i,find,top=0;
while(1)/*循环条件用真，用
return来结束循环和整个函数*/
for(i=i&=8;i++)
if((row[i]||left[i+opline-1]||right[8-i+opline])==0)/*判断当前的点是否可放
{ find=1;/*找到的话结束循环
if(find)/*找到了这点
{ oprow=i;
row[oprow]=1; left[oprow+opline-1]=1;
right[8-oprow+opline]=1;queen[opline]=/*把这个点放上
back[top].row=back[top].line=
/*记录回溯点*/
opline++;oprow=1;/*开始找下一行
else /*需要进行回溯
{ if(opline==9)
if(top==0)
return 0;/*如果栈取空了，说明查找结束
oprow=back[top]./*如果栈中还有元素可取
opline=back[top]./*取出栈顶元素
row[oprow]=0; left[oprow+opline-1]=0;/*同时将这个棋子拿起*/
right[8-oprow+opline]=0;queen[opline]=0;
}while(oprow==8);/*当取到的
oprow的右边可以放子时，开始下一步操作
kaiserin();
6.1树最适合用来表示具有（ 有序 ）性和（ 层次 ）性的数据。
6.2 在选择存储结构时，既要考虑数据值本身的存储，还需要考虑（数据间关系 ）
的存储。
6.3对于一棵具有 n个结点的树，该树中所有结点的度数之和为（ n-1 ）。
6.4已知一棵树如图 6.11所示，试回答以下问题：
图6.11 一棵树
（1）树中哪个结点为根结点？哪些结点为叶子结点？
【答】：A是根结点；E，G，H，I，C，J，K，L为叶结点。
（2）结点 B的双亲为哪个结点？其子女为哪些结点？
【答】：B的双亲结点是 A，其子女结点为 E和 F。
（3）哪些结点为结点 I的祖先？哪些结点为结点 B的子孙？
【答】：F，B，A是结点 I的祖先结点；E，F，G，H，I是 B的子孙结点。
（4）哪些结点为结点 D的兄弟？哪些结点为结点 K的兄弟？
【答】：B，C，L是结点 D的兄弟结点，J是结点 K的兄弟结点。
（5）结点 J的层次为多少？树的高度为多少？
【答】：结点 J的层次为 3，树的高度为 4。
（6）结点 A、C的度分别为多少？树的度为多少？
【答】：结点 A的度为 4，结点 C的度是 0，树的度是 4。
（7）以结点 B为根的子树的高度为多少？
【答】：以结点 B为根的子树的高度是 3。
（8）试给出该树的括号表示及层号表示形式。
【答】：该树的括号表示为：A（B（E，F（G，H，I）
）），C，D（J，K），L），该树的层号
表示为：10A，20B，30E，30F，40G，40H，40I，20C，20D，25J，25K，20L
6.5试写出图 6.11所示树的前序遍历、后序遍历和层次遍历的结果。
【答】：前序遍历：ABEFGHICDJKL
后序遍历：EGHIFBCJKDLA
层次遍历：ABCDLEFJKGHI
6.6试给出图 6.11所示树的双亲表示法和数组方式孩子表示法的表示。
【答】：
双亲表示法：
data parent
数组方式的孩子表示法：
data Child[0] Child[1] Child[2] Child[3]
A 1 2 3 11
B 4 5 -1 -1
C -1 -1 -1 -1
D 9 10 -1 -1
E -1 -1 -1 -1
F 6 7 8 -1
G -1 -1 -1 -1
H -1 -1 -1 -1
I -1 -1 -1 -1
J -1 -1 -1 -1
K -1 -1 -1 -1
L -1 -1 -1 -1
6.7已知一棵度为
……，nm个度为
m的结点，问该树中有多少个叶子结点？
【答】：
树中结点总数
n=n0+n1+n2+…+nm
树中结点的度数之和为
n-1，且有：n-1=n1+2n2+3n3+…+mnm
所以叶子结点个数为：n0=n2+2n3+…+(m-1)nm
6.8假设树采用指针方式的孩子表示法表示，试编写一个非递归函数，实现树的前序遍历
算法。
【答】：本程序在运行时请按树的括号表示法输入拟遍历的树，例如，对习题
所示的树为例，应输入
A（B（E，F（G，H，I）），C，D（J，K），L）
定义树的链式存储结构及建立树的存储结构
CreateTree函数（
tree.h）内容如下：
#include &stdio.h&
#include &malloc.h&
#include &string.h&
// 树的最大度定义为
#define MAXN 5
#define MAXLEN 100
typedef char dataT
typedef struct node
struct node *child[MAXN];
/*----------------------------------------------------------------*
树的括号法转化到树指针方式的孩子表示法
*-----------------------------------------------------------------*/
TreeNode *CreateTree (TreeNode *root,char string[MAXLEN])
TreeNode *stack[MAXLEN],*temp = NULL,*n;
int childSeq[MAXLEN]; // 其第几个孩子
length = strlen (string);
for (i = 0;i &i++)
if (string[i] == ',')
else if (string[i] == '(')
stack[++top] =
childSeq[top] = 0;
else if (string[i] == ')')
else if (top != -1)
n = (TreeNode*)malloc (sizeof (TreeNode));
n-&key = string[i];
for (j = 0;j & MAXN;j++)
n-&child[j] = NULL;
stack[top]-&child[childSeq[top]++] =
root = (TreeNode *)malloc (sizeof (TreeNode));
root-&key = string[i];
for (j = 0;j & MAXN;j++)
root-&child[j] = NULL;
void PreOrder (TreeNode *root)
if (root != NULL)
printf (&%5c&,root-&key);
for (i = 0;i & MAXN;i++)
{ PreOrder (root-&child[i]);
树的前序非递归遍历算法及其测试程序（6_8.c）如下所示：
#include &tree.h&
/*前序遍历（非递归） */
void PreOrder1(TreeNode *root)
TreeNode *stack[MAXLEN];
int top=-1,i;
while (root || top!=-1)
{ printf(&%c&,root-&key);
for (i=MAXN-1;i&0;i--)
if (root-&child[i])
stack[++top]=root-&child[i];
root=root-&child[0];
if (top&-1)
{root=stack[top--];
int main ()
{ char string[MAXLEN];
TreeNode *root = NULL;
printf (&请用树的括号表示法输入一棵树
scanf (&%s&,string);
root = CreateTree (root,string);
PreOrder1(root);
假设树采用指针方式的孩子表示法表示，试编写一个非递归函数，实现树的后序遍历
算法。
【答】：
#include &tree.h&
int PostOrderByStack (TreeNode *root)
TreeNode *
TreeNode *stack[MAXLEN];
// childSeq表示当前打印到了此树第几个孩子，
int top,childSeq[MAXLEN];
top = -1; //初始化空栈
while (temp != NULL)
for (i = 0;i & MAXN;i++)
{ if (temp-&child[i] != NULL)
childSeq[++top] = i + 1;
stack[top] =
temp = temp-&child[i];
// 如果此节点是叶子节点，则输出该结点
if (i == MAXN)
{ printf (&%5c&,temp-&key);
temp = NULL;
while (top != -1 )
for (i = childSeq[top];i & MAXN;i++)
if (stack[top]-&child[i] != NULL)
temp = stack[top]-&child[i];
childSeq[top] = i + 1;
if (i == MAXN)
printf (&%5c&,stack[top]-&key);
if (temp != NULL)
if (top == -1)
int main ()
{ char string[MAXLEN];
TreeNode *root = NULL;
printf (&请用树的括号表示法输入一棵树
scanf (&%s&,string);
root = CreateTree (root,string);
PostOrderByStack (root);
6.10假设树采用指针方式的孩子表示法表示，试编写一个函数，判断两棵给定的树是否
等价（两棵树等价当且仅当其根结点的值相等且其对应的子树均相互等价）。
#include &tree.h&
#define TRUE 1
#define FALSE 0
/*--------------------------------------------------*
递归比较两棵树是否相等
*--------------------------------------------------*/
int PreCmp (TreeNode *tree1,TreeNode *tree2)
if (tree1 == NULL && tree2 == NULL)
return TRUE;
else if (tree1 == NULL && tree2 != NULL || tree1 != NULL && tree2 == NULL)
return FALSE;
if (tree1-&key != tree2-&key)
return FALSE;
for (i = 0;i & MAXN;i++)
if (PreCmp (tree1-&child[i],tree2-&child[i]) == FALSE)
return FALSE;
return TRUE;
int main ()
char string[MAXLEN];
TreeNode *tree1 = NULL,*tree2 = NULL;
printf (&请用树的括号表示法输入第一棵树
scanf (&%s&,string);
tree1 = CreateTree (tree1,string);
printf (&请用树的括号表示法输入第二棵树
scanf (&%s&,string);
tree2 = CreateTree (tree2,string);
if (PreCmp (tree1,tree2) == TRUE)
printf (&两树相等
printf (&两树不相等
7.1选择题。
（1）前序遍历和中序遍历结果相同的二叉树为（ F ）；前序遍历和后序遍历结果相同的
二叉树为（ B ）。
A．一般二叉树 B．只有根结点的二叉树
C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树
E．所有结点只有左子树的二叉树 F．所有结点只有右子树的二叉树。
（2）以下有关二叉树的说法正确的是（ B ）。
A．二叉树的度为 2 B．一棵二叉树的度可以小于 2
C．二叉树中至少有一个结点的度为 2 D．二叉树中任一个结点的度均为 2
（3）一棵完全二叉树上有 1001个结点，其中叶子结点的个数为（ D ）。
A．250 B．500 C．254 D．501
（4）一棵完全二叉树有 999个结点，它的深度为（ B ）。
A．9 B．10 C．11 D．12
（5）一棵具有 5层的满二叉树所包含的结点个数为（ B ）。
A．15 B．31 C．63 D．32
7.2用一维数组存放完全二叉树： ABCDEFGHI，则后序遍历该二叉树的结点序列为
（ HIDEBFGCA ）。
7.3有 n个结点的二叉树，已知叶结点个数为 n0，则该树中度为 1的结点的个数为
（ n-2n0+1 ）；若此树是深度为 k的完全二叉树，则 n的最小值为（ 2k-1 ）。
7.4设 F是由 T1、T2和 T3三棵树组成的森林，与 F对应的二叉树为 B。已知 T1、T2
和 T3的结点数分别是 n1、n2和 n3，则二叉树 B的左子树中有（ n1-1）个结点，二叉树
B的右子树中有（ n2+n3）结点。
7.5高度为 k的二叉树的最大结点数为（ 2k-1 ），最小结点数为（ k ）。
7.6对于一棵具有 n个结点的二叉树，该二叉树中所有结点的度数之和为（ n-1 ）。
7.7已知一棵二叉树如图 7.12所示，试求：
（1）该二叉树前序、中序和后序遍历的结果；
【答】：前序： abdgecfh；中序： dgbcafhc；后序：gdebhfca
（2）该二叉树是否是满二叉树？是否是完全二叉树？
【答】：该二叉树不是满二叉树，也不是完全二叉树。
（3）将它转换成对应的树或森林；
【答】：
图7.12 一棵二叉树
（4）这棵二叉树的深度为多少？（4）这棵二叉树的深度为多少？
【答】：该二叉树的深度为
（5）试对该二叉树进行前序线索化；
【答】：
abcdefgh`
（6）试对该二叉树进行中序线索化。
【答】：
7.8试述树和二叉树的主要区别。
（1）树的结点个数至少为
1，而二叉树的结点个数可以为
0。
（2）树中结点的最大度数没有限制，而二叉树结点的最大度数为
2。
（3）树分为有序树与无序树，而二叉树一定是有序树，它的结点有左，右之分。
7.9试分别画出具有
3个结点的树和具有
3个结点的二叉树的所有不同形态。
【答】：
三个结点的树有两种形态：
三个结点的二叉树具有五种形态：
7.10已知一棵二叉树的中序遍历的结果为
ABCEFGHD，后序遍历的结果为
ABFHGEDC，试画出此二叉树。
【答】：
已知一棵二叉树的前序遍历的结果为ABCDEF，中序遍历的结果为CBAEDF，试
画出此二叉树。
【答】：
7.12若一棵二叉树的左、右子树均有
3个结点，其左子树的前序序列与中序序列相同，
右子树的中序序列与后序序列相同，试画出该二叉树。
【答】：
7.13分别采用递归和非递归方式编写两个函数，求一棵给定二叉树中叶子结点的个数。
【答】：为方便测试二叉树相关程序，定义二叉树头文件
bintree.h如下：
#include &stdio.h&
#define N 100
extern char *a; /*存放扩充二叉树的前序序列
typedef struct node /*二叉树结构定义
struct node *lchild,*
typedef binnode *
creat(根据扩充二叉树的前序序列(字符串
a)建立二叉树
t的存储结构
void creat(bintree * t)
char ch=*a++;
if (ch==' ') *t=NULL;
{ *t=(bintree)malloc(sizeof(binnode));
(*t)-&data=
creat(&(*t)-&lchild);
creat(&(*t)-&rchild);
void preorder(bintree t) /*前序递归遍历二叉树*/
{ printf(&%c&,t-&data);
preorder(t-&lchild);
preorder(t-&rchild);
/*顺序栈定义*/
typedef struct
{ bintree data[N];
void init(seqstack *s) /*初始化空栈*/
s-&top=-1;
int empty(seqstack *s) /*判断栈是否为空*/
if (s-&top&-1) return 0;
else return 1;
int full(seqstack *s) /*判断栈是否为满
if (s-&top==N-1) return 1;
else return 0;
void push(seqstack *s ,bintree x) /*进栈*/
if (!full(s))
s-&data[++s-&top]=x;
bintree pop(seqstack *s) /*出栈*/
if (!empty(s))
return s-&data[s-&top--];
基于上述结构，递归方法与非递归方法求二叉树中叶子结点的个数的算法分别如
leaf2()所示：
#include &bintree.h&
char *a=&ABC D EF G &; /*扩充二叉树序树
t的前序序列
int leaf1(bintree t) /*递归方法求二叉树叶子结点的个数
if (t==NULL) return 0;
if (!t-&lchild && !t-&rchild)
return leaf1(t-&lchild)+leaf1(t-&rchild);
int leaf2(bintree t) /*非递归方法求二叉树叶子结点的个数
/*顺序栈*/
int count=0; /*叶子结点计数变量
init(&s); /*初始化空栈*/
while (t || !empty(&s))
{if (!t-&lchild && !t-&rchild) count++;
push(&s,t);
{t=pop(&s);
int main()
creat(&t); /*建立二叉树
t的存储结构
printf(&\n该二叉树一共有
%d个叶子结点！
\n&,leaf1(t));
printf(&\n该二叉树一共有
%d个叶子结点！
\n&,leaf2(t));
7.14试编写一个函数，将一棵给定二叉树中所有结点的左、右子女互换。
#include &bintree.h&
char *a=&ABC D EF G &; /*扩充二叉树序树
t的前序序列
void change(bintree t)
t-&lchild=t-&
t-&rchild=p;
change(t-&lchild);
change(t-&rchild);
int main()
creat(&t); /*建立二叉树
t的存储结构
preorder(t);
change(t);
printf(&\n&);
preorder(t);
7.15试编写一个函数，返回一棵给定二叉树在中序遍历下的最后一个结点。
【答】：
#include &bintree.h&
char *a=&ABC D EF G &; /*扩充二叉树序树
t的前序序列
bintree inlast(bintree t)
{ bintree p=t;
while (p && p-&rchild)
int main()
creat(&t); /*建立二叉树
t的存储结构
printf(&二叉树中序遍历最后一个结点是%c\n&,inlast(t)-&data);
7.16试编写一个函数，返回一棵给定二叉树在前序遍历下的最后一个结点。
#include &bintree.h&
char *a=&ABC D EF G &; /*扩充二叉树序树
t的前序序列
/*求二叉树前序遍历的最后一个结点
bintree prelast(bintree t)
while (p && p-&lchild || p-&rchild)
if (p-&rchild)
int main()
creat(&t); /*建立二叉树
t的存储结构
printf(&二叉树前序遍历的最后一个结点是%c\n&,prelast(t)-&data);
7.17试编写一个函数，返回一棵给定二叉树在后序遍历下的第一个结点。
【答】：
#include &bintree.h&
char *a=&ABC D EF G &; /*扩充二叉树序树
t的前序序列
/*求二叉树后序遍历的第一个结点
bintree succfirst(bintree t)
while (p && p-&lchild || p-&rchild)
if (p-&lchild)
int main()
creat(&t); /*建立二叉树
t的存储结构
printf(&二叉树后序遍历的第一个结点是%c\n&,succfirst(t)-&data);
7.18假设二叉树采用链式方式存储，
root为其根结点，
p指向二叉树中的任意一个结点，
编写一个求从根结点到
p所指结点之间路径长度的函数。
【答】：在后序遍历非递归算法中，当访问的结点为
p时，其祖先点正好全部在栈中，此
时栈中结点的个数就是根结点到
p所指结点之间路径长度。
#include&stdio.h&
#include&stdlib.h&
typedef struct node /*二叉树结点定义
struct node *lchild,*
typedef bintnode *
typedef struct stack
bintree data[100];
int tag[100];
void creat(bintree *t) ;
Depth，功能：求根结点到
x的路径长度
int Depth(bintree t,datatype x)
int i=0,j;
while(t || s.top!=0)
s.data[s.top]=t;
s.tag[s.top]=0;
while(s.top&0 && s.tag[s.top-1])
t=s.data[s.top];
if(t-&data==x) return s. //此时栈中的结点都是
x的祖先结点
if(s.top&0)
t=s.data[s.top-1];
s.tag[s.top-1]=1;
else t=NULL;
creat(根据扩充二叉树的前序序列建立二叉树
t的存储结构
void creat(bintree *t)
scanf(&%c&,&ch);
if (ch==' ')
*t=(bintnode *)malloc(sizeof(bintnode));
(*t)-&data=
creat(&(*t)-&lchild);
creat(&(*t)-&rchild);
int main()
{ bintree root,p=NULL;
printf(&请输入扩充二叉树的前序序列：\n&);
creat(&root);
printf(&请输入树中的
1个结点值：\n&);
scanf(&%1s&,&x);
k=Depth(root,x);
printf(&根结点到%c的长度是
%d\n&,x,k);
7.19假设二叉树采用链式方式存储，
root为其根结点，
q分别指向二叉树中任意两
个结点，编写一个函数，返回
q最近的共同祖先。
【答】：方法同上题，利用后序遍历非递归算法分别求出
q的公共祖先，然后再查找
它们的最近公共祖先结点。
#include&stdio.h&
#include&stdlib.h&
typedef struct node /*二叉树结点定义
struct node *lchild,*
typedef bintnode *
typedef struct stack //顺序栈结构定义
bintree data[100];
int tag[100];
void creat(bintree *t) ; //创建二叉树结构函数声明
SeekAncestor的功能是返回二叉树
y的最近公共祖先结点*/
void SeekAncestor(bintree t,datatype x,datatype y,bintree *antor)
bintree data[100]={0};
int i=0,j;
while(t || s.top&-1)
{ while(t)
s.data[++s.top]=t;
s.tag[s.top]=0;
while(s.top&-1 && s.tag[s.top])
t=s.data[s.top];
if(t-&data==x)
while(i&=s.top) //记录
x结点的所有祖先结点
data[i]=s.data[i];
else if(t-&data==y)
while(s.top&-1)
while(j&=0&&t!=data[j])//查找
x的最近公共祖先结点
*antor=data[j]; //返回公共祖先结点地址
t=s.data[--s.top];
if(s.top&-1)
t=s.data[s.top];
s.tag[s.top]=1;
else t=NULL;
creat(根据扩充二叉树的前序序列建立二叉树
t的存储结构
void creat(bintree *t)
scanf(&%c&,&ch);
if (ch==' ')
*t=(bintnode *)malloc(sizeof(bintnode));
(*t)-&data=
creat(&(*t)-&lchild);
creat(&(*t)-&rchild);
int main()
bintree root,p=NULL;
datatype x='B',y='C';
printf(&请输入扩充二叉树的前序序列：\n&);
creat(&root);
printf(&请输入树中的两个结点值：\n&);
scanf(&%1s%c&,&x,&y);
SeekAncestor(root,x,y,&p);
if (p)printf(&%c和%c的最近公共祖先是：
%c\n&,x,y,p-&data);
8.1选择题
（1）如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（ D ）。
A．有向完全图 B．连通图 C．强连通图 D．有向无环图
（2）若邻接表中有奇数个表结点，则一定（ D ）。
A．图中有奇数个顶点 B．图中有偶数个顶点
C．图为无向图 D．图为有向图
（3）下列关于无向连通图特性的叙述中，正确的是（ A ）。
Ⅰ．所有顶点的度之和为偶数
Ⅱ．边数大于顶点个数减 1
Ⅲ．至少有一个顶点的度为 1
A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ
（4）假设一个有 n个顶点和 e条弧的有向图用邻接表表示，则删除与某个顶点 vi相关的
所有弧的时间复杂度是（ B ）。
A．O(n) B．O(e) C．O(n+e) D．O(n*e)
（5）已知一个有向图 8.30所示，则从顶点 a出发进行深度优先偏历，不可能得到的 DFS
序列为（ A ）。
A．a d b e f c B．a d c e f b C．a d c b f e D．a d e f c b
d
图 8.30有向图
（6）无向图 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）}，对该图进行深度优先遍历，得到的顶点序列正确的是（ 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
（7）下列哪一个选项不是图 8.31所示有向图的拓扑排序结果（ C ）。
A．AFBCDE B．FABCDE C．FACBDE D．FADBCE
图 8.31 AOV网
（8）判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（ D ）。
A．单源最短路 Dijkstra算法 B．所有顶点对最短路 Floyd算法
C．广度优先遍历算法 D．深度优先遍历算法
（9）在一个带权连通图 G中，权值最小的边一定包含在 G的（ A ）。
A．最小生成树中 B．深度优先生成树中
C．广度优先生成树中 D．深度优先生成森林中
（10）下图所示带权无向图的最小生成树的权为（ C ）。
A．14 B．15 C．17 D．18
图8.32 带权无向图
8.2对于如图 8.33所示的无向图，试给出：
（1）图中每个顶点的度；
（2）该图的邻接矩阵；
（3）该图的邻接表与邻接多重表；
（4）该图的连通分量。
图8.33无向图图8.34有向图
（1）D(V0)=2；D（V1）=2；D（V2）=3；D（V3）=3；D（V4）=2；D（V5）=2；D（V6）
=1。
（2）该图的邻接矩阵如图 8.33.1所示。
图 8.33.2 邻接表
图 8.33.1邻接矩阵
（3）该图的邻接表如图 8.30.2所示；该图的邻接多重表如图 8.30.3所示。
图 8.33.3 邻接多重表
（4）该图的两个连通分量如图 8.33.4所示。
图 8.33.4 两个连通分量
8.3对于如图 8.34所示的有向图，试给出：
（1）顶点 D的入度与出度；
（2）该图的出边表与入边表；
（3）该图的强连通分量。
【答】：
（1）顶点 D的入度是 2；顶点 D的出度为 1。
（2）该图的出边表如图 8.34.1所示，该图的入边表如图 8.34.2所示。
图8.34.1 出边表图8.34.1 出边表
图8.34.2 入边表
（3）该图的两个强连通分量如图
8.34.3所示。
E
图8.34.3 两个强连通分量
8.4试回答下列关于图的一些问题。
（1）有
n个顶点的有向强连通图最多有多少条边？最少有多少条边？
（2）表示一个有
500个顶点，
500条边的有向图的邻接矩阵有多少个非零元素？
（3）G是一个非连通的无向图，共有
28条边，则该图至少有多少个顶点？
【答】：
（1）有
n个顶点的有向强连通图昨多有
n(n-1)条边；最少有
n-1条边。
（2）500个。
（3）9个顶点。
8.35所示的是某个无向图的邻接表，试：
（1）画出此图；
（2）写出从顶点
DFS遍历结果；
（3）写出从顶点
BFS遍历结果。
【答】：
8.35邻接表对应的无向图如图
8.35.1所示。
图
8.5的邻接表
（2）从顶点
DFS遍历结果是：A，B，C，F，E，G，D
（3）从顶点
BFS遍历结果是：A，B，C，D，F，E，G
8.6证明，用
Prim算法能正确地生成一棵最小生成树。
【证明】：
Prim算法是按照逐边加入的方法来构造最小生成树过程的。记构造过程中生成的子图为
G’始终是一棵树。这是因为初始时
V(G’)={u0}，E（G’）=Ф，是一棵树。随后每一
步都是向
G’中添加一个顶点同时添加一条边，始终保持
G’中所有顶点连通。这样，当
n
个顶点时是仅有
n-1条边的连通图，所以
G’是一棵树。
Prim算法在执行过程中，始终能保证
G’=（V’，E’）是无向连通网络
G=（V，E）上某个最小代价生成树的连通图，如果该结论正
确，则随着
V(G’)顶点不断增加，当
V(G’)=V(G)时，G’=(V’,E’)就是
G=(V,E)上的最小代价生
成树。
Prim算法的每一步都能保证
G’=(V’,E’)是无向连通网络
G=(V,E)上某个代价生成
树的子连通图。
初始时，G’仅有一个顶点
V（G’）={u0}，E（G’）=Ф，设该树为
G
的某个最小生成树的子连通图。现假设第
G’=(V’,E’)中含有
i个顶点，不妨设该树为
G（V，E）中存在一棵最小生成树包含着
i+1步，存在
uTi，v.Ti,且(u,v)是最
小两栖边，将顶点
u,v）添加到树
Ti中，所得树
Ti+1是包含
V（Ti）+{v}顶点集的生
成树，且具有
i+1个顶点。根据
MST性质，此时在
G=(V,E)中必存在一棵最小生成树包含着
Ti+1。由此可知，当
i=n时，G’(Tn)即为无向图
n个顶点的最小生成树。
当然在进行最小两栖边选择时，如果同时存在几个具有相同代价的最小两栖边，则可任选
一条，因些
Prim算法构造的最小生成树不是唯一的。但它们的最小（代价）总和是相等的。
8.7证明，用
Kruskal算法能正确地生成一棵最小生成树。
【证明】：
算法首先构造具有
n个不同顶点的
n个连通分量，然后在
E（G）中选择边(u,v)，若
u,v
顶点属于不同的两个连通分量，则把该边添加到树
T中，每添加一条边就减少一个连通分量。
当添加了共
n-1条边时，就把
n个连通分量变成一个连通分量，此时
n-1
条边的树。由于
n是有限数，
E（G）中边数也是有限的，所以算法具有有穷性。
T的边为（u1,v1）,(u2,v2)，…，(un-1,vn-1)，按权值从小到大排列，若存在一棵
树
T’的代价总和小于
T的代价总和，则必在
T’中存在一条边（
u’,v’）∈TE’，（u’,v’）
.TE，
且(u’,v’)的代价小于(un-1,vn-1)的代价，这就说明(u’,v’)边没有选取的原因是因为
u’,v’在同一个
连通分量，添加（
u’,v’）将产生回路，说明
T’不可能是树（添加一条边没有减少一个连通分
量，这样
T’的边数将大于
n-1）。这与
T’是一棵树的假设
相矛盾。证毕。
8.36所示的连通图，分别用
Kruskal
算法构造其最小生成树。
【答】：
Prim算法求解最小生成树的过程如图
8.36.1
所示。
图
8.36无向连通网
（b）选取（D,F）
4
ABCDEFG（b）选取（D,F）
4
ABCDEFG
CDEFG34
（c）选取（C,F）
（e）选取（
8.36.1 Prim算法求解最小生成树过程
（2）采用
Kruskal算法求解最小生成树时首先要对边进行由小到大进行排序，本题对边进行
排序的结果是：（D,F）1、（C,F）2、（A,F）3、（A,C）4、（F,G）4、（D,E）4、（D,B）4、（C,D）
5、（E,G）5、（A,D）6、（D,G）6、（A,B）7 。根据
Kruskal算法，构造最小生成树的过程如图
8.33.2所示。
（a）选取（A，F）
（d）选取（F,G）
A
B
（f）选取（D,B）
（a）选取（D，F）
（d）选取（F,G）
（b）选取（C,F）（c）选取（A,F）
4
G
E
（e）选取（
D,E）（f）选取（D,B）
图
8.36.2 Kruskal算法求解最小生成树过程
8.9对于如图 8.37所示的有向网，用 Dijkstra方法求从顶点 A到图中其他顶点的最短路径，
并写出执行算法过程中距离向量 d与路径向量 p的状态变化情况。
BACEDGF28
图 8.37有向网 图8.38 题8.10的AOV网
【答】：对于如图 8.37所示的有向网， Dijkstra方法求从顶点 A到图中其它顶点的最短径时，
距离向量与路径向量的状态变化如下表示：
d 路径向量
0 1 2 3 4 5 6 0 1 2 3 4 5 6
{A } -0 48 ∞ 15 28 ∞
40 -1 0 -1 0 0 -1 0
1 { AD} 3 0 48 ∞ 15 28 48 38 -1 0 -1 0 0 3 3
2 {ADE } 4 0 48 61 15 28 48 38 -1 0 4 0 0 3 3
3 { ADG} 6 0 48 61 15 28 48 38 -1 0 4 0 0 3 3
4 {ADGB } 1 0 48 60 15 28 48 38 -1 0 1 0 0 3 3
5 {ADGBF} 5 0 48 57 15 28 48 38 -1 0 5 0 0 3 3
6 {ADGBFC } 2 0 48 57 15 28 48 38 -1 0 5 0 0 3 3
从表中可以看出源点 A到其它各顶点的最短距离及路径为：
A→B：48 路径：A→B
A→C：57 路径：A→D→F→C
A→D：15 路径：A→D
A→E：28 路径：A→E
A→F：48 路径：A→D→F
A→G：38 路径：A→D→G
8.10试写出如图 8.38所示的 AOV网的 4个不同的拓扑序列。
【答】：图 8.38所示的 AOV网的 4个不同的拓扑序列为：
（1）ABDCEFGIH
（2）ABDECFGIH
（3）DABCEFGIH
（4）DAECBFGIH
8.11计算如图 8.39所示的 AOE网中各顶点所表示的事件的发生时间 ve(j)，vl(j)，各边所表
示的活动的开始时间 e(i)，l(i)，并找出其关键路径。
【答】：为描述方便，将 AOE网中的所有边事件记为 a0-a7，如图 8.39所示。按照关键路径算
法，求得各顶事件的最早与最晚开始时间如下表所示。
v0v1v2v3v5v46
a7
图 8.39 题 8.10的 AOE网
顶点 ve vl活动
e l l-e关键活动
v0 0 0 a0 0 0 0 √
v1 6 6 a1 0 1 1
v2 4 5 a2 6 6 0 √
v3 13 13 a3 4 5 1
v4 22 22 a4 4 5 1
v5 25 25 a5 13 13 0 √
a6 13 15 2
a7 22 22 0 √
可见，该 AOE网的关键路径是 a0,a2,a5,a7。（注：图中箭头指示求解的顺序）
8.12无向图采用邻接表作为存储结构，试写出以下算法
（1）求一个顶点的度；
（2）往图中插入一个顶点；
（3）往图中插入一条边；
（4）删去图中某顶点；
（5）删去图中某条边。
【答】：本题的参考解答基于以下的存储结构：
#define m 20 /*预定义图的最大顶点数 */
t /*顶点信息数据类型 */
typedef struct node{ /*边表结点*/
/*邻接点*/
struct node *
typedef struct vnode{ /*头结点类型*/
/*顶点信息*/
edgenode * /*邻接链表头指针 */
typedef struct{ /*邻接表类型*/
vertexnode adjlist [m]; /*存放头结点的顺序表
int n,e; /*图的顶点数与边数
（1）求一个顶点的度；
/*求无向图
i个顶点的度
int d(adjgraph g ,int i)
edgenode *p;
p=g.adjlist[i].
（2）往图中插入一个顶点；
void insertvex(adjgraph *g,datatype x)
{ int i=0,flag=0;
/*查找待插入的结点是否存在
while (!flag&&i&g-&n)
{if (g-&adjlist[i].vertex==x) flag=1;
if (flag) {
printf(&结点已存在
if (g-&n&m) { printf(&邻接表已满！&);
g-&adjlist[g-&n].vertex=x;
g-&adjlist[g-&n].firstedge=NULL;
（3）往图中插入一条边；
/*在无向图
g中插入无向边（
void insertedge(adjgraph *g,int i,int j)
{ edgenode *p,*s;
int flag=0;
if (i&g-&n&&j&g-&n)
{ p=g-&adjlist[i].
while (!flag&&p)
{if (p-&adjvex==j) flag=1;
if (flag) {printf(&边已存在!&);
/*插入无向边
s=(edgenode *)malloc(sizeof(edgenode));
s-&adjvex=j; /*邻接点序号为
s-&next=g-&adjlist[i].
g-&adjlist[i].firstedge=s; /*将新结点*s插入顶点
vi的边表头部*/
s=(edgenode *)malloc(sizeof(edgenode));
s-&adjvex=i; /*邻接点序号为
s-&next=g-&adjlist[j].
g-&adjlist[j].firstedge=s; /*将新结点*s插入顶点
vj的边表头部*/
printf(&插入边不合法
（4）删去}
数据结构时间复杂度计算
3.分析以下算法的时间复杂度，并写出分析过程。void fun(int n) {
for (i = 1; i &= i ++)
for (j = 0; j &=n; j ++) {
while (k &= n) k = k * 5;
}}有具体的过程
我有更好的答案
采纳率：87%
为您推荐：
其他类似问题
您可能关注的内容
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。当前位置： >>
数据结构(第二版)习题答案
（C语言版）
（第 2版）
揭安全 李云清 杨庆红
江西师范大学计算机信息工程学院
联系方式：（习题答案仅供参考）
1.1什么是数据结构？
【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储
于计算机中，并在这些数据上定义了一个运算集合。
1.2数据结构涉及哪几个方面？
【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集
合。
1.3两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不
一样，它们是否可以认作是同一个数据结构？为什么？
【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不
一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，
所以它们是两种不同的数据结构。
1.4线性结构的特点是什么？非线性结构的特点是什么？
【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结
点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元
素之间的关系可以是一对多的或多对多的。
1.5数据结构的存储方式有哪几种？
【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。
1.6算法有哪些特点？它和程序的主要区别是什么？
【答】：算法具有（
1）有穷性（
2）确定性（
3）0个或多个输入（4）1个或多个输出（
5）可
行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。
1.7抽象数据类型的是什么？它有什么特点？
【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。
抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一
个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这
些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本
数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作
的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。
1.8算法的时间复杂度指的是什么？如何表示？
【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的
机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在
同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以
对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算
法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为
n的数据处理问题，用
T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写
O符号表示算法
的时间复杂度，大写
O符号给出了函数
f的一个上限。其它义如下：
定义：f (n)=O (g (n)) 当且仅当存在正的常数
n0，使得对于所有的
f (n) ≤c g(n)。
上述定义表明，函数
f顶多是函数
n0。因此对于足够大的
f 的一个上限（不考虑常数因子
c）。在为函数
f 提供一个上限函数
g 时，通常使用比较
简单的函数形式。比较典型的形式是含有
n的单个项（带一个常数系数）。表
1-1列出了一些
常用的
g函数及其名称。对于表
1-1中的对数函数
logn，没有给出对数基，原因是对于任何大
于
logan =logbn/logba,所以
logbn都有一个相对的乘法系数
1/logba，
其中
a是一个常量。
1-1常用的渐进函数
1.9算法的空间复杂度指的是什么？如何表示？
【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表
示为问题规模的函数，并通过大写O符号表示空间复杂度。
1.10对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度
T(n)。
（1） i++;
（2） for(i=0;i&n;i++)
if (a[i]&x) x=a[i];
（3）for(i=0;i&n;i++)
for(j=0;j&n;j++)
printf(“%d”,i+j);
（4）for (i=1;i&=n-1;i++)
for(j=i+1;j&=n;j++)
if(a[j]&a[j+1]) k=j;
t=a[k]; a[k]=a[i]; a[i]=t;
（5）for(i=0;i&n;i++)
for(j=0;j&n;j++)
{++x;s=s+x;}
【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n）；（5）O（n2）
2章线性表及其顺序存储
2.1选择题
（1）表长为 n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，
插入一个元素所需移动元素的平均个数为（ E ），删除一个元素所需移动元素的平均个数
为（ A ）。
A．（n . 1）/2 B．n C．n + 1 D．n . 1
E．n/2 F．(n + 1)/2 G．(n . 2)/2
（2）设栈 S和队列 Q的初始状态为空，元素 e1、e2、e3、e4、e5和 e6依次通过栈 S，
一个元素出栈后即进入队列 Q，若 6个元素出队的序列为 e2、e4、e3、e6、e5和 e1，则栈 S
的容量至少应该为（ C ）。
A．6 B．4 C．3 D．2
（3）设栈的输入序列为 1、2、3 … n，若输出序列的第一个元素为 n，则第i个输出的元素为
（ B ）。
A．不确定 B．n .
i + 1 C．i D．n .
i
（4）在一个长度为 n的顺序表中删除第 i个元素（ 1& = i& = n）时，需向前移动（ A ）个
元素。
A．n.i B．n .
i +1 C．n .
i . 1 D．i
（5）若长度为 n的线性表采用顺序存储结构存储，在第 i个位置上插入一个新元素的时
间复杂度为（ A ）。
A．O(n) B．O(1) C．O(n2) D．O(n3)
（6）表达式 a*(b+c).d的后缀表达式是（ B ）。
A．abcd*+. B．abc+*d. C．abc*+d. D．.+*abcd
（7）队列是一种特殊的线性表，其特殊性在于（ C ）。
A．插入和删除在表的不同位置执行 B．插入和删除在表的两端位置执行
C．插入和删除分别在表的两端执行 D．插入和删除都在表的某一端执行
（8）栈是一种特殊的线性表，具有（ B）性质。
A．先进先出 B．先进后出 C．后进后出 D．顺序进出
（9）顺序循环队列中（数组的大小为 n），队头指示 front指向队列的第 1个元素，队尾
指示 rear指向队列最后元素的后 1个位置，则循环队列中存放了 n .1个元素，即循环队列满
的条件为（ B ）。
A．(rear + 1)%n = front . 1 B．(rear + 1)%n = front
C．(rear)%n = front D．rear + 1 = front
（10）顺序循环队列中（数组的大小为 6），队头指示 front和队尾指示 rear的值分别为 3
和 0，当从队列中删除 1个元素，再插入 2个元素后， front和 rear的值分别为（ D ）。
A．5和 1 B．2和 4 C．1和 5 D．4和 2
2.2什么是顺序表？什么是栈？什么是队列？
【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表
现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），
因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约
定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具
有先进先出，后进后出的特点。
2.3设计一个算法，求顺序表中值为
x的结点的个数。
【答】：顺序表的存储结构定义如下（文件名
seqlist.h）：
#include &stdio.h&
#define N 100 /*预定义最大的数据域空间
/*假设数据类型为整型
typedef struct {
datatype data[N]; /*此处假设数据元素只包含一个整型的关键字域
/*线性表长度*/
} /*预定义的顺序表类型
countx（L,x）用于求顺序表
x的结点的个数。
int countx(seqlist *L,datatype x)
{ int c=0;
for (i=0;i&L-&i++)
if (L-&data[i]==x) c++;
2.4设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组
a中，倒
置的结果是使得数组
a[0]等于原来的最后一个元素，
a[1] 等于原来的倒数第
2个元
素，…，a的最后一个元素等于原来的第一个元素。
【答】：顺序表的存储结构定义同题
2.3，实现顺序表倒置的算法程序如下：
void verge(seqlist *L)
{int t,i,j;
j=L-&length-1;
while (i&j)
t=L-&data[i];
L-&data[i++]=L-&data[j];
L-&data[j--]=t;
2.5已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为
x的结点，
使顺序表中的结点仍然是从小到大有序。
【答】：顺序表的定义同题
2.3，实现本题要求的算法程序如下：
void insertx(seqlist *L,datatype x)
if (L-&length&N)
{ j=L-&length-1;
while (j&=0 && L-&data[j]&x)
{ L-&data[j+1]=L-&data[j];
L-&data[j+1]=x;
L-&length++;
2.6将下列中缀表达式转换为等价的后缀表达式。
(2) (5-6)/7
(3) 5-6*7*8
(5) 5*(7-6)+8/9
(6) 7*(5-6*8)-9
(7) 5+6*7 后缀表达式：5 6 7*+
(8) (5-6)/7 后缀表达式：5 6-7/
(9) 5-6*7*8后缀表达式：5 6 7*8*-
(10)5*7-8后缀表达式：5 7* 8-
(11)5*(7-6)+8/9后缀表达式：5 7 6-*8 9/+
(12)7*(5-6*8)-9后缀表达式：7 5 6 8*-*9-
2.7循环队列存储在一个数组中，数组大小为
n，队首指针和队尾指针分别为
rear，请
写出求循环队列中当前结点个数的表达式。
【答】：循环队列中当前结点个数的计算公式是：
(n+rear-front)%n
1,2,3,4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果
有
n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。
【答】：
解题思路：栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是
1，2，3，4
全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于
序列中的任何一个数其后面所有比它小的数应该是倒序的，例如
4321是一个有效的出栈序列，
1423不是一个有效的出栈结果（
4后面比它小的两个数
2，3不是倒序）。据此，本题可以通过
算法产生
n个数的全排列，然后将满足出栈规则的序列输出。
产生
n个数的全排列有递归与非递归两种实现算法。
产生全排列的递归算法：
R={r1,r2,…,rn}是要进行排列的
n个元素，Ri=R-{ri}。集合
X中元素的全排列记为
perm(X)。(ri)perm(X)表示在全排列
perm(X)的每一个排列前加上前缀
ri得到的排列。R的全排
列可归纳定义如下：
n=1时，perm(R)=(r)，其中
R中惟一的元素；
当
n&1时，perm(R)由(r1)perm(R1),(r2)perm(R2),…,(rn)perm(Rn)构成。
依此递归定义，可设计产生
perm(R)的递归算法如下：
递归解法：
#include&stdio.h&
int cont=1; /*全局变量，用于记录所有可能的出栈序列个数
void print(int str[],int n);
/*求整数序列
void perm(int str[],int k,int n)
if (k==n-1) print(str,n);
{ for (i=k;i&n;i++)
{temp=str[k]; str[k]=str[i]; str[i]=
perm(str,k+1,n); /*递归调用*/
temp=str[i]; str[i]=str[k]; str[k]=
/*本函数判断整数序列
str[]是否满足进出栈规则,若满足则输出*/
void print(int str[],int n)
{int i,j,k,l,m,flag=1,b[2];
for(i=0;i&n;i++) /*对每个
str[i]判断其后比它小的数是否为降序序列*/
for(j=i+1;j&n&&j++)
if (str[i]&str[j]) {if (m==0) b[m++]=str[j];
else {if (str[j]&b[0]) {flag=0;}
else b[0]=str[j];
if(flag) /*满足出栈规则则输出
str[]中的序列*/
{ printf(& %2d:&,cont++);
for(i=0;i&n;i++)
printf(&%d&,str[i]);
printf(&\n&);
int main()
{int str[100],n,i;
printf(&input a int:&); /*输出排列的元素个数
scanf(&%d&,&n);
for(i=0;i&n;i++) /*初始化排列集合
str[i]=i+1;
printf(&input the result:\n&);
perm(str,0,n);
printf(&\n&);
当参与进出栈的元素个数为
4时，输出的结果如下图所示。
该算法执行的时间复杂度为
O（n!）。随着
n的增大，算法的执行效率非常的低。
非递归解法：（2_7_8.c）
对一组数穷尽所有排列，还可一种更直接的方法，将一个排列看作一个长整数，则所有排
列对应着一组整数，将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按
数列的递增顺序逐一列举每个排列对应的每一个整数，这能更有效地完成排列的穷举。从一个
排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为
1,2,4,6,5,3，并令其对应的长整数为
124653。要寻找比长整数
124653更大的排列，可从该排列
的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中
的
6比它的前一位数字
4大，则说明还有可能对应更大整数的排列。但为顺序从小到大列举出
所有的排列，不能立即调整得太大，如本例中将数字
4交换得到的排列为
126453就
不是排列
124653的下一个排列。为得到排列
124653的下一个排列，应从已考察过的那部分数
字中选出比数字
4大，但又是它们中最小的那一个数字，比如数字
4交换。该数字
也是从后向前考察过程中第一个比
4大的数字，5与
4交换后，得到排列
125643。在前面数字
1，2，5固定的情况下，还应选择对应最小整数的那个排列，为此还需将后面那部分数字的排
列颠倒，如将数字
6，4，3的排列顺序颠倒，得到排列
1,2,5,3,4,6，这才是排列
1，2，4，6，
5，3的下一个排列。按照以上想法可以编写非递归程序实现
n个数的全排列，对满足进出栈
规则的排列则计数并输出。
/*本程序输出
1 2 ... n个序列进栈出栈的序列
#include &stdio.h&
int pl(int n)
{ int a[100]; /*最大处理范围为
int flag=1,flag1=0;
int i,j,k,x,count=0;
rf = fopen(&stack.txt&, &w&) ; /*pl.txt用于存放进出栈序列结果
for (i=1;i&=n;i++) /*初始序列*/
while (flag) /* 还剩余未输出的排列
{ flag1=1; /*判断本次排列是否符合进栈出栈序列
for (i=1;i&=n;i++)
while (j&=n && a[j]&a[i]) j++; /*找
a[i]后第一个比
a[i]小的元素
while (k&=n) /*如果
a[j]后还有比
a[i]小且比
a[j]大的元素,则此排列无效*/
{if ( a[k] &a[i] && a[k]&a[j]) flag1=0;
if (flag1)
{ for (i=1;i&=n;i++) /*输出当前排列
printf(&%4d&,a[i]); fprintf(rf,&%4d&,a[i]);}
printf(&\n&); fprintf(rf,&\n&);
count++; /*计数器加
i=n; /*从后向前找相邻位置后大前小的元素值
while (i&1 && a[i]&a[i-1]) i--;
if (i==1) flag=0; /*未找到则结束
{j=i-1;i=n;/*若找到,则在该位置的后面从右向左找第一个比该元素大的值*/
while (i&j && a[i]&a[j]) i--;
k=a[j]; /*交换两元素的值
a[j]=a[i];
/*对交换后后面的数据由小到大排序
for ( i=k+1;i&=n;i++) /*插入排序*/
while (j&=k && x&a[j]) { a[j+1]=a[j]; j--;}
fclose(rf);
/*返回排列总个数
void main()
{int n,m=0;
printf(&please input n:&); /*输入排列规模
scanf(&%d&,&n);
printf(&\nm=%d&,m); /*输出满足进出栈的排列总个数
程序运行时如果输入
4，则输出的结果如下图所示。
该算法的时间复杂度也是
O(n!)。
结论：如果
n个数按编号由小到大的顺序进栈，进栈的过程中可以出栈，则所有可能的出栈序
列的总数为：
3章线性表的链式存储
3.1选择题
（1）两个有序线性表分别具有 n个元素与 m个元素且 n≤m，现将其归并成一个有序表，
其最少的比较次数是（ A ）。
A．n B．m C．n . 1 D．m + n
（2）非空的循环单链表 head的尾结点（由 p所指向）满足（ C）。
A．p-&next==NULL B．p==NULL C．p-&next==head D．p==head
（3）在带头结点的单链表中查找 x应选择的程序体是（ C ）。
A．node *p=head-& while (p && p-&info!=x) p=p-&
if (p-&info==x) return p else return NULL;
B．node *p= while (p&& p-&info!=x) p=p-&
C．node *p=head-& while (p&&p-&info!=x) p=p-&
D．node *p= while (p-&info!=x) p=p-&
（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。
A．必须是连续的 B．部分地址必须是连续的
C．一定是不连续的 D．连续不连续都可以
（5）在一个具有 n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间
复杂度是（ B ）。
A．O(1) B．O(n) C．O(n2) D．O(nlog2
（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队
尾结点，则在进行删除操作时（ D ）。
A．仅修改队头指针 B．仅修改队尾指针
C．队头、队尾指针都要修改 D．队头,队尾指针都可能要修改
（7）若从键盘输入 n个元素，则建立一个有序单向链表的时间复杂度为（ B ）。
A．O(n) B．O(n2) C．O(n3) D．O(n × log2n)
（8）下面哪个术语与数据的存储结构无关（ D ）。
A．顺序表 B．链表 C．散列表 D．队列
（9）在一个单链表中，若删除 p所指结点的后续结点，则执行（ A ）。
A．p-&next=p-&next-& B．p=p-& p-&next=p-&next-&
C．p-&next=p-& D．p =p-&next-&
（10）在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ B ）。
A．s-&next=p;p-&next=s; B．s-&next=p-&p-&next=s;
C．s-&next=p-&p=s; D．p-&next=s;s-&next=p;
3.2设计一个算法，求一个单链表中的结点个数。
【答】：单链表存储结构定义如下（相关文件： linklist.h）
#include &stdlib.h&
#include &stdio.h&
typedef struct node
struct node *
typedef linknode *
/*尾插法创建带头结点的单链表
linklist creatlinklist()
{ linklist head,r,x,s;
head=r=(linklist)malloc(sizeof(linknode));
printf(&\n请输入一组以
0结束的整数序列：
scanf(&%d&,&x);
{ s=(linklist)malloc(sizeof(linknode));
s-&data=x;
r-&next=s;
scanf(&%d&,&x);
r-&next=NULL;
/*输出带头结点的单链表
void print(linklist head)
printf(&List is:\n&);
{ printf(&%5d&,p-&data);
printf(&\n&);
基于上述结构定义，求单链表中的结点个数的算法程序如下：
int count(linklist head)
linklist p=
3.3设计一个算法，求一个带头结点单链表中的结点个数。
【答】：带头结点的单链表的存储结构定义同题
3.2，实现本题功能的算法程序如下（
#include &linklist.h&
int count(linklist head)
{ int c=0;
linklist p=head-&
main() /*测试函数*/
head=creatlinklist();
print(head);
printf(&\nLength of head is:%d&,count(head));
5个数据时，产生的输出结果如下图所示：
3.4设计一个算法，在一个单链表中值为
y的结点前面插入一个值为
x的结点。即使值为
x的
新结点成为值为
y的结点的前驱结点。
【答】：
#include &linklist.h&
void insert(linklist head,int y,int x)
y的结点前插入一个值为
linklist pre,p,s;
while (p && p-&data!=y)
if (p)/*找到了值为
{ s=(linklist)malloc(sizeof(linknode));
s-&data=x;
s-&next=p;
pre-&next=s;
void main() /*测试程序*/
head=creatlinklist(); /*创建单链表*/
print(head); /*输出单链表*/
printf(&\n请输入
x的值:\n&);
scanf(&%d %d&,&y,&x);
insert(head,y,x);
print(head);
程序的一种运行结果如下图所示：
3.5设计一个算法，判断一个单链表中各个结点值是否有序。
【答】：
#include &linklist.h&
int issorted(linklist head,char c)
c=’a’时判断链表是否为升序，当参数
c=’d’是判断链表是否为降序*/
{ int flag=1;
linklist p=head-&
switch (c)
{case 'a':/*判断带头结点的单链表
head是否为升序
while (p &&p-&next && flag)
{if (p-&data&=p-&next-&data) p=p-&
else flag=0;
case 'd':/*判断带头结点的单链表
head是否为降序
while (p &&p-&next && flag)
{if (p-&data&=p-&next-&data) p=p-&
else flag=0;
int main() /*测试程序*/
head=creatlinklist();
print(head);
if (issorted(head,'a')) printf(&单链表
head是升序排列的！
if (issorted(head,'d')) printf(&单链表
head是降序排列的！
else printf(&单链表
head是无序的！\n&);
程序运行时的三种输出结果如下图所示：
3.6设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。
【答】：
#include &linklist.h&
void verge(linklist head)
{/*本函数的功能是就地倒置带头结点的单链表
linklist p,q;
head-&next=NULL;
while (p) /*每次从原表取一个结点插入到新表的最前面
q-&next=head-&
head-&next=q;
int main() /*测试函数*/
head=creatlinklist(); /*创建单链表*/
print(head); /*输出原单链表
verge(head); /*就地倒置单链表
print(head); /*输出倒置后的单链表
3.7设计一个算法，将一个结点值自然数的单链表拆分为两个单链表，原表中保留值为偶数的
结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。
【答】：
#include &linklist.h&
linklist sprit(linklist head)
{ /*将带头结点的单链表
head中的奇数值结点删除生成新的单链表并返回
linklist L,pre,p,r;
L=r=(linklist)malloc(sizeof(linknode));
r-&next=NULL;
{ if (p-&data%2==1) /*删除奇数值结点
pre-&next=p-&
r-&next=p;
else /*保留偶数值结点
r-&next=NULL; /*置链表结束标记
int main() /*测试函数*/
{linklist head,L;
head=creatlinklist(); /*创建单链表*/
print(head); /*输出原单链表
L=sprit(head); /*分裂单链表
printf(&\n原单链表为
print(head); /*输出倒置后的单链表
printf(&\n分裂所得奇数单链表为
本程序的一组测试情况如下图所示。
3.8设计一个算法，对一个有序的单链表，删除所有值大于
y的结点。
【答】：
#include &linklist.h&
void deletedata(linklist head,datatype x,datatype y)
{ /*删除带头结点单链表中所有结点值大于
linklist pre=head,p,q;
p=head-& /*初始化*/
while (p && p-&data&=x) /*找第
x的结点位置
while (p && p-&data&=y) /*找第
q=pre-& /*删除大于
pre-&next=p;
while (pre!=p) /*释放被删除结点所占用的空间
void main() /*测试函数*/
{ linklist head,L;
datatype x,y;
head=creatlinklist(); /*创建单链表*/
print(head); /*输出原单链表
printf(&\n请输入要删除的数据区间
scanf(&%d%d&,&x,&y);
deletedata(head,x,y);
print(head); /*输出删除后的单链表
3.9设计一个算法，在双链表中值为
y的结点前面插入一个值为
x的新结点。即使值为
x的新
结点成为值为
y的结点的前驱结点。
【答】：
首先定义双链表的数据结构，相关文件
dlink.h，内容如下：
/*预定义的数据类型
typedef struct dlink_node{ /*双链表结点定义
struct dlink_node *llink,*
typedef dnode* /*双链表结点指针类型定义
/*尾插法创建带头结点的双链表
dlinklist creatdlinklist(void)
{ dlinklist head,r,s;
head=r=(dlinklist) malloc(sizeof(dnode)); /*建立双链表的头结点
head-&llink=head-&rlink=NULL;
printf(&\n请输入双链表的内容：（整数序列，以
0结束）\n&);
scanf(&%d&,&x);
while (x) /*输入结点值信息，以
{ s=(dlinklist ) malloc(sizeof(dnode));
s-&data=x;
s-&rlink=r-& /*将新结点
s插入到双链表链尾*/
s-&llink=r;
r-&rlink=s;
scanf(&%d&,&x);
/*输出双链表的内容
void print(dlinklist head)
printf(&\n双链表的内容是：
{ printf(&%5d&,p-&data);
本题的求解程序如下：
#include &stdio.h&
#include &dlink.h&
void insertxaty(dlinklist head,datatype y,datatype x)
{ dlinklist s,p;
/*首先在双链表中找
y所在的结点，然后在
y前面插入新结点*/
while (p && p-&data!=y)
if (!p) printf(&\n双链表中不存在值为
y的结点,无法插入新结点!\n&);
else /*插入值为
{ s=(dlinklist)malloc(sizeof(dnode));
s-&data=x;
s-&rlink=p;
s-&llink=p-&
p-&llink-&rlink=s;
p-&llink=s;
void main() /*测试函数*/
datatype x,y;
head=creatdlinklist();
print(head);
printf(&\n请输入要输入的位置结点值
scanf(&%d&,&y);
printf(&\n请输入要输入的结点值
scanf(&%d&,&x);
insertxaty(head,y,x);/*在值为
y的结点前插入值为
print(head);/*输出新的双链表
本程序的一组测试情况如下图所示。
3.10设计一个算法，从右向左打印一个双链表中各个结点的值。
【答】：
本题的双链表定义同题
3.9，实现从右向左打印双链表的各个结点的值可以用递归程序实
现如下：
#include &stdio.h&
#include &dlink.h&
void vprint(dlinklist head)
{ /*递归方法从右向左打印双链表的值
if (head-&rlink)
{vprint(head-&rlink);
printf(&%5d&,head-&rlink-&data);
void main() /*测试函数*/
head=creatdlinklist();
print(head);
printf(&\n从右向左打印的双链表的内容是
vprint(head);
本程序的一组测试情况如下图所示。
3.11设计一个算法，将一个双链表改建成一个循环双链表。
【答】：
#include &stdio.h&
#include &dlink.h&
/*将一个双链表改成循环双链表
void dlinktocdlink(dlinklist head)
while (r-&rlink) /*寻找尾结点*/
head-&llink=r;
void printcdlink(dlinklist head)
{ /*打印双链表
while (p!=head)
{printf(&%5d&,p-&data);
int main() /*测试函数*/
head=creatdlinklist();
dlinktocdlink(head);
printf(&\n循环双链表的内容是：
printcdlink(head);
4章字符串、数组和特殊矩阵
4.1稀疏矩阵常用的压缩存储方法有（ 三元组顺序存储 ）和（十字链表 ）两种。
4.2设有一个 10 × 10的对称矩阵 A采用压缩方式进行存储，存储时以按行优先的顺序存
储其下三角阵，假设其起始元素 a00的地址为 1，每个数据元素占 2个字节，则 a65的地址为
（ 53 ）。
4.3若串 S =“software”，其子串的数目为（ 36 ）。
4.4常对数组进行的两种基本操作为（ 访问数据元素 ）和（ 修改数组元素 ）。
4.5 要计算一个数组所占空间的大小，必须已知（数组各维数）和（每个元素占用的空
间）。
4.6对于半带宽为 b的带状矩阵，它的特点是：对于矩阵元素 aij，若它满足（|i-j|&b），
则 aij = 0。
4.7字符串是一种特殊的线性表，其特殊性体现在（ 该线性表的元素类型为字符 ）。
4.8试编写一个函数，实现在顺序存储方式下字符串的 strcompare（S1，S2）运算。
【答】：
#include &stdio.h&
#include &string.h&
#define MAXSIZE 100
typedef struct{
char str[MAXSIZE];
/* 函数 strcompare()的功能是：当 s1&s2时返回 1，当 s1==s2时返回 0，当 s1&s2时返回-1*/
int strcompare(seqstring s1,seqstring s2)
{ int i,m=0,
len=s1.length&s2.length ?s1.length:s2.
for(i=0;i&=i++)
if(s1.str[i]&s2.str[i])
else if(s1.str[i]&s2.str[i])
int main()
{ seqstring s1,s2;
printf(&input char to s1:\n&);
gets(s1.str);
s1.length=strlen(s1.str);
printf(&input char to s2:\n&);
gets(s2.str);
s2.length=strlen(s2.str);
m=strcompare(s1,s2);
if(m==1) printf(&s1&s2\n&);
else if(m==-1) printf(&s2&s1\n&);
else if(m==0) printf(&s1=s2\n&);
4.9试编写一个函数，实现在顺序存储方式下字符串的
replace（S，T1，T2）运算。
【参考程序
/*本程序用来在顺序存储下用快速匹配模式实现在字符串
T2替换所有
T1出现的可
能*/
#include&malloc.h&
#include&string.h&
#include&stdio.h&
# define maxsize 100
typedef struct{
char str[maxsize];
next[]函数
void getnext(seqstring*p,int next[])
next[0]=-1;
while(i&p-&length)
if(j==-1||p-&str[i]==p-&str[j])
{++i;++j;next[i]=j;}
j=next[j];
//快速模式匹配算法
int kmp(seqstring*t,seqstring*p,int next[],int temppos)
i=temppos,j=0;
while (i&t-&length && j&p-&length)
if(j==-1||t-&str[i]==p-&str[j])
{i++; j++;}
else j=next[j];
if (j==p-&length) return (i-p-&length);
else return(-1);
//替换函数
void takeplace(seqstring*S,seqstring*T1,seqstring*T2)
int next[maxsize],temppos=0,pos,i;
int lent1,lent2;
lent1=strlen(T1-&str); //求
lent2=strlen(T2-&str); //求
getnext(T1,next);//求
next[]向量
pos=kmp(S,T1,next,temppos); //快速模式匹配
temppos=pos+T1-&
if (pos!=-1) //匹配成功
if (lent1&lent2) //T1串长度大于
for (i=i&S-&i++) //前移
S-&str[i-lent1+lent2]=S-&str[i];
for(i=0;i&T2-&i++) //替换
S-&str[pos+i]=T2-&str[i];
S-&length-=lent1-lent2; //修改长度
if (lent2&lent1) //T2串长度大于
for (i=S-&length-1;i&=i--) //后移留空
S-&str[i+lent2-lent1]=S-&str[i];
for(i=0;i&T2-&i++) //替换
S-&str[pos+i]=T2-&str[i];
S-&length+=lent2-lent1; //修改长度
else //T1长度与
T2长度相等
{ for(i=0;i&T2-&i++)
S-&str[pos+i]=T2-&str[i];
temppos=pos+T2-& //修改下一次模式匹配的起点位置
}while(pos!=-1);
S-&str[S-&length]='\0';
int main()
{ seqstring*S,*T1,*T2;
printf(&\n\n本程序用来实现字符串替换，将
T1所有出现\nThis program
is used for characters batch takeing place,The T1 characters batch will take place all the T2's
appearances in characters batch S: \n\n&);
printf(&请输入
S中的字符(plese input characters batch S:)\n&);
S=(seqstring*)malloc(sizeof(seqstring));
T1=(seqstring*)malloc(sizeof(seqstring));
T2=(seqstring*)malloc(sizeof(seqstring));
scanf(&%s&,S-&str);
S-&length=strlen(S-&str);
printf(&输入要被替换的串
(input T1):\n&);
scanf(&%s&,T1-&str);
T1-&length=strlen(T1-&str);
printf(&输入替换串
(input T2):\n&);
scanf(&%s&,T2-&str);
T2-&length=strlen(T2-&str);
takeplace(S,T1,T2);
printf(&替换后的字符串为：\n&);
printf(&%s\n&,S-&str);
【参考程序
#include&stdio.h&
#define MAXSIZE 100
typedef struct{
char str[MAXSIZE];
void getnext(seqstring p,int next[]) //求模式的
next[0]=-1;
while(i&p.length)
{if(j==-1||p.str[i]==p.str[j])
{++i;++j;next[i]=j;}
else j=next[j];
void replace(seqstring *s,seqstring t1,seqstring t2,int next[])
{int i,j,k,c,m;
i=0;j=0;k=0;
while(i&s-&length)
while(i&s-&length&&j&t1.length)
{if(j==-1||s-&str[i]==t1.str[j])
{i++; j++;}
else j=next[j];
if(j==t1.length) //匹配成功
if(t1.length==t2.length) //两串长度相等直接替换
for(k=0;k&t2.k++)
s-&str[c+k]=t2.str[k];
else if(t1.length&t2.length)
{ for(m=s-&length-1;m&i-1;m--)
s-&str[t2.length-t1.length+m]=s-&str[m]; //后移留空
for(k=0;k&t2.k++)
s-&str[c+k]=t2.str[k];
s-&length=s-&length-t1.length+t2.
s-&str[s-&length]='\0';
{ for(m=i-1;m&s-&m++) //前移
s-&str[m-t1.length+t2.length]=s-&str[m];
for(k=0;k&t2.k++)
s-&str[c+k]=t2.str[k];
s-&length=s-&length-t1.length+t2.
s-&str[s-&length]='\0';
i=i+t2.length-t1.
int main()
{ int next[MAXSIZE];
seqstring s,t1,t2;
printf(&Input string s:&); //输入主串
gets(s.str);
printf(&\nInput string t1:&); //输入模式串
gets(t1.str);
printf(&\nInput string t2:&); //输入拟替换的串
gets(t2.str);
s.length=strlen(s.str);
t1.length=strlen(t1.str);
t2.length=strlen(t2.str);
getnext(t1,next);
replace(&s,t1,t2,next);
puts(s.str);
4.10试编写一个函数，实现在链式存储方式下字符串的
strcompare（S1，S2）运算。
【参考程序】：
/*建立字符串链式存储结构文件
linkstring.h*/
#include &stdio.h&
#include &stdlib.h&
typedef struct node
struct node *
typedef linkstrnode *
/*---------------------------------------*/
/* 尾插法建立单链表 */
/*---------------------------------------*/
void strcreate(linkstring *S)
linkstrnode *p,*r;
*S=NULL; r=NULL;
while ((ch=getchar())!='\n')
{ p=(linkstrnode *)malloc(sizeof(linkstrnode));
p-&data= /*产生新结点*/
if (*S==NULL) /*新结点插入空表
{ *S=p; r=p;}
else {r-&next=p;
if (r!=NULL) r-&next=NULL; /*处理表尾结点指针域
/*---------------------------------------------*/
/*输出单链表的内容 */
/*---------------------------------------------*/
void print(linkstring head)
linkstrnode *p;
{printf(&%c--&&,p-&data);
printf(&\n&);
#include “linkstring.h”
int strcompare(linkstrnode*S1,linkstrnode*S2)
while(S1&&S2)
{ if(S1-&data&S2-&data)
else if(S1-&data&S2-&data)
return -1;
if(S1) return 1;
else if(S2) return -1;
int main()
linkstring s1,s2;
printf(&\nPlease input s1:&);
strcreate(&s1); /*建立字符串
print(s1);
printf(&\nPlease input s2:&);
strcreate(&s2); /*建立字符串
print(s2);
k=strcompare(s1,s2);
if (k==1) printf(&s1&s2&);
if (k==-1)printf(&s1&s2&);
printf(&s1==s2&);
4.11试编写一个函数，实现在链式存储方式下字符串的
replace（S，T1，T2）运算。
/*题目：链式存储方式下字符串的
replace(S,T1,T2）运算*/
【参考程序】：
#include &linkstring.h&
/*单链表拷贝函数
linkstring copy(linkstring head)
{ linkstring L=NULL,r=NULL,s,p;
{s=(linkstring)malloc(sizeof(linkstrnode));
s-&data=p-&
if (L==NULL) L=r=s;
{r-&next=s;
if (r!=NULL) r-&next=NULL;
/*------------------------------------------------*/
/* 在字符串
/*------------------------------------------------*/
linkstring replace(linkstring S,linkstring T1,linkstring T2)
{linkstring p,q,r,s,pre,temp,
int flag=1;
if (S==NULL|| T1==NULL ) return S; /*若
T1为空,则原串不变*/
pos=S; /*pos表示可能的
S中的起始位置*/
while (pos && flag) /*flag表示
while ( p&&q ) /*从
pos开始找子串
{ if (p-&data==q-&data)
{ p=p-&q=q-&}
if (q!=NULL) flag=0; /*未找到子串
{ flag=1; /*找到了子串
while (r!=p) /*首先删除子串
p指向删除串
T1的下一个结点*/
if (T2!=NULL) /*T2不为空*/
{ temp=r=copy(T2); /*复制一个
while (r-&next!=NULL) /*找
temp串的尾结点*/
r-&next=p;
if (pre==NULL) /*如果
S= /*新串成为链首
else /*T1不是链首串
pre-&next=
pos=p; /*从
p开始继续找子串
T2子串为空
{ if (pre==NULL) /*T1为链首串
pre-&next=p;
int main()
{linkstring S,T1,T2;
printf(&\nPlease input S:&);
strcreate(&S); /*建立字符串
printf(&\nPlease input T1:&);
strcreate(&T1); /*建立字符串
print(T1);
printf(&\nPlease input T2:&);
strcreate(&T2); /*建立字符串
print(T2);
S=replace(S,T1,T2);
printf(&\nThe result is:\n&);
4.12已知如下字符串，求它们的
next数组值：
（1）“bbdcfbbdac”
（2）“aaaaaaa”
【答】：-1012345
（3）“babbabab”
4.13已知正文
t =“ababbaabaa”，模式
p =“aab”，试使用
KMP快速模式匹配算法寻找
t中首次出现的起始位置，给出具体的匹配过程分析。
【答】：模式
next向量如下表所示：
第一趟匹配：
0 1 2 3 4 5 6 7 8 9
a b a b b a a b a a
i=1，j=1，匹配失败，此时
next[1]=0，即下一趟匹配从
i=1，j=0开始；
第二趟匹配：
0 1 2 3 4 5 6 7 8 9
a b a b b a a b a a
i=1，j=0，匹配失败，此时
j=next[0]=-1，下一趟匹配从
i=2，j=0开始；
第三趟匹配：
0 1 2 3 4 5 6 7 8 9
a b a b b a a b a a
i=3，j=1，匹配失败，此时
j=next[1]=0，下一趟匹配从
i=3，j=0开始；
第四趟匹配：
0 1 2 3 4 5 6 7 8 9
a b a b b a a b a a
i=3，j=0，匹配失败，此时
j=next[0]=-1，下一趟匹配从
i=4，j=0开始；
第五趟匹配：
0 1 2 3 4 5 6 7 8 9
a b a b b a a b a a
i=4，j=0，匹配失败，此时
j=next[0]=-1，下一趟匹配从
i=5，j=0开始；
第五趟匹配：
0 1 2 3 4 5 6 7 8 9
a b a b b a a b a a
i=8，j=3，匹配完成，表明匹配成功的位置是：
4.14已知三维数组
A[3][2][4]，数组首地址为
100，每个元素占用
1个存储单元，分别计
算数组元素
A[0][1][2]在按行优先和按列优先存储方式下的地址。
【答】：
A[0][1][2]按行优先方式在内存的存储地址为：
100+0*8+1*4+2=106
A[0][1][2]按列优先方式在内存的储储地址为：
100+2*6+1*3+0*8=115
4.15已知两个稀疏矩阵
B，其行数和列数均对应相等，编写一个函数，计算
B
之和，假设稀疏矩阵采用三元组表示。
【参考程序
#include&stdio.h&
typedef struct {
int data[100][100];
int m,n; /*分别存放稀疏矩阵的行数、列数和非零元素的个数
typedef int spmatrix[100][3]; //三元组存储结构
void add(spmatrix a,spmatrix b,spmatrix c) //基于三元组结构的矩阵相加算法
{int i,j,k,t,r;
while(i&=a[0][2]&&j&=b[0][2])
{if(a[i][0]&b[j][0]||(a[i][0]==b[j][0]&&a[i][1]&b[j][1]))
c[k][0]=a[i][0];
c[k][1]=a[i][1];
c[k][2]=a[i][2];
if(a[i][0]&b[j][0]||(a[i][0]==b[j][0]&&a[i][1]&b[j][1]))
c[k][0]=b[j][0];
c[k][1]=b[j][1];
c[k][2]=b[j][2];
if(a[i][0]==b[j][0]&&(a[i][1]==b[j][1]) )
c[k][0]=a[i][0];
c[k][1]=a[i][1];
c[k][2]=a[i][2]+b[j][2];
if (c[k][2]!=0 ) k++; /*如果相加的和不为
0,则生成一个有效项
while(j&=b[0][2])
{ c[k][0]=b[j][0];
c[k][1]=b[j][1];
c[k][2]=b[j][2];
while(i&=a[0][2])
c[k][0]=a[i][0];
c[k][1]=a[i][1];
c[k][2]=a[i][2];
c[0][0]=a[0][0];
c[0][1]=a[0][1];
c[0][2]=k-1;
compressmatrix将普通矩阵存储转换为三元组存储结构
void compressmatrix(matrix *A , spmatrix B)
for ( i=0; i&A-&m; i++)
for (j=0;j&A-&n; j++)
if (A-&data[i][j] !=0)
{ B[k][0]=i;
B[k][1]=j;
B[k][2]=A-&data[i][j];
B[0][0]=A-&m;
B[0][1]=A-&n;
B[0][2]=k-1;
printf(&the spmatrix is:\n&);
while(i&=B[0][2])
{ printf(&%d%5d%5d\n&,B[i][0],B[i][1],B[i][2]);
void creat(int r,int w,matrix *s)
printf(&input numbers:\n&);
for(i=0;i&r;i++)
for(j=0;j&w;j++)
scanf(&%d&,&data);
s-&data[i][j]=
printf(&the array is:\n&);
for(i=0;i&r;i++)
{ for(j=0;j&w;j++)
printf(&%5d&,s-&data[i][j]);
printf(&\n&);
int main()
{matrix p,q;
spmatrix a,b,c;
int r,w,i;
printf(&input r,w:&); /*输入行和列*/
scanf(&%d%d&,&r,&w);
creat(r,w,&p);
creat(r,w,&q);
compressmatrix(&p,a);
compressmatrix(&q,b);
add(a,b,c);
printf(&the spmatrix c is:\n&);
while(i&=c[0][2])
{ printf(&%d%5d%5d\n&,c[i][0],c[i][1],c[i][2]);
程序运行时先输入矩阵的行和列，然后按普通矩阵格式输入矩阵值，一组程序测试用例运
行结果如下图：
【参考程序
#include &stdio.h&
#include &malloc.h&
#define MAX 100
typedef struct{
int data[MAX][3];
matrix *Input(matrix *A)
{ int i,j;
A = (matrix*)malloc(sizeof(matrix));
scanf(&%d%d%d&,&A-&m,&A-&n,&A-&value);
A-&data[0][0] = A-&m;
A-&data[0][1] = A-&n;
A-&data[0][2] = A-&
for(i = 1;i &= A-&i ++)
for(j = 0;j & 3; j ++)
scanf(&%d&,&A-&data[i][j]);
void Output(matrix *A)
{ int i,j;
printf(&************************************\n&);
for(i = 0;i &= A-&i ++)
for(j = 0;j & 3;j ++)
printf(&%d &,A-&data[i][j]);
printf(&\n&);
printf(&************************************\n&);
matrix *addmatrix(matrix *A,matrix *B,matrix *C)
{ int i = 1,j =1,k = 1;
C = (matrix*)malloc(sizeof(matrix));
while(i &= A-&value && j &= B-&value)
if(A-&data[i][0] == B-&data[j][0])
if(A-&data[i][1] == B-&data[j][1])
C-&data[k][0] = A-&data[i][0];
C-&data[k][1] = A-&data[i][1];
C-&data[k][2] = A-&data[i][2] + B-&data[j][2];
if(C-&data[k][2] != 0) k ++;
else if(A-&data[i][1] & B-&data[j][1])
C-&data[k][0] = A-&data[i][0];
C-&data[k][1] = A-&data[i][1];
C-&data[k][2] = A-&data[i][2];
C-&data[k][0] = B-&data[j][0];
C-&data[k][1] = B-&data[j][1];
C-&data[k][2] = B-&data[j][2];
else if(A-&data[i][0] & B-&data[j][0])
C-&data[k][0] = A-&data[i][0];
C-&data[k][1] = A-&data[i][1];
C-&data[k][2] = A-&data[i][2];
C-&data[k][0] = B-&data[j][0];
C-&data[k][1] = B-&data[j][1];
C-&data[k][2] = B-&data[j][2];
while(i &= A-&value)
C-&data[k][0] = A-&data[i][0];
C-&data[k][1] = A-&data[i][1];
C-&data[k][2] = A-&data[i][2];
while(j &= B-&value)
C-&data[k][0] = B-&data[j][0];
C-&data[k][1] = B-&data[j][1];
C-&data[k][2] = B-&data[j][2];
C-&data[0][0] = (A-&data[0][0]&=B-&data[0][0])?A-&data[0][0]:B-&data[0][0];
C-&data[0][1] = (A-&data[0][1]&=B-&data[0][1])?A-&data[0][1]:B-&data[0][1];
C-&data[0][2] = k-1;
C-&value = k-1;
int main()
matrix * A = NULL,*B = NULL,*C = NULL;
printf(&提示：请按三元组格式输入矩阵内容。
printf(&Input A matrix:\n&);
A = Input(A);
printf(&Input B matrix:\n&);
B = Input(B);
C = addmatrix(A,B,C);
Output(C);
程序运行时按照三元组的格式输入矩阵信息，程序运行结果如下图所示：
4.16写出两个稀疏矩阵相乘的算法，计算：
Cpn = Apm .Bmn
其中，A、B和
C都采用三元组表示法存储。
【答】：
#include &stdio.h&
#include &malloc.h&
#define MAX 100
typedef struct{
int data[MAX][3];
matrix *Input(matrix *A)
{ int i,j;
A = (matrix*)malloc(sizeof(matrix));
scanf(&%d%d%d&,&A-&m,&A-&n,&A-&value);
A-&data[0][0] = A-&m;
A-&data[0][1] = A-&n;
A-&data[0][2] = A-&
for(i = 1;i &= A-&i ++)
for(j = 0;j & 3; j ++)
scanf(&%d&,&A-&data[i][j]);
void Output(matrix *A)
printf(&*******************************\n&);
for(i = 0;i &= A-&i ++)
for(j = 0;j & 3;j ++)
printf(&%d &,A-&data[i][j]);
printf(&\n&);
printf(&*******************************\n&);
/* 基于三元组存储结构的矩阵相乘算法
matrix *MulMatrix(matrix *A,matrix *B,matrix *C)
{ int i ,j ,k ,r=1,p,q,s;
C = (matrix*)malloc(sizeof(matrix));
C-&m=A-&m;
C-&n=B-&n;
C-&data[0][0]=C-&m;
C-&data[0][1]=C-&n;
for (i=0;i&C-&m;i++)
for (j=0;j&C-&n;j++)
for (k=0;k&A-&n;k++)
while (p&=A-&value)
if (A-&data[p][0]==i&&A-&data[p][1]==k)
while (q&=B-&value)
if (B-&data[q][0]==k&&B-&data[q][1]==j)
if (p&=A-&value && q&=B-&value)
s=s+A-&data[p][2]*B-&data[q][2];
{ C-&data[r][0]=i;
C-&data[r][1]=j;
C-&data[r][2]=s;
C-&data[0][2]=r-1;
C-&value=r-1;
int main()
matrix * A = NULL,*B = NULL,*C = NULL;
printf(&提示：请按三元组格式输入矩阵内容。
printf(&Input A matrix:\n&);
A = Input(A);
printf(&Input B matrix:\n&);
B = Input(B);
C = MulMatrix(A,B,C);
Output(C);
程序运行时，要求按照三元组的格式输入矩阵信息。
5.1试述递归程序设计的特点。
【答】：
（1）具备递归出口。递归出口定义了递归的终止条件，当程序的执行使它得到满足时，
递归执行过程便终止。有些问题的递归程序可能存在几个递归出口。
（2）在不满足递归出口的情况下，根据所求解问题的性质，将原问题分解成若干子问题，
子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合
成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。
5.2试简述简单递归程序向非递归程序转换的方法。
【答】：简单递归程序转换为非递归程序可以采用算法设计中的递推技术。递归方法与递
推方法共同采用的分划技术，为使用递推技术解决递归问题奠定了基础。由于简单递归问题求
解过程中无需回溯，因而要转换成非递归方式实现完全可以使用递推技术。为了使用自底向上
的递推方式来解决递归问题，利用子问题已有的解构造规模较大子问题的解，进而构造原问题
的解，必须建立原问题与子问题解之间的递推关系，然后定义若干变量用于记录求解过程中递
推关系的每个子问题的解；程序的执行便是根据递推关系，不断修改这些变量的值，使之成为
更大子问题的解的过程；当得到原问题解时，递推过程便可结束了。
5.3 试简述复杂递归程序向非递归程序转换的方法，并说明栈在复杂递归程序转换成非
递归程序的过程中所起的作用。
【答】：复杂递归问题在求解的过程中无法保证求解动作一直向前，需要设置一些回溯点，
当求解无法进行下去或当前处理的工作已经完成时，必须退回到所设置的回溯点，继续问题的
求解。因此，在使用非递归方式实现一个复杂递归问题的算法时，经常使用栈来记录和管理所
设置的回溯点。
5.4试给出例题
Fact(5)的执行过程分析。
【答】：Fact(5)的执行过程如下图所示：
2 + … + anxn
5.5已知多项式
pn(x) = a0 + a1x + a2x的系数按顺序存储在数组
a中，试：
（1）编写一个递归函数，求
n阶多项式的值；
（2）编写一个非递归函数，求
n阶多项式的值。
【答】：
#include &stdio.h&
#include &math.h&
#include &stdlib.h&
double pnx1(double a[],int n,double x) //（1）递归函数
{ if (n==0) return a[0];
return pnx1(a,n-1,x)+a[n]*pow(x,n);
double pnx2(double a[],int n,double x) //（2）非递归迭代函数
for (i=n-1;i&=0;i--)
t=a[i]+t*x;
int main()
{ double *a,x,p;
printf(&请输入
scanf(&%d%lf&,&n,&x);
a=(double*)malloc((n+1)*sizeof(double));
printf(&请输入
%d项系数：
for (i=0;i&=n;i++)
scanf(&%lf&,&a[i]);
p=pnx1(a,n,x);
printf(&%f\n&,p);
p=pnx2(a,n,x);
printf(“%f\n”,p);
5.6已知两个一维整型数组
b，分别采用递归和非递归方式编写函数，求两个数组的
内积（数组的内积等于两个数组对应元素相乘后再相加所得到的结果）。
【答】：
#include &iostream&
long sum1(int a[],int b[],int n) //非递归函数
for (i=0;i&n;i++)
s+=a[i]*b[i];
long sum2(int a[],int b[],int n) //递归函数
return a[0]*b[0];
return sum2(a,b,n-1)+a[n-1]*b[n-1];
int main()
int i,n,*a,*b;
cout&&&输入数组的长度
a=new int [n];
b=new int [n];
cout&&&请输入数组
for (i=0;i&5;i++)
cin&&a[i];
cout&&&请输入数组
for (i=0;i&5;i++)
cin&&b[i];
s=sum1(a,b,5);
cout&&&非递归计算的和
s=sum2(a,b,5);
cout&&&递归计算的和
delete []a;
delete []b;
Ackerman函数
Ack(m，n)值的递归函数，
Ackerman函数在
n ≥ 0时的
定义为：
Ack(0，n)=n+1;
Ack(m，0)=Ack(m.1，1);
Ack(m，n)=Ack(m.1，Ack(m，n.1)) n&0且
// 输入 m,和 n的值，计算
#include &stdio.h&
int Ack (int m,int n)
{ if (m == 0)
{ return n + 1;
else if (n == 0)
{ return Ack (m - 1,1);
{ return Ack (m - 1,Ack (m,n - 1));
int main ()
printf (&Please input m n\n&);
scanf (&%d%d&,&m,&n);
printf (&Ack (m,n) = %d\n&,Ack (m,n));
已知多项式
Fn(x)的定义如下：
2xFn.1( ) .
2( n .1) Fn.2 xn &1
试写出计算
Fn(x)值的递归函数。
【答】：
// 输入 n，x 计算
#include &stdio.h&
// 为了符合递归函数的表达这里将
x作为参数传递，在实际运用中建议使用全局变量。
// C++中也可以传递引用
int Function (int n,const int &x)
int Function (int n,int x)
{ if (n == 0)
{ return 1;
else if (n == 1)
{ return 2 *
{ return 2 * x * Function (n - 1,x) - 2 * (n - 1) * Function (n - 2,x);
int main ()
printf (&input n,x:\n&);
scanf (&%d%d&,&n,&x);
printf (&F(x) = %d\n&,Function (n,x));
Hanoi塔问题：设有
3个分别命名为
Z的塔座，在塔座
X上从上到下放有
n个直径各不相同、编号依次为
1，2，3，…，n的圆盘（直径大的圆盘在下，直径小的圆盘在上），
现要求将
n个圆盘移至塔座
Z上，并仍然按同样的顺序叠放，且圆盘移动时必须遵循以
下规则：
（1）每次只能移动一个圆盘；
（2）圆盘可以插在塔座
Z中任何一个塔座上；
（3）任何时候都不能将一个大的圆盘压在一个小的圆盘之上。
试编写一个递归程序实现该问题。
【答】：
#include &stdio.h&
void Hanoi(int n,char x,char y,char z)
printf(&%c--&%c\n&,x,z);
Hanoi(n-1,x,z,y);
printf(&%c--&%c\n&,x,z);
Hanoi(n-1,y,x,z);
int main()
printf(&请输入盘子个数：
scanf(&%d&,&n);
Hanoi(n,'X','Y','Z');
5.10八皇后问题：在一个
8×8格的国际象棋棋盘上放上
8个皇后，使其不能相互攻击，
即任何两个皇后不能处于棋盘的同一行、同一列和同一斜线上。试编写一个函数实现八皇后问
题。
【答】：
解法一：（程序
place.cpp）
解向量：(x1，x2，…，xn)
显约束：xi=1，2，…，n
1）不同列：xi≠xj
2）不处于同一正、反对角线：
|i-j|≠|xi-xj|
#include &stdio.h&
#include &math.h&
#define n 8
int x[n+1]={0}; //x[i]的含义表示第
int sum=0; //sum用于记录
n后问题的所有解
void print(); //输出
n后问题的解
int Place(int k) //检测第
k行的皇后放置是否符后规则
{ for (int j=1;j&k;j++)
if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
void Backtrack(int t) //放置
n后问题的第
{ if (t&n) { sum++;
print(); //输出一种解方案
getchar();
for (int i=1;i&=n;i++)
{ x[t]=i; //试探在第
if (Place(t)) Backtrack(t+1);
void print() //输出
n后问题的解
printf(&%d皇后问题的第
%d种解为:\n&,n,sum);
for (i=1;i&=n;i++)
printf(&%d:%d\n&,i,x[i]);
int main()
Backtrack(1);
解法二：
程序思想：
用
3个数组分别存放
8列，15个左对角线和
15个右对角线的值
,同时用一个
8元素大小的
数组记录下放置的皇后的位置。
初始时将三个数组全部标记为
0。
一，从第一行开始，从左向右开始查找。当找到第一个能够放下棋子的点
x,y（其对应的
列，左对角，右对角全部为
0）后，将此棋子所对应的列，左对角，右对角全部设置为
1，然
后继续放置下一行――x + 1行（调用自身的子函数）。
二，当其子函数执行完毕后，将放在
x,y上的点拿起，然后将这点对应的列，左对角，右
对角元素全部置
0，然后继续在此行的
y后查找能放置的点。
三，如果当前要放置的棋子为第
9个棋子的时候，打印结果。
5_10.c（递归法）
5_10_byStack.c (用栈回溯法
/*****************************************************/
/*八皇后问题递归解法 */
/*****************************************************/
#include&stdio.h&
int left[16],right[16],row[9],queen[9],count=0; /*分别用来存放左对角线和右对角线的使用
,row数组记录行数的棋子摆放情况，未使用的话就赋予
0，使用的话就赋予
/*row 的数组用来存放列的使用情况，当第
m列被使用的时候在
row[n]=m*/
queen数组用来专门存放当前皇后的摆放情况*/
int prin()/*打印出皇后的放置情况
printf(& The %d th&,count);
for(m=1;m&=8;m++)
printf(& %d&,queen[m]);
printf(&\n&);
int kaiserin(int line)/*line表示当前放棋子的列数,第一次放的时候为
{/*本变量用来记录当前行放子的列数
for(i=1;i&=8;i++)
if((row[i]||left[i+line-1]||right[8-i+line])==0)/*看当前的列是否可以放
row[i]=1;left[i+line-1]=1;
right[8-i+line]=1;queen[line]=i;
if(line==8)/*如果当前找到第
8行了，说明找成功了，打印
kaiserin(line+1);/*找到了，但是还没找完，将这点放上，然后尝试下一列
left[i+line-1]=0;row[i]=0;
right[8-i+line]=0;queen[line]=0;
/*不管找到没找到，重新初始化当前放子的点，开始右移放子
void init()/*将三个数组进行初始化
for(i=1;i&16;i++)
left[i]=right[i]=0;
for(i=1;i&9;i++)
queen[i]=row[i]=0;
int main()
kaiserin(1);
/********************************************/
/*八皇后问题回溯法 */
/********************************************/
#include&stdio.h&
#define max 10
typedef struct{/*用来存放回溯点的信息，
row用来存放回溯点所放的行数，line用来存放所放
的列数*/
int left[16],right[16],row[9],queen[9],count=0;/*分别用来存放左对角线和右对角线的使用情
况,row数组记录行数的棋子摆放情况，未使用的话就赋予
0，使用的话就赋予
/*row 的数组用来存放列的使用情况，当第
m列被使用的时候在
row[n]=m*/
queen数组用来专门存放当前皇后的摆放情况*/
void print() /*打印出皇后的放置情况
printf(&The %d th&,count);
for(m=1;m&=8;m++)
printf(& %d&,queen[m]);
printf(&\n&);
void init()/*将三个数组进行初始化
for(i=1;i&16;i++)
queen[i]=left[i]=right[i]=0;
for(i=1;i&9;i++)
int kaiserin()
{ node back[max];
int opline=1,oprow=1,i,find,top=0;
while(1)/*循环条件用真，用
return来结束循环和整个函数*/
for(i=i&=8;i++)
if((row[i]||left[i+opline-1]||right[8-i+opline])==0)/*判断当前的点是否可放
{ find=1;/*找到的话结束循环
if(find)/*找到了这点
{ oprow=i;
row[oprow]=1; left[oprow+opline-1]=1;
right[8-oprow+opline]=1;queen[opline]=/*把这个点放上
back[top].row=back[top].line=
/*记录回溯点*/
opline++;oprow=1;/*开始找下一行
else /*需要进行回溯
{ if(opline==9)
if(top==0)
return 0;/*如果栈取空了，说明查找结束
oprow=back[top]./*如果栈中还有元素可取
opline=back[top]./*取出栈顶元素
row[oprow]=0; left[oprow+opline-1]=0;/*同时将这个棋子拿起*/
right[8-oprow+opline]=0;queen[opline]=0;
}while(oprow==8);/*当取到的
oprow的右边可以放子时，开始下一步操作
kaiserin();
6.1树最适合用来表示具有（ 有序 ）性和（ 层次 ）性的数据。
6.2 在选择存储结构时，既要考虑数据值本身的存储，还需要考虑（数据间关系 ）
的存储。
6.3对于一棵具有 n个结点的树，该树中所有结点的度数之和为（ n-1 ）。
6.4已知一棵树如图 6.11所示，试回答以下问题：
图6.11 一棵树
（1）树中哪个结点为根结点？哪些结点为叶子结点？
【答】：A是根结点；E，G，H，I，C，J，K，L为叶结点。
（2）结点 B的双亲为哪个结点？其子女为哪些结点？
【答】：B的双亲结点是 A，其子女结点为 E和 F。
（3）哪些结点为结点 I的祖先？哪些结点为结点 B的子孙？
【答】：F，B，A是结点 I的祖先结点；E，F，G，H，I是 B的子孙结点。
（4）哪些结点为结点 D的兄弟？哪些结点为结点 K的兄弟？
【答】：B，C，L是结点 D的兄弟结点，J是结点 K的兄弟结点。
（5）结点 J的层次为多少？树的高度为多少？
【答】：结点 J的层次为 3，树的高度为 4。
（6）结点 A、C的度分别为多少？树的度为多少？
【答】：结点 A的度为 4，结点 C的度是 0，树的度是 4。
（7）以结点 B为根的子树的高度为多少？
【答】：以结点 B为根的子树的高度是 3。
（8）试给出该树的括号表示及层号表示形式。
【答】：该树的括号表示为：A（B（E，F（G，H，I）
）），C，D（J，K），L），该树的层号
表示为：10A，20B，30E，30F，40G，40H，40I，20C，20D，25J，25K，20L
6.5试写出图 6.11所示树的前序遍历、后序遍历和层次遍历的结果。
【答】：前序遍历：ABEFGHICDJKL
后序遍历：EGHIFBCJKDLA
层次遍历：ABCDLEFJKGHI
6.6试给出图 6.11所示树的双亲表示法和数组方式孩子表示法的表示。
【答】：
双亲表示法：
data parent
数组方式的孩子表示法：
data Child[0] Child[1] Child[2] Child[3]
A 1 2 3 11
B 4 5 -1 -1
C -1 -1 -1 -1
D 9 10 -1 -1
E -1 -1 -1 -1
F 6 7 8 -1
G -1 -1 -1 -1
H -1 -1 -1 -1
I -1 -1 -1 -1
J -1 -1 -1 -1
K -1 -1 -1 -1
L -1 -1 -1 -1
6.7已知一棵度为
……，nm个度为
m的结点，问该树中有多少个叶子结点？
【答】：
树中结点总数
n=n0+n1+n2+…+nm
树中结点的度数之和为
n-1，且有：n-1=n1+2n2+3n3+…+mnm
所以叶子结点个数为：n0=n2+2n3+…+(m-1)nm
6.8假设树采用指针方式的孩子表示法表示，试编写一个非递归函数，实现树的前序遍历
算法。
【答】：本程序在运行时请按树的括号表示法输入拟遍历的树，例如，对习题
所示的树为例，应输入
A（B（E，F（G，H，I）），C，D（J，K），L）
定义树的链式存储结构及建立树的存储结构
CreateTree函数（
tree.h）内容如下：
#include &stdio.h&
#include &malloc.h&
#include &string.h&
// 树的最大度定义为
#define MAXN 5
#define MAXLEN 100
typedef char dataT
typedef struct node
struct node *child[MAXN];
/*----------------------------------------------------------------*
树的括号法转化到树指针方式的孩子表示法
*-----------------------------------------------------------------*/
TreeNode *CreateTree (TreeNode *root,char string[MAXLEN])
TreeNode *stack[MAXLEN],*temp = NULL,*n;
int childSeq[MAXLEN]; // 其第几个孩子
length = strlen (string);
for (i = 0;i &i++)
if (string[i] == ',')
else if (string[i] == '(')
stack[++top] =
childSeq[top] = 0;
else if (string[i] == ')')
else if (top != -1)
n = (TreeNode*)malloc (sizeof (TreeNode));
n-&key = string[i];
for (j = 0;j & MAXN;j++)
n-&child[j] = NULL;
stack[top]-&child[childSeq[top]++] =
root = (TreeNode *)malloc (sizeof (TreeNode));
root-&key = string[i];
for (j = 0;j & MAXN;j++)
root-&child[j] = NULL;
void PreOrder (TreeNode *root)
if (root != NULL)
printf (&%5c&,root-&key);
for (i = 0;i & MAXN;i++)
{ PreOrder (root-&child[i]);
树的前序非递归遍历算法及其测试程序（6_8.c）如下所示：
#include &tree.h&
/*前序遍历（非递归） */
void PreOrder1(TreeNode *root)
TreeNode *stack[MAXLEN];
int top=-1,i;
while (root || top!=-1)
{ printf(&%c&,root-&key);
for (i=MAXN-1;i&0;i--)
if (root-&child[i])
stack[++top]=root-&child[i];
root=root-&child[0];
if (top&-1)
{root=stack[top--];
int main ()
{ char string[MAXLEN];
TreeNode *root = NULL;
printf (&请用树的括号表示法输入一棵树
scanf (&%s&,string);
root = CreateTree (root,string);
PreOrder1(root);
假设树采用指针方式的孩子表示法表示，试编写一个非递归函数，实现树的后序遍历
算法。
【答】：
#include &tree.h&
int PostOrderByStack (TreeNode *root)
TreeNode *
TreeNode *stack[MAXLEN];
// childSeq表示当前打印到了此树第几个孩子，
int top,childSeq[MAXLEN];
top = -1; //初始化空栈
while (temp != NULL)
for (i = 0;i & MAXN;i++)
{ if (temp-&child[i] != NULL)
childSeq[++top] = i + 1;
stack[top] =
temp = temp-&child[i];
// 如果此节点是叶子节点，则输出该结点
if (i == MAXN)
{ printf (&%5c&,temp-&key);
temp = NULL;
while (top != -1 )
for (i = childSeq[top];i & MAXN;i++)
if (stack[top]-&child[i] != NULL)
temp = stack[top]-&child[i];
childSeq[top] = i + 1;
if (i == MAXN)
printf (&%5c&,stack[top]-&key);
if (temp != NULL)
if (top == -1)
int main ()
{ char string[MAXLEN];
TreeNode *root = NULL;
printf (&请用树的括号表示法输入一棵树
scanf (&%s&,string);
root = CreateTree (root,string);
PostOrderByStack (root);
6.10假设树采用指针方式的孩子表示法表示，试编写一个函数，判断两棵给定的树是否
等价（两棵树等价当且仅当其根结点的值相等且其对应的子树均相互等价）。
#include &tree.h&
#define TRUE 1
#define FALSE 0
/*--------------------------------------------------*
递归比较两棵树是否相等
*--------------------------------------------------*/
int PreCmp (TreeNode *tree1,TreeNode *tree2)
if (tree1 == NULL && tree2 == NULL)
return TRUE;
else if (tree1 == NULL && tree2 != NULL || tree1 != NULL && tree2 == NULL)
return FALSE;
if (tree1-&key != tree2-&key)
return FALSE;
for (i = 0;i & MAXN;i++)
if (PreCmp (tree1-&child[i],tree2-&child[i]) == FALSE)
return FALSE;
return TRUE;
int main ()
char string[MAXLEN];
TreeNode *tree1 = NULL,*tree2 = NULL;
printf (&请用树的括号表示法输入第一棵树
scanf (&%s&,string);
tree1 = CreateTree (tree1,string);
printf (&请用树的括号表示法输入第二棵树
scanf (&%s&,string);
tree2 = CreateTree (tree2,string);
if (PreCmp (tree1,tree2) == TRUE)
printf (&两树相等
printf (&两树不相等
7.1选择题。
（1）前序遍历和中序遍历结果相同的二叉树为（ F ）；前序遍历和后序遍历结果相同的
二叉树为（ B ）。
A．一般二叉树 B．只有根结点的二叉树
C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树
E．所有结点只有左子树的二叉树 F．所有结点只有右子树的二叉树。
（2）以下有关二叉树的说法正确的是（ B ）。
A．二叉树的度为 2 B．一棵二叉树的度可以小于 2
C．二叉树中至少有一个结点的度为 2 D．二叉树中任一个结点的度均为 2
（3）一棵完全二叉树上有 1001个结点，其中叶子结点的个数为（ D ）。
A．250 B．500 C．254 D．501
（4）一棵完全二叉树有 999个结点，它的深度为（ B ）。
A．9 B．10 C．11 D．12
（5）一棵具有 5层的满二叉树所包含的结点个数为（ B ）。
A．15 B．31 C．63 D．32
7.2用一维数组存放完全二叉树： ABCDEFGHI，则后序遍历该二叉树的结点序列为
（ HIDEBFGCA ）。
7.3有 n个结点的二叉树，已知叶结点个数为 n0，则该树中度为 1的结点的个数为
（ n-2n0+1 ）；若此树是深度为 k的完全二叉树，则 n的最小值为（ 2k-1 ）。
7.4设 F是由 T1、T2和 T3三棵树组成的森林，与 F对应的二叉树为 B。已知 T1、T2
和 T3的结点数分别是 n1、n2和 n3，则二叉树 B的左子树中有（ n1-1）个结点，二叉树
B的右子树中有（ n2+n3）结点。
7.5高度为 k的二叉树的最大结点数为（ 2k-1 ），最小结点数为（ k ）。
7.6对于一棵具有 n个结点的二叉树，该二叉树中所有结点的度数之和为（ n-1 ）。
7.7已知一棵二叉树如图 7.12所示，试求：
（1）该二叉树前序、中序和后序遍历的结果；
【答】：前序： abdgecfh；中序： dgbcafhc；后序：gdebhfca
（2）该二叉树是否是满二叉树？是否是完全二叉树？
【答】：该二叉树不是满二叉树，也不是完全二叉树。
（3）将它转换成对应的树或森林；
【答】：
图7.12 一棵二叉树
（4）这棵二叉树的深度为多少？（4）这棵二叉树的深度为多少？
【答】：该二叉树的深度为
（5）试对该二叉树进行前序线索化；
【答】：
abcdefgh`
（6）试对该二叉树进行中序线索化。
【答】：
7.8试述树和二叉树的主要区别。
（1）树的结点个数至少为
1，而二叉树的结点个数可以为
0。
（2）树中结点的最大度数没有限制，而二叉树结点的最大度数为
2。
（3）树分为有序树与无序树，而二叉树一定是有序树，它的结点有左，右之分。
7.9试分别画出具有
3个结点的树和具有
3个结点的二叉树的所有不同形态。
【答】：
三个结点的树有两种形态：
三个结点的二叉树具有五种形态：
7.10已知一棵二叉树的中序遍历的结果为
ABCEFGHD，后序遍历的结果为
ABFHGEDC，试画出此二叉树。
【答】：
已知一棵二叉树的前序遍历的结果为ABCDEF，中序遍历的结果为CBAEDF，试
画出此二叉树。
【答】：
7.12若一棵二叉树的左、右子树均有
3个结点，其左子树的前序序列与中序序列相同，
右子树的中序序列与后序序列相同，试画出该二叉树。
【答】：
7.13分别采用递归和非递归方式编写两个函数，求一棵给定二叉树中叶子结点的个数。
【答】：为方便测试二叉树相关程序，定义二叉树头文件
bintree.h如下：
#include &stdio.h&
#define N 100
extern char *a; /*存放扩充二叉树的前序序列
typedef struct node /*二叉树结构定义
struct node *lchild,*
typedef binnode *
creat(根据扩充二叉树的前序序列(字符串
a)建立二叉树
t的存储结构
void creat(bintree * t)
char ch=*a++;
if (ch==' ') *t=NULL;
{ *t=(bintree)malloc(sizeof(binnode));
(*t)-&data=
creat(&(*t)-&lchild);
creat(&(*t)-&rchild);
void preorder(bintree t) /*前序递归遍历二叉树*/
{ printf(&%c&,t-&data);
preorder(t-&lchild);
preorder(t-&rchild);
/*顺序栈定义*/
typedef struct
{ bintree data[N];
void init(seqstack *s) /*初始化空栈*/
s-&top=-1;
int empty(seqstack *s) /*判断栈是否为空*/
if (s-&top&-1) return 0;
else return 1;
int full(seqstack *s) /*判断栈是否为满
if (s-&top==N-1) return 1;
else return 0;
void push(seqstack *s ,bintree x) /*进栈*/
if (!full(s))
s-&data[++s-&top]=x;
bintree pop(seqstack *s) /*出栈*/
if (!empty(s))
return s-&data[s-&top--];
基于上述结构，递归方法与非递归方法求二叉树中叶子结点的个数的算法分别如
leaf2()所示：
#include &bintree.h&
char *a=&ABC D EF G &; /*扩充二叉树序树
t的前序序列
int leaf1(bintree t) /*递归方法求二叉树叶子结点的个数
if (t==NULL) return 0;
if (!t-&lchild && !t-&rchild)
return leaf1(t-&lchild)+leaf1(t-&rchild);
int leaf2(bintree t) /*非递归方法求二叉树叶子结点的个数
/*顺序栈*/
int count=0; /*叶子结点计数变量
init(&s); /*初始化空栈*/
while (t || !empty(&s))
{if (!t-&lchild && !t-&rchild) count++;
push(&s,t);
{t=pop(&s);
int main()
creat(&t); /*建立二叉树
t的存储结构
printf(&\n该二叉树一共有
%d个叶子结点！
\n&,leaf1(t));
printf(&\n该二叉树一共有
%d个叶子结点！
\n&,leaf2(t));
7.14试编写一个函数，将一棵给定二叉树中所有结点的左、右子女互换。
#include &bintree.h&
char *a=&ABC D EF G &; /*扩充二叉树序树
t的前序序列
void change(bintree t)
t-&lchild=t-&
t-&rchild=p;
change(t-&lchild);
change(t-&rchild);
int main()
creat(&t); /*建立二叉树
t的存储结构
preorder(t);
change(t);
printf(&\n&);
preorder(t);
7.15试编写一个函数，返回一棵给定二叉树在中序遍历下的最后一个结点。
【答】：
#include &bintree.h&
char *a=&ABC D EF G &; /*扩充二叉树序树
t的前序序列
bintree inlast(bintree t)
{ bintree p=t;
while (p && p-&rchild)
int main()
creat(&t); /*建立二叉树
t的存储结构
printf(&二叉树中序遍历最后一个结点是%c\n&,inlast(t)-&data);
7.16试编写一个函数，返回一棵给定二叉树在前序遍历下的最后一个结点。
#include &bintree.h&
char *a=&ABC D EF G &; /*扩充二叉树序树
t的前序序列
/*求二叉树前序遍历的最后一个结点
bintree prelast(bintree t)
while (p && p-&lchild || p-&rchild)
if (p-&rchild)
int main()
creat(&t); /*建立二叉树
t的存储结构
printf(&二叉树前序遍历的最后一个结点是%c\n&,prelast(t)-&data);
7.17试编写一个函数，返回一棵给定二叉树在后序遍历下的第一个结点。
【答】：
#include &bintree.h&
char *a=&ABC D EF G &; /*扩充二叉树序树
t的前序序列
/*求二叉树后序遍历的第一个结点
bintree succfirst(bintree t)
while (p && p-&lchild || p-&rchild)
if (p-&lchild)
int main()
creat(&t); /*建立二叉树
t的存储结构
printf(&二叉树后序遍历的第一个结点是%c\n&,succfirst(t)-&data);
7.18假设二叉树采用链式方式存储，
root为其根结点，
p指向二叉树中的任意一个结点，
编写一个求从根结点到
p所指结点之间路径长度的函数。
【答】：在后序遍历非递归算法中，当访问的结点为
p时，其祖先点正好全部在栈中，此
时栈中结点的个数就是根结点到
p所指结点之间路径长度。
#include&stdio.h&
#include&stdlib.h&
typedef struct node /*二叉树结点定义
struct node *lchild,*
typedef bintnode *
typedef struct stack
bintree data[100];
int tag[100];
void creat(bintree *t) ;
Depth，功能：求根结点到
x的路径长度
int Depth(bintree t,datatype x)
int i=0,j;
while(t || s.top!=0)
s.data[s.top]=t;
s.tag[s.top]=0;
while(s.top&0 && s.tag[s.top-1])
t=s.data[s.top];
if(t-&data==x) return s. //此时栈中的结点都是
x的祖先结点
if(s.top&0)
t=s.data[s.top-1];
s.tag[s.top-1]=1;
else t=NULL;
creat(根据扩充二叉树的前序序列建立二叉树
t的存储结构
void creat(bintree *t)
scanf(&%c&,&ch);
if (ch==' ')
*t=(bintnode *)malloc(sizeof(bintnode));
(*t)-&data=
creat(&(*t)-&lchild);
creat(&(*t)-&rchild);
int main()
{ bintree root,p=NULL;
printf(&请输入扩充二叉树的前序序列：\n&);
creat(&root);
printf(&请输入树中的
1个结点值：\n&);
scanf(&%1s&,&x);
k=Depth(root,x);
printf(&根结点到%c的长度是
%d\n&,x,k);
7.19假设二叉树采用链式方式存储，
root为其根结点，
q分别指向二叉树中任意两
个结点，编写一个函数，返回
q最近的共同祖先。
【答】：方法同上题，利用后序遍历非递归算法分别求出
q的公共祖先，然后再查找
它们的最近公共祖先结点。
#include&stdio.h&
#include&stdlib.h&
typedef struct node /*二叉树结点定义
struct node *lchild,*
typedef bintnode *
typedef struct stack //顺序栈结构定义
bintree data[100];
int tag[100];
void creat(bintree *t) ; //创建二叉树结构函数声明
SeekAncestor的功能是返回二叉树
y的最近公共祖先结点*/
void SeekAncestor(bintree t,datatype x,datatype y,bintree *antor)
bintree data[100]={0};
int i=0,j;
while(t || s.top&-1)
{ while(t)
s.data[++s.top]=t;
s.tag[s.top]=0;
while(s.top&-1 && s.tag[s.top])
t=s.data[s.top];
if(t-&data==x)
while(i&=s.top) //记录
x结点的所有祖先结点
data[i]=s.data[i];
else if(t-&data==y)
while(s.top&-1)
while(j&=0&&t!=data[j])//查找
x的最近公共祖先结点
*antor=data[j]; //返回公共祖先结点地址
t=s.data[--s.top];
if(s.top&-1)
t=s.data[s.top];
s.tag[s.top]=1;
else t=NULL;
creat(根据扩充二叉树的前序序列建立二叉树
t的存储结构
void creat(bintree *t)
scanf(&%c&,&ch);
if (ch==' ')
*t=(bintnode *)malloc(sizeof(bintnode));
(*t)-&data=
creat(&(*t)-&lchild);
creat(&(*t)-&rchild);
int main()
bintree root,p=NULL;
datatype x='B',y='C';
printf(&请输入扩充二叉树的前序序列：\n&);
creat(&root);
printf(&请输入树中的两个结点值：\n&);
scanf(&%1s%c&,&x,&y);
SeekAncestor(root,x,y,&p);
if (p)printf(&%c和%c的最近公共祖先是：
%c\n&,x,y,p-&data);
8.1选择题
（1）如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（ D ）。
A．有向完全图 B．连通图 C．强连通图 D．有向无环图
（2）若邻接表中有奇数个表结点，则一定（ D ）。
A．图中有奇数个顶点 B．图中有偶数个顶点
C．图为无向图 D．图为有向图
（3）下列关于无向连通图特性的叙述中，正确的是（ A ）。
Ⅰ．所有顶点的度之和为偶数
Ⅱ．边数大于顶点个数减 1
Ⅲ．至少有一个顶点的度为 1
A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ
（4）假设一个有 n个顶点和 e条弧的有向图用邻接表表示，则删除与某个顶点 vi相关的
所有弧的时间复杂度是（ B ）。
A．O(n) B．O(e) C．O(n+e) D．O(n*e)
（5）已知一个有向图 8.30所示，则从顶点 a出发进行深度优先偏历，不可能得到的 DFS
序列为（ A ）。
A．a d b e f c B．a d c e f b C．a d c b f e D．a d e f c b
d
图 8.30有向图
（6）无向图 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）}，对该图进行深度优先遍历，得到的顶点序列正确的是（ 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
（7）下列哪一个选项不是图 8.31所示有向图的拓扑排序结果（ C ）。
A．AFBCDE B．FABCDE C．FACBDE D．FADBCE
图 8.31 AOV网
（8）判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（ D ）。
A．单源最短路 Dijkstra算法 B．所有顶点对最短路 Floyd算法
C．广度优先遍历算法 D．深度优先遍历算法
（9）在一个带权连通图 G中，权值最小的边一定包含在 G的（ A ）。
A．最小生成树中 B．深度优先生成树中
C．广度优先生成树中 D．深度优先生成森林中
（10）下图所示带权无向图的最小生成树的权为（ C ）。
A．14 B．15 C．17 D．18
图8.32 带权无向图
8.2对于如图 8.33所示的无向图，试给出：
（1）图中每个顶点的度；
（2）该图的邻接矩阵；
（3）该图的邻接表与邻接多重表；
（4）该图的连通分量。
图8.33无向图图8.34有向图
（1）D(V0)=2；D（V1）=2；D（V2）=3；D（V3）=3；D（V4）=2；D（V5）=2；D（V6）
=1。
（2）该图的邻接矩阵如图 8.33.1所示。
图 8.33.2 邻接表
图 8.33.1邻接矩阵
（3）该图的邻接表如图 8.30.2所示；该图的邻接多重表如图 8.30.3所示。
图 8.33.3 邻接多重表
（4）该图的两个连通分量如图 8.33.4所示。
图 8.33.4 两个连通分量
8.3对于如图 8.34所示的有向图，试给出：
（1）顶点 D的入度与出度；
（2）该图的出边表与入边表；
（3）该图的强连通分量。
【答】：
（1）顶点 D的入度是 2；顶点 D的出度为 1。
（2）该图的出边表如图 8.34.1所示，该图的入边表如图 8.34.2所示。
图8.34.1 出边表图8.34.1 出边表
图8.34.2 入边表
（3）该图的两个强连通分量如图
8.34.3所示。
E
图8.34.3 两个强连通分量
8.4试回答下列关于图的一些问题。
（1）有
n个顶点的有向强连通图最多有多少条边？最少有多少条边？
（2）表示一个有
500个顶点，
500条边的有向图的邻接矩阵有多少个非零元素？
（3）G是一个非连通的无向图，共有
28条边，则该图至少有多少个顶点？
【答】：
（1）有
n个顶点的有向强连通图昨多有
n(n-1)条边；最少有
n-1条边。
（2）500个。
（3）9个顶点。
8.35所示的是某个无向图的邻接表，试：
（1）画出此图；
（2）写出从顶点
DFS遍历结果；
（3）写出从顶点
BFS遍历结果。
【答】：
8.35邻接表对应的无向图如图
8.35.1所示。
图
8.5的邻接表
（2）从顶点
DFS遍历结果是：A，B，C，F，E，G，D
（3）从顶点
BFS遍历结果是：A，B，C，D，F，E，G
8.6证明，用
Prim算法能正确地生成一棵最小生成树。
【证明】：
Prim算法是按照逐边加入的方法来构造最小生成树过程的。记构造过程中生成的子图为
G’始终是一棵树。这是因为初始时
V(G’)={u0}，E（G’）=Ф，是一棵树。随后每一
步都是向
G’中添加一个顶点同时添加一条边，始终保持
G’中所有顶点连通。这样，当
n
个顶点时是仅有
n-1条边的连通图，所以
G’是一棵树。
Prim算法在执行过程中，始终能保证
G’=（V’，E’）是无向连通网络
G=（V，E）上某个最小代价生成树的连通图，如果该结论正
确，则随着
V(G’)顶点不断增加，当
V(G’)=V(G)时，G’=(V’,E’)就是
G=(V,E)上的最小代价生
成树。
Prim算法的每一步都能保证
G’=(V’,E’)是无向连通网络
G=(V,E)上某个代价生成
树的子连通图。
初始时，G’仅有一个顶点
V（G’）={u0}，E（G’）=Ф，设该树为
G
的某个最小生成树的子连通图。现假设第
G’=(V’,E’)中含有
i个顶点，不妨设该树为
G（V，E）中存在一棵最小生成树包含着
i+1步，存在
uTi，v.Ti,且(u,v)是最
小两栖边，将顶点
u,v）添加到树
Ti中，所得树
Ti+1是包含
V（Ti）+{v}顶点集的生
成树，且具有
i+1个顶点。根据
MST性质，此时在
G=(V,E)中必存在一棵最小生成树包含着
Ti+1。由此可知，当
i=n时，G’(Tn)即为无向图
n个顶点的最小生成树。
当然在进行最小两栖边选择时，如果同时存在几个具有相同代价的最小两栖边，则可任选
一条，因些
Prim算法构造的最小生成树不是唯一的。但它们的最小（代价）总和是相等的。
8.7证明，用
Kruskal算法能正确地生成一棵最小生成树。
【证明】：
算法首先构造具有
n个不同顶点的
n个连通分量，然后在
E（G）中选择边(u,v)，若
u,v
顶点属于不同的两个连通分量，则把该边添加到树
T中，每添加一条边就减少一个连通分量。
当添加了共
n-1条边时，就把
n个连通分量变成一个连通分量，此时
n-1
条边的树。由于
n是有限数，
E（G）中边数也是有限的，所以算法具有有穷性。
T的边为（u1,v1）,(u2,v2)，…，(un-1,vn-1)，按权值从小到大排列，若存在一棵
树
T’的代价总和小于
T的代价总和，则必在
T’中存在一条边（
u’,v’）∈TE’，（u’,v’）
.TE，
且(u’,v’)的代价小于(un-1,vn-1)的代价，这就说明(u’,v’)边没有选取的原因是因为
u’,v’在同一个
连通分量，添加（
u’,v’）将产生回路，说明
T’不可能是树（添加一条边没有减少一个连通分
量，这样
T’的边数将大于
n-1）。这与
T’是一棵树的假设
相矛盾。证毕。
8.36所示的连通图，分别用
Kruskal
算法构造其最小生成树。
【答】：
Prim算法求解最小生成树的过程如图
8.36.1
所示。
图
8.36无向连通网
（b）选取（D,F）
4
ABCDEFG（b）选取（D,F）
4
ABCDEFG
CDEFG34
（c）选取（C,F）
（e）选取（
8.36.1 Prim算法求解最小生成树过程
（2）采用
Kruskal算法求解最小生成树时首先要对边进行由小到大进行排序，本题对边进行
排序的结果是：（D,F）1、（C,F）2、（A,F）3、（A,C）4、（F,G）4、（D,E）4、（D,B）4、（C,D）
5、（E,G）5、（A,D）6、（D,G）6、（A,B）7 。根据
Kruskal算法，构造最小生成树的过程如图
8.33.2所示。
（a）选取（A，F）
（d）选取（F,G）
A
B
（f）选取（D,B）
（a）选取（D，F）
（d）选取（F,G）
（b）选取（C,F）（c）选取（A,F）
4
G
E
（e）选取（
D,E）（f）选取（D,B）
图
8.36.2 Kruskal算法求解最小生成树过程
8.9对于如图 8.37所示的有向网，用 Dijkstra方法求从顶点 A到图中其他顶点的最短路径，
并写出执行算法过程中距离向量 d与路径向量 p的状态变化情况。
BACEDGF28
图 8.37有向网 图8.38 题8.10的AOV网
【答】：对于如图 8.37所示的有向网， Dijkstra方法求从顶点 A到图中其它顶点的最短径时，
距离向量与路径向量的状态变化如下表示：
d 路径向量
0 1 2 3 4 5 6 0 1 2 3 4 5 6
{A } -0 48 ∞ 15 28 ∞
40 -1 0 -1 0 0 -1 0
1 { AD} 3 0 48 ∞ 15 28 48 38 -1 0 -1 0 0 3 3
2 {ADE } 4 0 48 61 15 28 48 38 -1 0 4 0 0 3 3
3 { ADG} 6 0 48 61 15 28 48 38 -1 0 4 0 0 3 3
4 {ADGB } 1 0 48 60 15 28 48 38 -1 0 1 0 0 3 3
5 {ADGBF} 5 0 48 57 15 28 48 38 -1 0 5 0 0 3 3
6 {ADGBFC } 2 0 48 57 15 28 48 38 -1 0 5 0 0 3 3
从表中可以看出源点 A到其它各顶点的最短距离及路径为：
A→B：48 路径：A→B
A→C：57 路径：A→D→F→C
A→D：15 路径：A→D
A→E：28 路径：A→E
A→F：48 路径：A→D→F
A→G：38 路径：A→D→G
8.10试写出如图 8.38所示的 AOV网的 4个不同的拓扑序列。
【答】：图 8.38所示的 AOV网的 4个不同的拓扑序列为：
（1）ABDCEFGIH
（2）ABDECFGIH
（3）DABCEFGIH
（4）DAECBFGIH
8.11计算如图 8.39所示的 AOE网中各顶点所表示的事件的发生时间 ve(j)，vl(j)，各边所表
示的活动的开始时间 e(i)，l(i)，并找出其关键路径。
【答】：为描述方便，将 AOE网中的所有边事件记为 a0-a7，如图 8.39所示。按照关键路径算
法，求得各顶事件的最早与最晚开始时间如下表所示。
v0v1v2v3v5v46
a7
图 8.39 题 8.10的 AOE网
顶点 ve vl活动
e l l-e关键活动
v0 0 0 a0 0 0 0 √
v1 6 6 a1 0 1 1
v2 4 5 a2 6 6 0 √
v3 13 13 a3 4 5 1
v4 22 22 a4 4 5 1
v5 25 25 a5 13 13 0 √
a6 13 15 2
a7 22 22 0 √
可见，该 AOE网的关键路径是 a0,a2,a5,a7。（注：图中箭头指示求解的顺序）
8.12无向图采用邻接表作为存储结构，试写出以下算法
（1）求一个顶点的度；
（2）往图中插入一个顶点；
（3）往图中插入一条边；
（4）删去图中某顶点；
（5）删去图中某条边。
【答】：本题的参考解答基于以下的存储结构：
#define m 20 /*预定义图的最大顶点数 */
t /*顶点信息数据类型 */
typedef struct node{ /*边表结点*/
/*邻接点*/
struct node *
typedef struct vnode{ /*头结点类型*/
/*顶点信息*/
edgenode * /*邻接链表头指针 */
typedef struct{ /*邻接表类型*/
vertexnode adjlist [m]; /*存放头结点的顺序表
int n,e; /*图的顶点数与边数
（1）求一个顶点的度；
/*求无向图
i个顶点的度
int d(adjgraph g ,int i)
edgenode *p;
p=g.adjlist[i].
（2）往图中插入一个顶点；
void insertvex(adjgraph *g,datatype x)
{ int i=0,flag=0;
/*查找待插入的结点是否存在
while (!flag&&i&g-&n)
{if (g-&adjlist[i].vertex==x) flag=1;
if (flag) {
printf(&结点已存在
if (g-&n&m) { printf(&邻接表已满！&);
g-&adjlist[g-&n].vertex=x;
g-&adjlist[g-&n].firstedge=NULL;
（3）往图中插入一条边；
/*在无向图
g中插入无向边（
void insertedge(adjgraph *g,int i,int j)
{ edgenode *p,*s;
int flag=0;
if (i&g-&n&&j&g-&n)
{ p=g-&adjlist[i].
while (!flag&&p)
{if (p-&adjvex==j) flag=1;
if (flag) {printf(&边已存在!&);
/*插入无向边
s=(edgenode *)malloc(sizeof(edgenode));
s-&adjvex=j; /*邻接点序号为
s-&next=g-&adjlist[i].
g-&adjlist[i].firstedge=s; /*将新结点*s插入顶点
vi的边表头部*/
s=(edgenode *)malloc(sizeof(edgenode));
s-&adjvex=i; /*邻接点序号为
s-&next=g-&adjlist[j].
g-&adjlist[j].firstedge=s; /*将新结点*s插入顶点
vj的边表头部*/
printf(&插入边不合法
（4）删去}
我要回帖
更多推荐
- ·百度账号注销多久可以重新注册贴吧注销后注销前账号发的评论，别人还能回复你吗？你还能收到吗
- ·朋友圈我多次被禁？我又没触犯什么法律法规，为何长时间禁言要多久恢复？请平台审核人解封
- ·电脑音响连接智能电视没有音频输出口怎么连接音响上怎么没声音，有一条音频线不知道该插电视没有音频输出口怎么连接音响上哪儿，有谁知道吗？求求各位帮帮忙！
- ·可以用电脑清除荣耀手机恢复出厂设置密码密码并保留数据？
- ·win10系统,QQ输入法打字谷歌拼音输入法不在框内？
- ·家里有台老功放，用了3.5mm耳机接口转usb转莲花头插好了，只有两个左边和中间还有低音炮有声音，求大神看看怎么弄
- ·有没有专门安卓手机玩电玩游戏的平 台？
- ·如何加入携程网上的北京市导游协会
- ·我的家用格力中央空调显示E2为什么开机就显示E2，这该怎么办呢？
- ·格力三匹格兰仕三批定频柜机E4故障分析开五十分钟显示E丨，ovc接N极还是五十分钟显示E1，请问是那里出现问题？
- ·2018微信最新的版本公众号微货助手里提现出来的钱没有领怎么办
- ·怎么进u盘安装重装系统步骤图解启动求大神
- ·计算机基础大一考试题考试word文件一般在哪
- ·求一些分娩电视剧或流产电视剧的百度云
- ·求琅琊榜1和2的琅琊榜1电视剧百度云资源源 谢谢
- ·移动硬盘插电脑显示无法访问到电脑上显示无法访问
- ·i5 3570 gtx 950 2g b75技嘉主板用什么内存条 内存条一条4g 一条8g 大约功耗多少？
- ·大家想办法13000万配一台高端台式电脑主机品牌机
- ·这些黑暗ins风滤镜怎么调是怎么调的啊 什么软件有没有教程
- ·手机qq音乐怎么设置流量的最近播放，过多久才会需要流量才能听？可以更改吗？
- ·在数据结构的时间复杂度中计算时间复杂度的题目，请问我错了的这几题，应该怎么做？详细过程，谢谢！
- ·乐视手机突然密码解不开忘了账号密码怎么办
- ·百度知道问大家回答的人可以删除吗不了问过的问题，发过的图片，怎么回事？是版本太低了吗
- ·8.4版本的360360添加黑名单单在哪？？
- ·我的电脑显卡是1060,cpu,i53440内存16g，240g固态硬盘，怎么会卡顿，求大神回答
- ·可以帮我破chinanet怎么登陆-7sid
- ·求龙马2017短篇ROU合集文包 可发我百度云或者谢谢谢谢谢谢
- ·想查一下这个怎么查看电脑内存和配置一体的配置如何，是否可以玩吃鸡？
- ·戴尔vostro270s主板戴尔vostrooxfwhv,想再装一条8G内存条能不能兼容？cpu想装i5 3570兼容吗
- ·查看老公微信登录方式用声音解锁在哪声音索解锁不了怎么办?
- ·vivox21算是高端机吗
- ·南昌什么时候可以用5g莫非网络大家觉得怎么样
- ·我快手绑定手机号了但是手机号不会用了要怎么解除别人绑定我的手机号找回
- ·新买的8位QQ没挂出常用可以每天去看设备锁和QQ等级升级天数吗？没出常用不能加好友对吗？
- ·梦见将梦见很多大白菜什么意思叶子掰掉是什么意思
- ·湖北中国石化星期几优惠充值有什么优惠一般星期几还是每月几号充值有优惠
