MOOC 算法初步-北京大学 中国大学慕课答案

MOOC算法初步-北京大学中国大学慕课答案1.5单元测验1、问题：本节反复用的一个例子是用无刻度桶的量水问题。现在还是假设有A（7升）、B（5升）两个桶。有人给出了一个算法，请问它的执行将导致的结果。选项：A、A=6,B=0B、A=3,B=0C、A=0,B=3D、算法描述不清楚正确答案:【A=3,B=0】2、问题：许多人小时候都做过“农夫，狼、羊和白菜”过河的智力题。这里就假设大家都是知道规则的。现在我们虚构一个农夫和5样动物（称它们为A，B，C，D，E）过河的题目。假设没农夫在场的时候，A要吃B，B要吃C，C要吃D，D要吃E；没有其他吃的关系了。同时还假设那条船上除了农夫外，还可以容纳最多2个动物。有人设计了一个让它们过河的算法如下：此题有三问：（1）这个算法是否成功地将它们都带过河了？（2）如果那条小船除农夫外，最多还只能容纳1个动物，有可能设计一个成功的算法吗？（3）假设小船除农夫外，最多还可以容纳2个动物，但总共有6个动物（还是那种链式吃关系），有可能设计一个成功的算法吗？选项：A、（1）是（2）可能（3）可能B、（1）否（2）可能（3）可能C、（1）是（2）不可能（3）不可能D、（1）否（2）不可能（3）不可能正确答案:【（1）是（2）不可能（3）不可能】3、问题：变量及其赋值，是讨论计算机算法和程序的一个最基本的概念。在算法描述的表达中，有时用箭头，例如x1，表示让变量x的值为1，而xx+1则表示将x的当前值加上1后再放到x中。很多时候，人们也用等号（=），例如x=1，x=x+1，分别与x1，xx+1是相同的意思。也就是说，这里的等号不同于数学中的等号。算法描述中为了表示数学意义上的“相等”，则常常用符号“==”，不相等就用“!=”。这些描述算法操作的符号对于初学者，刚开始可能会有些困惑，习惯就好了。考虑下面的算法，该算法执行输出的前3个数为:选项：A、20，10，5B、10，5，2.5C、10，5，16D、上面的都不对正确答案:【10，5，16】4、问题：在上一题中的第2条语句，写起来比较啰嗦，常常用所谓“while循环”来表示。第3条语句，则用所谓条件语句“ifthenelse”来表示。于是，上面的算法也可以描述为：现在的问题是，一共会输出几个数，该算法就结束了。也就是问循环执行的次数。选项：A、3个B、5个C、7个D、9个正确答案:【7个】5、问题：根据算法的描述，估计某些语句（操作）的执行次数，是算法效率分析的要求，其中主要是对循环结构的理解。分析下面这个三重循环构成的算法，指出其中语句4的执行次数。做完了这一题，你一定也能按序列出其中print语句输出的所有三元组了。选项：A、3次B、6次C、10次D、27次正确答案:【10次】6、问题：除了准确数出语句的执行次数，在算法学习和应用中更多的是采用所谓“大O记法”来大致估计算法的效率（复杂性）。对于下面的算法进行分析：（1）指出正确的“大O记法”；（2）设n=3，算法结束时x和y那一个较大。选项：A、O(n)，xyB、O(n^2)，xyC、O(n^3)，xyD、O(n^4)，xy正确答案:【O(n^3)，xy】7、问题：在讲到算法类型的时候，我们提到一种区别的维度是“数值计算”和“非数值计算”。数值计算通常体现出“迭代收敛”的特征。例如下面的算法（牛顿法求的根）就是一个典型的样式。设x=5，e=0.01，问该算法循环将会执行多少次（提示：可编程或用excel验证）。选项：A、少于5次B、在5次和10次之间C、在10次和20次之间D、算法不会结束（死循环）正确答案:【在5次和10次之间】8、问题：我们回到前面的第5题。那题看起来没什么实际意义，但基于对它的理解，可以很容易构造一个解“真问题”的算法：求哪些整数（三元组，a,b,c）满足勾股定律。我们知道a=3，b=4和c=5是满足的。现在的问题就是，给定一个上限n，有哪些小于n的整数a，b和c会满足勾股定理呢？要求是，如果有的话，一个也不能漏。稍微想一下，可知满足等式的a、b和c中不可能有相等的，因而总有个大小顺序，设a最小，c最大，这样就等价于我们要求0abcn，满足。对前面第5题的算法稍作修改（将其循环体中的简单输出改成一个条件输出），就有了下面这个很实用的求直角三角形整数勾股弦的算法：现在关心算法中的第5句会被执行的次数（尽管不一定每次都有输出）。显然这是一个与n有关的量。下面哪一种或几种说法是正确的。选项：A、(n-1)^3次B、(n-1)*(n-2)*(n-3)次C、(n-1)*(n-2)*(n-3)/6次D、O(n^3)正确答案:【(n-1)*(n-2)*(n-3)/6次#O(n^3)】2.4单元测验1、问题：利用欧几里得扩展式中系数的关系式：，，（其中q为当前a除以b取整，设ab），试用手工计算求解整数34和21扩展式中系数的回推过程。采用辗转相除计算gcd(34,21)，当余数为0时，取。选项：，，利用上述关系式，可得，。试计算A、x4=-1，y4=2B、x4=2，y4=-3C、x4=-3，y4=5D、x4=-8，y4=13正确答案:【x4=2，y4=-3】2、问题：设a、b为两个正整数，整数x0、y0满足a*x0+b*y0=gcd(a,b)，即x0、y0是（a,b）欧几里得扩展式的一组解。对于以下关于求解满足a*x+b*y=gcd(a,b)，x、y通解的描述，请选择正确的选项，k为整数。选项：A、x=x0-(b)*k，y=y0+a*kB、x=x0-(a/gcd(a,b))*k，y=y0+(b/gcd(a,b))*kC、x=x0-a*k，y=y0+b*kD、x=x0-(b/gcd(a,b))*k，y=y0+(a/gcd(a,b))*k正确答案:【x=x0-(b/gcd(a,b))*k，y=y0+(a/gcd(a,b))*k】3、问题：设a、b为两个正整数，且ab,请选择以下正确的选项。选项：A、若a、b均为偶数，则gcd(a，b)=2gcd(a/2，b/2)B、若a为偶数，b为奇数，则gcd(a，b)=gcd(a/2，b)C、gcd(a，b)=gcd(a-b,b)D、gcd(a，b)=gcd(a-b,a)正确答案:【若a、b均为偶数，则gcd(a，b)=2gcd(a/2，b/2)#若a为偶数，b为奇数，则gcd(a，b)=gcd(a/2，b)#gcd(a，b)=gcd(a-b,b)#gcd(a，b)=gcd(a-b,a)】4、问题：两个整数a，b分别为55，34，采用扩展欧几里得算法得出一组解（x，y）为（13，-21），满足等式ax+by=gcd(a,b)。请选择以下正确的选项。选项：A、13是满足ax+by=gcd(a,b)，x绝对值最小的整数B、21是满足ax+by=gcd(a,b)，y绝对值最小的整数C、x的绝对值还可以减小，会引发y的绝对值发生变化D、y的绝对值还可以减小，会引发x的绝对值发生变化正确答案:【13是满足ax+by=gcd(a,b)，x绝对值最小的整数#21是满足ax+by=gcd(a,b)，y绝对值最小的整数】5、问题：设a、b为两个正整数，请选择以下正确的选项。选项：A、gcd(a/m,b/m)=gcd(a，b)/m，其中，m为整数，且能被a、b整除B、lcm(a,b)=a*b/gcd(a,b),（lcm(a,b)为a和b的最小公倍数）C、gcd(ab,m)=gcd(a,m)*gcd(b,m)，m为整数D、以上都不对正确答案:【gcd(a/m,b/m)=gcd(a，b)/m，其中，m为整数，且能被a、b整除#lcm(a,b)=a*b/gcd(a,b),（lcm(a,b)为a和b的最小公倍数）#gcd(ab,m)=gcd(a,m)*gcd(b,m)，m为整数】6、问题：可以采用蛮力法（枚举法）求满足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。请选择以下正确的选项。选项：A、此方法得到的x，y值不一定是所有满足扩展式中绝对值最小的B、采用这个蛮力法计算a=7，b=5，得到的x、y值为3、-4C、若取x0，y0，仍按上表步骤和算式，即，x从-1开始，尝试y=1、2、......，也可以得到一组x、y解满足ax+by=dD、以上都不对正确答案:【此方法得到的x，y值不一定是所有满足扩展式中绝对值最小的#采用这个蛮力法计算a=7，b=5，得到的x、y值为3、-4】3.3单元测验1、问题：有序列表list如下图所示，含10个元素。用如下二分法搜索算法搜索目标对象（1）x=15，（2）x=45。设变量low、high初值为0、9。以下选项是算法结束时变量low、high的值，请选择正确的选项。选项：A、（1）low=5，high=4；（2）low=10，high=9B、（1）low=6，high=5；（2）low=11，high=10C、（1）low=4，high=5；（2）low=10，high=9D、（1）low=4，high=5；（2）low=9，high=10正确答案:【（1）low=5，high=4；（2）low=10，high=9】2、问题：采用习题1所述的二分搜索算法在一个有序列表中搜索目标对象x，如果查找成功就返回对应的序号。如果没有找到该目标对象，就把x插入到列表中，使得结果仍保持有序(假设序列中没有重复数据)。当x不在列表中，打破循环条件时，对应边界值仍保存在low、mid、high变量中，应该将x插入到什么位置（忽略越界问题）？选项：A、x应该插入到结束循环时mid值所指的位置B、x应该插入到结束循环时low值所指的位置C、x应该插入到结束循环时high值所指的位置D、不一定正确答案:【x应该插入到结束循环时low值所指的位置】3、问题：采用二分法求解方程F(x)=0的一个实根，有时很难快速获得满足F(a)*F(b)0的两个端点(a,b)。如果函数F(x)能写成两个简单函数差的形式，F(x)=f(x)-g(x)，例如，求方程：的解，，，一种求端点(a,b)的方法是画出f(x)、g(x)的函数图，两条曲线相交的点即为方程F(x)=0的解。在图中找到这些相交的点，就可以估测出对应相交点两侧的端点。利用这个方法估测方程选择以下选项中与实根最接近的区间。实数根的两个端点a和b，选项：A、[3，4]B、[2，3]C、[3，3.5]D、[3.5，4]正确答案:【[3.5，4]】4、问题：假设有序列表中可能会有某些重复的元素，要求采用二分搜索查找目标对象时，找到后能定位到重复元素的第一个。以下给出了（a）、（b）、（c）、（d）四个算法（循环体外部分省略），希望在while循环结束时，若列表中包含搜索对象x，low值指向与x匹配的第一个元素。请选择正确的选项。选项：A、(a)满足要求B、（b）满足要求C、（c）满足要求D、（d）满足要求正确答案:【(a)满足要求#（c）满足要求】4.4单元测验1、问题：假设5个符号出现的频次分别为：12，13，20，25，30，下图是对应这5个符号产生编码树，根据哈夫曼编码算法回答哪棵是最优编码树。（方便起见，节点中直接标注了对应的频次）选项：A、（a）、（b）是最优编码树B、（b）、（c）是最优编码树C、（a）、（d）是最优编码树D、（b）、（d）是最优编码树正确答案:【（b）、（d）是最优编码树】2、问题：某信源有8种符号X={A1,A2,A3,A4,A5,A6,A7,A8}，在数据中出现的概率为P=(0.28,0.18,0.17,0.11,0.10,0.08,0.06,0.02)，请构建哈夫曼编码树，并选择以下正确的选项。选项：A、码位均值为2.78B、得到的哈夫曼编码，2个2位码，3个3位码，1个4位码，2个5位码C、得到的哈夫曼编码，1个1位码，2个2位码，2个3位码，1个4位码，2个5位码D、码位均值为2.61正确答案:【码位均值为2.78#得到的哈夫曼编码，2个2位码，3个3位码，1个4位码，2个5位码】3、问题：关于哈夫曼编码算法，请选择以下正确的选项。选项：A、哈夫曼编码算法得到的编码树是一个最优编码树B、基于贪心策略得到的结果是最优结果C、哈夫曼编码树只要设定好左右边值是“0”还是“1”，得到的编码是唯一的D、哈夫曼编码树一定是一棵满二叉树（除叶节点外每个节点都有两个子节点）正确答案:【哈夫曼编码算法得到的编码树是一个最优编码树#哈夫曼编码树一定是一棵满二叉树（除叶节点外每个节点都有两个子节点）】4、问题：下图（a）是本节给出的哈夫曼编码树算法，树节点可以采用二维数组node[][]描述，设需要为s0~s4共计5个字符编码，其对应的出现频次分别为1，3，4，5，7。节点node[i][j]，i表示节点ID，j对应节点的不同属性，依次为对应的符号，频率，左右子节点，用“-1”表示对应的属性为空。运行算法1~3行后，形成叶节点如下图（b）所示，继续运行算法构建哈夫曼树中其他节点，选择以下正确的选项。选项：A、算法结束时，node[5][:]=[-1,4,0,1]B、算法结束时，node[6][:]=[-1,9,2,5]C、算法结束时，node[7][:]=[-1,14,5,6]D、算法结束时，node[8][:]=[-1,20,6,7]正确答案:【算法结束时，node[5][:]=[-1,4,0,1]#算法结束时，node[8][:]=[-1,20,6,7]】5、填空题：一棵哈夫曼树有59个节点，则其叶子节点的个数是几个？正确答案:【30】5.4单元测验1、问题：本课程中谈到的“图”是由一些节点和边构成结构。若一个图有n个节点，每两个节点之间最多有1条边，那么它最多有多少条边？选项：A、nB、n-1C、n(n-1)D、n(n-1)/2正确答案:【n(n-1)/2】2、问题：“连通图”是一类很重要的图。它的直观含义是从任何一个节点都可以经由边到达任何一个其他节点。若一个连通图有n个节点，那么它最少有多少条边？（有最少边数的连通图有个“昵称”——“树”）。选项：A、n+1B、nC、n-1D、n-2正确答案:【n-1】3、问题：下图是一个连通图（4个节点，5条边），可以通过删去若干条边留下一棵树（这样的树称为原图的“生成树”）。此题两问。（1）你认为从中需要删除多少条边才能留下一棵生成树？（2）一共有多少种可能的删法？选项：A、（1）1条；（2）5种可能B、（1）2条；（2）10种可能C、（1）1条；（2）4种可能D、（1）2条；（2）8种可能正确答案:【（1）2条；（2）8种可能】4、问题：“最小生成树”是针对加权连通图而言的。下面是一个加权图（最左边）和它的几个生成树（每条边附近的数字为权值）。哪个（哪些）是最小生成树呢？选项：A、图（2）B、图（3）C、图（4）D、都不是正确答案:【图（4）】5、问题：考虑一个加权图有5个节点（a,b,c,d,e）和8条边（见下表）。按照本节课介绍的算法，应该是涉及到节点d和e的(d,e)边被选中，然后以此为基础一条条选后续的边，每一条边将带来一个新节点，形象上看就是一棵树慢慢长出来，最后包括了所有节点。试给出节点“长出来”的顺序。选项：A、d,e,c,b,aB、d,e,a,b,cC、d,e,b,c,aD、d,e,c,a,b正确答案:【d,e,c,b,a】6、问题：在本课介绍的最小生成树算法中，每次为了决定选哪条边，都要把边集合看一遍。如果一个图有m条边，相当于每次都要做m次判断“是这条边吗？”。为了减少这种判断的次数，提高算法的效率，将图的边按照权值大小顺序排列是一个办法（假设不考虑顺序的产生）。以前面一题的图为例，将它的边集以两种方式（数据组织方式）给出如下，（1）是随机顺序的，（2）是从小到大顺序的。我们关心采用不同的数据组织方式对效率的影响。例如，对于方式（1），为了得到最开始的边（d,e），一共要问8次“是这条边吗？”。对于方式（2），则只需要问2次，一次是（d,e），一次是（c,d），发现它的权值大于（d,e）的权值，就知道不用看下面的了。此题要回答的是，在两种方式下，分别总共问了多少次。（假设一条边被选取后依然留在表中，于是后面还会看到它）选项：A、（1）20；（2）13B、（1）24；（2）15C、（1）32；（2）17D、（1）40；（2）19正确答案:【（1）32；（2）17】6.4单元测验1、问题：采用递归法计算Fib(6)，一共发生了几次加法运算？选项：A、7次B、12次C、20次D、30次正确答案:【12次】2、问题：采用如下课程介绍的快速幂算法计算矩阵C的44次幂，试问共发生了几次矩阵相乘运算？（忽略矩阵内部元素的运算）选项：A、5次B、8次C、10次D、11次正确答案:【8次】3、问题：继续第4题，下图是基于习题4所述的思路计算其中图（a）得到的部分结果，请填写“？”对应的路径值。选项：A、dist[2,0]=8，dist[1,2]=6，dist[2,1]=8，dist[2,2]=8，dist[4,4]=18B、dist[2,0]=8，dist[1,2]=9，dist[2,1]=8，dist[2,2]=9，dist[4,4]=22C、dist[2,0]=8，dist[1,2]=9，dist[2,1]=8，dist[2,2]=9，dist[4,4]=18D、dist[2,0]=7，dist[1,2]=6，dist[2,1]=5，dist[2,2]=9，dist[4,4]=19正确答案:【dist[2,0]=8，dist[1,2]=9，dist[2,1]=8，dist[2,2]=9，dist[4,4]=18】4、问题：采用课程介绍的快速幂算法（如习题2所示）计算矩阵C的n次幂，算法运行过程中用power_matrix存放矩阵C的奇数次幂，coef_matrix存放矩阵C的自乘结果，设幂次n=11，下图给出了算法循环第1轮和第2轮后，power_matrix和coef_matrix的运行结果，请给出第3轮和第4轮后，power_matrix和coef_matrix的运行结果。（即，填写表中红色“？”对应的内容）选项：A、第3轮后，power_matrix=B、第3轮后,power_matrix=C、第4轮后，power_matrix=D、第4轮后,power_matrix=正确答案:【第3轮后，power_matrix=,coef_matrix=,coef_matrix=,coef_matrix=,coef_matrix=,coef_matrix=#第4轮后,,coef_matrix=】power_matrix=5、问题：通过一个走棋子的游戏进一步理解动态规划的设计思想。下图是一个m*n的网格grid[m,n]，每个格子中的数字可以理解为跨越这个格子的距离，求从左上角grid[0,0]到右下角grid[m-1,n-1]距离之和最短的路径，要求从起点只能向右或向下走一格。图（a）中灰色标记是一条路径，总距离和为29，显然不是最短路径。通过每个网格可选路径的关系式可用递归法计算grid[0,0]到右下角grid[m-1,n-1]的最短路径，但效率会非常低。试想如果只有一行网格，则只含一条路径，起点到每个格子的最短距离即每个格子的值累计相加，如图（b）所示。如果有两行网格，起点到第二行每个格子的最短距离是，同列上一行的值，或者同行前一列的值，二者中较小者加上当前格子的值，多行网格路径以此类推。计算grid[0,0]到grid[m-1,n-1]的最短路径问题，就是从左到右，从上到下填写一张m*n的二维路径表，表中的值代表起点到当前格子的最短路径，表的右下角对应的结果就是我们要求的最短路径。这是一个典型的动态规划过程。基于上述思路，二维数组grid[i,j]表示网格[i,j]的路径值，dist[i,j]存放起点到每个网格的最短距离，对于dist[i,j]的路径更新规则，请选择以下正确的选项。选项：A、dist[0,0]=grid[0,0]B、if(0im)，dist[i,0]=dist[i-1,0]+grid[i,0]C、if(0imand0jn),dist[i,j]=dist[i-1,j-1]+min(grid[i-1,j],grid[i,j-1])+grid[i,j]D、if(0imand0jn),dist[i,j]=min(dist[i-1,j],dist[i,j-1])+grid[i,j]正确答案:【dist[0,0]=grid[0,0]#if(0im)，dist[i,0]=dist[i-1,0]+grid[i,0]#if(0imand0jn),dist[i,j]=min(dist[i-1,j],dist[i,j-1])+grid[i,j]】7.4单元测验1、问题：此题是7.1题的继续。用相同的例子数据，我们看课上介绍的动态规划算法的执行过程。这里只考虑最优回报的计算过程，暂不考虑具体的投资组合形式。我们已经知道，动态规划算法的执行过程可以用逐项填一张表的过程来形象地展示。我们的例子是总投资额6万，要考虑在3个项目的分配，因此要填一个7行，3列的表，对应下表的左边3列（右边3列此题用不到）。现在看到的是大多数表项已经有的结果。试按照算法流程，给出所标识的F1(1)，F2(3)和F3(5)的值，其中Fi(x)是在前i个项目上投资x可以获得的最大回报。（提示：采用上题给出的三个项目的回报函数，结合表中已有部分数据计算）选项：A、1，3，6B、2，5，9C、2，7，11D、3，8，13正确答案:【2，7，11】2、问题：这一题是7.2题的继续。设想在决定投资方案前临时增加了第4个项目，它的回报函数是f4(x)=2*x。于是你在前面算的基础上继续计算第4列的数据（也就是对应F4()的数据）就可以了。试给出F4(2)，F4(4)和F4(6)。选项：A、F4(2)=3；F4(4)=8；F4(6)=13B、F4(2)=4；F4(4)=9；F4(6)=14C、F4(2)=5；F4(4)=9；F4(6)=14D、F4(2)=5；F4(4)=9；F4(6)=13正确答案:【F4(2)=5；F4(4)=9；F4(6)=13】3、问题：这一题是7.3题的继续。要考虑具体的投资组合了。下面给出的是一张填好的扩充后的表，包括了xi，第i个项目在对应Fi()时的投入。试给出该表数据对应的最优投资组合。（注：在确定Fi()的时候，可能有多种符合的情况，给出的xi只是代表其中一种。也就是说，实现最大总回报的最优投资组合可能有多种，但从这样的表中只会得到其中一种。）选项：A、x1=0，x2=1，x3=1，x4=4B、x1=1，x2=2，x3=2，x4=1C、x1=1，x2=2，x3=3，x4=0D、x1=0，x2=2，x3=0，x4=4正确答案:【x1=1，x2=2，x3=2，x4=1】4、问题：优化投资组合问题一般来说是很复杂的，本课中介绍的是一个相对简化的版本。此题在于对这种版本投资组合问题的理解。设想你有6万元，要在3个项目上做投资安排。三个项目的投资回报函数如下表所示。试目测判断下列给出的哪些是最佳投资组合。选项：A、在项目1上投0，在项目2上投6，在项目3上投0B、在项目1上投2，在项目2上投2，在项目3上投2C、在项目1上投1，在项目2上投2，在项目3上投3D、在项目1上投0，在项目2上投3，在项目3上投3正确答案:【在项目1上投2，在项目2上投2，在项目3上投2#在项目1上投1，在项目2上投2，在项目3上投3】8.5单元测验1、问题：下图是一个4节点的有向图，利用Floyd多源最短路径算法依次经过节点A、B、C、D中转后，得到最短路径矩阵。编程实现多源最短路径算法，并列出A-D、B-D的路径值在经过中转点A、B、C、D后的更新值。选项：A、A-D的更新过程：B、A-D的更新过程：----9，B-D的更新过程过程：9-9-9-8-10-9，B-D的更新过程过程：9-9-8-8C、A-D的更新过程：-10-9-9，B-D的更新过程过程：9-9-8-8D、A-D的更新过程：-9，B-D的更新过程过程：9-8-8-8--正确答案:【A-D的更新过程：-10-9-9，B-D的更新过程过程：9-9-8-8】2、问题：下图是一个7节点连通图，权值如图所示。尝试利用Dijkstra算法思路手工计算源点A到其他点的最短路径，并选择以下正确的选项。选项：A、当节点集S={A,C,F,B}，时，下一个进入S的节点是EB、当节点集S={A,C,F,B}，时，下一个进入S的节点是DC、A-G最短路径的前驱节点是ED、A-G最短路径的前驱节点是D正确答案:【当节点集S={A,C,F,B}，时，下一个进入S的节点是E#A-G最短路径的前驱节点是D】3、问题：下图是采用课程介绍的多源路径算法得到最短路径前驱点矩阵，利用该矩阵选择如下正确的最短路径。选项：A、D-A的最短路径是，D-C-B-AB、A-B的最短路径是，A-C-BC、E-C的最短路径是，E-D-B-CD、E-D的最短路径是，E直接连接到D正确答案:【A-B的最短路径是，A-C-B#E-C的最短路径是，E-D-B-C#E-D的最短路径是，E直接连接到D】4、问题：下图中，i-j的路径是经过单源路径算法（Dijkstra）或多源路径算法（Floyd）得到的最短路径，中间节点包含节点v1，v2，…vk。对于单源路径算法，i表示源点（s），对于多源路径算法，i可以是任意节点。请选择以下正确的选项。选项：A、采用Floyd算法，能保证点i-j间的中间节点v1，v2，…vk，包括i，j中任意节点对之间都是最短路径B、采用Dijkstra算法，能保证源点i到所有中间节点v1，v2，…vk，以及j是最短路径，不能确保这些节点之间也一定是最短路径C、采用Dijkstra算法，能保证源点i-j是最短路径，不能确保路径中其他节点对之间也一定是最短路径D、采用Dijkstra算法，能保证源点i-j间的中间节点v1，v2，…vk，包括i，j中任意节点对之间都是最短路径正确答案:【采用Floyd算法，能保证点i-j间的中间节点v1，v2，…vk，包括i，j中任意节点对之间都是最短路径#采用Dijkstra算法，能保证源点i-j间的中间节点v1，v2，…vk，包括i，j中任意节点对之间都是最短路径】5、问题：继续采用题4的题干和图示。选择以下正确的选项。选项：A、采用Floyd算法，i-j路径中所有相邻节点之间一定都是直接连接的，即i-v1，v1-v2，……vk-j都是直接连接B、采用Floyd算法，i-j路径中i-v1，vk-j一定直接连接，其他节点则不一定C、采用Dijkstra算法，i-j路径中所有相邻节点之间一定都是直接连接的，即i-v1，v1-v2，……vk-j都是直接连接D、采用Dijkstra算法，i-j路径中i-v1，vk-j一定直接连接，其他节点则不一定正确答案:【采用Floyd算法，i-j路径中所有相邻节点之间一定都是直接连接的，即i-v1，v1-v2，……vk-j都是直接连接#采用Dijkstra算法，i-j路径中所有相邻节点之间一定都是直接连接的，即i-v1，v1-v2，……vk-j都是直接连接】9.4单元测验1、问题：“聚类”，也是一个日常生活中的用语，在交谈中用它，人们基本也知道是什么意思。但在讨论算法的语境下（或者说作为一个技术专用术语），它有特定的含义。下面这些陈述句中所体现的情况是否属于“聚类”的范畴？试在算法的背景下指出哪些不属于聚类的范畴。选项：A、如果把人们的受教育程度分为“受过高等教育”和“没有受过高等教育”两类，张三刚从大学毕业了，因此他应该属于“受过高等教育”类别的。B、幼儿园举办亲子活动，午餐的时候，为了便于交流，特意安排家长们聚在一起，小朋友们聚在一起。C、产品经过自动检测的流水线，就被分成了次品和正品两类。D、经过长期的观察研究，发现小学生在课堂上的表现可以分为“积极踊跃”“沉静寡言”和“心里有数”三种类别。正确答案:【如果把人们的受教育程度分为“受过高等教育”和“没有受过高等教育”两类，张三刚从大学毕业了，因此他应该属于“受过高等教育”类别的。#幼儿园举办亲子活动，午餐的时候，为了便于交流，特意安排家长们聚在一起，小朋友们聚在一起。#产品经过自动检测的流水线，就被分成了次品和正品两类。】2、问题：课上我们以城市群建设问题为背景，学习了层次聚类法。我们知道了，层次聚类法的一个核心问题是在合并两个类的时候，如何确定合并成的新类与其他类的距离。课上用的是“较大值”。这一题我们还是用课上的例子（数据稍微有点修改），见下图左。考虑用“平均值”作为确定距离的依据，也就是说，当两个类合并的时候，它们形成的新类与其他类的距离等于合并前它们两个距离的均值。下图右是经过了一次合并的结果，6个类变成了5个类。请理解其中新类“南京合肥”与其他类的距离。试继续做两次合并，达到3个类。下列说法哪些是正确的。选项：A、在结果的3个类中，武汉和南昌属于同一类B、在结果的3个类中，上海与南京合肥属于同一类C、在结果的3个类中，上海与杭州属于同一类D、上面的都不对正确答案:【在结果的3个类中，上海与南京合肥属于同一类#在结果的3个类中，上海与杭州属于同一类】3、问题：此题考虑K-means聚类方法。类似于课程中的例子，假设有如下16个数据点：1,2,5,11,15,18,19,21,25,27,29,32,33,37,40,57。要聚成3类（从左到右，分别称为第一类，第二类，第三类），初始中心为10，20，30。试根据算法流程完成聚类。根据你的聚类结果，下面哪些说法是正确的。选项：A、根据初始中心，最开始1,2,5,11,15同属第一类，但后来15属于第二类了B、聚类结束时，第二类最大，有7个数C、聚类结束时，第三类的中心大于35D、聚类结束时，11也属于第二类了正确答案:【根据初始中心，最开始1,2,5,11,15同属第一类，但后来15属于第二类了#聚类结束时，第二类最大，有7个数#聚类结束时，第三类的中心大于35】4、问题：本节课最后我们特别介绍了如何将层次聚类和K-means聚类结合起来，优势互补的问题。下面哪些说法是合适的。选项：A、层次聚类的效率低，K-means聚类的质量和效率都和初始中心的选取很有关系B、结合的方式是先在少部分数据上运行层次聚类，为后续K-means聚类产生较好的初始中心C、结合的方式是先在少部分数据上运行层次聚类，为后续K-means聚类产生较好的初始中心D、以上都不对正确答案:【层次聚类的效率低，K-means聚类的质量和效率都和初始中心的选取很有关系#结合的方式是先在少部分数据上运行层次聚类，为后续K-means聚类产生较好的初始中心#结合的方式是先在少部分数据上运行层次聚类，为后续K-means聚类产生较好的初始中心】10.3单元测验1、问题：假设一门课将一部分内容安排成了线上内容，包括课程相关的视频和集中讨论两部分。对于线上内容学生可以自愿选择是否参加，不影响总成绩。学期结束时，老师希望对学生在线上的学习情况用KNN进行分析，老师能够统计到每个学生线上收看视频的时间，以及参与集中讨论的时间。现在老师希望做两个分类工作：（1）根据学生看视频和参与讨论的时间，将学生分成“自主学习型”（看视频较多）和“集中学习型”（参与讨论较多）两类。（2）根据学生参与线上内容的程度，将学生分成“课堂学习型”和“课堂+线上学习型”。试问对于上述两个分类工作，如果考虑欧式距离和余弦相似度，应该选择哪种距离函数比较合适？选项：A、（1）和（2）都选择余弦相似度B、（1）选择欧式距离，（2）选择余弦相似度C、（1）选择余弦相似度，（2）选欧式距离D、（1）和（2）都选欧式距离正确答案:【（1）选择余弦相似度，（2）选欧式距离】2、问题：采用KNN分类，表中列出了与被测对象距离最近的5个结果，采用欧式距离，有2个类别“0”、“1”。请选择以下正确的选项。选项：A、采用多数表决法，K=3时，结果为“0”类，K=5时为“1”类B、用加权多数表决法，直接用距离倒数作为权值。结果与A一致C、用加权多数表决法，直接用距离倒数作为权值。K=3和K=5时，结果均为“0”类D、采用加权表决规则后，K值越大，准确性越高正确答案:【采用多数表决法，K=3时，结果为“0”类，K=5时为“1”类#用加权多数表决法，直接用距离倒数作为权值。K=3和K=5时，结果均为“0”类】3、问题：如下图所示，样本中有三个类别C1、C2、C3，采用KNN分类算法，图中给出了被测数据对象X和Y在特征空间中的映射点，以X、Y为中心的圆表示对应K个与X、Y最相近点的分布情况。依据KNN的多数表决规则，X归为C3类，Y归为C2类，但感觉这个分类结果与图示有些偏差，直观上X和Y都比较接近C1。你觉得可以采取哪些措施来改进算法以避免这种情况发生？选项：A、X的问题是K值选择太小，可以适当增大K值，Y的问题是K值过大，可以适当减小K值B、Y的分类问题可能是由于样本数不平衡造成，可以考虑压缩C2类别的样本数量C、Y的问题可以考虑用加权多数表决法解决D、X的问题可能是C3类含比较异常的样本，去除异常样本数据可以提高分类准确度正确答案:【Y的分类问题可能是由于样本数不平衡造成，可以考虑压缩C2类别的样本数量#Y的问题可以考虑用加权多数表决法解决#X的问题可能是C3类含比较异常的样本，去除异常样本数据可以提高分类准确度】4、填空题：K近邻算法也可以用于做回归预测。通过某种距离度量关系找出样本集中与被测对象最相近的K个样本，分类任务是选择K个样本中占比最高的类别，来推断被测对象的类别；回归任务是，对K个样本某个被关注的属性计算均值，作为被测对象的预测值。回归同样可以进行加权计算，例如，以距离的倒数为权值计算均值。以下是一个利用KNN算法预测房屋出租价格的回归问题，每个样本包含一些房屋属性（建筑面积，卧室数，洗手间数，建造年代，距公交站距离，出租价格），如下表1所示。被预测对象提供房屋属性（建筑面积，卧室数，洗手间数，建造年代，距公交站距离）。表2是K=5时计算得到的与被预测对象距离最近的5个样本及对应的租价。试问，如果用近邻样本租金直接取均值，被测对象的房屋租金为多少？（租金取整数）正确答案:【4880】5、填空题：继续上题，采用距离倒数加权计算均值，房屋租金为多少？（租金取整数）正确答案:【4907】11.4单元测验1、问题：下图是本课开始例子的一个简化，其中的数据表示对应两个城市之间的旅行花费（比如机票价格），例如北京和上海之间是1000。本题有两问（1）试给出从北京出发，依次到上海、乌鲁木齐、杭州、哈尔滨，返回北京所需的旅行花费；（2）试目测给出在这5个城市之间做一次巡回推销（即从一个城市出发，经过其他每个城市恰好一次，返回原地）的最少花费。（注：这里的目测给出，本质上就是要枚举所有可能的排列，一个个检查对应的代价，找出最小的。）选项：A、（1）9400，（2）6400B、（1）5800（2）5800C、（1）9400（2）5900D、上面的都不对正确答案:【（1）9400（2）5900】2、问题：这一题关于求解推销员问题的遗传算法。讲课中提到对于每一个样本基因（即节点排列实例），要做三种变异（变换）操作：交换，反转，循环。然后看变换后的结果的代价如何，留下其中优胜的。如此循环往复多次。现在考虑一个排列：0,1,2,3,4,5,6,7,8,9，并假设随机产生的位点指向2和6。试判断下面的选项哪个是正确的。选项：A、交换：0,1,6,3,4,5,2,7,8,9；反转：0,1,6,5,4,3,2,7,8,9；循环：0,1,6,2,3,4,5,7,8,9B、交换：0,1,6,3,4,5,2,7,8,9；反转：9,8,7,6,5,4,3,2,1,0；循环：0,1,6,7,8,9,2,3,4,5C、交换：0,1,6,3,4,5,2,7,8,9；反转：0,1,6,5,3,4,2,7,8,9；循环：0,1,6,2,3,4,5,7,8,9D、上面的都不全对正确答案:【交换：0,1,6,3,4,5,2,7,8,9；反转：0,1,6,5,4,3,2,7,8,9；循环：0,1,6,2,3,4,5,7,8,9】3、问题：这一课我们学了三种求解推销员问题的算法，蛮力法（枚举法），遗传算法，以及基于最小生成树的算法。它们各有优势和劣势。下述断言中有哪些是错的。选项：A、三个算法都能给出最优解，差别在于效率B、三个算法效率差不多，差别在于给出的解的质量C、枚举法是精确算法，遗传算法是近似算法D、遗传算法和基于最小生成树的算法都是近似算法，不同在于后者能保证近似的精度在一定范围内，前者则不能保证正确答案:【三个算法都能给出最优解，差别在于效率#三个算法效率差不多，差别在于给出的解的质量】4、问题：基于最小生成树算法。下图是某完全图的一棵最小生成树，假设该图任何3个节点之间的权值关系满足严格的三角不等式（即设任意两边之和至少比第3边大1）。试指出在该图上推销员行走的代价肯定不超过120的路线。选项：A、h,i,f,g,a,e,b,c,d,hB、h,i,e,c,d,b,f,g,a,hC、a,b,c,d,e,f,g,h,i,aD、a,g,h,i,e,c,d,b,f,a正确答案:【h,i,e,c,d,b,f,g,a,h#a,g,h,i,e,c,d,b,f,a】综合考试1、问题：考虑有一袋硬币，设其中有2分和5分的共41枚，总值为154分。人们用符号表示这些量，a=2，b=5，m=41，s=154，并基于这些量设计了一个算法如下。选项：最后的结果n有什么意义吗？A、钱袋中2分硬币的个数B、钱袋中5分硬币的个数C、钱袋中2分硬币的总值D、没什么可解释的意义正确答案:【钱袋中5分硬币的个数】2、问题：《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数。操作过程为，1）先对两个整数用2约简；2）以较大的数减较小的数；3）以减数和差做为新的两个数，重复2），直到减数和差相等为止。则1）中约掉的若干个2与3）结束时的减数乘积为最大公约数。下图给出一个对应的算法，采用该算法求gcd(165，24)，选择以下正确的选项。选项：A、算法3~7循环13次结束，第5次循环后，a，b=45，24B、算法3~7循环14次结束，第3次循环后，a，b=93，24C、算法3~7循环15次结束，第14次循环后，a，b=3，3D、算法3~7循环13次结束，第13次循环后，a，b=3，0正确答案:【算法3~7循环14次结束，第3次循环后，a，b=93，24】3、问题：在有序列表list中搜索目标元素x，list中可能有重复元素，也有可能搜索对象x不在list中。采用如下算法进行搜索，算法结束时返回low值，请选择以下关于low所指元素的描述（忽略越界问题）。（注意：红色“####”所标记的代码行与课程学习的二分搜索有所不同，注意体会其中的变化原因）选项：A、low所指是第一个等于或者大于x的元素B、low所指是第一个与x相等的元素C、low所指是最后一个与x相等的元素D、low所指是最后一个等于或者小于x的元素正确答案:【low所指是第一个等于或者大于x的元素】4、问题：一个字符串含8种字符，每个字符出现的频次分别为19，15，10，8，6，3，2，1。采用Huffman编码对这8个字符进行编码，形成的码串总位数是多少？码位均值是多少？选项：A、码位总长度为167，码位均值为2.61B、码位总长度为180，码位均值为2.70C、码位总长度为156，码位均值为2.51D、码位总长度为174，码位均值为2.74正确答案:【码位总长度为167，码位均值为2.61】5、问题：按照讲课中介绍的最小生成树算法，某人在下面的加权图上做了一次模拟执行，给出的边的顺序为：(a,b)，(d,e)，(b,e)，(b,c)。试考虑下面认识的正确性。选项：A、结果错误，这些边对应的不是最小生成树B、结果正确C、结果错误，虽然这些边对应一棵最小生成树，但顺序不对D、上面的都不对正确答案:【结果错误，虽然这些边对应一棵最小生成树，但顺序不对】6、问题：在课程所介绍的投资组合算法中，如下图所示，体现动态规划工作表的填写是从左到右一列列进行的。是否也可以从上到下一行行填写呢？选项：A、可以，只要调换讲课中给出的伪代码中第4和第5句的顺序就行了B、可以，但算法的描述像（a）那样修改不行C、不可以，因为计算表中一个单元的时候需要用到它左边列的数据D、说不清楚正确答案:【可以，只要调换讲课中给出的伪代码中第4和第5句的顺序就行了】7、问题：设a、b是两个大于0的整数，选择以下关于gcd(a,b)正确的选项。选项：A、设ab，r=a%b（a除b的余数），则，rb/2B、设，gcd(a,b)=d，a=m·d，b=n·d，则，m、n互为质数C、设，a=k·x，b=k·y，x，y，k均为整数，则，gcd(a，b)=k·gcd(x，y)D、设ab，且a，b均为奇数，则，gcd(a，b)=gcd((a+b)/2，(a-b)/2)正确答案:【设，gcd(a,b)=d，a=m·d，b=n·d，则，m、n互为质数#设，a=k·x，b=k·y，x，y，k均为整数，则，gcd(a，b)=k·gcd(x，y)#设ab，且a，b均为奇数，则，gcd(a，b)=gcd((a+b)/2，(a-b)/2)】8、问题：继续采用上题所描述的算法，选择以下正确的选项。选项：A、算法结束时，并不能确定list中是否包含xB、算法结束时，low=high=midC、将x插入到算法结束时low所指的位置，仍能保持list中元素的有序排列D、以上都不对正确答案:【算法结束时，并不能确定list中是否包含x#将x插入到算法结束时low所指的位置，仍能保持list中元素的有序排列】9、问题：下图是一个有n个层的三角形数字塔，第1层（顶层）1个数，第2层2个数，……，第n层n个数，这些数字可以理解为对应的路径消耗。从顶层开始逐层向下走，每一步只能从当前位置向左下或右下方移动一层，直到到达最底层。求自顶层到底层的最短路径，下图（a）标记了一条路径，但显然不是最短的。解答该问题有两个基本的方法，一是采用递归法自上而下逐级调用，再回推最终得到最优解。另一种是记忆法，自下而上从最底层开始逐层计算出每个位置向下走的最短路径并保存结果为上一层计算使用，最终计算出最顶层位置到底层的最短路径。以下图（b）为例，倒数第二层数字16的位置到底层的最短路径，取其左下（25）和右下（28）二者中较小的（25），加上自身的数字（16），就是该位置到底层的最短路径41，这是一个动态规划的过程。对于这两种算法思想，思考其对应的算法效率。选项：A、递归法（自上而下）的时间效率是2^nB、递归法（自上而下）的时间效率是n^2C、记忆法（自下而上）的时间效率是n^2D、记忆法（自下而上）的时间效率是n正确答案:【递归法（自上而下）的时间效率是2^n#记忆法（自下而上）的时间效率是n^2】10、问题：继续上题。采用一个n*n的二维数组cost[][]保存上述三角形数字塔，如下图所示。利用上述自下而上的记忆法计算每个位置的最短路径，并保存在二维数组dist[][]中，如上题图（b）中，cost[4][4]=16，dist[4][4]=41,则算法结束时dist[0][0]就是求得的最短路径值。基于这样的数据结构，选择以下正确的路径更新规则。选项：A、第n-1行元素更新规则,dist[n-1][j]=cost[n-1][j]B、自下而上，第n-2~0行,0~i列元素的更新规则，dist[i][j]=cost[i][j]+min(dist[i+1][j],dist[i+1][j+1])C、自下而上，第n-2~0行,0~i列元素的更新规则，dist[i][j]=cost[i][j]+min(cost[i+1][j],cost[i+1][j+1])D、自下而上，第n-2~0行,1~i列元素的更新规则，dist[i][j]=cost[i][j]+m