《数据结构》附录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分）
0 SUN 1 MON 2 THU 3 FRI 4 WED 5 TUE 6 SAT 7 8 9 2．（6分） 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的结点 （2） h = log2 ( n+1 ) 或 h = [ log2 n ] + 1 （方括号表示向下取整） （3） O ( log2 ( n+1 ) ) 或 O ( log2 n )