1、设 n 是描述问题规模的非负整数 。
x0;
while(n>(x1)*(x1))
xx1;
a、o(logn) b、o(n^1/2) c、o(n) d、o(n^2)
答案b 解析
2、若将一棵树 t 转化为对应的二叉树 bt。
a、先序遍历 b、中序遍历 c、后序遍历 d、按层遍历
答案b 解析均为5,6,7,2,3,4, 1。因此选b.
3、对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点。
a、56 b、57 c、58 d、60
答案c 解析答案选c.
4、在任意一棵非空平衡二叉树。
i则 t1 与 t3 可能不相同 ii则 t1 与 t3 一定不相同 iii则 t1 与 t3 一定相同
a、仅 i b、仅 ii c、仅 i、ii d、仅 i、iii
答案a 解析 在非空平衡二叉树中插入结点一定插入在叶结点的位置。 若删除的是t1的叶结点平衡二叉树和以前不同。 对于比较绝对的说法ii和iii通常只需举出反例即可。 若删除的是t1的非叶结点平衡二叉树和以前不同。 若删除的是t1的非叶结点调整后的平衡二叉树和以前相同。.
5、下图所示的 aoe 网表示一项包含 8 个活动的工程。活动 d 的最早开始时间和最迟开始时间分别是。 a、3 和 7 b、12 和 12 c、12 和 14 d、15 和 15
答案c 解析14. 常规方法:按照关键路径算法算得到下表。 从表中可知故选c.
6、用有向无环图描述表达式 (x y)((x y) / x) 。
a、5 b、6 c、8 d、9
答案a 解析如下图所示。答案选
a.
7、选择一个排序算法时。
i数据的规模 ii数据的存储方式 iii算法的稳定性 iv数据的初始状态
a仅 iii b仅 i、ii c仅 ii、iii、iv di、ii、iii、iv
答案d 解析 当数据规模较小时可选择复杂度为0(n^2)的简单排序方法当数据规模大到内存无法放下时需选择外部排序方法,i正确。 数据的存储方式主要分为顺序存储和链式存储ii 正确。 若对数据稳定性有要求iii显然正确。 当数据初始基本有序时iv正确。所以选d.
8、现有长度为 11 且初始为空的散列表 ht。
a、4 b、5.25 c、6 d、6.29
答案c 解析如下表所示。 由于h(key)因此选c.
9、设主串 t 。
a、9 b、10 c、12 d、15
答案b 解析对于s有 根据kmp算法所以选b.
10、排序过程中 。
a、5, 2, 16, 12, 28, 60, 32, 72 b、2, 16, 5, 28, 12, 60, 32, 72 c、2, 12, 16, 5, 28, 32, 72, 60 d、5, 2, 12, 28, 16, 32, 72, 60
答案d 解析 就不能算是完整的一趟。 选项a故选d。
11、设外存上有 120 个初始归并段。
a、1 b、2 c、3 d、4
答案b 解析