《数据结构(C语言版第2版)》(严蔚敏著)第三章练习题答案

发布时间：2023-10-09 04:36:55 来源：文档文库

小中大

字号：

手机查看

《数据结构（C语言版第2版）》（严蔚敏著）
第三章练习题答案
第3章栈和队列
1．选择题
（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，1答案：C
解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的
后进先出原则，所以不可能出现C选项所示的情况。
（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。
A．iB．n-iC．n-i+1D．不确定答案：C
解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第
一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。
（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。
A．r-fB．(n+f-r%nC．n+r-fD．（n+r-f%n答案：D
解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值
可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f%n。
（4）链式栈结点为：(data,link，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。
A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；答案：A
解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即
摘除栈顶结点。
（5）设有一个递归算法如下intfact(intn{//n大于等于0if(n<=0return1;
elsereturnn*fact(n-1;}
则计算fact(n需要调用该函数的次数为（）。
A．n+1B．n-1C．nD．n+2答案：A
解释：特殊值法。设n=0，易知仅调用一次fact(n函数，故选A。
D．x=top->link；

（