深度学习（机器学习）算法面试(二)

╰半夏微凉° 2022-03-18 08:10 280阅读 0赞

**\#考察数据结构：**  
基于图的特征降维方法的是LE(Laplacian eigenmap)、LLE(local linear embedding)  
\*\*\*\***稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序**

**不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序**

原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；

原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。\*\*\*\*

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70]

**二叉搜索树：二叉查找树**（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。  
已知int a\[\]=\{1,2,3,4,5\}；int\*p\[\]=\{a,a+1,a+2,a+3\}；int *q=p；表达式(p\[0\]+1)+*\*(q+2)的值是\_\_\_\_。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 1]  
**进栈序列为(1,2,3…,n)有多少种出栈顺序， f(n)=h(n)= C(2n,n)/(n+1)**

*Var(x)定义为概率密度函数f的二阶矩，给出了x的方差  
Var(X)=E\[(X-E(X))²\]=E(X²)-\[E(X)\]²  
注：E\[(X-E(X))²\]不是E\[(X-E(X))²\]，而是(X-E(X))²的数学期望。*\*

**某颗二叉树中有2000个节点，则它的最小高度怎么求？  
最小高度自然就是等于2000个结点的完全二叉树的高度  
设根结点高度为1，n个结点完全二叉树高度：下取整(log2n) + 1  
现在是下取整(log2(2000)) + 1= 11**

**树：**  
\*\*结点的度：\*\*结点拥有的子树的数目  
\*\*叶子结点：\*\*度为0的结点  
\*\*分支结点：\*\*度不为0的结点  
树的度：树中结点的最大的度  
层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1  
树的高度：树中结点的最大层次  
森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 6]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70]: /images/20220318/fb956dc246fa4f4d9d055968d5031aac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 1]: /images/20220318/7fd6f28f55b74d8985cd6b0f39374255.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 2]: /images/20220318/4978db4c52054bd892d4c77373babe4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 3]: /images/20220318/de47b0bda9f940cea37919c1f674cfc2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 4]: /images/20220318/a73a81f9bd9f48d9a524117b885add4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 5]: /images/20220318/99d9041af2a94fcb8b29585e58442cf6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODYzMjI0Ng_size_16_color_FFFFFF_t_70 6]: /images/20220318/dd13eb4a986b49ebbf0a9d308946ebaa.png