栈与队列习题参考答案.doc

《栈与队列习题参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、习题三参考答案备注:红色字体标明的是与书本内容有改动的内容。一、选择题1.在栈中存取数据的原则是（）。A．先进先出.先进后出.后进后出.没有限制．若将整数、、、依次进栈，则不可能得到的出栈序列是（）。．...．在链栈中，进行出栈操作时（）。．需要判断栈是否满.需要判断栈是否为空.需要判断栈元素的类型.无需对栈作任何差别．在顺序栈中，若栈顶指针指向栈顶元素的下一个存储单元，且顺序栈的最大容量是，则顺序栈的判空条件是（）。．.．在顺序栈中，若栈顶指针指向栈顶元素的下一个存储单元，且顺序栈的最大容量是。则顺序栈的判满的条件是（）。．.．在队列中存取数据元素的原则是（）。．先进先出

2、.先进后出.后进后出.没有限制．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，和分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为，则队列的判空条件是（）。．...()．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，和分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为，则队列的判满条件是（）。．...().在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，和分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个

3、存储单元，队列的最大存储容量为，则队列的长度是（）。．..().().设长度为的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度为（）。．()．()．()．()二、填空题1.栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除操作的一端称为栈顶，而另一端称为栈底。栈具有后进先出的特点。2.栈也有两种存储结构，一种是顺序存储，另一种是链式存储；以这两种存储结构存储的栈分别称为顺序栈和链栈。3.在顺序栈中，假设栈顶指针是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是;栈顶元素的访问形式是[];4.在不

4、带表头结点的链栈中，若栈顶指针直接指向栈顶元素，则将一个新结点入栈时修改链的两个对应语句为()；;。5.在不带表头结点的链栈中，若栈顶指针直接指向栈顶元素，则栈顶元素出栈时的修改链的对应语句为();。6.队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为队尾，允许删除的一端称为队首。队列具有先进先出的特点。1.由于队列的删除和插入操作分别在队首和队尾进行，因此，在链式存储结构描述中分别需要设置两个指针分别指向队首结点和队尾结点，这两个指针又分别称为队首指针和队尾指针。8.循环顺序

5、队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的求模（或取余）运算来实现的。9.在循环顺序队列中，若规定当时，循环队列为空；当()时，循环队列为满，则入队操作时的队尾指针变化的相应语句是()；出队操作时的队首指针变化的相应语句是()。10.无论是顺序栈还是顺序队列，插入元素时必须先进行栈或队列是否为满的判断，删除元素时必须先进行栈或队列是否为空的判断；而链栈或链队列中，插入元素无需进行栈或队列是否为满的判断，只要在删除元素时先进行栈或队列是否为空的判断。三、算法设计题1.编写一个函数，要求借助一个栈把一个数组中的数据元素逆置。参考答案:借助一个

6、顺序栈将已知一个数组中的数据元素逆置([]){();构造一个容量为的顺序栈(<)([]);(<)[]();}2.编写一个函数判断一个字符序列是否为回文序列，所谓回文序列就是正读与反读都相同的字符序列，例如：和均是回文序列。要求只使用栈来实现。参考答案:判断字符序列是否为回文序列,若是则返回值,否则返回。(){();;(;<();)(());(;<();){(()())();(());};}3.假设以一个数组实现两个栈：一个栈以数组的第一个存储单元作为栈底，另一个栈以数组的最后一个存储单元作为栈底,这种栈称为顺序双向栈。试编写一个顺序双向栈类，类中要求编写个方法。一个是构造方

7、法(),此方法实现构造一个容量为的顺序双向空栈；一个是实现入栈操作的方法(),此方法完成将数据元素压入到第(或)号栈中的操作；一个是实现出栈操作的方法（),此方法完成将第号栈的栈顶元素出栈的操作。参考答案:{[];栈存储空间;栈顶指针,指示第号的栈顶元素的下一个位置;栈顶指针,指示第号的栈顶元素的下一个位置栈尾指针,指示第号的栈底元素栈尾指针,指示第号的栈底元素构造方法(){初始化栈,即构造一个双向空栈[]为栈分配个存储单元;;}入栈操作方法(,){将数据元素压入到第(的值为或)号栈中(>)栈满("栈已满")抛出异