一、单项选择题： 1 ～ 40 小题，每小题 2 分，共 80 分。 下列每题给出的四个选项

1. 设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是 x=0 ； while(n>=(x 1)* （ x 1)) x=x 1 ；

A. O (log n ) B. O ( n 1/2 ) C. O ( n ) D. O ( n 2 )

2. 若将一棵树 T 转化为对应的二叉树 BT ，则下列对 BT 的遍历中，其遍历序列与 T 的 后根遍历序列相同的是

A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历

3. 对 n 个互不相同的符号进行哈大曼编码。若生成的哈夫曼树共有 115 个结点．则 n 的值是

A. 56 B. 57 C. 58 D. 60

4. 在任意一棵非空平衡二叉树 (AVL 树 ) T 1 中，删除某结点 v 之后形成平衡二叉树 T 2 ， 再将 v 插入 T 2 形成平衡二叉树 T 3 。下列关于 T 1 与 T 3 的叙述中，正确的星 I. 若 v 是 T 1 的叶结点，则 T 1 与 T 3 可能不相同 Ⅱ . 若 v 不是 T 1 的叶结点．则 T 1 与 T 3 一定不相同 Ⅲ . 若 v 不是 T 1 的叶结点，则 T 1 与与 T 3 一定相同

A. 仅 I B. 仅 Ⅱ C. 仅 I 、 Ⅱ D. 仅 I 、 Ⅲ