为了方便下面表述,仅能进行入队操作...
为了方便下面表述,仅能进行入队操作的一端称为A端,既能进行入队操作又能进行出队操作的一端称为B端。
方法一:模拟
按照a, b, c, d, e依次入队的顺序进行模拟。
A选项:a从A端入队,b从B端入队,c从A端入队,d从A端入队,e从A端入队,b, a, c, d, e依次从B端出队。
B选项:a从A端入队,b从B端入队,c从A端入队,d从B端入队,e从A端入队,d, b, a, c, e依次从B端出队。
C选项:a从A端入队,无法继续执行,错误。
D选项:a从A端入队,b从B端入队,c从B端入队,d从A端入队,e从B端入队,e, c, b, a, d依次从B端出队。
本题选C。
方法二:栈+队列
某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,这是一个输出受限的双端队列,当然命题组为了降低难度,没有给出专业术语,根据描述就知道如何操作,这样就是一个一个模拟。
当然,由于这个双端队列两端都能操作,模拟难度极大,这时候我们需要进行简化。
简化思路一:既能进行入队操作又能进行出队操作的一端视为一个完整的栈,仅能进行入队操作的一端用于插入元素。即简化为栈+插入。
栈是先进后出的数据结构,如果所有元素入栈后出栈,得到的是输入序列的逆序序列。
简化思路二:仅能进行入队操作的一端视为队列的尾部,既能进行入队操作又能进行出队操作的一端中具有出队功能的部分视为队列的头部,这样得到一个完整的队列,既能进行入队操作又能进行出队操作的一端中具有入队功能的部分用于插入元素。即简化为队列+插入。
队列是先进先出的数据结构,得到的是输出序列与输入序列一致。
由于这道题要求元素全部入队后进行操作,可以简化为栈+队列。如图(a)所示。
栈部分的子序列先出队,形成一个逆序子序列,队列部分的子序列后出队,形成一个顺序子序列。如图(b)所示。
A选项:a, c, d, e是a, b, c, d, e的顺序子序列,a, c, d, e从A端入队,b是a, b, c, d, e的逆序子序列,b从B端入队,得到序列为 b,a,c,d,e 。正确。
B选项:a, c, e是a, b, c, d, e的顺序子序列,a, c, e从A端入队,d, b是a, b, c, d, e的逆序子序列,b, d从B端入队,得到序列为 d,b,a,c,e 。正确。
C选项:a, e是a, b, c, d, e的子序列,a, e从A端入队,d, b, c不是a, b, c, d, e的逆序子序列,错误。
D选项:a, d是a, b, c, d, e的子序列,a, d从A端入队,e, c, b是a, b, c, d, e的逆序子序列,b, c, e从B端入队,得到序列为 e,c,b,a,d 。正确。
本题选C。
方法三:找规律
入队序列a, b, c, d, e转化为下标序列1, 2, 3, 4, 5,为一个单调递增序列。
A选项:b, a, c, d, e转化为2, 1, 3, 4, 5
B选项:d, b, a, c, e转化为4, 2, 1, 3, 5
C选项:d, b, c, a, e转化为4, 2, 3, 1, 5
D选项:e, c, b, a, d转化为5, 3, 2, 1, 4
很明显,只有C选项的折线图中间有一个凸起。这个绝对不是巧合哦!本题结果序列至多由一个下标单调递减序列和一个下标单调递增序列拼接而成。C选项明显不符合要求。
本题选C。
登录后提交答案