数据结构第三章作业答案参考（C语言）

1. 经过以下栈运算后，x的值是（ ）。 InitStack(s); Push(s,'a'); Push(s,'b'); Pop(s,x); Gettop(s,x); A. a B. b C. 1 D. 0 2．循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。 A．rear=rear+1 B. rear=(rear+1) mod(m-1) C. rear=(rear+1)mod m D. rear=(rear+1) mod(m+1) 3. 栈和队列的共同点是（ ）。 A．都是先进先出 B．都是先进后出 C．只允许在端点处插入和删除元素 D．没有共同点 4. 若用一个大小为6的数组来实现循环队列，且当 rear 和 front 的值分别为 0 和 3。当从队列中删除一个元素，再插入两个元素后，rear 和 front 的值分别为：（ ）。 A．1 和 5 B．2 和 4 C．4 和 2 D．5 和 1 5. 程序填顺序循环队列的类型定义如下： typedef int ET; typedef struct{ ET *base; int Front; int Rear; int Size; }Queue; Queue Q; 队列 Q 是否“满”的条件判断为（ C ）。 A．(Q.Front+1)=Q.Rear B．Q.Front=(Q.Rear+1) C．Q.Front=(Q.Rear+1）% Q.size D．(Q.Front+1) % Q.Size=(Q.Rear+1）% Q.size 6. 若进栈序列为1，2，3，4，进栈过程中可以出栈，则（ ）不可能是一个出栈序列。 A．3，4，2，1 B．2，4，3，1 C．1，4，2，3 D．3，2，1，4 7. 向顺序存储的循环队列 Q 中插入新元素的过程分为三步： （ ）。 A．进行队列是否空的判断，存入新元素，移动队尾指针 B．进行队列是否满的判断，移动队尾指针，存入新元素 C．进行队列是否空的判断，移动队尾指针，存入新元素 D．进行队列是否满的判断，存入新元素，移动队尾指针 8. 关于栈和队列，（ ）说法不妥。 A. 栈是后进先出表 B. 队列是先进先出表 C. 递归函数在执行时用到栈 D. 队列非常适用于表达式求值的算符优先法 9. 若用数组S[0..m]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（ ）。 A．S1的栈底位置为0，S2的栈底位置为m B．S1的栈底位置为0，S2的栈底位置为m/2 C．S1的栈底位置为1，S2的栈底位置为m D．S1的栈底位置为1，S2的栈底位置为m/2 二、程序填空题（没特别标注分数的空的为3分，共 23 分）。 1.下面的算法是将一个整数e压入堆栈S，请在空格处填上适当的语句实现该操作。 typedef struct{ int *base; int *top; int stacksize; }SqStack; int Push(SqStack S,int e) { if ( S.top- S.base>= S.stacksize ) { S.base=(int *) realloc(S.base,(S.stacksize+1)*sizeof(int)); if( !S.base ) { printf(“Not Enough Memory!\n”); return(0);