计算机软件基础第二章课后答案.docx
《计算机软件基础第二章课后答案.docx》由会员分享，可在线阅读，更多相关《计算机软件基础第二章课后答案.docx（20页珍藏版）》请在冰点文库上搜索。
计算机软件基础第二章课后答案
已知线性表L（a1,a2,…,an）元素按递增有序排列，用向量作存储结构，试编写算法：
删除表中在c与d（c≤d）之间的元素。
解：
dele（L,n,c,d）1.k=0
2.fori=1ton
3.ifL[i]≥.L[i]≤d
4.k←k+1
5.endif
6.ifL[i]＞d
7.L[i-k]←L[i]
8.endif
9.endfor
10.n←n-k
11.return
有一铁路交换站如题图（栈），火车从右边开进交换站，然后再开到左边，每节车厢均有编号如1，2，3，…，n。
请问：
（1）当n=3和n=4时有哪几种排序方式哪几种排序方式不可能发生
（2）当n=6时，325641这样的排列是否能发生154623的排列是否能发生
N=3时可能的出栈序列：
1231S1X2S2X3S3X
1321S1X2S3S3X2X
2131S2S2X1X3S3X
2311S2S2X3S3X1X
312CAB
3211S2S3S3X2X1X
N=4，不可能的排列：
4312421342314123413231243142341214232413
N=6时，325641可能154623不可能
试画出表达式A*（B-D）/D+C**（E*F）执行过程中NS,OS栈的变化情况。
B-D=T1D/T1=T2T2*A=T3E*F=T4T4**C=T5T5+T3=T6
D
）
B
-
（
*
A
;
C
+
T2
*
A
;
）
F
*
E
（
**
C
+
T3
;
;
T4
**
C
+
T3
;
;
T5
+
T3
;
D
/
T1
*
A
;
;
T6
;
用三元组和带行辅助向量形式表示下列稀疏矩阵：
（1）：
（2）：
（1）：
三元组带行辅助向量
行
列
值
1
1
15
1
4
22
1
6
-15
2
2
11
2
3
3
3
4
-6
5
1
91
6
3
28
（2）:
三元组
i
1
2
3
4
5
6
POS
1
4
6
7
7
8
NUM
3
2
1
0
1
1
行
列
值
1
1
8
1
5
-13
1
9
26
2
1
15
2
4
6
2
8
5
3
2
-3
3
4
4
3
6
3
4
4
2
4
8
4
5
3
-12
6
2
2
7
4
4
8
1
7
9
1
12
9
4
2
9
6
6
9
9
30
i
1
2
3
4
5
6
7
8
9
POS
1
4
7
10
12
13
14
15
16
NUM
3
3
3
2
1
1
1
1
4
D
E
F
I
J
K
G
L
A
B
C
前8行：
1+2+4+8+16+32+64+128+256=511
第9行：
满的尾512加起来超过1000
1000-511=489这是第9行的度为1的结点
489/2=244余1
256-244=1212-1=11这是第8行度为1的结点
则度为1的结点数：
n1=489+11=500
度为2的结点数：
n2=n1-1=499
度为0的节点数：
n0=1
1个节点只有非空左子树
11个结点只有非空右子树
第一种做法：
N1=0/1，N是奇；N是偶，N1=11000=N0+1+N21N0=N2+12N0=500，N2=499
第二法：
N=1000，29N01=N-（29-1）=1000-511=489第10层总结点数：
29=512第10层空的结点数：
512-489=23空结点数是奇数第9层叶子结点数：
N02=（23-1）/2=11总叶子结点数：
N0=N01+N02=489+11=500N2=N-N0-N1=1000-500-1=499度为3的树，1个度为1的结点，3个度为2的结点，4个度为3的结点，求叶子结点数N=N0+N1+N2+N3=N0+1+3+4B=N-1=N1+2*N2+3*N3=1+2*3+3*4=19N=20N0=12
设一棵二叉树其中序和后序遍历为
中序：
BDCEAFHG
后序：
DECBHGFA
画出这棵二叉树的逻辑结构，并写出先序遍历结果。
先序遍历：
ABCDEFGH
其逻辑结构如下：
1，2，3依次进栈，求可能的出栈序列。
1231S1X2S2X3S3X
1321S1X2S3S3X2X
2131S2S2X1X3S3X
2311S2S2X3S3X1X
312CAB
3211S2S3S3X2X1X
1，2，3，4
43124213423141234132
312431423412
1423
2413
325641154623
完全二叉树有1000个结点，问：
叶子结点有多少度为2的结点有多少多少个结点只有非空的左子树
第一种做法：
N1=0/1，N是奇N1=0；N是偶N1=1
N=1000，N1=1
1000=N0+1+N21
N0=N2+12
N0=500，N2=499
第二法：
N=1000，29第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=500
N2=N-N0-N1=1000-500-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=19N=20N0=12
设一棵二叉树的中序遍历和后序遍历结果为：
中序：
BDCEAFHG
后序：
DECBHGFA
求先序ABCDEFGH
DLR先序
LDR中序
LRD后序
给定一组元素{17，28，36，54，30，27，94，15，21，83，40}，画出由此生成的二叉排序树。
17
28
36
54
30
27
94
15
21
83
40
给定一组权值W={8，2，5，3，2，17，4}，画出由此生成的哈夫曼树。
下标
数据
双亲
左孩子
右孩子
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
8：
111
5：
101
4：
1101
3：
1100
2：
1000
2：
1001
2．34有一图如题图所示：
（1）写出此图的邻接表与邻接矩阵；
（2）由结点V1作深度优先搜索和广度优先搜索；
（3）试说明上述搜索的用途。
2
10
11
9
19
18
8
12
17
20
16
7
13
15
6
14
5
4
1
3
邻接矩阵：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
2
1
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
3
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
4
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
5
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
7
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
8
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
10
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
11
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
12
0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
13
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
14
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
15
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
17
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
18
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
19
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
20
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
邻接表：
DFS：
V1，V2，V3，V4，V5，V6，V7，V8，V9，V10，V11，V12，V13，V14，V15，V16，V17，V18，V19，V20
BFS：
V1，V2，V5，V8，V3，V10，V4，V6，V7，V9，V12，V11，V14，V15，V18，V13，V19，V16，V17，V20
2．35有一有向图如下：
（1）写出每一个结点的入度和出度各为多少；
（2）写出此图的邻接矩阵与邻接表；
顶点
入度
出度
V1
3
0
V2
2
2
V3
1
2
V4
2
1
V5
2
1
V6
1
4
V1
V2
V3
V4
V5
V6
V1
0
0
0
0
0
0
V2
1
0
0
1
0
0
V3
0
1
0
0
0
1
V4
0
0
1
0
1
0
V5
1
0
0
0
0
0
V6
1
1
0
1
1
0
DFS：
V6V1V2V4V3V5
BFS：
V6V1V2V4V5V3
2．36求下图中结点a到各结点之间的最短路径。
2．37求下图中所示AOV网所有可能的拓扑排序结果。
V1
V2
V3
V4
V5
V6
0
0
0
0
0
1
3
8
^
6
8
^
4
^
8
^
V7
0
V8
0
0
^
^
8
^
4
^
拓扑排序：
V7->V5->V2->V4->V6->V3->V1->V8
下图所示AOE网，求
（1）每一事件最早开始时间和最晚开始时间；
（2）该计划最早完成时间为多少。
1
开始
2
3
4
5
7
6
8
9
10
结束
a2=6
a1=5
a3=3
a4=6
a5=3
a10=4
a9=1
a6=7
a8=4
a7=4
a11=4
a14=2
a13=2
a12=5
活动最早最迟开始时间
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
E
0
0
5
6
6
12
12
12
19
19
16
20
23
25
L
4
0
9
6
16
12
19
16
19
19
23
20
23
25
L-E
4
0
4
0
10
0
7
4
0
0
7
0
0
0
事件最早最迟开始时间
V1
V2
V3
V4
V5
V6
V7
V8
V9
V10
VE
0
5
6
12
19
16
20
23
25
27
VL
0
9
6
12
19
23
20
23
25
27
画一棵以20个记录进行对分查找的判定树，并求等概率下的平均查找长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
4
3
4
5
2
4
3
4
5
1
4
3
4
5
2
4
5
3
4
5
ASL=（1+2*2+3*4+4*8+5*5）/20=
（13,29,01,23,44,55,20,84,27,68,11,10,79,14）
下标
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
数据
68
01
20
55
23
44
27
29
13
11
10
84
79
14
次数
1
1
1
1
1
1
2
1
1
4
6
1
7
5
线性探测再散列：
p=17,m=19
ASL1=（1+1+1+1+1+1+2+1+1+4+6+1+7+5）/14=33/14
平方探测再散列：
（13,29,01,23,44,55,20,84,27,68,11,10,79,14）
ASL2=（1+1+1+1+1+5+3+1+2+1+1+1+4+1）/14=24/14
升级会员 