《软件技术基础》课件第4章.ppt

3．以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。

5．以下运算实现循环队列的初始化，请在________处用适当句子予以填充。

voidInitCycQueue(Cycqueue*sq)

{________________;

________________;sq-rear=0;

}

6．链队在一定范围内不会出现________________的情况。当lq-front==lq-rear时，称为________________。7．以下运算实现在链队上取队头元素，请在_______处用适当句子予以填充。

intGetFront(LinkQ*lq,DataType*x)

{LinkQ*p;

if(lq-rear==lq-front)return(0);

else{________________;

________________=p-data;

return(1);

}

}三、选择题

1．设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是()。

A.?2 B.?3 C.?5 D.?6

2．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()。

A.?edcba B.?decba C.?dceab D.?abcde

3．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()。

A.?edcba B.?decbaC.?dceabD.?abcde5．向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为()。

A.?Top-next=s

B.?s-next=Top-next;Top-next=s

C.?s-next=Top;Top=s

D.?s-next=Top;Top=Top-next

6．从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤为()。

A.?x=Top-data;Top=Top-next

B.?Top=Top-next;x=Top-data

C.?x=Top;Top=Top-next

D.?x=Top-data7．循环队列的入队操作应为()。

A.?sq.rear=sq.rear+1;sq.data[sq.rear]=x;

B.?sq.data[sq.rear]=x;sq.rear=sq.rear+1;

C.?sq.rear=(sq.rear+1)%maxsize;sq.data[sq.rear]=x;

D.?sq.data[sq.rear]=x;sq.rear=(sq.rear+1)%maxsize;

8．循环队列的队空条件为()。

A.?(sq.rear+1)%maxsize==(sq.front+1)%maxsize

B.?(sq.rear+1)%maxsize==sq.front+1

C.?(sp.rear+1)%maxsize==sq.front

D.?sq.rear==sq.front四、算法设计

1．回文是指从左向右读和从右向左读均相同的字符序列，如“level”是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈，然后出栈与另一半字符进行比较。)

2．借助栈(可用栈的基本运算)来实现单链表的逆置运算。

3．利用栈的基本运算将栈S中值为m的元素全部删除。4．假设一个算术表达式中包含三种括号：圆括号“(”和“)”，方括号“[”和“]”以及花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用，如(...[...{...}...[...]...]...

(...[...]...)。试利用栈的运算编写判断给定表达式中所含括号是否正确配对出现的算法intcorrect(exp)；其中exp为字符串类型的变量。如果括号正确配对，则返回值1；否则返回值0。(提示：对表达式