数据结构课后习题答案

第一章（概论）习题参考答案

一、填空题
1. 集合、线性结构、树型结构、图状结构（网状结构）。
2. 顺序存储方法、链接存储方法、索引存储方法、散列存储方法
二、选择题。
1. B 2. C 3. D
三、简答题
1.算法与程序有何异同?
答：相同点：算法和程序的含义非常相似，就是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
不同点：首先，一个程序不一定满足有穷性，因此它不一定是算法。其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限制。
2.什么是数据结构？试举一个简单的例子说明。
答：数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容：数据的逻辑结构、存储结构和数据的运算。
例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。
3.什么是数据的逻辑结构？什么是数据的储存结构？
答：逻辑结构是指各数据元素之间的逻辑关系。逻辑结构包括四个方面的内容：集合、线性结构、树型结构、图状结构（网状结构）。
存储结构就是数据的逻辑结构用计算机语言的实现。存储结构包括四个方面的内容：顺序存储方法、链接存储方法、索引存储方法、散列存储方法
4.什么是算法？算法有哪些特性?
答：算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，算法还具有下列5个特性：有穷性、确定性、可行性、输入和输出。
四、算法分析题
1.
2.
3. 设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0;
while(i { k=k+10*i;i++;
}
分析：
i=1; //1
k=0; //1
while(i { k=k+10*i; //n-1
i++; //n-1
}
由以上列出的各语句的频度，可得该程序段的时间消耗：
T(n)=1+1+n+(n-1)+(n-1)=3n
可表示为T(n)=O(n)

(2) i=0; k=0;
do{
k=k+10*i; i++;
}
while(i分析：
i=0; //1
k=0; //1
do{ //n
k=k+10*i; //n
i++; //n
}
while(i由以上列出的各语句的频度，可得该程序段的时间消耗：
T(n)=1+1+n+n+n+n=4n+2
可表示为T(n)=O(n)

(3) i=1; j=0;
while(i+j<=n)
{
if (i>j) j++;
else i++;
}
分析：
通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，

所以该程序段的执行时间为：
T(n)=O(n)

(4)x=n; // n>1
　while (x>=(y+1)*(y+1))
y++;
分析：
由x=n且x的值在程序中不变，又while的循环条件(x>=(y+1)*(y+1))可知：当(y+1)*(y+1)刚超过n的值时退出循环。
由(y+1)*(y+1) 所以，该程序段的执行时间为：
向下取整(n^0.5-1)

(5) x=91; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++;

分析：
x=91; //1
y=100; //1
while(y>0) //1101
if(x>100) //1100
{　x=x-10; //100
y--; //100
}
else
x++; //1000
以上程序段右侧列出了执行次数。该程序段的执行时间为：
T(n)=O(1)

第二章(线性表)习题参考答案

一、基础知识题
1. 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。
答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。
链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。
头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。
2.何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：
（1）基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
（2）基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
3. 为什么在单循环链表中设置尾指针比设置头指针更好?
答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。
4在单

链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?
答：我们分别讨论三种链表的情况。
（1）单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
（2）双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。
（3）单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。
5.简述下列算法的功能。
LinkList Demo(LinkList L){ // L 是无头结点单链表
ListNode *Q,*P;
if(L&&L->next){
Q=L;L=L->next;P=L;
while (P->next) P=P->next;
P->next=Q; Q->next=NULL;
}
return L;
}// Demo

答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
二、算法设计题
1.设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入和删除算法：InsertList
和DeleteList.
答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。
链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。
头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。

2. 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
解：因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大(或相等)的结点数据，把x插入到这个数所在的位置就是了。算法如下：
void InsertIncreaseList( Seqlist *L , Datatype x )
{
int i;
for ( i=0 ; i < L -> length && L->data[ i ] < x ; i++) ;
// 查找并比较,分号不能少
InsertList ( L ，x , i ); // 调用顺序表插入函数
}
3. 设单链表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。
解：与上题相类似，只要从头找到第一个比x小(或相等)的结点数据，在这个位置插入就可以了。算法如下：
LinkList InsertDecreaseList( Linklist L, Datatype x )
{
int i;
ListNode *p,*s;
p=L;
file://查找
while(p->n

ext && p->next->data>x )
p=p->next;
s=(ListNode *)malloc(sizeof(ListNode));
s->data=x;
s->next=p->next;
p->next=s;
return L;
}
4.已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。
解：算法如下：
LinkList Link( LinkList L1 , LinkList L2 )
{
file://将两个单链表连接在一起
ListNode *p , *q ;
p=L1;
q=L2;
while ( p->next ) p=p->next; file://查找终端结点
p->next = q->next ; file://将L2的开始结点链接在L1之后
return L1 ;
}
本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为：
m+1=O(m)
5. 设A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。
解：根据已知条件，A和B是两个递增有序表，所以我们可以以A表为基础，按照插入单个元素的办法把B表的元素插入A表中，完成后，将表逆置就得到了一个按元素值递减有序的单链表C了。
算法如下：
LinkList MergeSort ( LinkList A , LinkList B )
{
// 归并两个递增有序表为一个递减有序表
ListNode *pa , *pb , *qa , *qb ;
pa=A;
pb=B ;
qa=A->next;
qb=B->next;
while ( qa && qb)
{
if ( qb->data < qa->data )
{
// 当B中的元素小于A中当前元素时，插入到它的前面
pb=qb;
qb=qb->next ;// 指向B中下一元素
pa->next=pb;
pb->next=qa;
pa=pb;

}
else if ( qb->data >= pa->data && qb->data <= qa->data)
{
// 当B中元素大于等于A中当前元素
// 且小于等于A中后一元素时，
// 将此元素插入到A的当前元素之后
pa=qa;
qa=qa->next; // 保存A的后一元素位置
pb=qb;
qb=qb->next; // 保存B的后一元素位置
pa->next=pb; file://插入元素
pb->next=qa;
}

else
{
// 如果B中元素总是更大,指针移向下一个A元素
pa=qa;
qa=qa->next;
}
}
if ( qb ) // 如果A表已到终端而B表还有结点未插入
{
// 将B表接到A表后面
pa->next=qb;
}
LinkList C=ReverseList ( A );// 调用前面2.8题所设计的逆置函数
return C; file://返回新的单链表C, 已是递减排列
}
该算法的时间复杂度分析如下：
算法中只有一个while
循环，在这个循环中，按照最坏的情况是B元素既有插到A的最前的，也有插到最后的，也就是说需要把A中元素和B中元素全部检查比较过，这时的所费时间就是m+n.
而新链表的长度也是m+n+1
(有头结点)，这样逆置函数的执行所费时间为m+n+1.所以可得整个算法的时间复杂度为：
m+n+m+n+1=2(m+n)+1= O(m+n)
---------------------------------------------------------------------------------------------------------
为验证本题，晓津设计了一个程序，清单如下：
//ListStruct.h 将链表

结构存为头文件
typedef char DataType; file://假设结点的数据类型是字符型
typedef struct node { file://结点类型定义
DataType data;
struct node *next;//结点的指针域
}ListNode;
typedef ListNode * LinkList;
// 以下是源文件 // 在VC++中运行通过。
#include
#include
#include "ListStruct.h"
#include
LinkList CreatList (void)
{ file://用尾插法建立带头结点的单链表
char ch;
LinkList head = (LinkList)malloc(sizeof( ListNode));
file://生成头结点
ListNode *s , *r;
r=head;//尾指针亦指向头结点
while ((ch=getchar())!='\n')
{
s=(ListNode *) malloc (sizeof(ListNode));
s->data=ch;
r->next=s;
r=s;
}
r->next=NULL;
return head;
}
void OutList( LinkList L)
{
ListNode *p;
p=L;
while (p->next)
{
cout << p->next->data << " " ;
p=p->next;
}
cout << endl;
}
LinkList ReverseList( LinkList head )
{
// 将head 所指的单链表逆置
ListNode *p ,*q ;//设置两个临时指针变量
if( head->next && head->next->next)
file://当链表不是空表或单结点时
{
p=head->next;
q=p->next;
p -> next=NULL; file://将开始结点变成终端结点
while (q)
{ file://每次循环将后一个结点变成开始结点
p=q;
q=q->next ;
p->next = head-> next ;
head->next = p;
}
return head;
}
return head; file://直接返回head
}

LinkList MergeSort ( LinkList A , LinkList B )
{
// 归并两个递增有序表为一个递减有序表
ListNode *pa , *pb , *qa , *qb ;
pa=A;
pb=B ;
qa=A->next;
qb=B->next;
while ( qa && qb)
{
if ( qb->data < qa->data )
{
// 当B中的元素小于A中当前元素时，插入到它的前面
pb=qb;
qb=qb->next ;// 指向B中下一元素
pa->next=pb;
pb->next=qa;
pa=pb;

}

else if ( qb->data >= pa->data && qb->data <= qa->data)
{
// 当B中元素大于等于A中当前元素
// 且小于等于A中后一元素时，
// 将此元素插入到A的当前元素之后
pa=qa;
qa=qa->next; // 保存A的后一元素位置
pb=qb;
qb=qb->next; // 保存B的后一元素位置
pa->next=pb; file://插入元素
pb->next=qa;
}

else
{
// 如果B中元素总是更大,指针移向下一个A元素
pa=qa;
qa=qa->next;
}
}
if ( qb ) // 如果A表已到终端而B表还有结点未插入
{
// 将B表接到A表后面
pa->next=qb;
}
LinkList C=ReverseList ( A );// 调用前面2.8题所设计的逆置函数
return C; file://返回新的单链表C, 已是递减排列
}

void main()
{
LinkList A, B, C;
A=CreatList();
OutList (A);
B=CreatList();
OutList (B);
C=MergeSort (A ,B);
OutList (C);
}

以下是一位学友鲁周航提供的算法：
我的算法思路为：当A、B都不空时，各取A、B表中的第一个结点比较，哪个值小，就把它用头插法插入C表。（利用原来的头结点，始终是取第一个结点比较）继续取值比较。当A表为空，或B表为空，则把剩余结点用头插法插入C表。
void LinkList(Nodetype *A,Nodet

ype *B, Nodetype **C)
{//假设A和B已建立，C表的头结点已初始化
Nodetype *p, *q;
p=A->Next;
q=B->Next;
while(p&&q)//两表中都有数
{
if(p->DataData)//如A中的结点值大于B中结点值
{
A->Next=p->Next;//A指向A表的下一个结点
p->Next=C->Next;//把P的结点用头插法，插入C表。
C->Next=p;
p=A->Next;//P指向A表的第一个结点，继续比较
}
else
{
B->Next=q->Next;//算理同上面
q->Next=C->Next;
C->Next=q;
q=B->Next;
}
}
if(p)//如A表还有结点，则把剩余结点，用头插法插入C表
{
while(p)
{
A->Next=p->Next;
p->Next=C->Next;
C->Next=p;
p=A->Next;
}
}
else
if(q)//如B表还有结点，则把剩余结点，用头插法插入B表
{
while(q)
{
B->Next=q->Next;
q->Next=C->Next;
C->Next=q;
q=B->Next;
}
}
free(A);//释放原头结点空间
free(B);
}
你的算法要排表两次，第一次为插入，第二次为逆序。
6.写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
解：要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。
算法如下：
//设已建立三个带头结点的空循环链表A,B,C.
//以下是
void DivideList( LinkList L, LinkList A, LinkList B,
LinkList C)
{
ListNode *p=L->next, *q;
ListNode *a=A,
ListNode *b=B;
ListNode *c=C;
while ( p )
{
if ( p->data>='a' &&p->data<='z'|| p->data>='A'
&&p->data<='Z')
{
q=p; file://保存字母结点位置
p=p->next;//指向下一结点
a->next=q;//将字母结点链到A表中
q->next=A;// 形成循环链表
a=a->next; // 指向下一结点
}
else if( p->data>='0' && p->data<='9')
{ // 分出数字结点
q=p;
p=p->next;
b->next=q;
q->next=B;
b=b->next;
}
else
{ file://分出其他字符结点
q=p;
p=p->next;
c->next=q;
q->next=C;
c=c->next;
}
}
}//结束
以下学友X.P.的算法：
Void Creative(LinkList L, LinkList A, LinkList B,
LinkList C)
{
ListNode *p,*pa,*pb,*pc;
p=L->next;
pa=A;
pb=B;
pc=C;
while(p)
if((p->data>='a')&&(p->data<='z'))||((p->data>='A')&&(p->data<='Z'))
{
pa->next=p;
pa=p;
p=p->next;
pa->next=A->next;
}
else if(p->data>='0')&&(p->data<='9')
{
pb->next=p;
pb=p;
p=p->next;
pb->next=B->next;
}
else
{
pc->next=p;
pc=p;
p=p->next;
pc->next=C->next;
}
}
7.假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。
解：已知指向这个结点的指针

是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的，把这个结点删除就可以了。
算法如下：
void DeleteNode( ListNode *s)
{
file://删除单循环链表中指定结点的直接前趋结点
ListNode *p, *q;
p=s;
while( p->next!=s)
{
q=p;
p=p->next;
}
q->next=s; file://删除结点
free(p); file://释放空间
}

第三章(栈和队列)习题参考答案

一、填空题

二、选择题

三、算法分析题

四、算法设计题
6. 假设循环队列中只设rear和length
来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。
解：知道了尾指针和元素个数，当然就能知道队头元素了。算法如下：
int FullQueue( CirQueue *Q)
{
//判队满,队中元素个数等于空间大小
return Q->length==QueueSize;
}
void EnQueue( CirQueue *Q, Datatype x)
{
// 入队
if(FullQueue( Q))
Error("队已满，无法入队");
Q->Data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1
Q->length++;
}
Datatype DeQueue( CirQueue *Q)
{
//出队
if(Q->length==0)
Error("队已空，无元素可出队");
int tmpfront; //设一个临时队头指针
if(Q->rear > Q->length)//计算头指针位置
tmpfront=Q->rear - Q->length;
else
tmpfront=Q->rear + QueueSize - Q->length;
length--;
return Q->Data[tmpfront];
}
//如果需要验证上面的算法，则需定义好结点类型的队列结构，以相应的变量来表示尾指针和队列长度。

第四章(栈和队列)习题参考答案

一、填空题

二、选择题

三、算法分析题
1. 串常量是指在程序中只可引用但不可改变其值的串。
串变量是可以在运行中改变其值的。
2. 主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。
3.S是串名，用双引号（””）括起的字符序列是串的值。
四、算法设计题


第五章(栈和队列)习题参考答案

一、基础知识题
1.给出C语言的三维数组地址计算公式。
解： 这个公式书上就有，稍稍变化一下就是，因为C语言的数组下标下界是0，所以
Loc(Amnp)=Loc(A000)+((i*n*p)+k)*d
其中Amnp表示三维数组。Loc(A000)表示数组起始位置。i、j、k表示当前元素的下标,d表示每个元素所占单元数。
2. 设有三对角矩阵An*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=aij,求：
(1)用i , j 表示k的下标变换公式。
(2)用 k 表示 i,j 的下标变换公式。[/B]
(1)解： 要求i,j 到k的下标变换公式，就是要知道在k之前已有几个非零元素，这些非零元素的个数就是k的值，一个元素所在行为i,所在列为j,则在其前面已有的非零元素

个数为：(i*3-1)+j-(i+1)。其中 (i*3-1)是这个元素前面所有行的非零元素个数，j-(i+1)是它所在列前面的非零元素个数化简可得：
k=2i+j; // c下标是从0开始的。
(2) 解： 因为K和i,j是一一对应的关系，因此这也不难算出：
i=(k+1)/3 //k+1表示当前元素前有几个非零元素,被3整除就得到行号；
j=(k+1)%3+(k+1)/3-1；
//k+1除以3的余数就是表示当前行中第几个非零元素，加上前面的0元素所点列数就是当前列。
3. 设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节?
A的终端结点a47的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何?
解： 首先，这首题有一个错误需改正一下,A的终端结点应该是a45而不是a47,这是很明显的，要不就是二维数组是A5*8才对。这里按5*6数组计算。因含5*6=30个元素，因此A共占30*4=120个字节。
a45的起始地址为：
Loc(a45)=Loc(a00)+(i*n+j)*d=1000+(4*6+5)*4=1116

按行优先顺序排列时，
a25=1000+(2*6+5)*4=1068

按列优先顺序排列时：(二维数组可用行列下标互换来计算)
a25=1000+(5*5+2)*4=1108

4. 特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么?
答：后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。
5.数组 、广义表与线性表之间有什么关系？
解：线性表的元素仅限于原子项，是一个数或结构，而广义表则无此限制，它的元素可以是原子项，也可以是一个广义表。二者是包含与被包含的关系，广义表则是线性表的推广,线性表是广义表的一个特例。
6. 画出下列广义表的图形表示：
(1) A(a,B(b,d),C(e,B(b,d),L(f,g))) (2) A(a,B(b,A))
解：(1)这是一个再入表。(2)则是一个递归表。
7. 设广义表L=((),()),试问head(L),tail(L),L的长度，深度各为多少?
解：head(L)=() tail(L)=(), 广义表L的长度为2(它包含两个空表)。它的深度是2(展开后括号层数为2)。
8.
9. 求下列广义表运算的结果：
(1)head ((p,h,w)); (2)tail((b,k,p,h)); (3) head
(((a,b),(c,d)));
(4)tail(((a,b),(c,d))); (5)head(tail(((a,b),(c,d))));
(6)tail(head(((a,b),(c,d)))).
解：
(1)head ((p,h,w))=p
(2)tail((b,k,p,h))=(k,p,h)
(3) head (((a,b),(c,d)))= (a,b)
(4)tail(((a,b),(c,d)))=((c,d))
(5)head(tail(((a,b),(c,d))))=(c,d)
(6)tail(head(((a,b),(c,d))))=(b)
注意：最外层括号是函数括号，然后一层括号表示一个广义表。如第（1）个广义表A=(p,h,w)
在此表中取头元素则得p.

二、算法设计题
1.
2. 当稀疏矩阵

A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。
解：这个算法有点繁，要考虑到两个稀疏矩阵的非零元素不是一一对应的，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A中的三元组，若有，则加入C，同时，这个元素如果在B中也有，则加上B的这个元素值，否则这个值就不变;如果A中没有，则找B，有则插入C，无则查找下一个矩阵元素。
算法及测试程序如下：
#include
#define MaxSize 10 //用户自定义
typedef int Datatype; //用户自定义
typedef struct
{ //定义三元组
int i,j;
Datatype v;
}TriTupleNode;
typedef struct
{ //定义三元组表
TriTupleNode data[MaxSize];
int m,n,t;//矩阵行，列及三元组表长度
}TriTupleTable;
void showMatrix(TriTupleTable *a)
{ //输出稀疏矩阵
int p,q;
int t=0;
for(p=0;pm;p++)
{
for(q=0;qn;q++)
{
if(a->data[t].i==p&&a->data[t].j==q)
{
printf("%d ",a->data[t].v);
t++;
}
else printf("0 ");
}//endfor
printf("\n");
}
}

///////////////////以下为矩阵加算法 ////////////

void AddTriTuple( TriTupleTable *A, TriTupleTable *B,
TriTupleTable *C)
{ //三元组表表示的矩阵A,B相加
int p,q,k,l;
C->m=A->m;//矩阵行数
C->n=A->n;//矩阵列数
C->t=0; //三元组表长度
C->data[C->t].v=0; //三元组元素初值
k=0; l=0;
for(p=0;pm;p++) //行
for(q=0;qn;q++) //列
if(A->data[k].i==p&&A->data[k].j==q)
{
//如果该元素在A表中有
C->data[C->t].v=0;//初始化三元组值
C->data[C->t].i=p;
C->data[C->t].j=q;
C->data[C->t].v+=A->data[k].v;
if(B->data[l].i==p&&B->data[l].j==q)
{ //同时在B中也有
C->data[C->t].v+=B->data[l].v;
l++; //指向B表下一元素
}
k++;C->t++;//指向A表下一元素，C表长增1
}
else if(B->data[l].i==p&&B->data[l].j==q)
{
//若A中无，而B中有该元素
C->data[C->t].v=0;//初始化三元组值
C->data[C->t].i=p;
C->data[C->t].j=q;
C->data[C->t].v+=B->data[l].v;
l++;C->t++;//指向B表下一元素，C表长增1
}//if..else为一个语句
}//end

//以下为测试程序
void main()
{
//主程序
TriTupleTable A={1,3,4,2,2,4,2,4,3,3,3,9};
A.m=5;
A.n=5;
A.t=4;
TriTupleTable B={2,3,4,2,4,5};
B.m=5;
B.n=5;
B.t=2;
TriTupleTable C;
printf("The Matrix A:\n\n");
showMatrix(&A);
printf("The Matrix B:\n\n");
showMatrix(&B);
AddTriTuple(&A,&B,&C);
printf("The Matrix C:\n\n");
showMatrix(&C);
}



第六章(树和二叉树)习题参考答案

一、填空题

二、选择题

三、应用题
1. 试找出分别满足下面条件的所有二叉树：
(1)前序序列和中序序列相同； (2)中序序列和后序序列相同；
(3)前序序列和后序序列相同； (4)前序、中序、后序序列均相同。
答：空树满足所有条件。非空树如下

：
(1) 前序序列和中序序列相同的二叉树是：没有左子树的二叉树(右单支树)。
(2) 中序序列和后序序列相同的二叉树是：没有右子树的二叉树(左单支树)。
(3) 前序序列和后序序列相同的二叉树是：只有根的二叉树。
(4) 前序、中序、后序序列均相同的二叉树：只有根结点的二叉树。
2. 若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。
(1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。
(1)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。
(1)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。
解：
(1)已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点...以此类推可画出所有结点：
○A
/ \
○B ○C
/ / \
○D ○E○F
/ \ /
○G ○H ○I
(2)以同样的方法可画出该二叉树：

○A
/ \
○B ○F
\ \
○C ○G
/ \ /
D○ E○○H
(3)这两棵不同的二叉树为：
○A ○A
/ \
○B ○B
3. 以二叉链表为存储结构， 写一算法交换各结点的左右子树。
要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。
#include
#include "bintree.h"
void ChangeBinTree(BinTree *T)
{ //交换子树
if(*T)
{ //这里以指针为参数使得交换在实参的结点上进行
//后序遍历
BinTree temp;
ChangeBinTree(&(*T)->lchild);
ChangeBinTree(&(*T)->rchild);
temp=(*T)->lchild;
(*T)->lchild=(*T)->rchild;
(*T)->rchild=temp;
}
}
void PrintNode(BinTree T)
{ //以前序序列打印结点数据
if(T)
{
printf("%c",T->data);
PrintNode(T->lchild);
PrintNode(T->rchild);
}
}
void main()
{ //测试程序
BinTree root;
CreatBinTree(&root);//建立二叉链表
PrintNode(root); //输出原表
printf("\n");
ChangeBinTree(&root);//交换子树
PrintNode(root); //输出新表
printf("\n");
}
//可输入"abc d ef g "来测试(注意空格)，看看对不对?
4. 以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法，所谓宽度是指二叉树的各层上，具有结点数最多的那一层上的结点总数。
解：要想求出二叉树的高度，可以采用前序遍历，设一个个记录高度的变量h
,在访问结点时查询该结点是否有孩子，有则高度加1，其中根结点比特殊，

自身算一层。
要求二叉树的宽度的话，则可根据树的高度设置一个数组，在访问结点时计算该结点下一层的孩子数并存入相应数组元素中，遍历左子树后向上返回一层计算右子树的宽度，并取出最大的一个数组元素作为树的宽度。
#include
#include "bintree.h"
#define M 10 //假设二叉树最多的层数
int Height(BinTree T)//求树的深度
{ //求深度算法由阮允准更正，在此深表感谢。
int lhigh,rhigh,high=0;
if(T!=NULL)
{
lhigh=Height(T->lchild);//左子树高度
rhigh=Height(T->rchild);//右子树高度

high=(lhigh>rhigh?lhigh:rhigh)+1;//树的高度等于左子树、右子树之间的大者加上根结点1。

}
return high;
}

int Width(BinTree T)
{
int static n[M];//向量存放各层结点数
int static i=1;
int static max=0;//最大宽度
if(T)
{
if(i==1) //若是访问根结点
{
n++; //第1层加1
i++; //到第2层
if(T->lchild)//若有左孩子则该层加1
n++;
if(T->rchild)//若有右孩子则该层加1
n++;
}
else
{ //访问子树结点
i++; //下一层结点数
if(T->lchild)
n++;
if(T->rchild)
n++;
}
if(maxWidth(T->lchild);//遍历左子树
i--; //往上退一层
Width(T->rchild);//遍历右子树
}
return max;
}//算法结束

void main()
{ //测试程序
BinTree root;
CreatBinTree (&root);
printf("\nHeight of BinTree:%d",Height(root));
printf("\nWidth of BinTree:%d",Width(root));
}
5. 线索链表作为存储结构。分别写出在前序线索树中查找给定结点*p的前序后继，以及在后序线索树中查找
*p的后序前趋的算法。
解，单是算法如下：只有这么几行。
//-----------------------------------------------
BinThrNode * SearchPostInPre(BinThrNode *p)
{
//查找结点*p的前序后继
if(p)
{
if(p->ltag==Link)return p->lchild;
else return p->rchild;
//右孩子要么本身就是前序后继，要么是线索指向前序后继
}
}
BinThrNode *SearchPreInPost(BinThrNode *p)
{
//查找*p结点的后序前趋
if(p)
{
if(p->rtag==Link)return p->rchild;
else return p->lchild;
//左孩子要么本身就是后序前趋，要么是线索指向后序前趋
}
}
6.


第七章(图)习题参考答案

一、名词解释题
1. 有向图
答：在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。
2.无向图
答：在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。
3.最小生成树
答：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。
二、判断题

三、填空题

四、选择题

五、综合题


第八章(查找)习题

参考答案

一、填空题

二、选择题

三、简答题

四、算法设计题



第九章(排序)习题参考答案

一、单项选择题

二、填空题

三、应用题
1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。
(1) 直接插入排序 (2)希尔排序 (3)冒泡排序 (4)快速排序
(5) 直接选择排序 (6) 堆排序 (7) 归并排序 (8)基数排序
上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。
答：(1)直接插入排序:(方括号表示无序区)
初始态: 265 301 751 129 937 863 742 694 076 438
第一趟：265 301 [751 129 937 863 742 694 076 438]
第二趟：265 301 751 [129 937 863 742 694 076 438]
第三趟：129 265 301 751 [937 863 742 694 076 438]
第四趟：129 265 301 751 937 [863 742 694 076 438]
第五趟：129 265 301 751 863 937 [742 694 076 438]
第六趟：129 265 301 742 751 863 937 [694 076 438]
第七趟：129 265 301 694 742 751 863 937 [076 438]
第八趟：076 129 265 301 694 742 751 863 937 [438]
第九趟：076 129 265 301 438 694 742 751 863 937

(2)希尔排序(增量为5，3，1)
初始态: 265 301 751 129 937 863 742 694 076 438
第一趟：265 301 694 076 438 863 742 751 129 937
第二趟：076 301 129 265 438 694 742 751 863 937
第三趟：076 129 265 301 438 694 742 751 863 937

(3)冒泡排序(方括号为无序区)
初始态 [265 301 751 129 937 863 742 694 076 438]
第一趟： 076 [265 301 751 129 937 863 742 694 438]
第二趟： 076 129 [265 301 751 438 937 863 742 694]
第三趟： 076 129 265 [301 438 694 751 937 863 742]
第四趟： 076 129 265 301 [438 694 742 751 937 863]
第五趟： 076 129 265 301 438 [694 742 751 863 937]
第六趟： 076 129 265 301 438 694 742 751 863 937

(4)快速排序：（方括号表示无序区，层表示对应的递归树的层数）
初始态： [265 301 751 129 937 863 742 694 076 438]
第二层： [076 129] 265 [751 937 863 742 694 301 438]
第三层： 076 [129] 265 [438 301 694 742] 751 [863 937]
第四层： 076 129 265 [301] 438 [694 742] 751 863 [937]
第五层： 076 129 265 301 438 694 [742] 751 863 937
第六层： 076 129 265 301 438 694 742 751 863 937

(5)直接选择排序：(方括号为无序区)
初始态 [265 301 751 129 937 863 742 694 076 438]
第一趟： 076 [301 751 129 937 863 742 694 265 438]
第二趟： 076 129 [751 301 937 863 742 694 265 438]
第三趟： 076 129 265[ 301 937 863 742 694 751 438]
第四趟： 076 129 265 301 [937 863 742 694 751 438]
第五趟： 076 129 265 301 438 [863 742 694 751 937]
第六趟： 076 129 265 301 438 694 [742 751 863 937]
第七趟： 076 129 265 301 438 694 742 [751 863 937]
第八趟： 076 129 265 301 438 694 742 751 [937 863]
第九趟： 076 129 265 301 438 694 742 751 863 937
(6)堆排序：

（通过画二叉树可以一步步得出排序结果）
初始态 [265 301 751 129 937 863 742 694 076 438]
建立初始堆： [937 694 863 265 438 751 742 129 075 301]
第一次排序重建堆：[863 694 751 765 438 301 742 129 075] 937
第二次排序重建堆：[751 694 742 265 438 301 075 129] 863 937
第三次排序重建堆：[742 694 301 265 438 129 075] 751 863 937
第四次排序重建堆：[694 438 301 265 075 129] 742 751 863 937
第五次排序重建堆：[438 265 301 129 075] 694 742 751 863 937
第六次排序重建堆：[301 265 075 129] 438 694 742 751 863 937
第七次排序重建堆：[265 129 075] 301 438 694 742 751 863 937
第八次排序重建堆：[129 075]265 301 438 694 742 751 863 937
第九次排序重建堆：075 129 265 301 438 694 742 751 863 937

(7)归并排序（为了表示方便，采用自底向上的归并，方括号为有序区）
初始态：[265] [301] [751] [129] [937] [863] [742] [694]
[076] [438]
第一趟：[265 301] [129 751] [863 937] [694 742] [076 438]
第二趟：[129 265 301 751] [694 742 863 937] [076 438]
第三趟：[129 265 301 694 742 751 863 937] [076 438]
第四趟：[076 129 265 301 438 694 742 751 863 937]

(8)基数排序（方括号内表示一个箱子共有10个箱子，箱号从0到9）
初始态 ：265 301 751 129 937 863 742 694 076 438
第一趟：[] [301 751] [742] [863] [694] [265] [076] [937]
[438] [129]
第二趟：[301] [] [129] [937 438] [742] [751] [863 265] [076]
[] [694]
第三趟：[075] [129] [265] [301] [438] [] [694] [742 751]
[863] [937]
在上面的排序方法中，直接插入排序、冒泡排序、归并排序和基数排序是稳定的，其他排序算法均是不稳定的，现举实例如下：以带*号的表示区别。
希尔排序：[8,1,10,5,6,*8]
快速排序：[2,*2,1]
直接选择排序：[2,*2,1]
堆排序：[2,*2,1]
2. 判别下列序列是否为堆(小根堆或大根堆)，若不是，则将其调整为堆：
(1) (100,86,48,73,35,39,42,57,66,21);
(2) (12,70,33,65,24,56,48,92,86,33);
(3) (103,97,56,38,66,23,42,12,30,52,06,20);
(4) (05,56,20,23,40,38,29,61,35,76,28,100).
答：堆的性质是：任一非叶结点上的关键字均不大于(或不小于)其孩子结点上的关键字。据此我们可以通过画二叉树来进行判断和调整：
(1) 此序列是大根堆。
(2) 此序列不是堆，经调整后成为小根堆：
(12，24，33，65，33，56，48，92，86，70)
(3) 此序列是一大根堆。
(4) 此序列不是堆，经调整后成为小根堆：（05，23，20，35，28，38，29，61，56，76，40，100）

四、算法设计题
1.
2.
3. 以单链表为存储结构，写一个直接选择排序算法。
答：
　#define int KeyType //定义KeyType 为int型
　typedef struct node{
KeyType key; //关键字域
OtherInfoType info; //其它信息域，
struct node * next; //链表中指针域
}RecNode; //记录结点类型

　typed

ef RecNode * LinkList ; //单链表用LinkList表示

　void selectsort(linklist head)
{RecNode *p,*q,*s;
if(head->next)&&(head->next->next)
{p=head->next;//p指向当前已排好序最大元素的前趋
while (p->next)
{q=p->next;s=p;
while(q)
{if (q->keykey) s=q;
q=q->next;
}//endwhile
交换s结点和p结点的数据；
p=p->next;
}//endwhile
}//endif
}//endsort
4.写一个堆删除算法：HeapDelete(R,i),将R[i]从堆中删去，并分析算法时间，提示：先将R[i]和堆中最后一个元素交换，并将堆长度减1，然后从位置i开始向下调整，使其满足堆性质。
答：void HeapDelete(seqlist *R,int i)
{//原有堆元素在R->data[1]~R->data[R->length],
//将R->data[i]删除，即将R->data[R->length]放入R->data[i]中后，
//将R->length减1，再进行堆的调整，
//以R->data[0]为辅助空间，调整为堆(此处设为大根堆)
int large;//large指向调整结点的左右孩子中关键字较大者
int low,high;//low和high分别指向待调整堆的第一个和最后一个记录
int j;
if (i>R->length)
Error("have no such node");
R->data[i].key=R->data[R->length].key;
R->length--；R->data[R->length].key=key;//插入新的记录
for(j=i/2;j>0;j--)//建堆
{
low=j;high=R->length;
R->data[0].key=R->data[low].key;//R->data[low]是当前调整的结点
for(large=2*low;large<=high;large*=2){
//若large>high，则表示R->data[low]是叶子，调整结束；
//否则令large指向R->data[low]的左孩子
if(largedata[large].keydata[large+1].key)
large++;//若R->data[low]的右孩子存在
//且关键字大于左兄弟，则令large指向它
if (R->data[0].keydata[large].key)
{ R->data[low].key= R->data[large].key;
low=large;//令low指向新的调整结点
}
else break;//当前调整结点不小于其孩子结点的关键字，结束调整
}//endfor
R->data[low].key=R->data[0].key;//将被调整结点放入最终的位置上
}//end of for
}end of HeapDelete
5.已知两个单链表中的元素递增有序，试写一算法将这两个有序表归并成一个递增有序的单链表。算法应利用原有的链表结点空间。
答:typedef struct node{
KeyType key; //关键字域
OtherInfoType info; //其它信息域，
struct node * next; //链表

中指针域
}RecNode; //记录结点类型

　typedef RecNode * LinkList ; //单链表用LinkList表示

　void mergesort(LinkList la,LinkList lb,LinkList lc)
{RecNode *p,*q,*s,*r;
lc=la;
p=la;//p是la表扫描指针，指向待比较结点的前一位置
q=lb->next;//q是lb表扫描指针，指向比较的结点
while(p->next)&&(q)
if (p->next->key<=q->key)
p=p->next;
else {s=q;q=q->next;
s->next=p->next;p->next=s;//将s结点插入到p结点后
p=s;}
if (!p->next) p->next=q;
free(lb);
}