数据结构(c语言版)习题集答案第三章

第三章栈、队列和数组一、名词解释：1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵二、填空题：1.栈修改的原则是_________或称________，因此，栈又称为________线性表。

在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。

2.栈的基本运算至少应包括________、________、________、________、________五种。

3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。

4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。

5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。

6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。

7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。

int InitStack(SqStackTp *sq){ ________;return(1);}8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。

Int Push(SqStackTp *sq,DataType x){ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}else{________________:________________=x;return(1);}}9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。

第3 章栈和队列习题1．选择题（1）若让元素1，2，3，4，5 依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1 （2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为（）。

A．i B．n-i C．n-i+1 D．不确定（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n （4）链式栈结点为：(data,link)，top 指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x 中,则应执行操作（）。

A.x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；（5）设有一个递归算法如下int fact(int n) { //n 大于等于0if(n<=0) return 1;else return n*fact(n-1); }则计算fact(n)需要调用该函数的次数为（）。

A．n+1 B．n-1 C．n D．n+2 （6）栈在（）中有所应用。

A．递归调用 B．函数调用 C．表达式求值 D．前三个选项都有（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。

主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是（）。

A．队列B．栈C．线性表D．有序表（8）设栈S 和队列Q 的初始状态为空，元素e1、e2、e3、e4、e5 和e6 依次进入栈S，一个元素出栈后即进入Q，若6 个元素出队的序列是e2、e4、e3、e6、e5 和e1，则栈S 的容量至少应该是（）。

第三章习题解答1.分别写出对链栈的入栈和出栈操作的算法。

链栈的结点类型定义如下：Typedef struct stacknode {SElemtype data;struct stacknode *next;}stacknode, *linkstack;入栈操作：Status push( linkstack &S, SElemtype e){ p=(linkstack)malloc(sizeof(stacknode));If (!p) return ERROR;p->data=e;p->next=S;S=p;return OK;}出栈操作：Status pop(linkstack &S, SElemtype &e){ if (!S) return ERROR;p=s;s=p->next;free(p);return OK;}P24/3.15假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。

试编写实现这个双向栈tws的三个操作：初始化inistack(tws),入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为变参）或函数设计这些操作算法各有什么优缺点。

双栈的结构类型定义如下：typedef struct{Elemtype *base[2];Elemtype *top[2];}BDStacktype; //双向栈类型栈的初始化操作：status Init_Stack(BDStacktype &tws,int m)//初始化一个大小为m的双向栈tws{ tws.base[0]=(Elemtype*)malloc(m*sizeof(Elemtype));tws.base[1]=tws.base[0]+m-1;tws.top[0]=tws.base[0];tws.top[1]=tws.base[1];return OK;}入栈操作：Status push(BDStacktype &tws,int i,Elemtype x) // x入栈,i=0表示低端栈,i=1表示高端栈{ if (tws.top[0]>tws.top[1]) return OVERFLOW;//注意此时的栈满条件if (i==0) *tws.top[0]++=x;elseif (i==1) *tws.top[1]--=x;else return ERROR;return OK;}出栈操作：Status pop(BDStacktype &tws, int i, Elemtype &x) // x出栈,i=0表示低端栈,i=1表示高端栈{ if (i==0){ if (tws.top[0]==tws.base[0]) return OVERFLOW;x=*--tws.top[0];}else if (i==1){ if (tws.top[1]==tws.base[1]) return OVERFLOW;x=*++tws.top[1];}else return ERROR;return OK;}P24/3.18试写一个判别表达式中开、闭括号是否配对出现的算法。

第三章栈、队列和数组一、名词解释：1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵二、填空题：1.栈修改的原则是_________或称________，因此，栈又称为________线性表。

在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。

2.栈的基本运算至少应包括________、________、________、________、________五种。

3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。

4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。

5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。

6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。

7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。

int InitStack(SqStackTp *sq){ ________;return(1);}8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。

Int Push(SqStackTp *sq,DataType x){ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}else{________________:________________=x;return(1);}}9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。

严蔚敏《数据结构（c语言版）习题集》算法设计题第三章参考答案第三章栈与队列typedef struct{Elemtype *base[ ];Elemtype *top[ ];}BDStacktype; //双向栈类型Status Init_Stack(BDStacktype &s int m)//初始化一个大小为m 的双向栈s{s base[ ]=(Elemtype*)malloc(sizeof(Elemtype));s base[ ]=s base[ ]+m;s top[ ]=s base[ ];s top[ ]=s base[ ];return OK;}//Init_StackStatus push(BDStacktype &s int i Elemtype x)//x入栈 i= 表示低端栈 i= 表示高端栈{if(s top[ ]>s top[ ]) return OVERFLOW; //注意此时的栈满条件if(i== ) *s top[ ]++=x;else if(i== ) *s top[ ] =x;else return ERROR;return OK;}//pushStatus pop(BDStacktype &s int i Elemtype &x)//x出栈 i= 表示低端栈 i= 表示高端栈{if(i== ){if(s top[ ]==s base[ ]) return OVERFLOW;x=* s top[ ];}else if(i== ){if(s top[ ]==s base[ ]) return OVERFLOW;x=*++s top[ ];}else return ERROR;return OK;}//popvoid Train_arrange(char *train)//这里用字符串train表示火车 H 表示硬席 S 表示软席{p=train;q=train;InitStack(s);while(*p){if(*p== H ) push(s *p); //把 H 存入栈中else *(q++)=*p; //把 S 调到前部p++;}while(!StackEmpty(s)){pop(s c);*(q++)=c; //把 H 接在后部}}//Train_arrangeint IsReverse()//判断输入的字符串中 & 前和 & 后部分是否为逆串是则返回否则返回{InitStack(s);while((e=getchar())!= & )push(s e);while((e=getchar())!= @ ){if(StackEmpty(s)) return ;pop(s c);if(e!=c) return ;}if(!StackEmpty(s)) return ;return ;}//IsReverseStatus Bracket_Test(char *str)//判别表达式中小括号是否匹配{count= ;for(p=str;*p;p++){if(*p== ( ) count++;else if(*p== ) ) count ;if (count< ) return ERROR;}if(count) return ERROR; //注意括号不匹配的两种情况return OK;}//Bracket_TestStatus AllBrackets_Test(char *str)//判别表达式中三种括号是否匹配{InitStack(s);for(p=str;*p;p++){if(*p== ( ||*p== [ ||*p== { ) push(s *p);else if(*p== ) ||*p== ] ||*p== } ){if(StackEmpty(s)) return ERROR;pop(s c);if(*p== ) &&c!= ( ) return ERROR;if(*p== ] &&c!= [ ) return ERROR;if(*p== } &&c!= { ) return ERROR; //必须与当前栈顶括号匹配}}//forif(!StackEmpty(s)) return ERROR;return OK;}//AllBrackets_Testtypedef struct {int x;int y;} coordinate;void Repaint_Color(int g[m][n] int i int j int color)//把点(i j)相邻区域的颜色置换为color{old=g[i][j];InitQueue(Q);EnQueue(Q {I j});while(!QueueEmpty(Q)){DeQueue(Q a);x=a x;y=a y;if(x> )if(g[x ][y]==old){g[x ][y]=color;EnQueue(Q {x y}); //修改左邻点的颜色}if(y> )if(g[x][y ]==old){g[x][y ]=color;EnQueue(Q {x y }); //修改上邻点的颜色}if(xif(g[x+1][y]==old){g[x+1][y]=color;EnQueue(Q,{x+1,y}); //修改右邻点的颜色}if(yif(g[x][y+1]==old){g[x][y+1]=color;EnQueue(Q,{x,y+1}); //修改下邻点的颜色}}//while}//Repaint_Color分析:本算法采用了类似于图的广度优先遍历的思想,用两个队列保存相邻同色点的横坐标和纵坐标.递归形式的算法该怎么写呢?3.21void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new{p=str;q=new; //为方便起见,设str的两端都加上了优先级最低的特殊符号InitStack(s); //s为运算符栈while(*p){if(*p是字母)) *q++=*p; //直接输出else{c=gettop(s);if(*p优先级比c高) push(s,*p);else{while(gettop(s)优先级不比*p低){pop(s,c);*(q++)=c;}//whilepush(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则}//else}//elsep++;}//while}//NiBoLan //参见编译原理教材3.22int GetValue_NiBoLan(char *str)//对逆波兰式求值{p=str;InitStack(s); //s为操作数栈while(*p){if(*p是数) push(s,*p);else{pop(s,a);pop(s,b);r=pute(b,*p,a); //假设pute为执行双目运算的过程push(s,r);}//elsep++;}//whilepop(s,r);return r;}//GetValue_NiBoLan3.23Status NiBoLan_to_BoLan(char *str,stringtype &new)//把逆波兰表达式str转换为波兰式new{p=str;Initstack(s); //s的元素为stringtype类型while(*p){if(*p为字母) push(s,*p);else{if(StackEmpty(s)) return ERROR;pop(s,a);if(StackEmpty(s)) return ERROR;pop(s,b);c=link(link(*p,b),a);push(s,c);}//elsep++;}//whilepop(s,new);if(!StackEmpty(s)) return ERROR;return OK;}//NiBoLan_to_BoLan分析:基本思想见书后注释.本题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b).3.24Status g(int m,int n,int &s)//求递归函数g的值s{if(m==0&&n>=0) s=0;else if(m>0&&n>=0) s=n+g(m-1,2*n);else return ERROR;return OK;}//g3.25Status F_recursive(int n,int &s)//递归算法{if(n<0) return ERROR;if(n==0) s=n+1;else{F_recurve(n/2,r);s=n*r;}return OK;}//F_recursiveStatus F_nonrecursive(int n,int s)//非递归算法{if(n<0) return ERROR;if(n==0) s=n+1;else{InitStack(s); //s的元素类型为struct {int a;int b;}while(n!=0){a=n;b=n/2;push(s,{a,b});n=b;}//whiles=1;while(!StackEmpty(s)){pop(s,t);s*=t.a;}//while}return OK;}//F_nonrecursive3.26float Sqrt_recursive(float A,float p,float e)//求平方根的递归算法{if(abs(p^2-A)<=e) return p;else return sqrt_recurve(A,(p+A/p)/2,e);}//Sqrt_recurve。

第三章栈和队列(参考答案)// 从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构// 和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。

3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 11 2 4 3 2 1 4 3 3 2 4 11 32 4 23 14 3 4 2 11 3 42 234 11 4 32 2 43 1设入栈序列元素数为n，则可能的出栈序列数为C2n n=(1/n+1)*(2n!/(n!)2)3.2 证明：由j<k和p j<p k说明p j在p k之前出栈，即在k未进栈之前p j已出栈，之后k进栈，然后p k出栈；由j<k和p j>p k说明p j在p k之后出栈，即p j被p k压在下面，后进先出。

由以上两条，不可能存在i<j<k使p j<p k<p i。

也就是说，若有1，2，3顺序入栈，不可能有3，1，2的出栈序列。

3.3 void sympthy(linklist *head, stack *s)//判断长为n的字符串是否中心对称{ int i=1; linklist *p=head->next;while (i<=n/2) // 前一半字符进栈{ push(s,p->data); p=p->next; }if (n % 2 !==0) p=p->next;// 奇数个结点时跳过中心结点while (p && p->data==pop(s)) p=p->next;if (p==null) printf(“链表中心对称”)；else printf(“链表不是中心对称”)；} // 算法结束3.4int match()//从键盘读入算术表达式，本算法判断圆括号是否正确配对（init s;//初始化栈sscanf(“%c”,&ch);while (ch!=’#’) //’#’是表达式输入结束符号switch (ch){ case ’(’: push(s,ch); break;case ’)’: if (empty(s)) {printf(“括号不配对”); exit(0);}pop(s);}if (!empty(s)) printf(“括号不配对”);else printf(“括号配对”);} // 算法结束3.5typedef struct // 两栈共享一向量空间{ ElemType v[m]; // 栈可用空间0—m-1int top[2] // 栈顶指针}twostack;int push(twostack *s,int i, ElemType x)// 两栈共享向量空间,i是0或1，表示两个栈，x是进栈元素，// 本算法是入栈操作{ if (abs(s->top[0] - s->top[1])==1) return(0);// 栈满else {switch (i){case 0: s->v[++(s->top)]=x; break;case 1: s->v[--(s->top)]=x; break;default: printf(“栈编号输入错误”); return(0);}return(1); // 入栈成功}} // 算法结束ElemType pop(twostack *s,int i)// 两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作{ ElemType x;if (i!=0 && i!=1) return(0);// 栈编号错误else {switch (i){case 0: if(s->top[0]==-1) return(0);//栈空else x=s->v[s->top--];break;case 1: if(s->top[1]==m) return(0);//栈空else x=s->v[s->top++]; break;default: printf(“栈编号输入错误”);return(0);}return(x); // 退栈成功}} // 算法结束ElemType top (twostack *s,int i)// 两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作{ ElemType x;switch (i){case 0: if(s->top[0]==-1) return(0);//栈空else x=s->v[s->top]; break;case 1: if(s->top[1]==m) return(0);//栈空else x=s->v[s->top]; break;default: printf(“栈编号输入错误”);return(0);}return(x); // 取栈顶元素成功} // 算法结束3．6void Ackerman(int m,int n)// Ackerman 函数的递归算法{ if (m==0) return(n+1);else if (m!=0 && n==0) return(Ackerman(m-1,1);else return(Ackerman(m-1,Ackerman(m,n-1))} // 算法结束3．7(1) linklist *init(linklist *q)// q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空{ q=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出q->next=q;return (q);} // 算法结束(2) linklist *enqueue(linklist *q，ElemType x)// q是以带头结点的循环链表表示的队列的尾指针，本算法将元素x入队{ s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出s->next=q->next; // 将元素结点s入队列q->next=s;q=s; // 修改队尾指针return (q);} // 算法结束(3) linklist *delqueue(linklist *q)//q是以带头结点的循环链表表示的队列的尾指针，这是出队算法{ if (q==q->next) return (null); // 判断队列是否为空else {linklist *s=q->next->next; // s指向出队元素if (s==q) q=q->next; // 若队列中只一个元素，置空队列else q->next->next=s->next;// 修改队头元素指针free (s); // 释放出队结点}return (q);} // 算法结束。

n(n + 1) 2
( 5 )1 + ( 1 + 2 ) + ( 1 + 2 + 3 ) + . . . + ( 1 + 2 + 3 + . . . + n ) =
∑
i =1
n
i(i + 1) 2
=
1 n 1 n 2 1 n 2 1 n ( 1 ) ( ) i i + = i + i = i ∑ ∑ ∑i + 2 ∑ 2 i =1 2 i =1 2 i =1 i =1
( 6 )i = 1 ;j = 0 ; w h i l e ( i + j < = n ){ @ i f ( i > j )j + + ; e l s ei + + ; } ( 7 )x = n ;y = 0 ; @ y + + ; } ( 8 )x = 9 1 ;y = 1 0 0 ; w h i l e ( y > 0 ){ @ i f ( x > 1 0 0 ){x=1 0 ;y ;} e l s ex + + ; } 解：( 1 )n 1 ( 2 )n 1 ( 3 )n 1 ( 4 )n + ( n 1 ) + ( n 2 ) + . . . + 1 = / /n 是不小于 1 的常数 w h i l e ( x > = ( y + 1 ) * ( y + 1 ) ){
n) n−2
1 . 1 1已知有实现同一功能的两个算法，其时间复杂度分别为 O
(2 ) 和 O(n ) ，假设现实计算机可连续
n 10

数据结构(C语言版)第三版__清华大学出版社_习题参考答案数据结构(C语言版)第三版__清华大学出版社_习题参考答案引言：数据结构是计算机科学的基础，对于学习和理解数据结构的相关概念和算法非常重要。

本文将对清华大学出版社出版的《数据结构(C语言版)第三版》中的习题进行参考答案的提供。

通过正确的理解和掌握这些习题的解答，读者可以加深对数据结构的认识，并提高自己的编程能力。

第一章：绪论1.1 数据结构的定义与作用数据结构是指数据对象以及数据对象之间的关系、运算和存储结构的总称。

数据结构的作用是在计算机中高效地组织和存储数据，同时支持常见的数据操作和算法。

1.2 算法的定义与特性算法是解决特定问题的一系列步骤和规则。

算法具有确定性、有穷性、可行性和输入输出性等特点。

第二章：线性表2.1 线性表的定义和基本操作线性表是同类型数据元素的一个有限序列。

线性表的基本操作包括初始化、查找、插入、删除和遍历等。

2.2 顺序存储结构顺序存储结构是将线性表中的元素按顺序存放在一块连续的存储空间中。

顺序存储结构的特点是随机存取、插入和删除操作需要移动大量元素。

2.3 链式存储结构链式存储结构通过结点之间的指针链表来表示线性表。

链式存储结构的特点是插入和删除操作方便，但查找操作需要遍历整个链表。

第三章：栈和队列3.1 栈的定义和基本操作栈是只能在一端进行插入和删除操作的线性表。

栈的基本操作包括初始化、入栈、出栈和获取栈顶元素等。

3.2 队列的定义和基本操作队列是只能在一端插入操作，在另一端进行删除操作的线性表。

队列的基本操作包括初始化、入队、出队和获取队头元素等。

第四章：串4.1 串的定义和基本操作串是由零个或多个字符组成的有限序列。

串的基本操作包括初始化、串的赋值、串的连接和串的比较等。

第五章：树5.1 树的基本概念和术语树是n（n>=0）个结点的有限集。

树的基本概念包括根结点、子树、深度和高度等。

5.2 二叉树二叉树是每个结点最多有两个子树的树结构。

习题答案1.填空题（1）栈（2）队列（3）后进先出（4）先进先出2.选择题（1）A （2）C （3）D （4）D、A （5）C （6）B3.思考题（1）栈是一种运算受限制的线性表，其只允许在表的一端进行插入和删除操作，俗称堆栈。

允许进行操作的一端称为“栈顶”，而另一个固定端称为“栈底”，栈中的数据在进行入栈和出栈时，遵循后进先出的原则。

队列同样是一种运算受限制的线性表，是限制在两端进行插入和删除操作的线性表。

允许进行插入操作的一端称为“队尾”，而允许进行删除操作的一端称为“队头”，队列中的数据在进行入队和出队时，遵循先进先出的原则。

4.编程题（1）//入栈//参数1为栈顶指针（头结点指针），参数2为插入的数据int linkstack_push(linkstack_t *s, datatype_t value){linkstack_t *temp;//使用malloc函数为新插入的结点申请内存空间temp = (linkstack_t *)malloc(sizeof(linkstack_t));//为新插入的结点赋值temp->data = value;//用头插法实现入栈temp->next = s->next;s->next = temp;return 0;}//判断栈是否为空int linkstack_empty(linkstack_t *s){return s->next == NULL ? 1 : 0; //判断下一个结点是否为空}//出栈datatype_t linkstack_pop(linkstack_t *s){linkstack_t *temp;datatype_t value;if(linkstack_empty(s)){printf("linkstack empty\n");return -1;}//头删法表示出栈，后入先出temp = s->next;s->next = temp->next;//保存出栈的数据value = temp->data;//释放出栈的结点的内存空间free(temp);temp = NULL;//返回出栈的数据return value;}（2）//入队//参数1为存放队列头尾结点指针的结构体地址，参数2为新入队的数据int linkqueue_enter(linkqueue_t *lq, datatype_t value){ linknode_t *temp;//使用malloc函数为头结点申请内存空间temp = (linknode_t *)malloc(sizeof(linknode_t));//采用尾插法的设计思想temp->data = value; //为新结点赋值temp->next = NULL; //将新结点的指针指向NULLlq->rear->next = temp; //入队，将新结点加入队列尾部lq->rear = temp; //移动rear指针，指向新加入的结点 return 0;}//判断队列是否为空int linkqueue_empty(linkqueue_t *lq){//当front与rear指向同一个结点时，判断队列为空return lq->front == lq->rear ? 1 : 0;}//出队//从头结点开始删除，包括头结点datatype_t linkqueue_out(linkqueue_t *lq){linknode_t *temp;datatype_t value;if(linkqueue_empty(lq)){printf("linkqueue empty\n");return -1;}temp = lq->front; //获取删除结点//移动front指针到下一个结点lq->front = lq->front->next;//获取下一个结点的数据value = lq->front->data;free(temp); //释放需要删除结点的内存空间 temp = NULL; //避免出现野指针//返回结点数据return value;}。

习题三3.1 3.10 3.133.5 3.6 3.15 3.17 3.19 3.243.29 3.313.5(1)给定操作序列P1P2P3…P i…P n（P k为S或X，k=1,2,…n ）是合法的，当且仅当满足下列条件：a. 序列中包含的S的个数和X的个数相等；b. 对于任意的j（1≤j≤n）；有P1P2P3…P j子序列中所包含的S的个数大于等于X的个数；(2)证明：设P1P2P3…P i…P n ，Q1Q2Q3…Q i…Q n是两个不同的合法序列；∵两者不同，∴ k=min{i| P i≠Q i , 1≤i≤n }且k>1， P k≠Q k（因P1，Q1肯定是S，否则不合法！）即，P1P2P3…P k-1 和Q1Q2Q3…Q k-1是相等的，但P k≠Q k由此可知：两个操作序列在前k-1步操作后输出序列和栈中所剩元素均相同，由于P k≠P k不妨设P k=X，而Q k=S；这样，在操作序列P1P2P3…P i…P n中的第k-1步后输出的第一个元素是目前栈中的元素，而对于操作序列Q1Q2Q3…Q i…Q n中的第k-1步后输出的第一个元素是目前还在栈外的元素。

所以输出序列不同。

即两个不同的合法操作序列，不可能得到相同的输出序列。

证毕！3.6 用反证法证明：假设存在这样的输出序列，P1…Pi…Pj…Pk…Pn，满足i<j<k,使Pj<Pk<Pi;因Pi 在这三个数中最大，且Pi最先出栈，按照题意所给进栈顺序，在Pi出栈时Pj 和Pk都还在栈中；又因，Pj <Pk，所以Pj比Pk先进栈，则出栈顺序应该是Pk先出栈而不是Pj先出栈，矛盾！证毕！3.10(1) 输出序列为：0,5,9,12,14,15(2)由于输入的数据个数不定，采用单链表存储输入的元素，又因是先输入的，后累加到累加器里，所以用链栈的形式存储。

（类型定义与书本上第二章相同）void test( ){LinkList L ,P;int x,sum;L=NULL; //建立空链表sum=0;printf(sum);scanf(x);//读入第一个数while(x){P=(LinkList)malloc(sizeof(LNode));//产生一个结点P->data=x;P->next=L; L=P;//插入在链头scanf(x);//读下一个数}while(L){sum+=sum+L->data;//取值累加printf(sum);//输出P=L->next; free(L); L=P;}}3.15 所用类型定义如下：#define Stack_Init_Size 100typedef struct stack{SElemType base0,base1,*top0,*top1;int StackSize ;} DuSqStack;void Inistack(DuSqStack &tws){tws.base0=( SElemType*)malloc(Stack_Init_Size*sizeof(SElemType));if(!tws.base0) exit(OVERFLOW);tws.top0= tws.base0;tws.base1=tws.top1=tws0.base0+ Stack_Init_Size-1;tws.StackSize= Stack_Init_Size;}// InistackStatus Push( DuSqStack &tws ,int i , SElemType x){//将元素x插在第i个栈中if (tws.top0>tws.top1) return (OVERFLOW);switch(i){case 0: *tws.top0=x; tws.top0++;break;case 1: *tws.top1=x; tws.top1--;break;}return OK;}// PushStatus Pop( DuSqStack &tws ,int i , SElemType &x){//将第i个栈的栈顶元素弹出，由x带回switch(i){case 0: if(tws.base0==tws.top0) return ERROR; x=*(--tws.top0);break; case 1: if(tws.base1==tws.top1) return ERROR; x=*(++tws.top0);break; }return OK;}// Pop3.17Status judge( ){//判断输入的字符序列是否为型如序列1&序列2，其中序列2是序列1的逆序列InitStack(S); 初始化栈Sc=getchar( );//读第一个字符while(c!= '&'&&c!= '@'){push(s,c); c=getchar( );}if(c!= '&') return FALSE;c=getchar( );//读下一个while(c!= '@'&& !EmptyStack(s)){pop(s,e);if(c!=e) return FALSE;c=getchar( );}if(c== '@'&& EmptyStack(s)) return TRUE;return FALSE;}// judge3.19Status judged(SqList L){//L为数据元素类型为字符的顺序存储的线性表，表示一个表达式，判断该表达//式的括号是否匹配InitStack(S);//初始化栈Sfor(j=0;j<L.length;j++){switch(L.elem[j]){case ‘(‘:case ‘[‘:case ‘{‘: push(S, L.elem[j]) ;break;case ‘)’:case ‘]’:case ‘}’: if(EmptyStack(S) return FALSE;else{ Pop(S,e);switch(L.elem[j]){case ‘)’:if(e!=’(‘ ) return FALSE;break;case ‘]’:if(e!=’[‘ ) return FALSE;break;case ‘}’:if(e!=’{‘ ) return FALSE;break;}}}}if(EmptyStack(S) return TRUE;else return FALSE;}// judged3.24int g(int m,int n){// 不考虑输入参数的非法性if(m==0 && n>=0) return 0;else if(m>0 && n>=0) return (g(m-1,2*n)+n);}// g3．29 类型定义#define MAX_Init_Size 100typedef struct {QElemType *base;int front,rear ,tag;} SqQueue;Status InitQueue(SqQueue &Q ){//初始化一个队列Q.base=( QelemType* )malloc(MAX_Init_Size*sizeof(QelemType));If(!Q.base) exit(OVERFLOW);G.front=Q.rear=Q.tag=0;//表示队列为空return OK;}// InitQueueStatus EnQueue(SqQueue &Q , QelemType x){//将元素x入队列, 若队列满则返回函数值ERROR，否则返回OKif((Q.front==Q.rear)&&(Q.tag==1)) return ERROR;Q.base[Q.rear]=x;Q.rear=(Q.rear+1)%MAX_Init_Size;if(Q.front==Q.rear) Q.tag=1;//尾指针追上头指针return OK;}// EnQueueStatus DelQueue(SqQueue &Q , QelemType &x){//删除队头元素，让x带回，若队列为空则返回函数值ERROR，否则返回OK if((Q.front==Q.rear)&&(Q.tag==0)) return ERROR;x=Q.base[Q.front];Q.front= (Q.front+1)% MAX_Init_Size;if(Q.front==Q.rear) Q.tag=0;//头指针追上尾指针return OK;}//DelQueue3.31Status Ispalindrome ( ){//判断输入的字符序列是否为回文，是返回TRUE ，否则返回FALSE InitStack(S);// 初始化栈SInitQueue(Q);//初始化一个队列Qc=getchar( );//读第一个字符while(c!= '@'){push(S,c); //入栈EnQueue(Q,c);//入队列c=getchar( );}while(!EmptyStack(S)){Pop(S,e);DelQueue(Q,c);if(c!=e) return FALSE;}return TRUE;}// Ispalindrome3.24Status g(int m,int n,int &s)//求递归函数g的值s{if(m==0&&n>=0) s=0;else if(m>0&&n>=0) s=n+g(m-1,2*n);else return ERROR;return OK;}//g3.29Status EnCyQueue(CyQueue &Q,int x)//带tag域的循环队列入队算法{if(Q.front==Q.rear&&Q.tag==1) //tag域的值为0表示"空",1表示"满"return OVERFLOW;Q.base[Q.rear]=x;Q.rear=(Q.rear+1)%MAXSIZE;if(Q.front==Q.rear) Q.tag=1; //队列满}//EnCyQueueStatus DeCyQueue(CyQueue &Q,int &x)//带tag域的循环队列出队算法{if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE;Q.front=(Q.front+1)%MAXSIZE;x=Q.base[Q.front];//if(Q.front==Q.rear) Q.tag=1; //队列空return OK;}//DeCyQueue分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.友情提示：部分文档来自网络整理，供您参考！文档可复制、编制，期待您的好评与关注！。

第1 章绪论5．选择题：C CBDCA6．试分析下面各程序段的时间复杂度。

（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）O（n （5）因为x++ 共执行了n-1+n-2+⋯⋯＋1= n(n-1)/2 ，所以执行时间为2）（6）O( n )第2 章线性表1．选择题babadbcabdcddac2．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next; // 假定第一个结点中数据具有最大值p=L->next->next;while(p != NULL ){// 如果下一个结点存在if(p->data > pmax->data) pmax=p;p=p->next;}return pmax->data;原表（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用的存储空间。

void inverse(LinkList &L) {// 逆置带头结点的单链表Lp=L->next; L->next=NULL;while ( p) {q=p->next; // q 指向*p 的后继p->next=L->next;L->next=p; // *p 插入在头结点之后p = q;}}（10）已知长度为n 的线性表 A 采用顺序存储结构，请写一时间复杂度为O (n) 、空间复杂度为O (1) 的算法，该算法删除线性表中所有值为item 的数据元素。

[ 题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i 个元素，第i+1 至第n 个元素要依次前移）。

本题要求删除线性表中所有值为item 的数据元素，并未要求元素间的相对位置不变。

数据结构(C语言版)(第2版)课后习题答案数据结构(C语言版)(第2版)课后习题答案1. 简介数据结构是计算机科学领域中非常重要的一门学科，它研究的是数据的组织、存储和管理方式。

本文将针对《数据结构(C语言版)(第2版)》的课后习题提供答案，帮助读者更好地理解和应用数据结构。

2. 第一章: 绪论在第一章中，主要介绍了数据结构的基本概念、分类和基本操作。

以下是部分习题的答案：2.1 习题1习题描述：什么是数据结构？答案：数据结构是指数据对象中元素之间的关系，以及对这些关系进行操作的方法和技术的集合。

2.2 习题2习题描述：数据结构的分类有哪些？答案：数据结构可以分为线性结构和非线性结构。

线性结构包括线性表、栈、队列等；非线性结构包括树、图等。

3. 第二章: 线性表第二章介绍了线性表的定义、分类和实现。

以下是部分习题的答案：3.1 习题1习题描述：什么是线性表？答案：线性表是由n个数据元素a1, a2, ..., an组成的有限序列，其中元素之间存在着一一对应的关系。

3.2 习题2习题描述：线性表的分类有哪些？答案：线性表可以分为顺序表和链表。

顺序表是用一段地址连续的存储单元一次存储线性表的所有元素，而链表是采用链式存储结构，通过每个元素存储其后继元素的地址来实现元素之间的逻辑关系。

4. 第三章: 栈与队列第三章讲解了栈和队列的定义、特性和实现。

以下是部分习题的答案：4.1 习题1习题描述：栈和队列有什么区别？答案：栈是一种后进先出的线性表，只能在表尾进行插入和删除操作；队列是一种先进先出的线性表，只能在表的一端进行插入和删除操作。

4.2 习题2习题描述：栈的应用有哪些？答案：栈在计算机科学中有广泛的应用，如函数的调用和返回、括号匹配、表达式求值等。

5. 第四章: 串第四章讲解了串的定义、模式匹配和实现。

以下是部分习题的答案：5.1 习题1习题描述：什么是串？答案：串是由零个或多个字符组成的有限序列，串中的字符个数称为串的长度。

p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) {
q->next=p;p=q; q=s;s=s->next; //把 L 的元素逐个插入新表表头 } q->next=p;s->next=q;L->next=s; }//LinkList_reverse 分析:本算法的思想是 ,逐个地把 L 的当前元素 q 插入新的链表头部 ,p 为新 表表头.
见书后答案.
2.17
Status Insert(LinkList &L,int i,int b)//在无头结点链表 L 的第 i 个 元素之前插入元素 b {
p=L;q=(LinkList*)malloc(sizeof(LNode)); q.data=b;
if(i==1) { q.next=p;L=q; //插入在链表头部 } else { while(--i>1) p=p->next; q->next=p->next;p->next=q; //插入在第 i 个元素的位置 } }//Insert
2.15
void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表 hb 接在 ha 后面形成链表 hc {
hc=ha;p=ha; while(p->next) p=p->next; p->next=hb; }//ListConcat
char *sport; enum{male,female} gender; char schoolname; //校名为'A','B','C','D'或'E' char *result; int score;

数据结构（ C语言版）（第 2版）课后习题答案李冬梅2015.3目录第 1 章绪论 (1)第 2 章线性表 (5)第 3 章栈和队列 (13)第 4 章串、数组和广义表 (26)第 5 章树和二叉树 (33)第 6 章图 (43)第 7 章查找 (54)第 8 章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0 ，± 1，± 2，, } ，字母字符数据对象是集合C={‘A’，‘B’， , ，‘Z’，‘ a’，‘ b’， , ，‘z ’} ，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

第三章一、填空题1、先进后出或者后进先出先进先出或者后进后出2、(rear-front+max)%max3、bceda二、选择题1、A2、D3、C三、应用题1、123 132 213 231 3212、用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。

即尾数组已满但头数组还是空的；循环队列也是一种数组，只是它在逻辑上把数组的头和尾相连，形成循环队列，当数组尾满的时候，要判断数组头是否为空，不为空继续存放数据；可以有效的利用资源；3、将栈中元素逆序4、将队列中的元素分开，大于等于0的放到一个队列中，小于0的放到另一个队列中。

四、算法设计题1、#include "stdio.h"#include "string.h"typedef struct{int data[50];//进制设为整型int top;}seqstack;//栈的初始化void initstack(seqstack *s){s->top=-1;}//判断栈是否为空int empty(seqstack *s){if(s->top==-1)return 1;elsereturn 0;}//进栈操作void push(seqstack *s,int x){if(s->top==49)//栈的下标为0-49printf("overflow!\n");else{s->top++;s->data[s->top]=x;}}//出栈操作char pop(seqstack *s){int x;if(empty(s)){printf("underflow!\n");x='\0';}else{x=s->data[s->top];s->top--;}return x;}int ishw(char a[],int n){int i;char b[10];seqstack s;initstack(&s);for(i=0;i<n;i++)push(&s,a[i]);i=0;while(!empty(&s)){b[i]=pop(&s);i++;}b[i]='\0';if(strcmp(a,b)==0)return 1;elsereturn 0;}main(){char str[10];gets(str);if(ishw(str,strlen(str))==1)printf("是回文！");elseprintf("不是回文！");}2、#include "stdio.h"#include "stdlib.h"typedef struct stacknode{char data;struct stacknode *next;}StackNode;void InitStack(StackNode **top){*top=NULL;}void Push(StackNode **top,char x){//将元素x插入链栈头部StackNode *p=(StackNode *)malloc(sizeof(StackNode)); p->data=x;p->next=*top;//将新结点*p插入链栈头部*top=p;}int sum(StackNode **top){int n=0;while(*top!=NULL){n++;*top=(*top)->next;}return n;}main(){StackNode *top;char ch;InitStack(&top);while((ch=getchar())!='\n'){Push(&top,ch);}printf("%d",sum(&top)); }。

第1章 绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。

．试分析下面各程序段的时间复杂度。

（1）O （1） （2）O （m*n ） （3）O （n 2） （4）O （log 3n ）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O （n 2） （6）O(n )第2章 线性表1．选择题．选择题babadbcabdcddac 2．算法设计题．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

ElemType Max (LinkList L ){if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值假定第一个结点中数据具有最大值 p=L->next->next;while(p != NULL ){//如果下一个结点存在if(p->data > pmax->data) pmax=p; p=p->next; }return pmax->data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。

的存储空间。

void inverse(LinkList &L) { // 逆置带头结点的单链表 Lp=L->next; L->next=NULL; while ( p) {q=p->next; // q 指向*p 的后继 p->next=L->next;L->next=p; // *p 插入在头结点之后 p = q; }}、空间(n)、空间（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)的数据元素。

复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

《数据结构（C语言版第2版）》（严蔚敏著）第三章练习题答案第3章栈和队列1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A．i B．n-i C．n-i+1 D．不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。

（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；答案：A解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。