原创力文档- 1、本文档共19页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
有一铁路交换站如题图（栈），火车从右边开进交换站，然后再开到左边，每节车厢均有编号如1，2，3，…，n。请问：
当n=3和n=4时有哪几种排序方式？哪几种排序方式不可能发生？
当n=6时，325641这样的排列是否能发生？154623的排列是否能发生？
N=3时可能的出栈序列：
123
1S1X2S2X3S3X
132
1S1X2S3S3X2X
213
1S2S2X1X3S3X
231
1S2S2X3S3X1X
312
CAB
321
1S2S3S3X2X1X
N=4，不可能的排列：43124213423141234132
312431423412
1423
2413
N=6时，325641可能 154623不可能
CQ[0：10]为一循环队列，初态front=rear=1，画出下列操作后队的头、尾指示器状态：
d,e,b,g,h入队；
d,e出队；
i,j,k,l,m入队；
（4）b出队；
（5）n,o,p,q,r入队；
rear
初态
（1）d,e,b,g,h入队
0 1 2 3 4 5 6 7 8 9 10
front rear
de
d
e
b
g
h
（2）d,e出队
（3）i,j,k,l,m入队
（4）b出队
（5）n,o,p,q,r入队
front rear
0
1
2
3
4
b
5
g
6
h
7
8
9
10
rear
front
0
1
2
3
4
5
6
7
8
9
10
m
b
g
h
i
j
k
l
rear
front
0
1
2
3
4
5
6
7
8
9
10
m
g
h
i
j
k
l
rear
front
0
1
2
3
4
5
6
7
8
9
10
mnopg
m
n
o
p
g
h
i
j
k
l
试画出表达式A*（B-D）/D+C**（E*F）执行过程中NS，OS栈的变化情况。
DBA-（*
D
B
A
-
（
*
T1=B-D
T1
#
A
T2=A*T1
*
D
#
T2
/
#
*（FT3=T2/D
*
（
F
T3=T2/D
NS OS
NS OS
E
** T4=E*F T4
** T5=C*T4
C
+
C
+
T5
+
T3
#
T3
#
T3
#
NS
OS
NS
OS
NS
OS
#T6=T3+T5T6返回结果
#
T6=T3+T5
T6
NS OS
将下面的树转换成二叉树。
ABC
A
B
C
D
E
F
G
I
J
K
L
A
B
A
D
B
C
E
45度旋转
F
C
D
E
F
G
I
J
G
K
K
L
I
L
J
调整后
A
B
D
C
E
G
F
K
I
L
J
完全二叉树有1000个结点，问：
叶子结点有多少？度为2的结点有多少？多少个结点只有非空的左子树？第一种做法：
N1=0/1，N是奇?N1=0；N是偶?N1=1N=1000，N1=1
1000=N0+1+N2 1
N0=N2+1 2
N0=500，N2=499
第二法：
N=1000，29N210?完全二叉的深度H=10
第10层叶子结点数：N01=N-(29-1)=1000-511=489
第10层总结点数：29=512
第10层空的结点数：512-489=23空结点数是奇数?N1=1
第9层叶子结点数：N02=（23-1）/2=11
总叶子结点数：N0=N01+N02=489+11=500N2=N-N0-N1=1000500-1=499
补充：度为3的树，1个度为1的结点，3个度为2的结点，4个度为3的结点，求叶子结点数？
N=N0+N1+N2+N3=N0+1+3+4
B=N-1=N1+2*N2+3*N3=1+2*3+3*4=19?N=20?N0=12
设一棵二叉树的中序遍历和后序遍历结果为：中序：BDCEAFHG
后序：DECBHGFA
求先序？ABCDEFGH
A
A
B
F
C
G
D
E
H
2.32给定一组元素{17，28，36，54，30，27，94，15，21，83，40}，画出由此生成的二叉排序树。
17
17
15
28
27
36
21
30
54
40
94
83
下标数据双亲左孩子右孩子给定一组权值W={8，2，5，3，2，
下标
数据
双亲
左孩子
右孩子
0
8
10
-1
-1
1
2
7
-1
-1
2
5
9
-1
-1
3
3
8
-1
-1
4
2
7
-1
-1
5
17
12
-1
-1
6
4
8
-1
-1
7
4
9
1
4
8
7
10
3
6
9
9
11
7
2
10
15
11
8
0
11
24
12
9
10
12
41
-1
5
11
17：
文档评论（0）