大数据与人工智能实验室机器学习组20201008测试题解析

一、选择题 1、线性表采用链式存储时，结点的存储地址（  ）。 A. 必须是不连续的 B. 连续与否均可 C. 必须是连续的 D. 和头结点的存储地址相连续 【答案：B】 2、下列属于聚类算法的是（  ）。 A. Decision Tree B. Support Vector Machine C. K-Means D. Singular Value Decomposition 【答案：C】 【解析：机器学习算法一般可划分为监督学习、无监督学习和强化学习三大类，监督学习可以大致分为分类和回归两类，无监督学习可以大致分为聚类和降维两类。Decision Tree（决策树）和Support Vector Machine（支持向量机）都属于监督学习算法；K-Means（K均值）属于无监督学习的聚类算法；Singular Value Decomposition（奇异值分解）属于无监督学习的降维算法。】 3、下述程序段输出结果为（  ）。

import numpy as np a = np.array([3, 5, 8]) b = np.array([[1, 2, 3], [4, 5, 6], [5, 7, 9]]) print(a * b)

A.

[[ 3 10 24] [ 4 5 6] [ 5 7 9]]

B.

[[ 3 10 24] [12 25 48] [15 35 72]]

C.

[ 63 87 111]

D.

ValueError: frames are not aligned

【答案：B】 【解析：在NumPy中，*运算符的功能是，对数组执行对应位置元素相乘（相当于np.multiply()），对矩阵执行矩阵乘法运算（相当于np.dot()）。】 4、设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向待插入的结点X，则在结点A和结点B之间插入结点X的操作序列为（  ）。 A. p->next = s; s->next = q; B. p->next = s->next; s->next = p; C. q->next = s; s->next = p; D. s->next = p->next; p->next = s; 【答案：C】 【解析：如下图所示。】

5、一棵完全二叉树含1001个结点，其中叶子结点的个数是（  ）。 A. 501 B. 500 C. 251 D. 250 【答案：A】 【解析：根据满二叉树的性质易得，有1023个结点的完全二叉树是满二叉树，该树有512个叶子结点。题目中所给完全二叉树有1001个结点，比满二叉树少22个结点。在满二叉树中，这22个结点对应的11个父亲结点即为题中完全二叉树的叶子结点。所以完全二叉树的叶子结点个数为512-22+(22÷2)=501个。】

二、填空题 1、设有算术表达式x+a*(y-b)-c/d，该表达式的前缀表示为：____________，后缀表示为：____________。 【答案：-+x*a-yb/cd；xayb-*+cd/-】 【解析：中缀表达式转换前（后）缀表达式的方法：首先按照运算符的优先级对所有的运算单位加括号，原式变为((x+(a*(y-b)))-(c/d))；转化为前缀表达式时，把运算符号移动到对应的括号前面，即-(+(x*(a-(yb)))/(cd))，去掉括号后的结果-+x*a-yb/cd即为前缀表达式；转化为后缀表达式时，把运算符号移动到对应的括号后面，即((x(a(yb)-)*)+(cd)/)-，去掉括号后的结果xayb-*+cd/-即为后缀表达式。】 2、在循环队列中，当队列为空时，有front = rear；而当所有队列空间全占满时，也有front = rear。为了区别这两种情况，规定循环队列最多只能有MAXSIZE - 1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是____________，队列判满的条件是____________。 【答案：front == rear；front == (rear + 1) % MAXSIZE】 【解析：采用顺序存储结构实现队列，由于存储空间是固定的，随着入队和出队的进行，存储的数据会溢出，如下图一所示。为了解决这个问题，我们可以采用循环队列的方法，如下图二所示。此时，无论是队列为空时，还是队列为满时，都有front = rear。此时，我们可以规定循环队列最多只能有MAXSIZE - 1个队列元素，那么当队列为空时，front = rear；当队列为满时，front = (rear + 1) % MAXSIZE。】

3、通常我们把分类错误的样本数占样本总数的比例称为____________；算法模型对于新样本的适应能力被称为____________；当模型把训练样本的特点当作所有潜在样本的特点，导致泛化能力下降，这种现象称为____________，与之对应的是____________。 【答案：错误率；泛化能力；过拟合；欠拟合】 4、Fayyed过程模型主要包含以下七个阶段知识表示：____________、____________、____________、____________、____________、____________、____________。 【答案：知识表示；数据清理；数据集成；数据选择；数据变换；数据挖掘；模式评估】

三、简答题 1、已知一棵树的先根遍历序列和后根遍历序列如下，请构造出该树。 先序序列：ABCDEFGHIJ 后序序列：CDEBFHIJGA 【答案：树形结构如下图所示】

2、给定一组权值(15, 9, 3, 2, 7, 6)，试设计相应的哈夫曼树，并计算相应的WPL。 【答案：哈夫曼树如下图所示；WPL=(2+3)×4+6×3+(15+7+9)×2=100。】

3、简述决策树的构造逻辑，ID3算法和C4.5算法的计算过程和特点。 【答案：决策树的构造过程可以理解成寻找纯净划分的过程，就是让目标变量的分歧最小。信息熵表示了信息的不确定度（纯度），计算上来讲就是信息量的统计均值。对于树中一个内部结点来说，有多种划分的选择，每种选择都对应一种属性，这个结点选择哪个属性进行划分得到的结果最纯，如何选择判定准则就是关键。在ID3算法中，计算出每个分支的信息熵，再赋上权重，可以获得该节点对应属性的信息增益。然而ID3算法对于可取值数目较多的属性有明显的偏好，这会给整体带来不利影响。C4.5算法在此基础上做了改变，它采用信息增益率（用原本的信息增益除以该属性的“固有值”）作为划分准则。直接选取信息增益率会导致对于数目少的属性偏好，因此C4.5算法从信息增益高出平均水平的属性里计算信息增益率。这两种算法都是基于离散的属性，如果为了使用而将连续的属性离散化，会造成一定的损失。】 4、监督学习通过定义一个模型，并根据训练集上的数据估计最优参数。梯度下降法是一个广泛被用来最小化模型误差的参数优化算法。梯度下降法通过多次迭代，并在每一步中最小化成本函数来估计模型的参数。 (1) 请指出下面公式中各部分的意义。$$\omega j=\omega j-\lambda \frac{\partial F(\omega j)}{\partial \omega j}$$ (2) 为了能够使得梯度下降法有较好的性能，我们需要把$\lambda$的值设定在合适的范围内。请简单叙述一下如何选取和调整$\lambda$。 【答案：(1) $\omega j$是模型参数，$F()$是成本函数，$\frac{\partial F(\omega j)}{\partial \omega j}$是$\omega j$的一阶导数，$\lambda$是学习率。(2) 学习率，梯度下降算法中迭代步长。假设待优化函数为$f(x)$，$\mathrm{d}$$x$为函数对变量$x$的导数，即下降方向。如果不用学习率，或者说学习率为1，使用负梯度，即最速下降法，有些情况下永远无法下降到最优值（即0点处），做一次梯度下降，就移动相对称的点上，来来回回走。学习率大，容易震荡，学习率小，收敛速度慢。一般情况下，随着迭代过程的继续，学习率应当适当减小，这样才能更稳妥地到达极值点。这种想法就是通过权重衰减因子实现的。$\lambda ={\lambda }_0\times (\frac{1}{1+decay\times i})$，其中$decay$为衰减因子，取值范围$[0,1]$，随着$i$的增加，学习率逐渐减小。】

四、算法题 1、LeetCode 78. 子集 给定一组不含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。 示例：

输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] /** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { }

【解法：迭代法实现子集枚举，时间复杂度：O(n×2ⁿ)，空间复杂度：O(n)】

/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { int total = 1 << numsSize; * returnColumnSizes = malloc(sizeof(int) * total); * returnSize = total; int** ret = malloc(sizeof(int*) * total); int t[numsSize], tSize; int* tmp; for (int mask = 0; mask < total; mask++) { tSize = 0; for (int i = 0; i < numsSize; i++) { if ((1 << i) & mask) { t[tSize++] = nums[i]; } } tmp = malloc(sizeof(int) * tSize); memcpy(tmp, t, sizeof(int) * tSize); (* returnColumnSizes)[mask] = tSize; ret[mask] = tmp; } return ret; }

【解析：记原序列中元素的总数为n。原序列中的每个数字a_i的状态可能有两种，即在子集中和不在子集中。我们用111表示在子集中，000表示不在子集中，那么每一个子集可以对应一个长度为n的 0/1序列，第i位表示a_i是否在子集中。可以发现0/1序列对应的二进制数正好从0到2ⁿ−1。我们可以枚举mask∈[0,2ⁿ−1]，mask的二进制表示是一个0/1序列，我们可以按照这个0/1序列在原集合当中取数。当我们枚举完所有2ⁿ个mask，我们也就能构造出所有的子集。】 2、剑指Offer 03. 数组中重复的数字 找出数组中重复的数字。 在一个长度为n的数组nums里的所有数字都在0～n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例：

输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3

限制：2 <= n <= 100000

int findRepeatNumber(int* nums, int numsSize) { }

【解法1：HashMap，时间复杂度：O(n)，空间复杂度：O(n)】

int findRepeatNumber(int* nums, int numsSize) { int *hash = (int*)calloc(numsSize, sizeof(int)); for (int i = 0; i < numsSize; i++) { if (hash[nums[i]] == 1) { return nums[i]; } else { hash[nums[i]]++; } } return -1; }

【解法2：利用原来的空间，不使用额外空间，时间复杂度：最坏条件下O(n)，空间复杂度：O(1)】

int findRepeatNumber(int* nums, int numsSize) { for (int i = 0; i < numsSize; i++) { while (nums[i] != i) { if (nums[i] == nums[nums[i]]) { return nums[i]; } int t = nums[i]; nums[i] = nums[t]; nums[t] = t; } } return -1; }