一.选择题
1.权值分别为9、3、2、8的结点，构造一棵哈夫曼树，该树的带权路径长度是？
A.36
B.40
C.45
D.46

正确答案：B

//选取9、3、2、8中最小的两个列出
    5
  /   \
 2     3
 //再选取9、8、5中最小的两个列出
    13         
   /  \      
  5    8
 / \            
2   3
//同上
         22
        /  \
      13    9
    /   \
   5     8
 /  \
2    3
//其中 22权重0,9权重1,8权重2，依次类推

带权外部路径长度计算；
WPL= 2×3 + 3×3 + 8×2 + 9×1 = 40

2.下面关于排序的空间复杂度说法不正确的有()(N为被排序数据的长度)
A.堆排序的空间复杂度为O(1)
B.冒泡排序的空间复杂度为O(1)
C.归并排序的空间复杂度为O(N)
D.插入排序的空间复杂度为O(N)
E.递归实现的快速排序的空间复杂度为O(logn)

正确答案：D
插入排序的空间复杂度是O（1）

3.ID3算法在分类树构建中， 使用哪个度量来进行分类节点
A.gini指标
B.信息增益
C.信息增益率
D.准确率

正确答案：B
id3:信息增益
c4.5 信息增益率
cart 基尼指数

4.由递归方式求的N的阶乘(即N！)，时间复杂度是多少?
A.O(N!)
B.O(logN)
C.O(N^2)
D.O(N)

正确答案：D
C出栈即代表整个序列都已入栈，因此出列顺序不可能为EF

5.圆内接三角形是锐角三角形概率是多少（）
https://www.nowcoder.com/questionTerminal/a0d05de7237541d8b62f79b05ad4c7c7

6.关于ROC曲线，下列说法中正确的是（）
A.ROC曲线的x轴代表假正类率(false positive rate, FPR)
B.ROC曲线的Y轴代表真正类率(true positive rate ,TPR),
C.AUC的值就是处于ROC 曲线下方的那部分面积的大小，通常介于0.5到1.0之间
D.AUC值越大，模型的分类效果越好

正确答案：ABCD

二.编程题
leetcode15题.三数之和
https://leetcode-cn.com/problems/3sum/

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res, k = [], 0
        for k in range(len(nums) - 2):
            if nums[k] > 0: break # 1. because of j > i > k.
            if k > 0 and nums[k] == nums[k - 1]: continue # 2. skip the same `nums[k]`.
            i, j = k + 1, len(nums) - 1
            while i < j: # 3. double pointer
                s = nums[k] + nums[i] + nums[j]
                if s < 0:
                    i += 1
                    while i < j and nums[i] == nums[i - 1]: i += 1
                elif s > 0:
                    j -= 1
                    while i < j and nums[j] == nums[j + 1]: j -= 1
                else:
                    res.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i - 1]: i += 1
                    while i < j and nums[j] == nums[j + 1]: j -= 1
        return res

三.问答题
1.机器学习特征筛选的方法
https://www.jianshu.com/p/9d80c85d07c5
https://blog.nowcoder.net/n/72442dbb7af84d76879d629c7eec99d0
2.样本不平衡的解决办法
https://blog.csdn.net/weixin_44766179/article/details/89048069
3.现有N个数，找出其中第M大的数，这里的N远大于M。请说明算法思路、复杂度

建立一个容量为M的小根堆，遍历这N个元素，当前元素如果大于堆顶元素就删除堆顶元素加入此元素，这样操作后的堆容量还是M，遍历完成依次取出堆顶元素，取到的最后一个元素就是所求。

因为需要的空间只是容量为M的堆，所以空间复杂度为O(M)
首先建立容量为M的堆得时间复杂度为O(N)
遍历到一个元素时，可能插入，也可能不插入，如果每次都插入，也就是最坏情况，插入一个元素的时间复杂度为O(log(M))，插入N个元素的时间复杂度也就是O(Nlog(M))。
最后取元素的时间复杂度为Mlog(M)
所以最坏时间复杂度为O(M+Nlog(M))=O(Nlog(M))。

4.说明GBDT和Xgboost的异同点
（1）GBDT的损失函数只利用了函数一阶导的信息，而xgboost利用了函数的二阶导信息，效率更高更准确。同时xgboost的损失函数还添加了模型复杂度的惩罚项，防止过拟合。
（2）Xgboost可以自定义弱学习器类型，自定义损失函数，前提是损失函数具有二阶导特性。
（3）Xgboost每一轮的训练中，不仅支持样本采样，还支持特征采样
（4）Xgboost每一轮的训练，各层节点可以并行训练，gbdt不行
（5）xgboost可以处理缺失值
（6）xgboost在寻找分裂节点和分裂值时，是采用了分位数的方法

四.附加题
在一个有限的实数列中,任意7个连续项之和都是负数,而任意11项之和都是正数。试问,这样的数列最多有多少项?
参答：最多16项，
如果有第17项，那么考察
A=a1+a2+...+a11
+a2+a3+...+a12
+...
+a7+a8+...+a17
按行看A>0，按列看A<0，矛盾