奇安信-算法-笔经

一.单选
1.对于有n个结点的二叉树,其高度为
答案：不确定 完全二叉树能确定

2.下面哪种排序算法不是稳定的（）
A.归并
B.冒泡
C.插入
D.快速排序
正确答案：D

3.岭回归和Lasso回归

4.下面关于二叉排序树的说法错误的是（ ）
A.在二叉排序树中，完全二叉树的查找效率最低
B.对二叉排序树进行中序遍历，必定得到节点关键字的有序序列
C.二叉排序树的平均查找长度是O(log2(n))
D.二叉排序树的查找效率与二叉树的树形有关

正确答案：A
A选项：在所有二叉树中，完全二叉树的平均分支长度最短（节点数相同的情况下），查找效率最高，描述相反，故错误
B选项：因为“左树<子树根节点<右树”，而中序遍历也是左树优先输出，子树根节点次之，右树最后输出，这也正是它排序的原理，正确
C选项：以完全二叉树作为典型，n个节点的树深度为log2(n)，其他树可以在增删时通过左旋和右旋调整成完全二叉树，正确
D选项：树的形状不同，分支的平均长度也会不同，树形能够综合考虑所有分支，故正确。但是要注意，除了完全二叉树外，其他树的深度并不能决定该树的查找效率，因为深度仅由最长的分支决定，只是考虑了一条路径，无法反映所有路径的平均长度。

二.多选
1.生成模型有哪些：
生成式模型：对x和y的联合分布p(x,y)建模，然后通过贝叶斯公式来求得p(yi|x)，然后选取使得p(yi|x)最大的yi
朴素贝叶斯
KNN
混合高斯模型 GMM
隐马尔科夫模型 HMM
贝叶斯网络
马尔科夫随机场
深度信念网络DBN
LDA

判别式模型：直接对条件概率建模
线性回归
逻辑回归
神经网络
SVM
高斯过程
条件随机场CRF
CART

2.MCMC采样
https://www.jianshu.com/p/71762a3c3dab

3.主题模型
https://blog.csdn.net/jiayalu/article/details/100533184
LSA
pLSA
LDA
HDP

4.排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪些排序算法是稳定的：
A.插入排序
B.基数排序
C.归并排序
D.冒泡排序

正确答案：A B C D

5.在某神经网络的隐层输出中，包含0.75，那么该神经网络采用的激活函数可能是（）
A.sigmoid
B.tanh
C.relu

正确答案：A B C
三种的值域都包括0.75

三.编程
1.01背包

估计超时了额。

KG = int(input())
nums = int(input())

weights = []
values = []
for i in range(nums):
    input_wuti = list(map(int,input().strip().split()))
    weights.append(input_wuti[0])
    values.append(input_wuti[1])

V = [[0]*(KG+1) for j in range(nums+1)]  
for k in range(1,nums+1):  
    for h in range(1,KG+1):  
        if h-weights[k-1]<0:
            V[k][h] = V[k-1][h]
        else:
            V[k][h]=max(V[k-1][h], V[k-1][h-weights[k-1]]+values[k-1])
print(V[nums][KG])

2.如果一个正整数能被7整除，称之为亲7树，对于给出的一组个位数，请找出使用所有数字排列的数中亲7数的个树：
其中给出的个位数字数组中每个都不相关，即使有重复数字，如[1,1,2]排列出的数为[12,121,112,121,211,211]，亲7数为[112,112]共2个
输入：个位数字数组，数组有m个元素x1,x1,x3...xm
输出：亲7数个树

示例：
输入：[1,1,2]
输出：2

AC

class Solution:
    def reletive_7(self , digit ):
        # write code here
        from itertools import permutations
        ls=[]
        nums=[]
        for k in digit:
            nums.append(str(k))
        for i in permutations(nums):
            ls.append(int("".join(list(i))))
        res=0
        for s in ls:
            if s%7==0:res+=1
        return res