《栈》作业 一、选择题 1. 对于栈操作数据的原则是（ ） A．先进先出 B．后进先出 C．后进后出 D．不分顺序 答案：B 解析：栈是一种遵循后进先出（LIFO, Last In First Out）原则的线性表。 2. 有6个元素按以下顺序进栈：6,5,4,3,2,1。下列哪个不是合法的出栈序列？ A．5 4 3 6 1 2 B．4 5 3 1 2 6 C．3 4 6 5 2 1 D．2 3 4 1 5 6 答案：C 解析：选项C破坏了栈的后进先出原则。 3. 在作进栈运算时，应先判别栈是否（）。在作退栈运算时应先判别栈是否（）。当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为（）。 A．空 / 满 / n1 B．满 / 空 / n C．空 / 空 / n+1 D．满 / 满 / n/2 答案：A 解析：进栈前需要检查栈是否已满，退栈前需要检查栈是否为空，栈的最大容量为元素数量加1。 4. 若已知一个栈的进栈序列是1,2,3,...,n，其输出序列为p1, p2, p3, ..., pn，若p1=3，则p2为（） A．可能是2 B．一定是2 C．可能是1 D．一定是1 答案：A 解析：由于p1=3，说明1和2仍在栈中，因此p2可能是2或1。 5. 设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（）。 A．2 B．3 C．5 D．6 答案：D 解析：考虑到出栈顺序的特点，栈中必须有足够的空间来存储所有未出栈的元素。 6. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A．|top[2]top[1]|=0 B．top[1]+1=top[2] C．top[1]+top[2]=m+1 D．top[1]=top[2] 答案：B 解析：当两个栈的栈顶相邻时，表示栈满了。 7. 执行完下列语句段后，i值为：int f(int x){return ((x>0) xf(x1):2);} int i; i=f(f(1)); A．2 B．4 C．8 D．无限递归 答案：B 解析：f(1)返回2，f(2)返回4。 8. 表达式3(2^(4+2263))5求值过程中当扫描到6时，对象栈和算符栈为（）。其中^为乘幂。 A．3,2,4,1,1；(^(+ B．3,2,8；(^ C．3,2,4,2,2；(^( D．3,2,8；(^( 答案：A 解析：根据表达式求值过程，扫描到6时，对象栈和算符栈的状态如选项A所示。 9. 用链接方式存储的队列，在进行删除运算时（）。 A．仅修改头指针 B．仅修改尾指针 C．头、尾指针都要修改 D．头、尾指针可能都要修改 答案：D 解析：删除运算时，可能需要同时修改头尾指针。 二、填空题 1. 在栈中，_____总是指向当前的栈顶元素。 答案：栈顶指针（或top） 解析：栈顶指针用于指示栈顶元素的位置。 2. 向顺序栈中压入元素时，应先将_____移动，然后再存入元素。 答案：栈顶指针（或top） 解析：顺序栈中，压入元素时需要先移动栈顶指针。 3. 如果元素的进栈序列是a,b,c,d,e，那么通过一个栈可以得到的不同排列个数是_____。 答案：13种（或阶乘数A_5^5） 解析：通过一个栈可以得到的不同排列个数等于元素的全排列数。 4. 循环队列的队满条件为_____。 答案：（rear+1）% maxsize == front % maxsize 解析：循环队列的队满条件涉及到队头和队尾指针的位置关系。 5. 若已知一个栈的入栈序列是1,234，则不可能的出栈序列是_____。 答案：3214（或其他不满足栈特性的序列） 解析：根据栈的特性，不可能出现3在2前面出栈的情况。 6. 在链式存储栈中，_____操作的时间复杂度为O(1)。 答案：入栈和出栈（或Push和Pop） 解析：链式存储栈的入栈和出栈操作只涉及指针的变化，时间复杂度为O(1)。 7. 若一个队列的入队序列是abcde，且队头指针指向a，则经过两次出队操作后，队头指针指向_____。 答案：c 解析：经过两次出队操作后，队头指针会向后移动两位，指向c。 8. 在双端队列中，_____可以在两端进行插入和删除操作。 答案：双端队列（或Deque） 解析：双端队列允许在两端进行插入和 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
