数据结构及应用算法教程习题第三章 排序

第三章习题1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。

（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。

2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。

如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。

直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’模式的字符序列。

其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。

例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。

6.假设表达式由单字母变量和双目四则运算算符构成。

试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。

7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。

9.简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ int i, n, A[255];n=0;while(!EmptyStack(S)){n++; Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}（2）void proc_2(Stack S, int e) { Stack T; int d;InitStack(&T);while(!EmptyStack(S)){ Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){ Pop(&T, &d);Push( &S, d);}}（3）void proc_3(Queue *Q){ Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){ Pop(&S, &d);EnterQueue(Q，d)}}实习题1．回文判断。

第三章栈和队列部分答案解释如下。

1、尾递归的消除就不需用栈2、这个数是前序序列为1,2,3,…,n，所能得到的不相似的二叉树的数目。

三、填空题1、操作受限（或限定仅在表尾进行插入和删除操作）后进先出2、栈3、3 1 24、23 100CH5、0 n+1 top[1]+1=top[2]6、两栈顶指针值相减的绝对值为1（或两栈顶指针相邻）。

7、(1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻（即值之差的绝对值为1）8、链式存储结构 9、S×SS×S×× 10、data[++top]=x；11、23.12.3*2-4/34.5*7/++108.9/+（注：表达式中的点(.)表示将数隔开，如23.12.3是三个数）12、假溢出时大量移动数据元素。

13、(M+1) MOD N (M+1)% N； 14、队列 15、先进先出 16、先进先出 17、s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s；r=s；18、牺牲一个存储单元设标记19、（TAIL+1）MOD M=FRONT (数组下标0到M-1，若一定使用1到M，则取模为0者，值改取M20、sq.front=(sq.front+1)%(M+1)；return(sq.data(sq.front))；(sq.rear+1)%(M+1)==sq.front；21、栈 22、（rear-front+m）% m； 23、（R-P+N）% N；24、（1）a[i]或a[1] （2）a[i] （3）pop（s）或s[1]；25、（1）PUSH（OPTR，w）（2）POP（OPTR）（3）PUSH（OPND，operate（a，theta，b））26、（1）T>0（2）i<n（3）T>0（4）top<n（5）top+1（6）true（7）i-1（8）top-1（9）T+w[i]（10）false四、应用题1、栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。

第三章习题1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。

（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。

2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。

如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。

直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’模式的字符序列。

其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。

例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。

6.假设表达式由单字母变量和双目四则运算算符构成。

试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。

7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。

9.简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ int i, n, A[255];n=0;while(!EmptyStack(S)){n++; Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}（2）void proc_2(Stack S, int e){ Stack T; int d;InitStack(&T);while(!EmptyStack(S)){ Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){ Pop(&T, &d);Push( &S, d);}}（3）void proc_3(Queue *Q){ Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){ Pop(&S, &d);EnterQueue(Q，d)}}实习题1．回文判断。

数据结构第三章的习题答案数据结构第三章的习题答案在学习数据结构的过程中，习题是巩固知识和提高能力的重要方式。

第三章的习题主要涉及线性表、栈和队列的实现和操作。

本文将对这些习题进行解答，并给出详细的步骤和思路。

1. 第一题要求实现一个线性表的插入操作。

线性表是一种常用的数据结构，它的特点是元素之间存在一对一的关系。

要实现插入操作，首先需要定义线性表的数据结构，可以使用数组或链表来实现。

然后，根据插入位置，将插入位置之后的元素依次后移，为要插入的元素腾出空间。

最后，将要插入的元素放入插入位置。

2. 第二题要求实现一个栈的压栈和出栈操作。

栈是一种后进先出（LIFO）的数据结构，可以使用数组或链表来实现。

压栈操作就是将元素放入栈顶，出栈操作就是将栈顶元素取出并删除。

要实现这两个操作，可以使用一个指针来指示栈顶位置，每次压栈时将指针加一，出栈时将指针减一。

需要注意的是，栈满时不能再进行压栈操作，栈空时不能进行出栈操作。

3. 第三题要求实现一个队列的入队和出队操作。

队列是一种先进先出（FIFO）的数据结构，同样可以使用数组或链表来实现。

入队操作就是将元素放入队尾，出队操作就是将队头元素取出并删除。

与栈不同的是，队列需要维护队头和队尾两个指针。

每次入队时将元素放入队尾，并将队尾指针后移一位；出队时将队头元素取出，并将队头指针后移一位。

需要注意的是，队列满时不能再进行入队操作，队列空时不能进行出队操作。

4. 第四题要求实现一个栈的括号匹配算法。

括号匹配是一种常见的应用场景，例如编程语言中的括号匹配。

要实现这个算法，可以使用栈来辅助。

遍历字符串中的每个字符，如果是左括号，则将其压入栈中；如果是右括号，则将栈顶元素取出并判断是否与右括号匹配。

如果匹配，则继续遍历下一个字符；如果不匹配，则说明括号不匹配，返回错误。

最后，如果栈为空，则说明括号匹配成功；如果栈不为空，则说明括号不匹配，返回错误。

5. 第五题要求使用栈实现一个逆波兰表达式的计算器。

第3章栈和队列一、填空题1、栈是限定仅在表尾进行插入或删除操作的线性表。

2、栈的修改是按照后进先出的原则进行的。

3、队是一种先进先出的线性表。

4、把队列头尾相接的顺序存储结构称为循环队列。

5、队列也是一种操作受限的线性表，允许插入的一端叫做__队尾___，允许删除的一端叫做__队头__。

二、判断题1、栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。

（√）2、任何一个递归过程都可以转换成非递归过程。

（√）3、若输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列3,2,5,6,4,1。

（√）4、通常使用队列来处理函数的调用。

（╳）5、循环队列通常用指针来实现队列的头尾相接。

（╳）三、单项选择题1、若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（C）种情况。

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选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

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

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

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

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

数据结构第三章习题本文共分为三部分，分别针对数据结构第三章中的不同习题进行解答。

第一部分，解答关于树和二叉树的习题。

1.对于给定的有“n(n>0)”个结点的树，边数应为“n-1”条。

解析：树是一种无环连通无向图，因此任意n个结点的树有n-1条边。

2.往2（2≤n≤64）叉树的每个结点上添加一个数据元素，设计一个数据结构，实现迅速求该2叉树中所有结点的数据元素之和。

解析：可以使用先序遍历算法来完成，先序遍历树的根节点，然后递归遍历左子树和右子树，将每个结点的数据元素加和。

3.设计一个算法，判定给定的二叉树是否是完全二叉树。

解析：可以使用层次遍历算法来判定。

如果一棵树是完全二叉树，那么层次遍历结果中，如果一些结点有右孩子，那么该结点之后的所有结点都必须有孩子；如果一些结点没有右孩子，则该结点之后的所有结点都不能有孩子。

4.设有一棵完全二叉树，编写算法，生成一棵采用二叉链表存储结构的二叉树。

解析：可以使用层次遍历算法来构建树。

从根节点开始，依次按层次遍历的顺序遍历所有结点，依次将结点和它的孩子结点用链表链接起来。

第二部分，解答关于图的习题。

1.利用邻接表存储图，写出一个算法，判断两个节点之间是否存在路径。

解析：可以使用深度优先算法或广度优先算法来判断两个节点之间是否存在路径。

首先从起始节点开始，遍历其邻接节点，递归或使用队列来保存需要遍历的节点，直到遍历到目标节点或遍历完所有的节点。

2.利用邻接表存储图，写出一个算法，求图的连通分量个数。

解析：可以使用深度优先算法或广度优先算法来求图的连通分量个数。

首先从起始节点开始，遍历其邻接节点，标记遍历过的节点，直到遍历完所有的节点。

每次从一个未标记的节点开始进行遍历，当所有的节点都被遍历过后，即可得到图的连通分量个数。

3.利用邻接表存储图，写出一个算法，判断给定的图是否为无向图。

解析：可以遍历所有的边，对于每一条边(u,v)，如果(u,v)存在，则判断(v,u)是否存在，如果都存在，则图为无向图，否则为有向图。

严蔚敏《数据结构（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);} // 算法结束。

选择题第3章线性表的链式存储（1）两个有序线性表分别具有n个元素与m个元素且n≤m，现将其归并成一个有序表，其最少的比较次数是（ A ）。

A．n B．m C．n− 1D．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->next; while (p && p->info!=x) p=p->next;if (p->info==x) return p else return NULL;B．node *p=head; while (p&& p->info!=x) p=p->next; return p;C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p;D．node *p=head; while (p->info!=x) p=p->next ; return p;（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。

A．必须是连续的C．一定是不连续的B．部分地址必须是连续的D．连续不连续都可以（5）在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（ B ）。

A．O(1) B．O(n)C．O(n2)D．O(n log2n)（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（D ）。

A．仅修改队头指针C．队头、队尾指针都要修改B．仅修改队尾指针D．队头,队尾指针都可能要修改（7）若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（ B ）。

习题答案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;}。