数据结构课程试卷参.pdfVIP

数据结构课程3卷参考答案（共3页）

院系

专业

一、填空（2分×15）

1、front=rear；(rear+2)%n=front

2、O（n1/2）

3、AB+CD-/EF-TR-*+

4、5，空

5、4265713；4675231

6、h+1，2h+1-1

7、各边权值之和最小的生成树，prim或kruscal

8、add_to.c_str();add_on.c_str();add_to=copy;

二、应用题

1、ABCDEFGH，ABDCEFHG（各4分）

2、（1）ASLsucc=31/12，ASLunsucc=60/14（6分）

（2）ASLsucc=18/12，ASLunsucc=12/14（6分）

3、初始关键字：68,5,16,94,23,71,73,72,69

i=2：5,68,16,94,23,71,73,72,69

i=3：5,16,68,94,23,71,73,72,69

i=4：5,16,68,94,23,71,73,72,69

i=5：5,16,23,68,94,71,73,72,69

i=6：5,16,23,68,71,94,73,72,69

i=7：5,16,23,68,71,73,94,72,69

i=8：5,16,23,68,71,72,73,94,69

i=9：5,16,23,68,69,71,72,73,94（7分）

当把69有序表时，所需的比较次数和移动次数分别为5次和6次。（2分）

算法需要一个记录的辅助空间。（1分）

4、

终点i=1i=2i=3i=4i=5i=6

45454040

2

(1,2)(1,2)(1,5,2)(1,5,2)

∝∝55555250

3

(1,5,3)(1,5,3)(1,5,2,3)(1,4,6,3)

12

4

(1,4)

2525

5

(1,5)(1,5)

∝42