2022 算法初步(北京大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2022-03-27到2022-06-12

第1周 开启算法学习之旅 1.5 单元测验

1、 问题:本节反复用的一个例子是用无刻度桶的量水问题。现在还是假设有A（7升）、B（5升）两个桶。有人给出了一个算法，请问它的执行将导致的结果。
选项：
A:A=6, B=0
B:A=3, B=0
C:A=0, B=3
D:算法描述不清楚
答案: 【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，5
B:10，5，2.5
C:10，5，16
D:上面的都不对
答案: 【10，5，16】

4、 问题:在上一题中的第2条语句，写起来比较啰嗦，常常用所谓“while循环”来表示。第3条语句，则用所谓条件语句“if   then   else   ”来表示。于是，上面的算法也可以描述为：现在的问题是，一共会输出几个数，该算法就结束了。也就是问循环执行的次数。
选项：
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)，x>y
B:O(n^2)，x<y
C:O(n^3)，x>y
D:O(n^4)，x<y
答案: 【O(n^3)，x>y】

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最大，这样就等价于我们要求0<a<b<c<n，满足。对前面第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周 量水问题 2.4 单元测验

1、 问题:利用欧几里得扩展式中系数的关系式：，，（其中q为当前a除以b取整，设a>b），试用手工计算求解整数34和21扩展式中系数的回推过程。采用辗转相除计算gcd(34,21)，当余数为0时，取，，利用上述关系式，可得，。试计算。
选项：
A:x4=-1，y4=2
B:x4=2，y4=-3
C: x4=-3，y4=5
D:x4=-8，y4=13
答案: 【x4=2，y4=-3】

2、 问题:设a、b为两个正整数，整数x0、y0满足ax0+by0 = gcd(a,b)，即x0、y0是（a, b）欧几里得扩展式的一组解。对于以下关于求解满足ax+by = gcd(a,b)，x、y通解的描述，请选择正确的选项，k为整数。
选项：
A:x = x0 – (b)k，y = y0 + ak
B:x = x0 – (a/gcd(a,b))k，y = y0 + (b/gcd(a,b))k
C:x = x0 – ak，y = y0 + bk
D: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为两个正整数，且a>b, 请选择以下正确的选项。
选项：
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)=ab/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)=ab/gcd(a,b), （lcm(a,b)为a和b的最小公倍数）】

6、 问题:可以采用蛮力法（枚举法）求满足 ax+by=d 的整数x和y，设a、b为正整数。先用欧几里德算法求出 d=gcd(a,b) ，然后按下表所示的方法，x从1开始，逐步尝试y=-1、-2、……，每次y绝对值增1，计算ax+by，若ax+by<d，则x+1，y不变，继续按上述方法改变y值并计算ax+by，直到最终满足ax+by=d，得到一组满足扩展式的x和y。请选择以下正确的选项。
选项：
A:此方法得到的x，y值不一定是所有满足扩展式中绝对值最小的
B:采用这个蛮力法计算a=7，b=5，得到的x、y值为3、-4
C:若取x<0，y>0，仍按上表步骤和算式，即，x从-1开始，尝试y=1、2、……，也可以得到一组x、y解满足ax+by=d
D:以上都不对
答案: 【此方法得到的x，y值不一定是所有满足扩展式中绝对值最小的;
采用这个蛮力法计算a=7，b=5，得到的x、y值为3、-4】

第3周 二分法 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=9
B:（1）low=6，high=5；（2）low=11，high=10
C:（1）low=4，high=5；（2）low=10，high=9
D:（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.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.78
B:得到的哈夫曼编码，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周 优化互连互通的成本 5.4 单元测验