数据结构模拟试题5参考答案..doc

·PAGE2· 数据结构上机实验与习题解析

第3部分模拟试题及参考答案 ·PAGE3·

数据结构模拟试题5参考答案

一、选择题（20分）

1-5 C C D A A

6-10 D B C B B

二、填空题（20分）

1．结点*p的左右链域为空

2．深度优先

3．N-1

4．A[N/2]

5．sq.front=（sq.fron+1）%M （sq.rear+1）%M==sq.front

6．4，9，14，17，20

7．0 入度减1 环

三、应用题（30分）

1．参考答案如下：

1）二叉树

E

E

A

B

D

G

C

F

H

I

2）对应的森林

F

F

H

I

C

E

A

B

D

G

2．参考答案如下：

80

80

60

40

120

70

100

3．参考答案如下：

1）G1的邻接表和G1的逆邻接表

1

1

2

3

4

2

3^

V1

V2^

V3

V4

4^

1^

1

1

2

3

4

V1

V2

V3

V4

4^

3^

1^

1^

2）G1的强连通分量

4．参考答案如下：

1）以所有字符的权值作为叶结点构成的哈夫曼树如下：

11

11

42

5

7

16

19

2）所有字符的哈夫曼编码如下：

A（7）：0011

B（19）：011

C（5）：0010

D（16）：010

E（42）：01

F（11）：000

5．参考答案如下：

事件的发生时间活动的开始时间

事件的发生时间活动的开始时间

Vi

ve

vl

ai

e

l

l-e

V1

0

0

a1

0

5

5

V2

6

7

a2

0

0

0

V3

3

3

a3

3

4

1

V4

12

12

a4

6

7

1

V5

18

18

a5

3

3

0

V6

21

21

a6

3

14

11

a7

12

12

0

a8

12

19

7

a9

18

18

0

6．参考答案如下：

1）该序列是一个小根堆

2）该序列不是一个小根堆，调整如下：

38

38

29

61

20

23

35

56

25

28

76

40

100

四．算法设计题（30分）

1．算法源代码如下：

voidfun(bitreeT,charx,intm)

{if(T)

{m++;

if(T-data==x){printf(%d,m);return;}

fun(T-lchild,x,m);

fun(T-rchild,x,m);

}

}

main()

{bitreebt;

intm=0;

fun(bt,m);

}

2．算法源代码如下：

#definemaxsize

typedefstruct{

intelem[maxsize];

inttop[2];

}stack;

stacks;

1）入栈操作

intpush(inti,intx)

{if(i0||i1){printf(输入数据有误);return0;}

if(s.top[1]-s.top[0]==1){printf(栈满);return0;}

switch(i)

{case0:s.elem[++s.top[0]]=x;break;

case1:s.elem[--s.top[1]]=x;

}

return1;

}

2）出栈操作

intpop(inti,int*x)

{if(i0||i1){printf(输入数据有误);return0;}

switch(i)

{case0:

if(s.top[0]==-1){printf(栈空);return-1;}

else*x=s.elem[s.top[0]--];

break;

case1:

if(s.top[0]==maxsize){printf(栈空);return-1;}

else*x=s.elem[s.top[1]++];

}

return1;

}

3．算法源代码如下：

voiddijkshort(mgraphG,intv)

{

ints[30];intd[30];intpre[30];

inti,j,k,p,min;