2.5 课后练习

1.选择题

（1）若已知一个堆栈的入栈序列是1,2,3,…, n ，其出栈序列为 P ₁ , P ₂ , P ₃ ,…, P _n ，若 P ₁ 是 n ，则 P _i 是（ ）。（第七届NOIP提高组初赛选择题第13题）

A. i

B. n −1

C. n − i ＋1

D.不确定

（2）设堆栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，以下出栈序列不可能出现的有（ ）。（第十一届NOIP提高组初赛试题选择题第14题）

A.a,b,c,e,d,f,g

B.b,c,a,f,e,g,d

C.a,e,c,b,d,f,g

D.d,c,f,e,b,a,g

E.g,e,f,d,c,b,a

（3）某个车站呈狭长形，宽度只能容下一辆车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1,2,3,…，则车辆出站的顺序为（ ）。（第十届NOIP提高组初赛试题第3题）

A.1,2,3,4,5

B.1,2,4,5,7

C.1,3,5,4,6

D.1,3,5,6,7

E.1,3,6,5,7

（4）已知元素（8,25,14,87,51,90,6,19,20），问这些元素以怎样的顺序入栈，才能使出栈的顺序满足：8在51前面；90在87的后面；20在14的后面；25在6的前面；19在90的后面。（ ）（第九届NOIP提高组初赛试题第19题）

A.20,6,8,51,90,25,14,19,87

B.51,6,19,20,14,8,87,90,25

C.19,20,90,8,6,25,51,14,87

D.6,25,51,8,20,19,90,87,14

E.25,6,8,51,87,90,19,14,20

（5）设有一顺序栈S，元素S ₁ ,S ₂ ,S ₃ ,S ₄ ,S ₅ ,S ₆ 依次入栈，如果6个元素出栈的顺序是S ₂ ,S ₃ ,S ₆ ,S ₅ ,S ₄ ,S ₁ ，则该顺序栈的容量至少是（ ）。

A.2

B.3

C.4

D.5

2.最大矩形面积（网站题目编号：402007）

3.情感理论（网站题目编号：402008）

4.恒真式（网站题目编号：402009）

5.表达式的值（网站题目编号：402010）

参考答案：

1. 选择题

（1）C；（2）C，E；（3）E；（4）D；（5）C。 qxp+ArhO3s/fqJZduHOTCekKUI9HksURKuSKuuCUomrfAUCRQVqZXTXMY7e3e8yx