第三章栈和队列习题答案

第三章 栈和队列习题答案 一、基础知识题 3.1 设将整数 1，2，3，4 依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为 Pu sh(1), Pop(),Pu sh(2),Pu sh(3), Pop(), Pop( ),Pu sh(4), Pop( ),则出栈的数字序列为何(这里 Pu sh(i)表示 i 进栈，Pop( )表示出栈)? (2)能否得到出栈序列1423 和1432?并说明为什么不能得到或者如何得到。 (3)请分析 1，2 ，3 ，4 的 24 种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答：(1)出栈序列为：1324 (2) 不 能 得 到1423序 列。 因 为 要 得 到14的 出 栈序 列， 则 应 做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3 在栈顶，2 在栈底，所以不能得到 23 的出栈序列。能得到 1432 的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 (3)在 1，2 ，3 ，4 的 24 种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 3.2 链栈中为何不设置头结点? 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 3.3 循环队列的优点是什么? 如何判别它的空和满? 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少 用一个 元 素 的空间,每 次入队前 测 试 入队后头尾指针是否会 重 合 ，如果会 重 合 就认 为队列已 满。三是设置一计 数器 记 录 队列中元 素 总 数，不仅 可判别空或满，还 可以得到队列中元 素 的个 数。 3.4 设长 度 为 n 的链队用单 循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢 ? 答：当 只设头指针时，出队的时间为 1，而入队的时间需要 n，因为每 次入队均 需从 头指针开 始 查 找 ，找 到最 后一个 元 素 时方可进行入队操作。若只设尾指针，则出入队时间均 为 1。因为是循环链...