第三、四章 栈和队列、串答案[1].doc

第三章 栈和队列答案一、 基础知识题1、单选题（1）栈的插入和删除操作在 A 进行。A栈顶 B栈底 C任意位置 D指定位置（2）当利用大小为n的数组顺序存储一个栈时，假定用top= =n表示栈空，则向这个栈插入一个元素时首先应执行 B 语句修改top指针。Atop+ Btop- Ctop=0 Dtop（3）若让元素1，2，3依次进栈，则出栈次序不可能出现 C 种情况。A3，2，1 B2，1，3 C3，1，2 D1，3，2（4）在一个顺序存储的循环队列中，队头指针指向队头元素的 A 位置。A前一个 B后一个 C当前 D后面（5）当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为 B 。An-2 Bn-1 Cn Dn+1 （6）假定一个不带表头结点链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为 D 。Afront = = rear Bfront ! = NULL Crear! = NULL Dfront = = NULL 2、填空题（1）队列的插入操作在 队尾 进行，删除操作在 队头 进行。（2）栈又称为 后进先出 的表，队列又称为 先进后出 的表。（3）向一个顺序栈插入一个元素时，首先使 栈顶指针 后移一个位置，然后把待插入元素 写入 到这个位置上。（4）从一个栈删除一个元素时，需要前移一位 栈顶指针 。（5）在一个循环队列Q中，判断队空的条件为 Q.front = =Q. rear ，判断队满的条件为 Q. rear+1）% MaxSize+1= =Q. front 。（6）在一个顺序栈中，若栈顶指针等于 -1 ，则为空栈；若栈顶指针等于 MaxSize-1 ，则为满栈。（7）向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给 新结点的指针域 ，然后把新结点的存储位置赋给 栈顶指针 。（8）向一个循环队列中插入一个元素时，需要首先移动 队尾指针 ，然后再向所指位置 写入 新插入的元素。（9）当用长度为n的数组顺序存储一个栈时，若用top= =n表示栈空，则表示栈满的条件为 top=0 。（10）向一个栈顶指针为top的链式栈中插入一个新结点* p时，应执行 p-next=top 和 top=p 的操作。（11）从一个栈顶指针为top的非空链式栈中删除结点，并不需要返回栈顶的值和回收结点时应执行 top= top-next 的操作。（12）中缀表达式3*（x+2）-5所对应的后缀表达式为 3 x 2+ * 5 - 。（13）后缀表达式“45*32+-”的值为 15 。（14）设一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为多少？ 3二、 算法设计题1、 试写一个判断表达式中开、闭括号是否配对出现的算法。2、 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。void InitCiQueue(CiQueue &Q)/初始化循环链表表示的队列QQ=(CiLNode*)malloc(sizeof(CiLNode);Q-next=Q;/InitCiQueue void EnCiQueue(CiQueue &Q,int x)/把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q-next指向头结点,Q-next-next指向队头元素p=(CiLNode*)malloc(sizeof(CiLNode);p-data=x;p-next=Q-next; /直接把p加在Q的后面Q-next=p;Q=p;/修改尾指针 Status DeCiQueue(CiQueue &Q,int x)/从循环链表表示的队列Q头部删除元素xif(Q=Q-next) return INFEASIBLE; /队列已空p=Q-next-next;x=p-data;Q-next-next=p-next;free(p);return OK;/DeCiQueue 第四章 串一 算法设计题1、 编写对串求逆的递推算法。void String_Reverse(Stringtype s,Stringtype &r)/求s的逆串rStrAssign(r,); /初始化r为空串for(i=Strlen(s);i;i-)StrAssign(c,SubString(s,i,1);StrAssign(r,Concat(r,c); /把s的字符从后往前添加到r中/String_Reverse 2、 编写算法，求得所有包含在串s中而不包含在串t中的字符（s中重复的字符只选一个）构成的新串r，以及r中每个字符在s中第一次出现位置。void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)/求所有包含在串s中而t中没有的字符构成的新串rStrAssign(r,);for(i=1;i=Strlen(s);i+)StrAssign(c,SubString(s,i,1);for(j=1;ji&StrCompare