一、单项选择题
下列每题给出的四个选项中，只有一个选项符合试题要求。
1、设n是描述问题规模的非负整数，下列程序段的时间复杂度是______
x=0;
while(n>=(x+1)*(x+1))
x=x+1;
A.O(log n)B.O(n1/2)C.O(n)D.O(n2)
2、若将一棵树丁转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与丁的后根遍历序列相同的是______
A.先序遍历B.中序遍历C.后序遍历D.按层遍历
3、对n个互不相同的符号进行哈大曼编码。若生成的哈夫曼树共有115个结点，则n的值是______
A.56B.57C.58D.60
4、在任意一棵非空平衡二叉树(AVL树)T1中，删除某结点v之后形成平衡二叉树T2，再将v插入T2形成平衡二叉树T3。下列关于T1与T3的叙述中，正确的是______
Ⅰ.若v是T1的叶结点，则T1与T3可能不相同
Ⅱ.若v不是T1的叶结点，则T1与T3一定不相同
Ⅲ.若v不是T1的叶结点，则T1与与T3一定相同
A.仅ⅠB.仅ⅡC.仅Ⅰ、ⅡD.仅Ⅰ、Ⅲ
5、下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是______