数据结构 附录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 )