第三章栈、队列和数组.doc

第三章 栈、队列 一、名词解释： 1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队 二、填空题： 1、栈修改的原则是_________。在栈顶进行插入运算，被称为________，在栈顶进行删除运算，被称为________。 2、对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。 3、对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。 4、一般地，栈和线性表类似有两种实现方法，即________实现和________实现。 5、实现在顺序栈上的进栈，主要语句为_____________________________________。 6、实现在顺序栈上的退栈，主要语句为____________________________________。 7、实现在顺序栈上判栈空的条件为________________。 8、实现在顺序栈上取栈顶元素，主要语句为_____________________。 9、设一个链栈的栈顶指针为top，栈中结点的格式为 info， next,栈空的条件是_____________；如果栈不为空，则取栈顶操作为______________；退栈操作为______________,______________,______________；p进栈操作为______________，______________。 10、在队列中，新插入的结点只能添加到________，被删除的只能是排在______的结点。 11、实现在循环队上的入队列，主要语句为____________________________________。 12、实现在循环队上的出队列，主要语句为____________________________________。 13、实现在循环队上判队空的条件为____________________________________。 14、实现在循环队上取队头，主要语句为____________________________________。 15、链队在一定范围内不会出现___________的情况。当lq.front==lq.rear试，队中无元素。 16、实现在链队上的入队列，主要语句为____________________________________。 17、实现在链队上的出队列，主要语句为____________________________________。 18、实现在链队上判队空的条件为____________________________________。 19、实现在链队上读队头元素，主要语句为____________________________________。 20、栈和队列都是 结构；对于栈只能在 插入和删除元素；对于队列只能在 插入和 删除元素。 21、 是被限定为只能在表的一端进行插入运算，在表的另一端进行删??运算的线性表。 22、在具有n个单元的循环队列中，队满时共有 个元素。 23、向顺序栈中压入元素的操作是 ， 。 24、从循环队列中删除一个元素时， ， 。 三、判断 （ ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （ ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 （ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ ）5. 栈和链表是两种不同的数据结构。 （ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （ ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 四、单项选择题 1.以下说法正确的是 ( ) ①因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ②因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ③对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢” ④对于顺序栈而言在栈满状态下如果此时再作迸