初始归并段所需时间为_0(n10gW 三.简答题(6’×5) 1.有n个不同的英文单词,它们的长度相等,均为皿,若 n>50,m<5,试问采用什么排序方法时间复杂度最佳 为什么? 采用基数排序方法最佳 因单词长度相等,而只有26个字母组成,符合基数排序 的条件。 因m<<n,故时间复杂性由0m(n+rm))变成0(n)。 2.对于一个栈,给出输入序列A,B,C,试给出全部可能 的输出序列。若输入序列的长度为n,则可能的输出序 列有多少? ABC, ACB, BAC, BCA, CBA C2n/(n+1) 3.求2-3树的结点数和叶子数的范围并证明之。 h+1 h+1 2-1(3-1)/2 h为树的高度 用数学归纳法证明。 4.求解下列递归方程: n=1 T(n)=f aT(n/b)+c 其中a>1,b>1,a∈N,b∈N 为简单起见,设n为b的整数幂 T(n)=0(n Log ba 5.快速排序的时间复杂度是多少?试推导之。 四.程序设计题(38’) 1.假设有两个集合A和B,均以元素值递增有序排列的带2 初始归并段所需时间为 O(n log w) 。 三. 简答题（6’5） 1． 有 n 个不同的英文单词，它们的长度相等，均为 m，若 n>>50，m<5，试问采用什么排序方法时间复杂度最佳？ 为什么？ 采用基数排序方法最佳。 因单词长度相等，而只有 26 个字母组成，符合基数排序 的条件。 因 m<<n，故时间复杂性由 O(m(n+rm))变成 O(n)。 2． 对于一个栈，给出输入序列 A，B，C，试给出全部可能 的输出序列。若输入序列的长度为 n，则可能的输出序 列有多少？ ABC，ACB，BAC，BCA，CBA C2n n /（n+1） 3． 求 2-3 树的结点数和叶子数的范围并证明之。 2 h +1 -1 ~ （3 h+1 -1）/2 2 h ~ 3h h 为树的高度 用数学归纳法证明。 4． 求解下列递归方程： 1 n=1 T（n）={ aT(n/b)+c n>1 其中 a>1, b>1, aN, bN 为简单起见，设 n 为 b 的整数幂。 T(n)=O(n L og b a ) 5． 快速排序的时间复杂度是多少？试推导之。 O(n log n) 四. 程序设计题（ 38’） 1．假设有两个集合 A 和 B，均以元素值递增有序排列的带