《数据结构》第三章习题参考答案 殷人昆版

， 《数据结构》第三章习题参考答案

一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）

1、栈和队列都是线性表，只是在插入和删除时受到了一些限制。( √ ) 2、循环队列也存在空间溢出问题。( √ )

3、任何一个递归过程都可以转换成非递归过程。( √ ) 4、消除递归不一定需要使用栈。( √ )

5、有n个数顺序（依次）进栈，出栈序列有Cn种，Cn=(1/（n+1）)*（2n）!/((n!)*(n!))。（ √ ）

6、循环队列方式能很好地解决队列的假溢出现象。（ √ ）

二、单项选择题

1、1．设有一个顺序栈S，元素P1，P2，P3，P4，P5，P6依次进栈，得到的出栈顺序P2，

P3，P4，P6，P5，P1，则顺序栈的容量至少为（ B ）。 A．2 B．3 C．4

D．无法确定

2．一个队列的输出序列是1，2，3，4，则队列的入队序列是（ A ）。

A．1，2，3，4 B．1，4，3，2 C．4，3，2，1 D．不确定

3、对于一个循环队列（最大元素个数为maxSize）进行入队操作时，对队列指针的修改

正确的语句是（ C ）。

A．rear = rear + 1 B．front = front + 1

C．rear = (rear + 1)% maxSize D．front = (front + 1)% maxSize

4、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。

A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m

5、表达式a*(b+c)-d的后缀表达式是( B )。 A．abcd*+- 表达式[a-（c*d+b）] B. abc+*d- C. abc*+d- 表达式b*c+a-d D. -+*abcd

6、

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分

别为多少？( B )

A. 1和 5 B. 2和4 C. 4和2 D. 5和1

7、设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为 （ D ）。 A．fedcba B. bcafed C. dcefba D. cabdef

三、填空题

1、一个栈的输入序列是：1，2，3则不可能的栈输出序列是_3,1,2____。

2、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_SXSSXSXX_____。

3、循环队列的引入，目的是为了克服 假溢出时大量移动数据元素 。

4、顺序栈的类声明如下，试：

1、填空完成进栈（push）和出栈(pop)函数的代码。 2、填空完成利用栈编写一个将十进制数Ｎ转换为另一基为Ｂ的Ｂ进制数的算法。

template template

class SeqStack{ void SeqStack :: Push(const T& x) { public：

SeqStack(); if(__IsEmpty()==true__) return; ~SeqStack(){delete []elements;}

elements[_++top__]=x; void Push(const T& x) ; //进栈

bool Pop(T& x) ; //出栈

}

bool IsEmpty()const //判断栈空 {return (top==-1)?true:false;} template bool IsFull()const //判断栈满

bool SeqStack :: Pop(T& x) {

{return (top==maxSize-1)?true:false;} private： if(_IsEmpty()==true __) return false; T* elements; //栈数组

x = _ elements[_top--__]__; int top; //栈顶指针

int maxSize; //栈最大可容纳元素个数 return true; };

}

//输入非负十进制整数，打印其B进制数 void ConversionData_10toB( ){

SeqStack S; int n,x;

cout << “输入一个十进制数：”;

cin>>n;

while(n){

S.Push(__n%B___);

四、综合题

1、计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈S1中，运算符放入栈S2中，但每次扫描到运算符时，要把它同S2的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符的优先级时，取出栈S1的栈顶和次栈顶的两个元素，以及栈S2的栈顶运算符进行运算将结果放入栈S1中（得到的结果依次用T1、T2等表示）。为方便比较，假设栈S2的初始栈顶为?（?运算符的优先级低于加、减、乘、除中任何一种运算）。现假设要计算表达式： A-B*C/D+E/F。写出栈S1和S2的变化过程。

【解答】

步骤 初始 1 2 3 4 5 6 7 8 栈S1 A A AB AB ABC AT1（注：T1=B*C） AT1D AT2（注：T2=T1/D） T3 （注：T3=A-T2） T3E T3E T3EF T3T4（注：T4=E/F） 栈S2 ???- ?- ?-* ?-* ?-/ ?-/ ?- 9 10 11 12 ?+ ?+ ?+/ ?+/ ?+ T5（注：T5= T3+ T4） ?

2、课本P131 3.1题

【解答】

（1）可能的不同出栈序列有

1 1?6C126=132种。(出栈序列为catalan数列)

（2）不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。

3、课本P131 3.2题

【解答】

因为借助栈由输入序列1, 2, 3, ?, n，可得到输出序列p1, p2, p3, ?, pn ，如果存在下标i, j, k，满足i < j < k，假设在输出序列中，出现pj < pk < pi的情形，则说明pj 出栈前pk 和 pi都已进栈，且留在栈中。由栈后进先出的性质可知，在栈中pk必然盖住pj，pk不出栈pj不可能出栈，pj出栈也不可能得到pj < pk的序列；

4、课本P131 3.3题

【解答】

由出栈序列可知栈中元素最多时有s1,s5,s6在栈中，所以栈的容量至少为3

5、课本P132 3.10题

【解答】

void List::Inverse (){

ListNode* p = first->link; Stack< ListNode*> S; while(p!=NULL){

S.Push(p); p = p->link; }

ListNode* q = first; while(!S.IsEmpty()){ S.Pop(p); q->link = p; q = q->link;

}

q->link = NULL; }

6、课本P132 3.12题

【解答】

void conversion( ){ //输入非负十进制整数，打印其B进制数 Stack S; int n,x;

cin>>n;

while(n){

S.Push(n%B); n=n/B; }

while(!S.IsEmpty()){ S.Pop(x);

cout<

} }

7、课本P132 3.13题

【解答】

//括号匹配算法，匹配成功返回1，否则返回零；输入参数为字符串顺序表 int CheckPairofBracket (SeqList str){ Stack s,temp;

for(int i = 0; i < str.GetSize(); i++){

if(str [i]==’(’|| str [i]==’{’|| str [i]==’[’)

s.Push(str [i]); else if(str [i]==’)’) {

if(s.GetTop()==’(’) s.Pop(temp); else return 0; }

else if( str [i]==’]’) {

if(s.GetTop()==’ [ ’) s.Pop(temp); else return 0; }

else if( str [i]==’ }’) {

if( s.GetTop()==’ { ’) s.Pop(temp); else return 0; }

}

if(s.IsEmpty())

return 1; else return 0;

}

8、课本P134 3.25题

【解答】

typedef Struct{

LinkNode* p; } CycleQueue;

void EnQueue(CycleQueue& Q, T & x){ LinkNode* s = new LinkNode(x); if(Q.p==NULL) //队列为空 {

Q.p = s;

Q.p->link =s; } else{

s->link = Q.p->link; Q.p->link = s; Q.p = s; } }

略……