2022-2023-2A卷

2023年6月29日13:00-15:00

5个选择(每个3分)15分+5个大题85分

选择题

1.快速排序partition操作

partition操作划分后数组是什么

其实就是考partition的过程

2.二叉搜索树与后序遍历

给了二叉树后序遍历的输出，选出先序遍历的输出

3.哈希表

插入位置在哪里

4.NP基本概念

NP和P问题的定义

好像有个选项是"P问题可以在多项式时间内被证明"

5.NP布尔SAT

...

大题

1.时间复杂度递归式计算

递归式的计算:

a.三个递归式

b.求strassen算法的递归式，并给出理由

2.树:红黑树，哈夫曼编码

a.将构建红黑树的过程画出来

b.黑高为6，最多有多少结点?

c.先利用Huffman算法画图，再与普通编码相比较，求压缩率

这里好像有一个假设频率都一样，Huffman怎么画图？(答案不唯一)

3.最小生成树Prim算法

a.给出七个点的坐标，先算出来距离，然后画图，再用最小生成树Prim算法得到生成树

b.采用邻接链表和邻接矩阵来表示答案

c.限制一段路程必须有，如何规划路线

4.动态规划

a.常规的矩阵链乘法题目，给出过程和答案

b.把第一个矩阵改成(a,20),情况会如何变化?

5.摊还分析

a.写一下摊还分析的三种方法(比如势能法)基本思路

b.利用摊还分析，来分析建堆函数和堆调整heapify函数的开销

其他信息

1.题目整体有难度，而且题量较大，普遍反映做的并不是很好;

2.期中的内容并没有考很多，从红黑树开始，后面的章节基本上每周一题;

3.在选择题的选项中，涉及到了近似算法的内容