第三章+栈和队列(参考答案).doc

第三章 栈和队列一、判断题1、链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。 （ ）2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（ ）二、填空题1、向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给_栈顶指针_。2、迷宫问题是一个回溯控制的问题，最好使用_栈_的方法来解决。3、有如下递归过程：Void Print(int w) int i; if (w!=0) Print(w1);for (i=1;inext=R-next _；_ R-next=S _；R=S；三、选择题1、设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A 2 ，第二次出栈得到的元素是 B 4 ；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C 1 ，第二次出队得到的元素是 D 2 。经操作后，最后在栈中或队中的元素还有 E 2 个。供选择的答案：AD：a1a2 a3a4 E：12 3 02、 栈是一种线性表，它的特点是 A 2 。设用一维数组A1,n来表示一个栈，An为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B 2 ；从栈中弹出（POP）一个元素时，变量T的值 C 1 。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D 6 ，变量T的值是 E 4 。供选择的答案：A： 先进先出 后进先出 进优于出 出优于进 随机进出B，C： 加1减1不变清 加2减2D： a,bb,cc,ab,a c,ba,cE： n+1n+2 n n-1 n-23、在做进栈运算时，应先判别栈是否 A 2 ；在做退栈运算时，应先判别栈是否 B 1 。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 2 。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 4 分别设在这片内存空间的两端，这样，只有当 E 3 时，才产生上溢。供选择的答案：A，B：空 满 上溢 下溢C：n-1 n n+1 n/2D： 长度深度 栈顶 栈底E：两个栈的栈顶同时到达栈空间的中心点 其中一个栈的栈顶到达栈空间的中心点两个栈的栈顶在达栈空间的某一位置相遇 两个栈均不空，且一个栈的栈顶到达另一个栈的栈底4、 以下哪一个不是队列的基本运算？BA）在队尾插入一个新元素 B）从队列中删除第i个元素C）判断一个队列是否为空 D）读取队头元素的值四、综合题1、写出下列程序段的输出结果（栈的元素类型SElem Type为char）。void main( )kacStack S;char x,y;InitStack(S);x=c;y=k;Push(S,x);Push(S,a);Push(S,y);2、写出下列程序段的输出结果：（队列中的元素类型QElem Type为char）。void main( )Queue Q; Init Queue (Q);char x=e; y=c;EnQueue(Q,h); EnQueue (Q,r); EnQueue (Q,y);DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;printf(x);答：输出结果为:yhar3、简述以下算法的功能（栈和队列的元素类型均为int）。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d); ;while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 答：算法功能为：将队列Q中的整数逆置。4、有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？答：CDEBACDBEACDBAE5、假设带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。typedef struct QNode / 结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct / 链队列类型 QueuePtr rear; / 队尾指针 LinkQueue;Status InitQueue(LinkQueue &Q)Q.rear=(Queueptr)malloc(sizeof(QNode);If(!Q.rear) exit(-2);Q.rear-next=Q.rear;/构成循环链表Return 1;/初始化队列Status EnQueue(LinkQueue &Q,QElemType e)p=(QueuePtr)malloc(sizeof(QNode);If(!p) exit(-2)p-data=e;p-next=Q.rear-next;Q.rear-next=p;Q.rear=p;Return 1;/插入元素e到队尾Status DeQueue(LinkQueue &Q,QElemType &e)if(Q.rear-next=Q.rear) return -1;P=Q.rear-next-next;e=p-data;Q.rear-next-next=p-next;free(p);Return 1;/删除队首元素，并用e返回其值6、设顺序双向循环队列的数据结构定义为：typedef structDataType listMaxSize;int front; /*队头指针*/int rear; /*队尾指针*/ BSeqCQueue;设Q为BSeqCQueue类型的变参，并设初始化操作时有：Q-rear = Q-front = 0，现要求：（1）给出顺序双向循环队列满和空的条件。（2）给出顺序双向循环队列的入队列操作和出队列操作算法思想。解：顺序双向循环队列的数据类型已给出，要区分队空和队满，可采用少用一个存储空间的方式。故有，队空条件：Q-rear = Q-front 队满条件：(Q.rear+1) % MaxSize = Q.front(1)算法Status EnQueue(BSeqCQueue &Q,QElemType e)if(Q.rear+1) % MaxSize = Q.front) return -1;Q.listQ.rear=e;Q.rear=(Q.rear+1) % MaxSize;Return 1;/将元素e入队(2)算法Status DeQueue(BSeqCQueue &Q,QElemType &e)if(Q.front=Q.rearreturn -1;e=Q.listQ.front;Q.front=(Q.font+1) % MaxSize;Return 1;/将队首元素出队7、假设称正读和反读都相同的字符序列为“回文”，例如abba和abcba是回文，abcde和ababab则不是回文，试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。【解答】算法如下：int IsHuiWen()Stack *S;Queue *QChar ch,temp;InitStack(&S);InitQueue(&Q);Printf(“n请输入字符序列：”);ch=getchar();While( ch!=) /*序列入栈和队列*/Push(&S,ch);EnQueue(&Q,ch);ch=getchar();while(!IsEmpty(&S) /*判断序列正读和反读是否一致*/Pop(&S,&temp1);DeQueue(&Q,&temp2);if(temp1!= temp2) /*序列不等于逆序列*/ return(FALSE); printf(“nNO”); return(TRUE); printf(“nYES”); /*序列等于逆序列*/*IsHuiWen()*/8、要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】#define maxQSize 100Typedef structQElemType elementmaxQsize;Int front;Int rear;SeqQueue; Int tag;入队算法：int EnQueue(SeqQueue *Q, QElemType x) /*将元素x入队*/ if(Q.front=Q.front & Q.tag=1) /*队满*/ return(FALSE); if(Q.front=Q.front & Q.tag=0) /*x入队前队空，x入队后重新设置标志*/ tag=1;Q-elememtQ.rear=x;Q-rear=(Q.rear+1)%MAXSIZE; /*设置队尾指针*/Return(TRUE);出队算法：int DeQueue( SeqQueue *Q , QElemType *x) /*删除队头元素，用x返回其值*/if(Q.front=Q.rear & tag=0) /*队空*/return(FALSE);*x=Q.elementQ.front;Q.front=(Q.front+1)%MAXSIZE; /*重新设置队头指针*/if(Q.front=Q.rear) tag=0; /*队头元素出队后队列为空，重新设置标志域*/Return(TR