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

向右看齐 2022-12-13 01:23 296阅读 0赞

一、选择题  
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)

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

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

[ 63  87 111]

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】  
【解析：如下图所示。】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70]

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`。】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 1]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 2]

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

三、简答题  
1、已知一棵树的先根遍历序列和后根遍历序列如下，请构造出该树。  
先序序列：ABCDEFGHIJ  
后序序列：CDEBFHIJGA  
【答案：树形结构如下图所示】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 3]

2、给定一组权值(15, 9, 3, 2, 7, 6)，试设计相应的哈夫曼树，并计算相应的WPL。  
【答案：哈夫曼树如下图所示；WPL=(2+3)×4+6×3+(15+7+9)×2=100。】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 4]

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

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

输入: nums = [1,2,3]
    输出:
    [
      [3],
      [1],
      [2],
      [1,2,3],
      [1,3],
      [2,3],
      [1,2],
      []
    ]

【解法：迭代法实现子集枚举，时间复杂度：O(n×2n)，空间复杂度：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。原序列中的每个数字ai的状态可能有两种，即在子集中和不在子集中。我们用111表示在子集中，000表示不在子集中，那么每一个子集可以对应一个长度为n的 0/1序列，第i位表示ai是否在子集中。可以发现0/1序列对应的二进制数正好从0到2n−1。我们可以枚举mask∈\[0,2n−1\]，mask的二进制表示是一个0/1序列，我们可以按照这个0/1序列在原集合当中取数。当我们枚举完所有2n个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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70]: /images/20221123/776fbbe3bc634b3e830e22cd5dec62e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201009201251887.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 2]: /images/20221123/b83102fd58184c4388ab97ad08682f34.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 3]: /images/20221123/22d86c94881e4938a4e8caa91f443d99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 4]: /images/20221123/a4819bbb8e3c43e7bda124ef7b527994.png