数据结构答案 黄刘生

本文格式为Word版，下载可任意编辑——数据结构答案黄刘生第一章绪论

1.1简述以下概念：数据、数据元素、数据类型、数据结构、规律结构、存储结构、线性结构、非线性结构。

●数据：指能够被计算机识别、存储和加工处理的信息载体。

●数据元素：就是数据的基本单位，在某些状况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。

●数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。寻常数据类型可以看作是程序设计语言中已实现的数据结构。

●数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的规律结构、存储结构和数据的运算。●规律结构：指数据元素之间的规律关系。

●存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.

●线性结构：数据规律结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。

●非线性结构：数据规律结构中的另一大类，它的规律特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。1.2试举一个数据结构的例子、表达其规律结构、存储结构、运算三个方面的内容。答：

例如有一张学生体检状况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的规律结构是线性结构。这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢?即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢?这就是存储结构的问题。在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。

1.3常用的存储表示方法有哪几种?答：

常用的存储表示方法有四种:

●顺序存储方法：它是把规律上相邻的结点存储在物理位置相邻的存储单元里，结点间的规律关系由存储单元的邻接关系来表达。由此得到的存储表示称为顺序存储结构，寻常借助程序语言的数组描述。

●链接存储方法：它不要求规律上相邻的结点在物理位置上亦相邻，结点间的规律关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,寻常借助于程序语言的指针类型描述。

●索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点

的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（DenseIndex）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。

●散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址1.4设三个函数f,g,h分别为f(n)=100n3+n2+1000,g(n)=25n3+5000n2,h(n)=n1.5+5000nlgn请判断以下关系是否成立：(1)f(n)=O(g(n))(2)g(n)=O(f(n))(3)h(n)=O(n1.5)(4)h(n)=O(nlgn)分析：

数学符号\的严格的数学定义：

若T（n）和f（n）是定义在正整数集合上的两个函数，则T（n）=O（f（n））表示存在正的常数C和n0，使得当n≥n0时都满足0≤T（n）≤C?f（n）。通俗地说，就是当n→∞时，f(n)的函数值增长速度与T（n)的增长速度同阶。一般，一个函数的增长速度与该函数的最高次阶同阶。即：

O(f(n))=n3O(g(n))=n3O(h(n))=n1.5所以答案为：答：

●（1）成立。●（2）成立。●（3）成立。●（4）不成立。

1.5设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大?分析：

要使前者快于后者，即前者的时间消耗低于后者，即：100n2j)j++;elsei++;}分析：

通过分析以上程序段，可将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)0)if(x>100)

{x=x-10;y--;}elsex++;分析：

x=91;//1y=100;//1

while(y>0)//1101if(x>100)//1100{x=x-10;//100y--;//100}else

x++;//1000

以上程序段右侧列出了执行次数。该程序段的执行时间为：T(n)=O(1)

1.7算法的时间繁杂度仅与问题的规模相关吗?答：

算法的时间繁杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的状况下，其时间繁杂度就是只与求解问题的规模相关的。我们在探讨时间繁杂度时，一般就是以最坏状况下的时间繁杂度为准的。1.8按增长率由小至大的顺序排列以下各函数：

2100,(3/2)n，(2/3)n，nn,n0.5,n!，2n，lgn,nlgn,n(3/2)答：

常见的时间繁杂度按数量级递增排列,依次为:常数阶0(1)、对数阶

0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。先将题中的函数分成如下几类：常数阶：2100对数阶：lgn

K次方阶：n0.5、n(3/2)

指数阶(按指数由小到大排)：nlgn、(3/2)n、2n、n!、nn注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。根据以上分析按增长率由小至大的顺序可排列如下：

(2/3)nnext;P=L;

while(P->next)P=P->next;P->next=Q;Q->next=NULL;}

returnL;}//Demo答：

该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的其次个结点成为新的开始结点，返回新链表的头指针。关闭

2.7设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入和删除算法：InsertList和DeleteList.解：算法如下:

#defineListSize100//假定表空间大小为100

typedefintDataType;//假定DataType的类型为int型typedefstruct{

DataTypedata[ListSize];//向量data用于存放表结点intlength;//当前的表长度}Seqlist;

//以上为定义表结构

voidInsertList(Seqlist*L,Datatypex,inti){

//将新结点x插入L所指的顺序表的第i个结点ai的位置上，即插入的合法位置为：0lengthintj;

if(iL->length)

Error(\非法位置，退出，该函数定义见教材P7.if(L->length>=ListSize)Error(“overflow\

for(j=L->length-1;j>=i;j--)L->data[j+1]=L->data[j];L->data[i]=x;L->length++;}

voidDeleteList(Seqlist*L,inti)

{//从L所指的顺序表中删除第i个结点ai,合法的删除位置为0length-1intj;

if(i=L->length)Error(\

for(j=i;jlength;j++)

L->data[j]=L->data[j+1];//结点前移L->length--;//表长减小}关闭

2.8试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓\就地\指辅助空间应为O(1)。答：

1.顺序表：

要将该表逆置，可以将表中的开始结点与终端结点互换，其次个结点与倒数其次个结点互换，如此反复，就可将整个表逆置了。算法如下：//顺序表结构定义同上题

voidReverseList(Seqlist*L){

DataTypetemp;//设置临时空间用于存放datainti;

for(i=0;ilength/2;i++)//L->length/2为整除运算{temp=L->data;//交换数据

L->data[i]=L->data[L->length-1-i];L->data[L->length-1-i]=temp;}}

2.链表：分析：

可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体状况入下：

(1)当链表为空表或只有一个结点时，该链表的逆置链表与原表一致。(2)当链表含2个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的：

结点结构定义如下：

typedefcharDataType;//假设结点的数据域类型的字符typedefstructnode{//结点类型定义DataTypedata;//结点的数据域structnode*next;//结点的指针域}ListNode;

typedefListNode*LinkList;

ListNode*p;LinkListhead;

LinkListReverseList(LinkListhead){//将head所指的单链表(带头结点)逆置ListNode*p,*q;//设置两个临时指针变量if(head->nextq=p->next;

p->next=NULL;//将开始结点变成终端结点while(q)

{//每次循环将后一个结点变成开始结点p=q;

q=q->next;

p->next=head->next;head->next=p;}

returnhead;}

returnhead;//如是空表或单结点表，直接返回head}关闭

2.9设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。答：

因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻觅到第一个小于或等于x的元素位置i后插入该位置即可。在寻觅过程中，由于大于x的元素都应放在x之后，所以可边寻觅，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。算法如下：

//顺序表存储结构如题2.7

voidInsertIncreaseList(Seqlist*L,Datatypex){

inti;

if(L->length>=ListSize)Error(“overflow\

for(i=L->length;i>0i--)L->data[i]=L->data[i];//比较并移动元素L->data[i]=x;L->length++;}关闭

2.10设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。答：

与上题相类似，只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。（边寻觅，边移动）算法如下：voidInsertDecreaseList(Seqlist*L,Datatypex){

inti;

if(L->length>=ListSize)Error(“overflow\

for(i=L->length;i>0i--)L->data[i]=L->data[i];//比较并移动元素L->data[i]=x;L->length++;}关闭

2.11写一算法在单链表上实现线性表的ListLength(L)运算。解：

由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下：

intListLength(LinkListL){

intlen=0;ListNode*p;

p=L;//设该表有头结点while(p->next){

p=p->next;len++;}

returnlen;}关闭

2.12已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间繁杂度。解：

分析：

由于要进行的是两单链表的连接，所以应找到放在前面的那张表的表尾结点，再将后表的开始结点链接到前表的终端结点后即可。该算法的主要时间消耗是用在寻觅第一张表的终端尾结点上。这两张单链表的连接顺序无要求，并且已知两表的表长，则为了提高算法效率，可选表长小的单链表在前的方式连接。具体算法如下：

LinkListLink(LinkListL1,LinkListL2，intm,intn){//将两个单链表连接在一起ListNode*p,*q,*s;

//s指向短表的头结点,q指向长表的开始结点，回收长表头结点空间if(mnext;free(L2);}else{s=L2;q=L1->next;free(L1);}p=s;

while(p->next)p=p->next;//查找短表终端结点p->next=q;//将长表的开始结点链接在短表终端结点后returns;}

本算法的主要操作时间花费在查找短表的终端结点上，所以本算的法时间繁杂度为：

O(min(m,n))关闭

2.13设A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间繁杂度。解：

根据已知条件，A和B是两个递增有序表，所以可以先取A表的表头建立空的C表。然后同时扫描A表和B表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C表中。如此反复，直到A表或B表为空。最终将不为空的A表或B表中的结点依次摘下并作为开始结点插入C表中。这时，得到的C表就是由A表和B表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(1)。算法如下：

LinkListMergeSort(LinkListA,LinkListB)

{//归并两个带头结点的递增有序表为一个带头结点递减有序表ListNode*pa,*pb,*q,*C;pa=A->next;//pa指向A表开始结点

C=A;C->next=NULL;//取A表的表头建立空的C表pb=B->next;//pb指向B表开始结点free(B);//回收B表的头结点空间while(papa=pa->next;}else

{//当B中的元素大于A中当前元素时，将pb表的开始结点摘下

q=pb;pb=pb->next;}

q->next=C->next;C->next=q;//将摘下的结点q作为开始结点插入C表

}

//若pa表非空，则处理pa表while(pa){

q=pa;pa=pa->next;

q->next=C->next;C->next=q;}//若pb表非空，则处理pb表while(pb){

q=pb;pa=pb->next;

q->next=C->next;C->next=q;}return(C);}

该算法的时间繁杂度分析如下：

算法中有三个while循环，其中其次个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A表和B表中的每个结点都被处理了一遍。所以若A表和B表的表长分别是m和n，则该算法的时间繁杂度O(m+n)关闭

2.14已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min和max是两个给定的参数。请分析你的算法的时间繁杂度。解：

要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和min比较，然后删除这个结点。由于为已知其是有序链表，则介于min和max之间的结点必为连续的一段元素序列。所以我们只要先找到所有大于min结点中的最小结点的直接前趋结点*p后，依次删除小于max的结点，直到第一个大于等于max结点*q位置，然后将*p结点的直接后继指针指向*q结点。算法如下：

voidDeleteList(LinkListL,DataTypemin,DataTypemax){

ListNode*p,*q,*s;p=L;

while(p->next

q=p->next;//p指向第一个不大于min结点的直接前趋，q指向第一个大于min的结点

while(qq=q->next;

free(s);//删除结点，释放空间}

{x=DeQueue(Q);Push(}while(!StackEmpty(EnQueue(Q,x);}}//Demo3

(5)CirQueueQ1,Q2;//设DataType为int型intx,i,n=0;

...//设Q1已有内容，Q2已初始化过while(!QueueEmpty(EnQueue(n++;}for(i=0;iTop=-1;//其实只是将栈置空}

由于要置空的是栈S，假使不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开拓另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。关闭

3.8利用栈的基本操作，写一个返回S中结点个数的算法intStackSize(SeqStackS),并说明S为何不作为指针参数?解：

算法如下：

intStackSize(SeqStackS){//计算栈中结点个数intn=0;

if(!EmptyStack(n++;}

returnn;}

上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最终返回元素个数。

关闭

3.9设计算法判断一个算术表达式的圆括号是否正确配对。(提醒：对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。解：

根据提醒，可以设计算法如下：intPairBracket(char*SR)

{//检查表达式ST中括号是否配对inti;

SeqStackS;//定义一个栈InitStack(

for(i=0;itop0=-1;

S->top1=StackSize;//这里的top2也指出了向量空间，但由于是作为

栈底，因此不会出错}

intEmptyStack(DblStack*S,inti){//判栈空(栈号i)

return(i==0}

intFullStack(DblStack*S){//判栈满,满时确定两头相遇

return(S->top0==S-top1-1);}

voidPush(DblStack*S,inti,DataTypex){//进栈(栈号i)

if(FullStack(S))

Error(\上溢、退出运行

if(i==0)S->Data[++S->top0]=x;//栈0入栈if(i==1)S->Data[--S->top1]=x;//栈1入栈}

DataTypePop(DblStack*S,inti){//出栈(栈号i)

if(EmptyStack(S,i))

Error(\下溢退出if(i==0)

return(S->Data[S->top0--]);//返回栈顶元素，指针值减1if(i==1)

return(S->Data[S->top1++]);//由于这个栈是以另一端为底的，所以指针值加1。}关闭

3.11Ackerman函数定义如下：请写出递归算法。┌n+1当m=0时

AKM(m,n)=│AKM(m-1,1)当m≠0，n=0时

└AKM(m-1,AKM(m,n-1))当m≠0,n≠0时

解：

算法如下

intAKM(intm,intn){

if(m==0)returnn+1;

if(m0

if(m0}关闭

3.12用其次种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。解：

算法设计如下://循环队列的定义

#defineQueueSize100

typedefcharDatatype;//设元素的类型为char型typedefstruct{intfront;intrear;

DataTypeData[QueueSize];}CirQueue;(1)置空队

voidInitQueue(CirQueue*Q){//置空队

Q->front=Q->rear=0;}

(2)判队空

intEmptyQueue(CirQueue*Q){//判队空

returnQ->front==Q->rear;}

(3)判队满

intFullQueue(CirQueue*Q)

{//判队满//假使尾指针加1后等于头指针，则认为满return(Q->rear+1)%QueueSize==Q->front;}(4)出队

DataTypeDeQueue(CirQueue*Q){//出队

DataTypetemp;if(EmptyQueue(Q))

Error(\队已空，无元素可以出队\temp=Q->Data[Q->front];//保存元素值

Q->front=(Q->front+1)%QueueSize;//循环意义上的加1returntemp;//返回元素值}(5)入队

voidEnQueue(CirQueue*Q,DataTypex){//入队

if(FullQueue(Q))

Error(\队已满，不可以入队\Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;//rear指向下一个空元素位置}

(6)取队头元素

DataTypeFrontQueue(CirQueue*Q){//取队头元素

if(EmptyQueue(Q))

Error(\队空，无元素可取\returnQ->Data[Q->front];}关闭

3.13假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。解：

算法如下：

//先定义链队结构:

typedefstructqueuenode{Datatypedata;

structqueuenode*next;

}QueueNode;//以上是结点类型的定义typedefstruct{

queuenode*rear;

}LinkQueue;//只设一个指向队尾元素的指针(1)置空队

voidInitQueue(LinkQueue*Q)

{//置空队：就是使头结点成为队尾元素QueueNode*s;

Q->rear=Q->rear->next;//将队尾指针指向头结点while(Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队{s=Q->rear->next;

Q->rear->next=s->next;free(s);

}//回收结点空间}

(2)判队空

intEmptyQueue(LinkQueue*Q){//判队空

//当头结点的next指针指向自己时为空队

returnQ->rear->next->next==Q->rear->next;}(3)入队

voidEnQueue(LinkQueue*Q,Datatypex){//入队

//也就是在尾结点处插入元素

QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申请新结点

p->data=x;p->next=Q->rear->next;//初始化新结点并链入Q-rear->next=p;

Q->rear=p;//将尾指针移至新结点}(4)出队

DatatypeDeQueue(LinkQueue*Q){//出队,把头结点之后的元素摘下Datatypet;QueueNode*p;

if(EmptyQueue(Q))

Error(\

p=Q->rear->next->next;//p指向将要摘下的结点x=p->data;//保存结点中数据if(p==Q->rear)

{//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点

Q->rear=Q->rear->next;Q->rear->next=p->next;}else

Q->rear->next->next=p->next;//摘下结点pfree(p);//释放被删结点returnx;}关闭

3.14对于循环向量中的循环队列，写出求队列长度的公式。解：

公式如下(设采用其次种方法，front指向真正的队首元素，rear指向真正队尾后一位置，向量空间大小：QueueSize

Queuelen=(QueueSize+rear-front)%QueueSize关闭

3.15假设循环队列中只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。解：

根据题意，可定义该循环队列的存储结构：#defineQueueSize100

typedefcharDatatype;//设元素的类型为char型typedefstruct{intquelen;intrear;

DatatypeData[QueueSize];

}CirQueue;CirQueue*Q;

循环队列的队满条件是：Q->quelen==QueueSize

知道了尾指针和元素个数，当然就能计算出队头元素的位置。算法如下：(1)判断队满

intFullQueue(CirQueue*Q)

{//判队满,队中元素个数等于空间大小returnQ->quelen==QueueSize;}(2)入队

voidEnQueue(CirQueue*Q,Datatypex){//入队

if(FullQueue(Q))

Error(\队已满，无法入队\Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1Q->quelen++;}(3)出队

DatatypeDeQueue(CirQueue*Q){//出队

if(Q->quelen==0)

Error(\队已空，无元素可出队\inttmpfront;//设一个临时队头指针

tmpfront=(QueueSize+Q->rear-Q->quelen+1)%QueueSize;//计算头指针位置

Q->quelen--;

returnQ->Data[tmpfront];}第四章串

4.1简述以下每对术语的区别：

空串和空白串；串常量和串变量；主串和子串；静态分派的顺序串和动态分派的顺序串；目标串和模式串；有效位移和无效位移。答：

●空串是指不包含任何字符的串，它的长度为零。

空白串是指包含一个或多个空格的串，空格也是字符。●串常量是指在程序中只可引用但不可改变其值的串。串变量是可以在运行中改变其值的。

●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。

●静态分派的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。

动态分派的顺序串是在编译时不分派串值空间，在运行过程中用malloc和

free等函数根据需要动态地分派和释放字符数组的空间(这个空间长度由分派时确定，也是顺序存储空间)。

●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后假使模式串与目标中相应的字符一致，则这次位移就是有效位移(也就是此后位置开始的匹配成功)，反之，若有不一致的字符存在，则此次位移就是无效位移(也就是此后位置开始的匹配失败)。

关闭

4.2假设有如下的串说明：

chars1[30]=\(1)在执行如下的每个语句后p的值是什么?

p=stchr(s1,'t');p=strchr(s2,'9');p=strchr(s2,'6');(2)在执行以下语句后，s3的值是什么?

strcpy(s3,s1);strcat(s3,\(3)调用函数strcmp(s1,s2)的返回值是什么?

(4)调用函数strcmp(后p的值是指向第一个字符t的位置,也就是p==后p的值是指向s2串中第一个9所在的位置,也就是p==之后，p的返回值是NULL。

(2)strcpy函数功能是串拷贝，strcat函数的功能是串联接。所以:在执行strcpy(s3,s1);后，s3的值是\

在执行strcat(s3,\后，s3的值变成\

在执行完strcat(s3,s2);后，s3的值就成了\(3)函数strcmp(串1，串2)的功能是串比较，按串的大小进行比较，返回大于0，等于0或小于0的值以表示串1比串2大，串1等于串2，串1小于串2。因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符比较是以ascii码值相比的)

(4)首先，我们要知道

if(i

strcpy(Temp,//把删除的字符以后的字符保存到临时串中

strcpy(//用临时串中的字符覆盖位置i之后的字符}

elseif(i+m>=strlen(S)intlength;}HString;

void*substr(HString*sub,HString*s,intpos,intlen)

{//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串

//pos的合法位置为0length-1inti;

if(poss->length-1||lenlengthlen=s->length-pos;//设置子串的串长elsesub->length=len;//设置子串的串长

sub->ch=(char*)malloc(len*sizeof(char));//为sub->ch申请结点空间

for(i=0;ilength;i++)//将s串中pos位置开始的共sub->length个字符复制到sub串中sub->ch[i]=s->ch[pos+i];}关闭

4.7一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：abcdefghijklmnopqrstuvwxyzngzqtcobmuhelkpdawxfyivrsj

则字符串\被加密为\试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密的文本串进行解密后输出。解：

加密算法可以用两个串中字符的一一对应关系来实现，当输入一个字符时，由算法在串Original中查找其位置，然后用串Cipher中相应位置的字符去替换

原来的字符就可以了。解密算法则恰恰相返。设字母映射表的存储结构如下：#defineMaxStrSize26typedefstruct{

charOriginal[MaxStrSize];//可容纳26个字符，并依次存储在Original[0..n]中

charCipher[MaxStrSize];//可容纳26个字符，并依次对应Original表中的密码

intlength;}SeqString;

voidEncrypt(SeqStringcodetable){//加密算法。charch;inti;

while((ch=getchar())!='\\0'){i=0;

while(i=codetable.length)

Error(\else

printf(\}

printf(\}

voidDecipher(SeqStringOriginal,SeqStringCipher,char*T){//解密算法。charch;

while((ch=getchar())!='\\0'){i=0;

while(i=codetable.length)Error(\else

printf(\}

printf(\}关闭

4.8写一算法voidStrReplace(char*T,char*P,char*S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。解：

由于S和P的长度不一定相等，所以在替换时可能要移动字符元素。我们可以用到前面设计的一系列算法。算法如下：

voidStrReplace(char*T,char*P,char*S){//串替换inti,m;

m=strlen(P);//取得子串长度

i=StrMatch(T,P);//取得串匹配位置StrDelete(T,i,m);//删除匹配处子串

StrInsert(T,S,i);//将S串插入到匹配位置处}关闭

4.9将NaveStrMatch改写为输出目标串中所有与模式串匹配的有效位移。解：

把相应的返回语句改为打印输出就可找到所有匹配位置。改写后如下：voidNaveStrMatch(SeqStringT,SeqStringP){

inti,j,k;

intm=P.lenth;//模式串长度intn=T.length;//目标串长度

for(i=0;idata;//找到并返回字符值

q=T;//指针恢复串T的开始结点p=p->next;}

printf(\returnNULL;}关闭

第五章数组与广义表

5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000。解：

按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置)a0000a0001a0002a0010a0011a0012a0100

第五章数组与广义表

5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000。

解：

按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置)a0000a0001a0002a0010a0011a0012a0100a0101a0102a0110a0111a0112a0200a0201a0202a0210a0211a0212a1000a1001a1002a1010a1011a1012a1100a1101a1102a1110a1111a1112a1200a1201a1202a1210a1211a1212

按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这里为了便于阅读，也将其书写为分行形式)：

a0000a1000a0100a1100a0200a1200a0010a1010a0110a1110a0210a1210a0001a1001a0101a1101a0201a1201a0011a1011a0111a1111a0211a1211a0002a1002a0102a1102a0202a1202a0012a1012a0112a1112a0212a0212关闭

5.2给出C语言的三维数组地址计算公式。解：

由于C语言的数组下标下界是0，所以Loc(Amnp)=Loc(A000)+((i*n*p)+k)*d

其中Amnp表示三维数组。Loc(A000)表示数组起始位置。i、j、k表示当前元素的下标,d表示每个元素所占单元数。关闭

5.3设有三对角矩阵An*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=aij,求：

(1)用i,j表示k的下标变换公式。(2)用k表示i,j的下标变换公式。(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元素所点列数就是当前列号关闭

5.4设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节?A的终端结点a45的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何?解：

(1)因含5*6=30个元素，因此A共占30*4=120个字节。(2)a45的起始地址为：

Loc(a45)=Loc(a00)+(i*n+j)*d=1000+(4*6+5)*4=1116(3)按行优先顺序排列时，a25=1000+(2*6+5)*4=1068

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

5.5特别矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么?答：

后者在采用压缩存储后将会失去随机存储的功能。由于在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。关闭

5.6简述广义表和线性表的区别与联系。答:

广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表。

关闭

5.7画出以下广义表的图形表示：

(1)A(a,B(b,d),C(e,B(b,d),L(f,g)))(2)A(a,B(b,A))解:

(1)这是一个再入表。(2)则是一个递归表。

5.8设广义表L=((),()),试问head(L),tail(L),L的长度，深度各为多少?

解：

●head(L)=()●tail(L)=(())●L的长度为2●L的深度为2

5.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)tailhead)(((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).

5.10当三角矩阵采用题5.3所述的压缩存储时，写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵。解：

转置矩阵就是将矩阵元素的行号与列号互换，根据已知的三对角矩阵的特点，其转置矩阵对角线元素不变，非零的非对角线元素aij与aji互换位置。又知元素的下标和存放一维数组空间位置的关系：k=2i+j。我们可以设计出这个矩阵的转置算法：

#defineN10//矩阵行、列数

#defineLength(3*N-2)//压缩矩阵的长度typedefstruct{

intdata[Length];}DiaMatrix;

voidTransMatrix(DiaMatrix*C){//压缩三对角矩阵转置inti,j;intt;

for(i=0;idata[2*i+j]=C->data[2*j+i];C->data[2*j+i]=t;}//endif}//end

5.11当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。

解：

矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是A的，依照矩阵元素的行列去找A中的三元组，若有，则参与C，同时，这个元素假使在B中也有，则加上B的这个元素值，否则这个值就不变;假使A中没有，则找B，有则插入C，无则查找下一个矩阵元素。

#defineMaxSize10//用户自定义typedefintDataType;//用户自定义typedefstruct{//定义三元组inti,j;DataTypev;}TriTupleNode;typedefstruct

{//定义三元组表

TriTupleNodedata[MaxSize];

intm,n,t;//矩阵行，列及三元组表长度}TriTupleTable;//以下为矩阵加算法

voidAddTriTuple(TriTupleTable*A,TriTupleTable*B,TriTupleTable*C)

{//三元组表表示的稀疏矩阵A,B相加intk,l;

DataTypetemp;

C->m=A->m;//矩阵行数C->n=A->n;//矩阵列数C->t=0;//三元组表长度k=0;l=0;

while(ktif(!temp)//相加不为零，参与C{C->data[c->t].i=A->data[k].i;C->data[c->t].j=A->data[k].j;C->data[c->t++].v=temp;}

k++;l++;}if

((A->data[k].i==B->data[l].i)

C->data[c->t].j=A->data[k].j;C->data[c->t++].v=A->data[k].v;k++;}if

((A->data[k].i==B->data[l].i)C->data[c->t].j=B->data[l].j;C->data[c->t++].v=B->data[l].v;l++;}}

while(kt)//将A中剩余三元组参与C{C->data[c->t].i=A->data[k].i;C->data[c->t].j=A->data[k].j;C->data[c->t++].v=A->data[k].v;k++;}

while(lt)//将B中剩余三元组参与C{C->data[c->t].i=B->data[l].i;C->data[c->t].j=B->data[l].j;C->data[c->t++].v=B->data[l].v;l++;}}关闭

第六章树

6.1.假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边.已知一棵树边的集合为

{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法出此树，并回复以下问题：

(1)哪个是根结点?(2)哪些是叶结点?(3)哪个是g的双亲?(4)哪些是g的祖先?

(5)哪些是g的孩子?(6)哪些是e的子孙?(7)哪些是e的兄弟?哪些是f的兄弟?

(8)结点b和n的层次各是多少?(9)树的深度是多少?(10)以结点c为根的子树的深度是多少?(11)树的度数是多少?答：

a是根结点；

dmnfjkl是叶结点；c是g的双亲；

c,a是g的祖先；j,k是g的孩子；imn是e的子孙；

d是e的兄弟；g,h是f的兄弟；b的层次是2；n的层次是5；树的深度是5；

以c为根的子树深度是3；树的度数是3；

关闭6.2一棵度为2的有序树与一棵二叉树有何区别?答：

一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，假使有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。关闭

6.3试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。答：

三个结点的树如下：只有两种形态○○/\\|○○○|○

三个结点的二叉树如下所示：有五种形态：(1)(2)(3)(4)(5)○○○○○/\\//\\\\

○○○○○○/\\/\\

○○○○

6.4已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，...nm个度为m的结点，问该树中有多少片叶子?解：

设该树中的叶子数为n0个。该树中的总结点数为n个，则有：n=n0+n1+n2+…+nm(1)又有除根结点外，树中其他结点都有双亲结点，且是唯一的(由树中的分支表示)，所以，有双亲的结点数为：

n-1=0*n0+1*n1+2*n2+…+m*nm(2)联立(1)(2)方程组可得：

叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm关闭

6.5一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其

余各层上每个结点都有k棵非空子树。假使按层次顺序(同层自左至右)从1开始对全部结点编号，问：

(1)各层的结点数目是多少?

(2)编号为i的结点的双亲结点(若存在)的编号是多少?

(3)编号为i的结点的第j个孩子结点(若存在)的编号是多少?

(4)编号为i的结点的有右兄弟的条件是什么?其右兄弟的编号是多少?解：

(1)层号为h的结点数目为kh-1

(2)编号为i的结点的双亲结点的编号是：|_(i-2)/k_|+1(不大于(i-2)/k的最大整数。也就是(i-2)与k整除的结果.以下/表示整除。(3)编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j;(4)编号为i的结点有右兄弟的条件是(i-1)能被k整除右兄弟的编号是i+1.

关闭6.6高度为h的完全二叉树至少有多少个结点?至多有多少个结点?解：

高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。关闭

6.7在具有n个结点的k叉树(k>=2)的k叉链表表示中，有多少个空指针?解：

n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+1;关闭

6.8假设二叉树包含的结点数据为1，3，7，12。(1)画出两棵高度最大的二叉树；

(2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。解：

(1)高度最大的两棵二叉树如图：○1○1/\\○3○3/\\○7○7/\\

○2○2/\\

○12○12

(2)两棵完全二叉树如下：

○12○12/\\/\\○7○3○7○3

/\\/\\○1○2○2○1关闭

6.9试找出分别满足下面条件的所有二叉树：

(1)前序序列和中序序列一致；(2)中序序列和后序序列一致；

(3)前序序列和后序序列一致；(4)前序、中序、后序序列均一致。答：

(1)前序序列和中序序列一致的二叉树是：空二叉树或没有左子树的二叉树(右单支树)。

(2)中序序列和后序序列一致的二叉树是：空二叉树或没有右子树的二叉树(左单支树)。

(3)前序序列和后序序列一致的二叉树是：空二叉树或只有根的二叉树。(4)前序、中序、后序序列均一致的二叉树：空树或只有根结点的二叉树。关闭

6.10试采用顺序存储方法和链接存储方法分别画也6.30所示各二叉树的存储结构。解：

(1)顺序存储方法：二叉树(a):

下标0123456789101112131415161718192021

__________________________________________________________________bt||1|2|∮|∮|3|∮|∮|∮|∮|4|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|5|__________________________________________________________________二叉树(b):

下标01234567891011121314151617181920212223242526

_______________________