2. 考研
  3. 设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1～9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6，7。若期望驶出的次序依次为1～9，则n至少是( )。

设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1～9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6，7。若期望驶出的次序依次为1～9，则n至少是( )。

admin2017-08-16  26
问题 设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1～9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6，7。若期望驶出的次序依次为1～9，则n至少是(          )。
选项 A、2
B、3
C、4
D、5
答案C
解析 在确保队列先进先出原则的前提下。根据题意具体分析：入队顺序为8，4，2，5，3，9，1，6，7，出队顺序为1．9。入口和出口之间有多个队列(n条轨道)，且每个队列(轨道)可容纳多个元素(多列列车)。如此分析：显然先入队的元素必须小于后入队的元素(如果8和4入同队列，8在前4在后，那么出队时只能是8在前4在后)，这样8入队列1，4入队列2，2入队列3，5入队列2(按照前面的原则“大的元素在小的元素后面”也可以将5入队列3，但这时剩下的元素3就必须放到一个新的队列里面，  无法确保“至少”，本应该是将5入队列2，再将3入队列3，不增加新队列的情况下，可以满足题意“至少”的要求)，3入队列3，9入队列1，这时共占了3个队列。后面还有元素1，直接再占用一个新的队列4，1从以列4出队后，剩下的元素6和7或者入队到队列2或者入队到队列3(为简单起见我们不的设n个队列的序分别1，2，…，n)，这样满足题目的要求。综上，共占用了4个队列。当然还有其他的入队出队的情况，请考生们自行推演。但要确保满足：1)队列中后面的元素大于前面的元素；2)确保占用最少(即满足题目中的“至少”)的队列。
转载请注明原文地址:https://kaotiyun.com/show/VDRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)