第三章 练习题-栈和队列

请同学按格式要求书写作业：

１. 作业本封面： 学号 ２. 每一章作业另起新页撰写； ３. 每一章抬头：第 × 章；

第三章 栈和队列

1.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 n-i+1 。

2.假设顺序栈的定义为：

typedef struct {

selemtype *base; /* 栈底指针*/ selemtype *top; /* 栈顶指针*/

int stacksize; /* 当前已分配的存储空间,以元素为单位*/ }sqstack;

变量st为sqstack型，则栈st为空的判断条件为 st.top==st.base; ，则栈st为满的判断条件为 st.top-st.base>=st.stacksize; 。

3．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) ，判断为空队列的条件是 ，为满队列的条件是 ；当队列非空时，若插入一个新的数据元素，则其队尾指针rear的变化是 ；当队列非满时，若删除一个数据元素，则其队头指针front的变化是 。

4. 设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答问题：若入栈次序为push(1)，pop()，push(2），push(3)，pop()，pop( )，push(4)，pop( )，则出栈的数字序列是什么？

5. 写出以下程序段的输出结果（队列中的元素类型QElemType 为char）。 Void main( ){

Queue Q; InitQueue(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); }

编程(在电脑上实现，不写到作业本上面)：循环队列采用第3种处理方法，即计数器的方法，判断对空和队满。函数：初始化，入队列，出队列，清空队列。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第三章 练习题-栈和队列在线全文阅读。