算法考试试题与答案.pdf

一、填空题（本题分，每空分）、算法的复杂性是 的度量，是评价算法优劣的重要依据。、设为正整数，利用大“”记号，将下列程序段的执行时间表示为 的函数，则下面 程序段的时间复杂度为。、计算机的资源最重要的是 和 资源。因而，算法的复杂性有 和 之分。，的渐进性态 、递归是指函数 或者 通过一些语句调用自身。、分治法的基本思想是将一个规模为 的问题分解为 个规模较小的子问题，这些子问题 互相 且与原问题相同。二、选择题（本题 分，每小题 分）、分支限界法与回溯法都是在问题的解空间树 上搜索问题的解二者。求解目标不同搜索方式相同 求解目标不同搜索方式也不同 求解目标相同搜索方式不同 求解目标相同搜索方式也相同 、回溯法在解空间树 上的搜索方式是。深度优先 广度优先 最小耗费优先 活结点优先 、在对问题的解空间树进行搜索的方法中 一个活结点最多有一次机会成为活结点的是。回溯法 分支限界法 回溯法和分支限界法 回溯法求解子集树问题 、以下关于判定问题难易处理的叙述中正确的是。可以由多项式时间算法求解的问题是难处理的 需要超过多项式时间算法求解的问题是易处理的 可以由多项式时间算法求解的问题是易处理的 需要超过多项式时间算法求解的问题是不能处理的、设是定义在正数集上的正函数 如果存在正的常数 和自然数使得当 时有则称函数 当充分大时有上界 记作 即的阶 的阶。不高于 不低于 等价于 逼近 、对于含有个元素的子集树问题最坏情况下其解空间的叶结点数目为。、程序可以不满足以下特征 输入 输出 确定性 有限性 、以下 不能在线性时间完成排序 计数排序 基数排序 堆排序 桶排序 、以下 不一定得到问题的最优解 贪心算法 回溯算法 分支限界法 动态规划法 、以下（）不包括在图灵机结构中 控制器读写磁头计算器磁带 三、简答题（本题分，每小题分）、设有个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：每个选手必须与其他名选手比赛各一次；每个选手一天至多只能赛一次；循环赛要在最短时间内完成。（）如果，循环赛最少需要进行几天；（）当时，请画出循环赛日程表。、简述最优子结构性质。、简单描述回溯法基本思想。、何谓、问题 四、算法填空（本题分，每空分）、算法是解单源最短路径问题的贪心算法。请你阅读下面伪代码并在空白处填上适当的代码。是一个 个结点的有向图，它由成本邻接矩阵表示，表示结点到源结点 的最短路径长度，记录结点的父结点。所有 的邻接点 、某工厂预计明年有 个新建项目，每个项目的投资额及其投资后的收益 已知。投资总额为，问如何选择项目才能使总收益最大。、后问题 用二维数组存储皇后位置若第行第列放有皇后则为非 值 否则 值为。分别用一维数组、表示竖列、左斜线、右斜线是否放有棋子，有则值为否则值为。安全检查 放皇后 ；输出结果；试探下一行 ；去皇后 ；、通过键盘输入一个高精度的正整数的有效位数，去掉其中任意个数字后，剩 下的数字按原左右次序将组成一个新的正整数。编程对给定的和，寻找一种方案，使得剩 下的数字组成的新数最小。（输入 （）从串首开始找 删除串 的第 个字符 删去串首可能产生的无用零 输出 五、请你阐述算法的基本思想。并给出下图的最小生成树（要求画出生成树，分析过程可以省略）（本题分）六、算法分析题（本题分）数字全排列问题：任意给出从到的个连续的自然数的各种排列。如时，共有 以下种排列方式：，。算法描述如下。画出时递归调用时堆栈变化情况 写出相对应的值。设数组的初始值为，。输出；初始调用时 答案：一、填空题（本题 分，每空 分）、算法效率 、时间、空间 时间复杂度、空间复杂度 、直接 间接 、独立 二、选择题（本题 分，每小题 分）：三、简答题（本题分，每小题分）、（）天（分）；（）当时，循环赛日程表（分）。、某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为 叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确 定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度 优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过 程，逐步构造出状态空间树，即边搜索，边构造。、问题 ：也即是多项式复杂程度的问题。就是的问题，也即是多项式复杂程度的非确定性问题。四、算法填空（本题分，每空分）、（）（）（）（）、（）（）（）（）、（）（）五、阐述算法的基本思想（本题 分）分算法的基本思想是：设 是连通带权图，。首先置，然后，只要是的真子集，就作如下的贪心选择：选取满足条件，且最小的边，将顶点 添加到中。这个过程一直进行到时为止。在这个过程中选取到的所有边恰好构成的一棵最小生成树。（分）最小生成树如下：六、算法设计题（本题分）输出数组各元素值；初始调用时 输出，输出，输出，输出，输出 输出