第三章 栈和队列习题答案 - 试题.docx

结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，>top0=-1;S->top1=StackSize;// 结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数， >top0=-1;S->top1=StackSize;//这 中结点个数的算法intStackSize(SeqStackS 1234,1243,1324,1342,1432,2134, 第三章 栈和队列习题答案 一、基础知识题 3.1 设将整数 1，2，3，4 依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中， 请回答下述问题： (1)若入、出栈次序为 Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Po )出,栈的数字 序列为何(这里 Push(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。因为是循环链表，尾 指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1 (2) SeqStack S1, S2, tmp; DataType x; ...//假设栈tmp 和 S2 已做过初始化 while ( ! StackEmpty (&S1)) {x=Pop(&S1) ; Push(&tmp,x); 是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出算法voidClearStack(SeqStack*S)，并中只设 是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出 算法voidClearStack(SeqStack*S)，并 中只设rear和quelen来分别指示队尾元素的位置和队中元 &T)){i=Pop(&T);Push(S,i);}}(4) while ( ! StackEmpty (&tmp) ) {x=Pop( &tmp); Push( &S1,x); Push( &S2, x); } (3) void Demo2( SeqStack *S, int m) { // 设 DataType 为 int 型 S