2018年1月11日
本期题目
(单选题)编号为123456789的火车经过如图11-1所示的轨道,从左边入口处移到右边出口处(每车必须且只能进临时轨道M一次,且不能再回到左边入口处)按照从左向右的顺序,下面的结果不可能的是?
A123456789
B 321987654
C 321456798
D 987651234
考点:考察求职者对数据结构的栈的理解
出现频率:★★★★★
【面试题分析】
栈:后进先出
选项A中,123逐个去,45678入栈,再出栈变成87654,9再过去;
选项B中,123入栈,再出栈变成321,456789再入栈,变成987654;
选项C中,123入栈,再出栈变成321,4567直接过去,89入栈再出栈,变成98;
选项D中,98765再前面,则1234必须全部先进栈,98765过去后,剩下1234必须先回到左边,再通过才满足1234,但是题意要求不可以再回去到左边的入口,所以这个选项不可行。
所以参考答案是 (D)
扩展知识:如果M只能容纳4列车。上面的选项应该选哪项才可行?(请在留言留下你的答案)