试证明:若借助栈由输入序列12…n得到的输出序列为p1p2…pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着i<j<k使pj<pk<pi。
正确答案:因为输入序列是从小到大排列的,所以若pj<pk<pi,则可以理解为通过输入序列pjpkpi可以得到输出序列pipjpk,显然通过序列123是无法得到312的,所以不可能存在着i<j<k使pj<pk<pi。
答案解析:有
微信扫一扫手机做题
试证明:若借助栈由输入序列12…n得到的输出序列为p1p2…pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着i<j<k使pj<pk<pi。
微信扫一扫手机做题