算法押题卷

【说明】

1、本试卷仅作为自用考前题目预测作用，不具有任何正式效力，且严肃声明：此试卷不具有复习代表性，仅供大家参考。

2、变长数组类型 vector、栈类型 stack、队列类型 queue、最小堆类型 minheap、最大堆类型 maxheap和矩阵类型 Matrix以及标准库中的常用算法函数等可直接使用，无需自行定义。

3、考试语言自定义，建议使用c++，不会的地方请勿直接使用中文表示，可以适当使用伪码。

一、基础知识题（每题10分，共4题，共40分）

1、写出下列函数的上界估计，并说明结果的正确性。（10分）

（1）

（2）

（3）

（4）

（5）

2、请使用一种程序设计语言描述二叉树的按层次遍历算法。该算法的C++函数原型规定为“template<class T, class Func> void LevelOrder(BtNode *x, Func Visit);”。（10分）

3、请使用一种程序设计语言改写连通图的深度优先遍历算法，要求能够计算出每个顶点在深度优先生成树中的层次（图使用邻接矩阵表示）。（10分）

4、编写一个使用分枝限界方法生成含 n 个分量的所有排列的子程序。该子程序的C++函数原型规定为“void Perm(int n);”。（10分）

二、算法设计题（每题10分，共6题，共60分）

5、使用一种程序设计语言写出选择排序算法的程序（升序排列），并给出时间复杂性。该算法的C++函数原型规定为“template void SelectionSort(T X, intn);”。（10分）

6、请使用一种程序设计语言描述二叉树的按层次遍历算法。该算法的C++函数原型规定为“template<class T, class Func> void LevelOrder(BtNode *x, Func Visit);”。（10分）

7、使用一种程序设计语言描述最小生成树的Prim算法。已知：G 是具有 n 个顶点的无向加权图，Matrix是矩阵类型，该算法的C++函数原型规定为“bool Prim(const Matrix &G, int v, vector &prev);”。（10分）

8、使用一种程序设计语言描述求解0/1背包问题的动态规划算法，并给出时间复杂性（假设所使用的程序设计语言已经定义vector和map等数据结构）。（10分）

9、使用一种程序设计语言描述求解旅行商问题（输出最优解）的回溯算法。该算法的C++函数原型规定为“vector TSP(const Matrix &G);”。（10分）

10、请为子集和问题（是否存在和为t的子集）设计一个拉斯维加斯算法。该算法的C++函数原型规定为“bool SetSum(const vector &W, int t, vector &X);”。（10分）

写在最后：该押题卷的难度、题型完全依照于样卷的模式，题目则完全依赖于《习题选讲》，也就是说选择其实非常少，不建议各位以试卷作为复习的重点，这份试卷与其说是用来押题，不如说是用来检验各位临考的能力。为了依照样卷模式，牺牲了一定的题目难度，所以这套押题卷其实总体来说可能偏容易？（误）

希望大家都能考出自己理想的成绩QWQ！ ——By Alexie-Z-Yevich 2022.5.8