1.设n是描述问题规模的非负整数，下列程序段的时间复杂度是（）
x=0;
while (n>=(x+1)*(x+1))
x=x+1;
A.O(logn) B.O(n1/2) C.O(n) D.O(n2)
答案：B
2.若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是（）
A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历
答案：B
3.对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是（）
A.56 B.57 C.58 D.60
答案：C。（115+1）/2=58。
4.在任意一棵非空平衡二叉树（AVL树）T1中，删除某结点v之后形成平衡二叉树T2，再将v插入T2形成平衡二叉树T3。下列关于T1与T3的叙述中，正确的是（）
I．若v是T1的叶结点，则T1与T3可能不相同
II．若v不是T1的叶结点，则T1与T3一定不相同
III．若v不是T1的叶结点，则T1与T3一定相同
A．仅I B．仅II C．仅I、II D．仅I、III
答案：A
5.用有向无环图描述表达式(x+y)((x+y)/x)，需要的顶点个数至少是（）
A．5 B．6 C．8 D．9
答案：A
6.选择一个排序算法时，除算法的时空效率，下列因素中，还需要考虑的是（）I．数据的规模II．数据的存储方式III．算法的稳定性IV．数据的初始状态
A．仅III B．仅I、II C．仅II、III、IV D．I、II、III、IV
答案：D
7.现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查（线性探测再散列）法解决冲突。将关键字序列87,40,30,6,11,22,98,20依次插入HT后，HT查找失败的平均查找长度是（）
A．4 B．5.25 C．6 D．6.29
答案：平均查找长度为（9+8+7+6+5+4+3）/7=6。
8.设主串T=”abaabaabcabaabc”，模式串S=”abaabc”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（）
A．9 B．10 C．12 D．15
答案：B