2022-2023-2B卷

2023年9月10日

选择题

5个 每个3分

1 partition操作

进行一次partition操作后，和基元交换的元素是谁

2 简单的选择题，选一个错误的选项

A 插入排序可能会比快速排序块（给定特定序列）

B 堆排序的时间复杂度是O(n^3)

C 在最坏情况下，基于比较的排序算法时间复杂度是 下界(nlgn)

D ……(稳定排序是什么含义)，然后说计数排序是不稳定的

四个里面选一个错误的，显然是选D

3 搜索二叉树，含有1-9这9个元素。然后中序遍历，结果是什么？

ans 1 2 3 4 5 6 7 8 9

4 hash插入

给了一个序列，依次插入hash表，采用二次探测法，然后问最后一个元素插入到什么位置。

很简单，这个是二次探测法(c1=1,c2=1)

5NP问题，下列那个问题不是NPC问题

有一个问题是单源最短路问题。其他的都是TSP，SAT，哈密尔顿环问题。

ans 最短路

大题

5个

一 时间复杂度

1. 2个主定理，1个递推式（期中模板）
2. 二分搜索的递推式是什么？解释一波，给出最紧确的界。

二 树

1. 红黑树插入（超简单）全程只有红黑树不旋转的那种情况。
2. 黑高为3，红黑树最多多少个结点？
3. Huffman a,b,c,d,e,f 频数是1，2，4，8，16，32，构建一个Huffman树
4. 然后写出字符串abcdef的Huffman编码
5. (3分)对于六个字符a,b,c,d,e,f，可能出现Huffman编码之后的压缩率和定长编码一样吗？请证明

三 最小生成树

1. 给了张图，用prim搞出最小生成树。
2. 怎样用最小堆优化prim？为什么用最小堆能优化？
3. 三条边，权值在整个图中最小，e1,e2,e3，什么情况下他们三个都在最小生成树中？什么情况下他们三个部分在最小生成树中？
4. 有两个子图G1，G2,最小生成树分别是A1,A2，是否A1和A2中的每条边都在G1和G2的并集的最小生成树中？请证明正确或举出反例。

四 动态规划

1. 钢条切割问题（就最初级的钢条切割），给出方案即可(还比期中的简单)
2. 动态规划两种实现方法，说明之。
3. 期中跳台阶问题翻版（只不过更简单，一个最后能转化为斐波那契的问题）
4. 画出跳台阶问题的子问题图

五 摊还分析（贼基础，课后习题翻版）

n个操作组成的序列，第i个操作代价为3i（i为2的整数幂），否则就是2

分别通过聚合分析，核算法，势能法得出他们的摊还代价。