- 1. 除了准确数出语句的执行次数，在算法学习和应用中更多的是采用所谓“大O记法”来大致估计算法的效率（复杂性）。对于下面的算法进行分析：（1）指出正确的“大O记法”；（2）设n=3，算法结束时x和y那一个较大。
- 2. 通过一个走棋子的游戏进一步理解动态规划的设计思想。下图是一个m＊n的网格grid[m,n]，每个格子中的数字可以理解为跨越这个格子的距离，求从左上角grid[0,0]到右下角grid[m-1,n-1]距离之和最短的路径，要求从起点只能向右或向下走一格。图（a）中灰色标记是一条路径，总距离和为29，显然不是最短路径。通过每个网格可选路径的关系式可用递归法计算grid[0,0]到右下角grid
- 3. 继续采用题4的题干和图示。选择以下正确的选项。
- 4. 可以采用蛮力法（枚举法）求满足ax+by=d的整数x和y，设a、b为正整数。先用欧几里德算法求出d=gcd(a,b)，然后按下表所示的方法，x从1开始，逐步尝试y=-1、-2、......，每次y绝对值增1，计算ax+by，若ax+byd，则x+1，y不变，继续按上述方法改变y值并计算ax+by，直到最终满足ax+by=d，得到一组满足扩展式的x和y。请选择以下正确的选项。
- 5. 继续采用上题所描述的算法，选择以下正确的选项。
- 6. 一个字符串含8种字符，每个字符出现的频次分别为19，15，10，8，6，3，2，1。采用Huffman编码对这8个字符进行编码，形成的码串总位数是多少？码位均值是多少？
- 7. 这一题关于求解推销员问题的遗传算法。讲课中提到对于每一个样本基因（即节点排列实例），要做三种变异（变换）操作：交换，反转，循环。然后看变换后的结果的代价如何，留下其中优胜的。如此循环往复多次。现在考虑一个排列：0,1,2,3,4,5,6,7,8,9，并假设随机产生的位点指向2和6。试判断下面的选项哪个是正确的。
- 8. 根据算法的描述，估计某些语句（操作）的执行次数，是算法效率分析的要求，其中主要是对循环结构的理解。分析下面这个三重循环构成的算法，指出其中语句4的执行次数。做完了这一题，你一定也能按序列出其中print语句输出的所有三元组了。
- 9. 考虑有一袋硬币，设其中有2分和5分的共41枚，总值为154分。人们用符号表示这些量，a=2，b=5，m=41，s=154，并基于这些量设计了一个算法如下。最后的结果n有什么意义吗？
- 10. 继续第4题，下图是基于习题4所述的思路计算其中图（a）得到的部分结果，请填写“？”对应的路径值。
- 11. 此题考虑K-means聚类方法。类似于课程中的例子，假设有如下16个数据点：1,2,5,11,15,18,19,21,25,27,29,32,33,37,40,57。要聚成3类（从左到右，分别称为第一类，第二类，第三类），初始中心为10，20，30。试根据算法流程完成聚类。根据你的聚类结果，下面哪些说法是正确的。
- 12. 这一题是7.3题的继续。要考虑具体的投资组合了。下面给出的是一张填好的扩充后的表，包括了xi，第i个项目在对应Fi()时的投入。试给出该表数据对应的最优投资组合。（注：在确定Fi()的时候，可能有多种符合的情况，给出的xi只是代表其中一种。也就是说，实现最大总回报的最优投资组合可能有多种，但从这样的表中只会得到其中一种。）
- 13. 许多人小时候都做过“农夫，狼、羊和白菜”过河的智力题。这里就假设大家都是知道规则的。现在我们虚构一个农夫和5样动物（称它们为A，B，C，D，E）过河的题目。假设没农夫在场的时候，A要吃B，B要吃C，C要吃D，D要吃E；没有其他吃的关系了。同时还假设那条船上除了农夫外，还可以容纳最多2个动物。有人设计了一个让它们过河的算法如下：此题有三问：（1）这个算法是否成功地将它们都带过河了？（2）如果
- 14. 下图是采用课程介绍的多源路径算法得到最短路径前驱点矩阵，利用该矩阵选择如下正确的最短路径。
- 15. 采用递归法计算Fib(6)，一共发生了几次加法运算？
- 16. K近邻算法也可以用于做回归预测。通过某种距离度量关系找出样本集中与被测对象最相近的K个样本，分类任务是选择K个样本中占比最高的类别，来推断被测对象的类别；回归任务是，对K个样本某个被关注的属性计算均值，作为被测对象的预测值。回归同样可以进行加权计算，例如，以距离的倒数为权值计算均值。以下是一个利用KNN算法预测房屋出租价格的回归问题，每个样本包含一些房屋属性（建筑面积，卧室数，洗手间数，建
- 17. 继续上题，采用距离倒数加权计算均值，房屋租金为多少？（租金取整数）
- 18. 课上我们以城市群建设问题为背景，学习了层次聚类法。我们知道了，层次聚类法的一个核心问题是在合并两个类的时候，如何确定合并成的新类与其他类的距离。课上用的是“较大值”。这一题我们还是用课上的例子（数据稍微有点修改），见下图左。考虑用“平均值”作为确定距离的依据，也就是说，当两个类合并的时候，它们形成的新类与其他类的距离等于合并前它们两个距离的均值。下图右是经过了一次合并的结果，6个类变成了5
- 19. 两个整数a，b分别为55，34，采用扩展欧几里得算法得出一组解（x，y）为（13，-21），满足等式ax+by=gcd(a,b)。请选择以下正确的选项。
- 20. 以下有几个带权值的有向图和无向图（注意权值不同）。试判断是否可以用我们学习的Dijkstra算法和Floyd算法求解单源或多源最短路径。选择以下正确的选项。
- 21. 下图是一个4节点的有向图，利用Floyd多源最短路径算法依次经过节点A、B、C、D中转后，得到最短路径矩阵。编程实现多源最短路径算法，并列出A-D、B-D的路径值在经过中转点A、B、C、D后的更新值。
- 22. 有序列表list如下图所示，含10个元素。用如下二分法搜索算法搜索目标对象（1）x=15，（2）x=45。设变量low、high初值为0、9。以下选项是算法结束时变量low、high的值，请选择正确的选项。
- 23. 下图（a）是本节给出的哈夫曼编码树算法，树节点可以采用二维数组node[][]描述，设需要为s0~s4共计5个字符编码，其对应的出现频次分别为1，3，4，5，7。节点node[i][j]，i表示节点ID，j对应节点的不同属性，依次为对应的符号，频率，左右子节点，用“-1”表示对应的属性为空。运行算法1~3行后，形成叶节点如下图（b）所示，继续运行算法构建哈夫曼树中其他节点，选择以下正确的选
- 24. 《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数。操作过程为，1）先对两个整数用2约简；2）以较大的数减较小的数；3）以减数和差做为新的两个数，重复2），直到减数和差相等为止。则1）中约掉的若干个2与3）结束时的减数乘积为最大公约数。下图给出一个对应的算法，采用该算法求gcd(165，24)，选择以下正确的选项。
- 25. 假设5个符号出现的频次分别为：12，13，20，25，30，下图是对应这5个符号产生编码树，根据哈夫曼编码算法回答哪棵是最优编码树。（方便起见，节点中直接标注了对应的频次）
- 26. 一棵哈夫曼树有59个节点，则其叶子节点的个数是几个？
- 27. 采用习题1所述的二分搜索算法在一个有序列表中搜索目标对象x，如果查找成功就返回对应的序号。如果没有找到该目标对象，就把x插入到列表中，使得结果仍保持有序(假设序列中没有重复数据)。当x不在列表中，打破循环条件时，对应边界值仍保存在low、mid、high变量中，应该将x插入到什么位置（忽略越界问题）？
- 28. 本课程中谈到的“图”是由一些节点和边构成结构。若一个图有n个节点，每两个节点之间最多有1条边，那么它最多有多少条边？
- 29. 按照讲课中介绍的最小生成树算法，某人在下面的加权图上做了一次模拟执行，给出的边的顺序为：(a,b)，(d,e)，(b,e)，(b,c)。试考虑下面认识的正确性。
- 30. 在本课介绍的最小生成树算法中，每次为了决定选哪条边，都要把边集合看一遍。如果一个图有m条边，相当于每次都要做m次判断“是这条边吗？”。为了减少这种判断的次数，提高算法的效率，将图的边按照权值大小顺序排列是一个办法（假设不考虑顺序的产生）。以前面一题的图为例，将它的边集以两种方式（数据组织方式）给出如下，（1）是随机顺序的，（2）是从小到大顺序的。我们关心采用不同的数据组织方式对效率的影响。