一、单项选择题

下列每题给出的四个选项中，只有一个选项符合试题要求。

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的最早开始时间和最迟开始时间分别是______

阅读全卷     帮助     下载试卷