软件技术数据结构部分习题解答

2.21 有一铁路交换站如题图(栈),火车从右边开进交换站,然后再开到左边,每节车厢均有编号如1,2,3,…,n。请问:

(1)当n=3和n=4时有哪几种排序方式?哪几种排序方式不可能发生?

(2)当n=6时,325641这样的排列是否能发生?154623的排列是否能发生? N=3时可能的出栈序列:

123 1S1X2S2X3S3X

132 1S1X2S3S3X2X

213 1S2S2X1X3S3X

231 1S2S2X3S3X1X

312 CAB

321 1S2S3S3X2X1X

N=4,不可能的排列:

4312 4213 4231 4123 4132

3124 3142 3412

1423

2413

N=6时,325641可能154623不可能

2.22 CQ[0:10]为一循环队列,初态front=rear=1,画出下列操作后队的头、尾指示器状态:

(1)d,e,b,g,h入队;

(2)d,e出队;

(3)i,j,k,l,m入队;

(4)b出队;

(5)n,o,p,q,r入队;

相关推荐
相关主题
热门推荐