上海交通大学：《数据结构考研试题》2001年试题答案

2001年试题答案: 关键路径: A B D C F E G 最早发生时间:0135101314 最迟发生时间=最早发生时间 2. 中序遍历序列: ABCDEFXHIJK E X C2n"/ 2)C2(n-1)"/mn指有序树 3)NO=N2+1 4)不是,因为二叉树不是树的特例。 5)2n-1 4.k-1-(m-1) (k-1) 推导参见严蔚敏《数据结构》(C语言版)p.305 P(-1-2) h-1→h-2 (-1)→p(0)h-1 h-2h-2

2001 年试题答案： 1． 关键路径： A B D C F E G 最早发生时间：0 1 3 5 10 13 14 最迟发生时间=最早发生时间： 2． 中序遍历序列：ABCDEFXHIJK J F K D H B E X I A C 3． 1）C2n n /（n+1） 2）C2（n-1） n-1 /n 指有序树 3）N0=N2+1 4）不是，因为二叉树不是树的特例。 5）2n-1 4．k-1-（m-1） mod （k-1） 推导参见严蔚敏《数据结构》（C 语言版）p.305 5． P（-1 -2） q（0） h-1 h-2 q（-1） p（0） h-1 h-2 h-1 h-2 h-2

P(1-2) (0) h-2h-2h-3h2 2q(1)→p(0)q(0) (0) h→h21)→(1) (-1)h-2h-2h3h2h-2 6.O(n3)

P（-1 -2） r（0） h-1 h-2 q（1） p（0） q（-1） r（1） h-2 h-2 h-2 h-3 h-2 P（-1 -2） r（0） h-1 h-2 q（1） p（0） q（0） r（0） h-2 h-2 h-2 h-2 h-2 P（-1 -2） r（0） h-1 h-2 q（1） p（1） q（0） r（-1） h-2 h-2 h-3 h-2 h-2 6 ． O (n log 35 ) 7 ． A B E F C D G H

1)3 2) CDEGH 3)不是,满足非空且无右子树的二叉树。 证明参见严蔚敏《数据结构》(C语言版)p.232 9 略 可以用非递归的后序遍历求解 当遍历到值为key的结点时,栈中所有结点就是它的所有祖先

1） 3 2） C D E G H 3） 不是，满足非空且无右子树的二叉树。 8． O （log2 n） 证明参见严蔚敏《数据结构》（C 语言版）p.232 9. 略 10. 可以用非递归的后序遍历求解， 当遍历到值为 key 的结点时，栈中所有结点就是它的所有祖先