应用题复习(含解).doc

一、应用题
1. 已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：
（1）设线性表L=（51，-9，-6，39，0，-11，34，70，-16），写出执行算法f11(&L)后的L状态；
（2）简述算法f11的功能。
void f11 (SeqList *L) {
int i,j;
for (i=j=0;i<L->len; i++)
if(L->elem[i]>=0){
if(i!=j)L->elem[j]=L->elem[i];
j++；
}
L->len=j;
}
【答案】
（1）L=(51,39,0,34,70)
(2) 删除顺序表中小于0的数。

2. 假设以带头结点的单链表表示线性表,阅读下列算法f22,并回答问题:
(1)设线性表为( a1, a2, a3, a4, a5, a6, a7 ), 写出执行算法f22后的线性表；
(2)简述算法f22的功能。
void fun(LNode *L)
{
//L为带头结点单链表的头指针
P =L;
while (p &&p->next){
q = p->next;
p->next =q->next;
p =q->next;
free(q);
}
}
【答案】
（1）(a2,a4,a6)
(2) 删除单链表中数据结点序号为奇数的那些结点。

3.假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。
(1)写出队满的条件表达式；
(2)写出队空的条件表达式；
(3)设m=50,rear=19,quelen=25,求队头元素的位置；
(4)写出一般情况下队头元素位置的表达式。
【答案】
(1)quelen==m
(2)quelen==0
(3)45
(4)front=(rear-quelen+1+m)%m

4.假设以数组seqn［m］存放循环队列的元素，设变量front和rear分别指示循环队列中队头元素的位置和队尾元素的位置。
(1)写出队满的条件表达式；
(2)写出队空的条件表达式；
(3)设m=40,rear=13,front=19,求队列的元素的个数quelen；
(4)写出一般情况下元素的个数的表达式。
【答案】
(1)(rear+1)%m==front
(2) rear==front
(3)34
(4) quelen=(rear-frontm)%m

5. 假设有一个如下图的8×8矩阵，矩阵元素都是整型量(次对角线以上的元素都是0)。
若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中，请回答下列问题：
(1)B数组的体积至少是多少?
(2)若a18存储在B[0]中，a56存储在B[k]中，则k值为多少?
(1)
(2)

【答案】
（1）36 （2）13

6. 阅读下列算法，并回答问题：
（1）Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写出执行f33 (&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态；
（2）简述算法f33的功能。
（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作）
void f31 (Queue*Q, Queue*Q1, Queue*Q2) {
int e;
lnitQueue (Q1);
lnitQueue (Q2);
while (!QueueEmpty (Q)) {
e=DeQueue (Q);
if (e>=0) EnQueue (Q1,e);
else EnQueue (Q2,e)
}
}
【答案】
（1）Q=() Q1=(1,0,2,9) q2=(-5,-4,-6)
（2）将Q队列中的数据全部出队；不小于0的进Q1，否则进Q2。

A
B
C
G
D
E
F
7. 已知二叉树如右图所示。
（1）画出该二叉树的二叉链表；
（2）分别写出该二叉树的先根、中根和后根遍历序列。
【答案】
(1) 二叉链表:
D
∧
∧
A

C

B
∧

E

∧
G
∧
∧
F
∧
∧

（2）先根遍历序列：ABDCEGF
中根遍历序列: DBAEGCF
后根遍历序列: DBGEFCA

8、假设一棵二叉树的先根遍历序列为ABCDEFGH，中根遍历序列为CDBEGFHA。
(1)画出该二叉树；（2）写出后根遍历序列。
D
B
E
H
G
F
A
C
【答案】
(1)二叉树

（2）后根遍历序列:DCGHFEBA
9、假设一棵二叉树的中根遍历序列为DGBEACHFI，后根遍历序列为GDEBHIFCA
(1)画出该二叉树；（2）写出先根遍历序列。
【答案】（1）二叉树：（2）先根遍历序列：ABDGECFHI

A
B
C
I
D
H
F
G
E

10．假设一棵二叉树的层次遍历序列为ABCDEFGHI，中根遍历序列为DHBEAFCIG。
(1)画出该二叉树；（2）写出先根和后根遍历序列。
【答案】
（1）二叉树：
A
B
C
I
D
F
G
H
E

（2）先根遍历序列：ABDHECFGI
后根遍历序列：HDEBFIGCA

0
0
0
0
0
0
1
1
1
1
1
1
T
G
M
S
H
D
A
25
11
6
14
5
3
2
35
17
10
7
18
60
11．设某通讯系统仅用七个英文字符{A，D，G，H，M，S，T}，每个字符的使用频率分别为{3，7，18，2，6，10，14}。请画出对应的哈夫曼编码树（按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。

【答案】

哈夫曼编码
A
D
G
H
M
S
T
0001
100
11
0000
001
101
01

12. 假设通信电文使用的字符集为{ S，T，B，F，C}，字符的哈夫曼编码依次为：011，10，00，010和11。
(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；
(2)若这些字符在电文中出现的频度分别为：4，7，5，2和9，求出电文的总长度。。
16
0
0
0
0
1
1
1
1
11
27
5
6
7
2
4
9
B
F
S
T
C
【答案】
（1）编码哈夫曼树 (2) 电文的总长度=4*3+7*2+5*2+2*3+9*2=60

v2
v3
v1
v5
v4
13、已知一个有向图如右图所示。
(1)试画出它的邻接表。（表结点按顶点编号递减排列）
1
2 ∧
3
4 ∧
5
5
4
3
2 ∧
4 ∧
4
2 ∧
(2)分别求出从v1出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。
【答案】（1）
(2)深度优先搜索序列：v1，v 4，v 3， v 5，v 2
广度优先搜索序列：v1，v 4，v 3， v 2，v 5

14、已知一个AOV网如右图所示。
V51
V11
V41
V21
V61
V31
(1)试画出它的邻接链表。（表结点按顶点编号递减排列）
(2)试写出按照拓扑排序算法得到的拓扑序列。

1
v1 0
6
v6 3
5
v5 1
3
V3 2
4
v4 2 ^
21
v2 0
6 ∧
4 ∧
6 ∧
4
3 ∧
6
5
3
【答案】
(1)

（2）v2,v5,v1,v3,v6,v4
15、请用普里姆算法(从顶点V3开始)和克鲁斯卡尔算法构造下图所示网络的最小生成树，按照并入最小生成树中边的次序填写下表，并画出最小生成树。
次序
1
2
3
4
5
始 点

终 点

权 值

14
v1
v4
v5
v2
v3
V6
10
8
18
16
12
10
15
19
20

【答案】
（1）普里姆算法14
v1
v4
v5
v2
v3
V6
8
16
12
10
构造过程： 最小生成树：
次序
1
2
3
4
5
始 点
V3
V1
V3
V2
V2
终 点
V1
V4
V2
V5
V6
权 值
12
14
16
8
10

（2）克鲁斯卡尔算法14
v1
v4
v5
v2
v3
V6
8
16
12
10
构造过程： 最小生成树：
次序
1
2
3
4
5
始 点
V2
V2
V3
V1
V3
终 点
V5
V6
V1
V4
V2
权 值
8
10
12
14
16

16、设关键字序列（17,8,13,25,24,16,3,19,1），写出用下列方法排序时,第一趟结束时关键字的排列状态。
(1)冒泡排序 (2)希尔排序(d1=4) （3）快速排序
【答案】
(1)冒泡排序 （8，13，17，24，16，3，19，1，25）
(2)希尔排序(d1=4) （1，8，3，19，17，16，13，25，24）
(3）快速排序（1，8，13，3，16）17（24，19，25）

52
24
30
12
61
70
46
79
83
17、对有序表{12,24,30,46,52,61,70,79,83}进行折半查找方法查找，
（1）求出查找24和83时所需比较的次数；
（2）画出判定树； （3）求ASL和MSL。
【答案】
(1)24比较2次；83比较4次
(2)判定树：
(3)ASL=(1+4+12+8)/9=25/9=2.78
MSL=4
18．已知一组数据元素为（68，21，95，71，14，57，28，33，80），要求：
（1）试从空树开始画出按元素排列顺序输入而生成的一棵二叉排序树；
（2）画出删除结点68后的二叉排序树。
【答案】
(1) 二叉排序树:

21
14
28
95
71
68
57
80
33
（2）删除结点68后的二叉排序树:
或：

21
14
28
95
80
71
57
33
21
14
95
71
57
28
80
33

19.选取哈希函数为H(K)=K % 7。用线性探测的开放地址法处理冲突。试在0～8的散列地址空间中对关键字序列{25,72,48,19,32,50,68}构造哈希表，并求出等概率下查找成功的平均查找长度。
【答案】
（1）
50
72

25
19
48
32
68
0 1 2 3 4 5 6 7 8
哈希表:

比较次数： 1 1 1 1 1 4 4
（2）

20. 下列是一棵五阶B-树,依次执行以下两步操作,画出每一步执行后所得到的B-树形。
(1)插入n;(2)删除e 。

【答案】
(1)插入n:

(2)删除e:

21．已知关键字序列为：（70,31,52,41, 88,12,27,66）哈希表长为9，哈希函数为：H (k)＝k %9，用链地址法处理冲突，试构造哈希表，并求等概率下查找成功的平均查找长度。

【答案】
(1) 哈希表:

∧
∧

∧

∧

0
1
2
3
4
5
6
7
8

27 ∧
12
31
52
41 ∧
70
88 ∧
66 ∧

(2)

22. 由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。

【答案】
A
B
D
L
K
C
F
E
G
H
I
J
还原后的森林：

第三棵树的前序序列GHIJ ；后序序列HJIG

23. 假设一棵树的先根序列为ABCEFIJGHKD，后根序列为BEIJFGKHCDA。请画出该树。
【答案】
（1）因为树的先根和后根遍历序列分别与其转换后对应的二叉树的先根和中根遍历序列相同，所以可先得到的对应的二叉树如下图所示：

（2）根据树与二叉树的转换规则，可得到树如下图所示：

24. 已知一个散列表如下图所示：

19

32

48
58
22

0 1 2 3 4 5 6 7 8 9 10 11 12
其散列函数为h(key)=key%13, 处理冲突的方法为双重散列法，探测序列为：
hi=(h(key)+i *h1(key))%m i=1,…，m－1
其中
h1(key)=key%11+1
回答下列问题：
（1）对表中关键字19，32和22进行查找时，所需进行的比较次数各为多少？
（2）该散列表在等概率查找时查找成功的平均查找长度为多少？
【答案】
（１）对关键字19，32和22进行查找的比较次数为２、１、3；
（２）平均查找长度
H(32)=32%13=6 比较1次
H(48)=48%13=9 比较1次
H(58)=58%13=6(冲突)
h1=58%11+1=4
H1(58)=(6+4)%13=10(成功) 比较2次

H(22)=22%13=9(冲突)
h1=22%11+1=1
H1(22)=(9+1)%13=10(冲突)
H2(22)=(9+2*1)%13=11(成功) 比较3次

H(19)=19%13=6(冲突)
h1=19%11+1=9
H1(19)=(6+9)%13=2(成功) 比较2次