耿国华数据结构附录A样卷习题答案及B卷习题答案 下载本文

数据结构 附录A 样卷一参考答案 一:判断题

题号 答案 1 × 2 × 3 √ 4 × 5 √ 6 √ 7 × 8 √ 9 × 10 × 二:选择题

题 1 2 C 3 A 4 D 5 D 6 D 7 B 8 D 9 D 10 11 A A 12 13 14 15 16 17 18 19 20 C B C C B C B C B 答 B 三:填空

1表长的一半 2 排好序列 3, 4 312 5 N+1 6 S->next=P->next P->next=S 7 路径递增 8 Log(2)(N) 9中序 10 97 11 链域个数不同 12 63 13 1476 14 P->next=head 15 散列查找 16 先进先出 17 5 18 FDBECA 19将矩阵第i行全部置0

四,构造题 1,

计算函数值

key Key%7 75 5 33 5 52 3 41 6 12 5 88 4 66 3 27 6 (1)哈希表(4分,每对1个0.5分)

index key 0 27 1 2 3 52 4 88 5 75 6 33 7 41 8 12 9 66 (2)比较次数(3分)

key Cmp 75 1 33 2 52 1 41 2 12 4 88 1 66 7 27 5 ASL=(1+2+1+2+4+1+7+5)/8=23/8

5, (1)

3 1 5 6 7 (2) ASL=(1+2*2+4*3+1*4)/8=21/8=2.62

0 2 4

《数据结构》附录B 样卷二 参考答案

一、简答题(15分,每小题3分) 6. 算法是解决特定问题的操作序列,可以用多种方式描述。程序是算法在计算机中的实现,与具体的计算机语言有关。 7. 主要与哈希函数、装填因子α有关。如果用哈希函数计算的地址分布均匀,则冲突的可能性较小,如果装填因子α较小,则哈希表较稀疏,发生冲突的可能性较小。 8. 图中结点可能有多个前驱,设置访问标志数组主要是为了避免重复访问同一个结点。 9. 头指针指向头结点,头结点的后继域指向首元素结点。 10. 当队尾到达数组最后一个单元时,就认为队满,但此时数组前面可能还有空单元,因此叫假溢出。解决的方法是采用循环队列,即令最后一个单元的后继是第一个单元。 二、判断题(10分,每小题1分)

(1)(√) (2)(×) (3)(×) (4)(√) (5)(×) (6)(√) (7)(×) (8)(√) (9)(×) (10)(×) 三、单项选择题(10分, 每小题1分)

1. D) 2. B) 3. C) 4. C) 5. B) 6. A) 7. C) 8. D) 9. C) 10.C) 四、填空题(10分,每空1分)

1. high low low high 2. S->next=R->next ; R->next=S ;

3. 时间 空间 4. A[2, 3] 5. 2h-1

五、构造题(20 分) 1.(4分)

2.(6分)

0 1 2 3 4 5 6 7 8

SUN MON THU FRI WED

TUE

SAT

ASLsucc = ( 1×4 + 2×2 + 3 ) / 7 = 11 / 7 3.(6分)

4.(4分)已知权值集合为:{ 5,7,2,3,6,9 },要求给出哈夫曼树,并计算其带权路径长度WPL。

WPL = 2×( 9 + 6 + 7 ) + 3×5 + 4×( 2 + 3 ) = 79

六、算法分析题(10分)

解: (1) 在二叉排序树中插入关键字为K的结点

9

(2) (3) h = log2 ( n+1 ) 或 h = [ log2 n ] + 1 (方括号表示向下取整) O ( log2 ( n+1 ) ) 或 O ( log2 n )