不自量力地投递了美团的春招题目（抄一抄题目，加深加深记忆）

涉及知识点——题目问题——答案

1排序——比较次数与元素初始排列的顺序有关的是——（冒泡）？

2二分查找——{7,9,11,13,15,17,19,21},采用二分查找节点，——查找21（15）需要比较3次成功——平均查找长度为3？

3最小生成树的两种算法——克鲁斯卡尔（kruskal）和普里姆算法（prim）

4了解分冶算法、动态规划、贪心算法、回溯算法

5分支限界法、最小路径——一张图，利用分支界限法求出最小路径的ABCDE规划

6

7OS抢占式的特点——进程调度中，抢占式的特点。

8IP协议——IP协议的作用是什么——将分组数据包发送到目的主机

网上摘抄———ip的主要作用是寻址与路由——(a)用IP地址来标识Internet的主机：在每个IP数据报中，都会携带源IP地址和目标IP地址来标识该IP数据报的源和目的主机。IP数据报在传输过程中，每个中间节点(IP 网关)还需要为其选择从源主机到目的主机的合适的转发路径(即路由)。IP协议可以根据路由选择协议提供的路由信息对IP数据报进行转发，直至抵达目的主机。IP数据报中，都会携带源IP地址和目标IP地址来标识该IP数据报的源和目的主机。IP数据报在传输过程中，每个中间节点(IP 网关)还需要为其选择从源主机到目的主机的合适的转发路径(即路由)。IP协议可以根据路由选择协议提供的路由信息对IP数据报进行转发，直至抵达目的主机。

9结构图的宽度

功能3和功能2是同一层的，均属于第二层，因此功能3.1和功能3.2都是和功能2.1、2.2、2.3同属于第三层结构，这样，第三层结构其实是五个模块。因此，宽度为5而不为3。该题目要注意结构的仔细分析。

10数据库——共有个不同实体类型，8个不同的二元联系，3个是1：n，4个是m:n，1个是m:n的三元联系。

11数据库——R/S得到什么——

R                              S                                                                    R/S

X       Y                      Y        F                                                        X

X1    Y1                    Y1       F1                                                     X1

X2    Y2                    Y2       F3                                                     X2

X2    Y3                    

X2    Y1

12汇编语言——R1和R2是两个寄存器，——i2=i1*[(i3+10)*2]

MOVF    i3，R2

ADDF    10，R2

MULF    2 ， R2

MOVF    i1，R1

MULF    R2，R1

MOVF    R1，i2

13TCP协议——建议连接和断开连接时，分别需要几次握手和几次挥手。

14读程序

i=0;s=0;
while(i<=100)
{int x=i%10;int y=i/10%10;int z=i/100;if(i%7==0||x==7||y==7||z==7){s+=i;}i++;
}
输出s;

15java——java中main函数的返回类型是——void

public    static    void    main(String args[]){}

16数组——

int    a1[][]={{5,6},{3,2}}
for(b1[]:a1){Arrays.sort(b1);for(int    k:b1)}

17哈夫曼树——通信，距离根节点越近，编码越少。权值越大，距离根节点越近。

网上——给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

18UML活动图——活动有哪几个特定的事件

19最坏情况的比较次数相同——希尔排序与堆排序——简单插入排序和堆排序——简单选择排序和希尔排序——冒泡排序和快速排序;

20将程序补充完整——1-1/2+1/3-1/4+1/5-1/6+……-1/100——选择一个程序

21OS——CPU何时由管态到目态——中断？

由于计算机系统的硬件区分目态和管态，用户程序在目态运行时不能直接使用I/O指令等特权指令，只有当用户程序执行到产生一次中断后，使机器在原来的目态下执行用户程序变成在管态下执行操作系统的系统调用程序。所以从目态转移到管态的惟一途径是中断。

目态：

目态又称为用户态，是用户程序执行时机器所处的状态。在此状态下禁止使用特权指令，不能直接取用系统资源与改变机器状态，并且只允许用户程序访问自己的存储区域。

管态：

管态又称系统态，核心态或特权状态。
　　CPU有两个状态，分别是管态和目态，当CPU处理系统程序的时候，CPU会转为管态，CPU在管态下可以执行指令系统的全集。（包括特权指令与非特权指令）

22折半查找——

23编程题目——看不懂题目，不过题目都抄了下来。明日再说，今天要先去追烈火如歌了。