pre->next=s;} }
else/*处理奇数链
if (q==NULL) {q=s;q->next=NULL;} /*第一奇数结点*/ else
{pre=q;
if (pre->data>s->data) {s->next=pre; q=s;} /*修改头指针*/ else
{while (pre->next!=NULL) /*查找插入位置*/ if (pre->next->data
第3章 桟和队列
3.1 选择题
1．一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是（ ）
A）不确定 B）n-i+1 C）i D）n-i 【答案】B
【解析】根据栈的性质（LIFO），若输出的第一个元素是n，则表明所有的元素已经入栈，则出栈顺序为n，n-1， ?，3，2，1。
2．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（ ）
A）6 B）4 C）3 D）2 【答案】C
【解析】根据栈的性质（LIFO）得，e2出栈前，栈中存有e1和e2两个元素，e4出栈前，栈中存有e1、e3和e4三个元素，e4和e3出栈以后，e5和e6入栈，栈中同样存在e1、e5和e6三个元素，然后三个元素依次出栈，所以栈的容量至少应该为3。
3．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（ ） A）top=top+1; V[top]=x B）V[top]=x; top=top+1 C）top=top-1; V[top]=x D）V[top]=x; top=top-1 【答案】C 【解析】栈式运算受限的线性表，只允许在栈顶进行插入和删除操作。本题中栈顶指针为n+1，该数组将栈顶放在了下标大的一端，所以在进行入栈操作时top指针应该进行减一操作。通常元素进栈的操作为：先移动栈顶指针后存入元素。
4．如果我们用数组A[1..100]来实现一个大小为100的栈，并且用变量top来指示栈顶，top的初值为0，表示栈空。请问在top为100时，再进行入栈操作，会产生（ ） A）正常动作 B）溢出 C）下溢 D）同步 【答案】B
【解析】当top为100时，表示栈已经满了，此时再进行入栈操作，则会造成溢出。
5．栈在（ ）中应用。
11
A）递归调用 B）子程序调用 C）表达式求值 D）A，Ｂ，Ｃ 【答案】D
7．用链接方式存储的队列，在进行删除运算时（ ） A）仅修改头指针 B）仅修改尾指针
C）头、尾指针都要修改 D）头、尾指针可能都要修改 【答案】D
【解析】若队列中的元素多于一个，删除队列中的队尾元素，只需修改队尾指针；若队列中只有一个元素，删除该元素后，队头队尾指针都需要修改。
8．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )
A）(rear-front+m)%m B）rear-front+1 C）rear-front-1 D）rear-front 【答案】A
【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的求元素个数的运算可以利用求模运算。
9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A）1和 5 B）2和4 C）4和2 D）5和1 【答案】B
【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。所以入队和出队时的操作分别为：rear=(rear+1)%m，front=(front+1)%m。
10．栈和队列的共同点是（ ）
A）都是先进先出 B）都是先进后出 C）只允许在端点处插入和删除元素 D）没有共同点 【答案】C
【解析】栈和队列都是运算受限的线性表，只允许在表端点处进行操作。 11．在一个链队列中，假定front和rear分别为队头和队尾指针，则插入*s结点的操作为（ ） A）front->next=s;front=s; B）s->next=rear;rear=s; C）rear->next=s;rear=s; D）s->next=front;front=s; 【答案】C
【解析】队列是运算受限的线性表（FIFO），插入元素只能插在队尾，所以需修改队尾指针。
12．判定一个栈S（元素个数最多为MAXSIZE）为空和满的条件分别为（ ） A）S->top!=-1 S->top!=MAXSIZE-1 B）S->top=-1 S->top=MAXSIZE-1 C）S->top=-1 S->top!=MAXSIZE-1 D）S->top!=-1 S->top=MAXSIZE-1 【答案】B
3.2 填空题
1．栈是_____________的线性表，其运算遵循_____________的原则。 【答案】（1）操作受限（或限定仅在表尾进行插入和删除操作） （2）后进先出
2．设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_____________，而栈顶指针值
12
是_____________H。设栈为顺序栈，每个元素占4个字节。 【答案】（1）23 （2）100CH
【解析】PUSH为入栈操作，POP为出栈操作。根据栈的性质，经过PUSH,PUSH,POP运算之后，栈中存在元素1，输出数据为2，然后经过PUSH,POP，3入栈，3出栈，然后经过PUSH,PUSH之后4，5入栈，此时出栈序列为2，3，栈中元素为1，4，5；每个元素占4个字节，所以栈顶指针的值为1000H+3*4=100CH（十六进制数）
3．循环队列的引入，目的是为了克服_____________。 【答案】假溢出时大量移动数据元素。
4．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_____________。 【答案】先进先出
5．已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_____________。 【答案】
s=(LinkList)malloc(sizeof(LNode)); s->data=x;
s->next=r->next; r->next=s; r=s;
【解析】根据队列的性质，新插入的元素永远插在队尾。
8．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M=_____________。 【答案】(M+1)% N；
【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。
9．当两个栈共享一存储区时，栈利用一维数组stack[1..n]表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_____________，栈2空时，top[2]为_____________，栈满时为_____________。 【答案】（1）0 （2）n+1 （3）top[1]+1=top[2]
【解析】为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的栈底分别设在这片内存空间的两端,这样,当两个栈的栈顶在栈空间的某一位置相遇时，才产生上溢，即top[1]+1=top[2]。
10．在作进栈运算时应先判别栈是否_____________；在作退栈运算时应先判别栈是否 _____________；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_____________。
为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____________分别设在内存空间的两端，这样只有当______________时才产生溢出。 【答案】（1）满 （2）空 （3）n （4）栈底 （5）两栈顶指针相邻 13．无论对于顺序存储还是链式存储的栈和队列来说，进行插入和删除运算的时间复杂度均相同为_____________。 【答案】O(1)
【解析】对于栈用栈顶指针表示栈顶，而栈的插入和删除操作均在栈顶进行。对于队列用队头和队尾指针分别表示允许插入和删除的一端。
14．在顺序队列中，当尾指针等于数组的上界，即使队列不满，再作入队操作也会产生溢出，这种现象称为_____________。
13
【答案】假溢出
【解析】产生该现象的原因是，被删元素空间在该元素被删除后就永远得不到使用。为了克服这种现象，采用循环队列来实现。
3.5 程序设计题
1．设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。)
【算法分析】判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。 【算法源代码】 int EXYX (char E[]){
/*E[]存放字符串表达式，以‘#’结束*/
char s[30]; /*s是一维数组，容量足够大，用作存放括号的栈*/ int top=0,i; /*top用作栈顶指针*/
s[top]='#'; /*‘#’先入栈，用于和表达式结束符号‘#’匹配*/ i=0; /*字符数组E的工作指针*/
while(E[i]!='#') /*逐字符处理字符表达式的数组*/ switch (E[i])
{case '(': s[++top]= '('; i++ ; break ;
case ')': if(s[top]=='('){top--; i++; break;}
else{printf(\括号不配对\ case '#': if(s[top]=='#'){printf(\括号配对\\n\
else {printf(\括号不配对\\n\括号不配对*/ default : i++; /*读入其它字符，不作处理*/ }
}/*算法结束*/
2．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。 【算法分析】
根据队列的先进先出的性质，队列的入队操作在队尾进行，出队操作在队头进行。而题目所采用的数据结构是只设一个尾指针的循环链表。我们可以根据循环链表的特点找到头指针。 【算法源代码1】
void EnQueue (LinkList rear, ElemType x)
/* rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾*/ { s=(LinkList)malloc(sizeof(LNode)); /*申请结点空间*/
s->data=x; s->next=rear->next; /*将s结点链入队尾*/ rear->next=s; rear=s; /*rear指向新队尾*/ }
【算法源代码2】
void DeQueue (LinkList rear)
/* rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息*/
{ if(rear->next==rear) {printf(\队空\\n\
s=rear->next->next; /*s指向队头元素*/ rear->next->next=s->next; /*队头元素出队*/ printf (\出队元素是:%d\
if(s==rear) rear=rear->next; /*空队列*/ free(s); }
14
3．设整数序列a1，a2，?，an，给出求解最大值的递归程序。 【算法分析】根据题意，本题的函数定义为：
a[1] n=1 maxvalue(a,n)= a[n] a[n]>maxvalue(a,n-1)
maxvalue(a,n-1) a[n] int MaxValue (int a[],int n) /*设整数序列存于数组a中，共有n个，本算法求解其最大值*/ {int max; if (n==1) max=a[1]; else if (a[n]>MaxValue(a,n-1)) max=a[n]; else max=MaxValue(a,n-1); return(max); } 4．试将下列递归函数改写为非递归函数。 void test(int *sum) { int x; scanf(\if(x==0) *sum=0 ; else {test(&sum); (*sum)+=x;} printf(\} 【算法分析】 该函数是以读入数据的顺序为相反顺序进行累加问题，可将读入数据放入栈中，等输入结束时，将栈中数据退出进行累加。累加的初值为0。 【算法源代码】 int test() { int x,sum=0,top=0,s[30]; scanf(\while (x!=0) {s[++top]=a; scanf(\printf(\while (top) {sum+=s[top--]; printf(\ } 5．编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。 【算法分析】 利用两个临时栈s1和s2。先将s栈中的内容移到s1栈中，再将s1栈中的内容移到s2栈中，最后将s2栈中的内容移到s栈中，即可实现。 【算法源代码】 reverse(SqStack *s) {SqStack *s1,*s2; /*s,s1,s2均为栈类型 ElemType x; /*栈中元素的类型，用于存储从栈中取出元素的临时变量*/ initstack(s1); /*栈的初始化*/ initstack(s2); while(!stackempty(s)) /*如果栈不空，将s栈中的内容移到s1栈中*/ {pop(s,x); /*取栈顶元素放入变量x中*/ push(s1,x); /*将变量x入栈*/ } while(!stackempty(s1)) /*如果栈不空，将s1栈中的内容移到s2栈中*/ 15