目录

一、编程语言

1、C/C++

（1）指针

例题1

以下代码的输出是（2，5）

int a[5]={1,2,3,4,5};
int *ptr=(int*)(&a+1);
printf("%d,%d",*(a+1),*(ptr-1));

解析1

  • 数组名的值是一个指针常量，也就是数组第一个元素的地址。
  • 对数组名取指，指向的是数组的最后一个元素的下一个（内容位置）
  • 对指针p的算数计算，步长为*p的步长

（2）编译底层相关

对齐

gcc下的默认对齐数是4不是最大长度，也就是说，即使有double存在的情况下，对齐也是4个字节对齐。 例如 如下 在64位系统下：sizeof(Data) = 24 在32位系统下：sizeof(Data) = 20

struct Date
{
    char a;
    int b;
    int64_t c;
    char d;
};

大小端和printf

假设在一个 32 位 little endian 的机器上运行下面的程序，结果是多少？(1,0,2)

#include <stdio.h>
int main(){
  long long a = 1, b = 2, c = 3;
  printf("%d %d %d\n", a, b, c);
 return 0;
}
  • 前两个%d %d输出a的八个字节
  • 最后一个%d输出b的低字节

原理

  1. printf()是一个库函数，C，C++中函数的参数是从右往左入栈的；
  2. 栈的生长方向是从高往低的
  3. 小端模式是低位存储在低字节
  4. %d格式输出的是4个字节大小，而long long为8个字节

类型转换

表达式会包含隐式类型转换，它由编译器自动执行，不需程序员介入。 何时发生隐式类型转换

1. 在混合类型的表达式中，操作数会被转换为相同类型

int ival; double dval;
ival >= dval; // ival converted to double

2. 条件表达式会被转换为bool类型。

int ival; if (ival) // ival converted to bool while (cin) // cin converted to bool

3. 初始化和赋值

int ival = 3.14 // 3.14 converted to int int *ip;
ip = 0; // the int 0 converted to a null pointer of type int *

4. 在函数调用时，所传递的参数也可能发生隐式类型转换。

如何转换：

1. 算术转换

算术转换保证在执行操作前，将二元操作符的两个操作数转换为同一类型，并使表达式的值也具有相同的类型。

算术转换通常的是做整形提升（integral promotion），对于所有比int小的整形，包括char、signed char、unsigned char、short和unsigned short，如果该类型的所有可能的值都能包含在int内，它们就会被提升为int，否则被提升为unsigned int。如果将bool值提升为int，则false转换为0，true转换为1。

包含short和int类型的表达式，short转换为int。如果int足以表示所有unsigned short类型的值，则将unsigned short转换为int，否则两个操作数均转换为unsigned int。long和unsigned int的转换也一样。只要机器上的long足够表示unsigned int类型所有的值，就将unsigned int转换为long，否则两个操作数都转换为unsigned long。在32位的机器上，long和int通常用一个字长表示，此时如果表达式包含unsigned int和long，两者都转换为unsigned long。

如果表达式包含signed和unsigned int，signed会被转换为unsigned。如果int 操作数的值恰为负数，其转换为unsigned int可能会变为一个很大的正数（转换结果是该负值对unsigned int的取值个数求模）。所以最好避免对int和unsigned int的两个操作数进行比较。

2. 其他隐式转换

（1）数组名转换为指向其第一个元素的指针

int ia[10]; // array of 10 ints int *ip = ia; // convert ia to pointer to first element

另外，任意数据类型的指针都可转换为void *，整形数值常量0可以转换为任意类型指针。

（2）指针值可转换为bool

如果指针为0，转换为false，否则转换为true。

if (cp) // true if pointer cp is not zero

（3）算术类型与bool的转换

算术类型转换为bool时，0转换为false，其他值（包括负值）转换为true。将bool转换为算术类型时，true转换为1，false转换为0。 （4）转换与枚举类型 枚举类型对象或枚举成员将自动转换为整形，其转换结果可以用于任何需要使用整数值的地方。具体会被转换为哪种整形，依赖于枚举成员的最大值和机器。enum对象或枚举成员至少提升为int，如果int无法表示枚举成员的最大值，则提升到能表示所有枚举成员值的、大于int型的最小类型（unsigned int 、long或unsigned long）。

（3）C++对象模型

早绑定、静态绑定

动态绑定的含义：运行时才绑定这个函数名与其对应的实际代码。有些地方也称这种机制为迟绑定，晚绑定。 查找其对应的代码的工作都是在编译阶段完成而非运行时完成的，这就是所谓的静态绑定，也叫早绑定。

根据<<深度探索c++对象模型>>里面说到的，普通成员函数在编译器实现时，大致经历一下转化过程：

1.改写函数的签名以安插一个额外的参数 - this指针 2. 将每一个对非静态成员数据成员的存取操作改为经由this指针来存取。 3.将成员函数重写成外部函数，函数名称经过“mangling”处理，使其在程序中有唯一的名字。 （重写成外部函数，是希望在实现成员函数的时候，使其效率接近普通非成员函数，尽可能避免带来额外开销）

（4）普通语法规则

static

  • static 局部变量仅会被初始化一次，其值作用域等同于普通局部变量，生存期为全局
  • static 全局变量对其他源文件隐藏，生存期为全局

操作符优先级

  • 逗号操作符具有最低优先级

（5）C++拷贝构造函数调用时机

#include <iostream>
using namespace std;

class A
{
private:
    int a;
public:
    A(int i){a=i;}  //内联的构造函数
    A(A &aa);
    int geta(){return a;}
};

A::A(A &aa)     //拷贝构造函数
{
    a=aa.a;
    cout<<"拷贝构造函数执行！"<<endl;
}

int get_a(A aa)     //参数是对象，是值传递，会调用拷贝构造函数
{
    return aa.geta();
}

int get_a_1(A &aa)  //如果参数是引用类型，本身就是引用传递，所以不会调用拷贝构造函数
{
    return aa.geta();
}

A get_A()       //返回值是对象类型，会调用拷贝构造函数。会调用拷贝构造函数，因为函数体内生成的对象aa是临时的，离开这个函数就消失了。所有会调用拷贝构造函数复制一份。
{
    A aa(1);
    return aa;
}

A& get_A_1()    //会调用拷贝构造函数，因为函数体内生成的对象aa是临时的，离开这个函数就消失了。所有会调用拷贝构造函数复制一份。
{
    A aa(1);
    return aa;
}

int _tmain(int argc, _TCHAR* argv[])
{
    A a1(1);
    A b1(a1);           //用a1初始化b1，调用拷贝构造函数
    A c1=a1;            //用a1初始化c1，调用拷贝构造函数

    int i=get_a(a1);        //函数形参是类的对象，调用拷贝构造函数
    int j=get_a_1(a1);      //函数形参类型是引用，不调用拷贝构造函数

    A d1=get_A();       //调用拷贝构造函数
    A e1=get_A_1();     //调用拷贝构造函数

    return 0;
}

调用时机

  • 显示调用
  • 使用一个已存在的对象初始化一个新的对象
  • 函数的返回类型是类的对象或者对象引用
  • 函数的参数是类的对象形式

以下情况不会调用

  • 赋值
  • 函数参数为引用形式

（6）malloc与new

区别

  • new/delete是C++关键字，需要编译器支持。malloc/free是库函数，需要头文件支持。
  • 使用new操作符申请内存分配时无须指定内存块的大小，编译器会根据类型信息自行计算。而malloc则需要显式地指出所需内存的尺寸。
  • new操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配，无须进行类型转换，故new是符合类型安全性的操作符。而malloc内存分配成功则是返回void * ，需要通过强制类型转换将void *指针转换成我们需要的类型。
  • new内存分配失败时，会抛出bac_alloc异常。malloc分配内存失败时返回NULL。
  • new会先调用operator new函数，申请足够的内存（通常底层使用malloc实现）。然后调用类型的构造函数，初始化成员变量，最后返回自定义类型指针。delete先调用析构函数，然后调用operator delete函数释放内存（通常底层使用free实现）。

malloc 一个类

class A
{
public:
    A(){};
    ~A(){};
    void foo(){
        cout<<"foo"<<":"<<a<<endl;
    }
    static void staticFoo(){
        cout<<"staticFoo"<<endl;
    }
private:
    int a;
};

int main(){
    cout<<sizeof(A)<<endl;
    ((A*) NULL) -> staticFoo();
    A* a = (A*)malloc(sizeof(A));
    a-> staticFoo();
    a->foo();
    return 0;
}

/*
输出：
4
staticFoo
staticFoo
foo:0
*/

2、java

（1）java初始化过程

  1. 父类静态代码块 （ java虚拟机加载类时，就会执行该块代码，故只执行一次）
  2. 子类静态代码块 （ java虚拟机加载类时，就会执行该块代码，故只执行一次）
  3. 父类属性对象初始化
  4. 父类普通代码块（每次new,每次执行 ）
  5. 父类构造函数（每次new,每次执行）
  6. 子类属性对象初始化
  7. 子类普通代码块（每次new,每次执行 ）
  8. 子类构造函数（每次new,每次执行）

静态块>main()>构造块>构造方法

（2）java并发

锁 语法关键字：synchronized

synchronized (aObject) {
    //原子操作
}
public synchronized returnType 原子操作方法名(参数列表){
    //原子操作
}

与锁相关的方法

  • Object.wait() 让当前线程进入等待状态，同时，wait()也会让当前线程释放它所持有的锁
  • Object.notify() 或者 Object.notifyAll() 唤醒当前对象上的等待状态线程（随机一个或者多个），不会释放锁

线程相关操作见

java多线程

JDK中并发辅助类

  • Semaphore计数信号量（类似于操作系统的信号量）
  • CyclicBarrier同步屏障，构造：CyclicBarrier c = new CyclicBarrier(2); 阻塞等待：c.await();，当调用次数达到2时，继续执行
  • CountDownLatch倒计时，类似于CyclicBarrier的功能，也有个await方法，但只能使用一次。

（3）Java基本数据类型

实数取整

向下取整:Math.floor(3.5)=3 Math.floor(-2.3)=-3.0 向上取整:Math.ceil(3.1)=4 Math.ceil(-2.3)=-2.0

有无符号

java中没有无符号数的类型，char大小为两字节（Unicode编码）无符号类型

类型转换

  • 字面量类型
    • 整数：
      • 无标记为小于int值的自动类型推断：123正确，1234567890123报错
      • L标记long：123L正确，1234567890123L正确，0xffffffffffffL正确
    • 浮点数：
      • 无标记为double：1.0正确，1E90正确
      • f标记float：1.0f正确，1E90f报错
  • 变量创建并使用字面量（或字面量计算）初始化（编译优化，编译后值为直接值）
    • 当不会出现精度丢失将进行自动类型转换
    • 对于整型：进行自动类型转换，byte b1=1; char c1 = 'a'; char c2 = 123; short s1='a'+1不会报错
    • 对于浮点数：
      • 用实数字面量初始化不进行自动类型转换，因为会出现精度丢失float f1=1.0;报错，因为1.0为double类型字面量
      • 用整形字面量初始化进行自动类型转换，float f3=1; float f4=1L; 不报错
  • 变量创建并使用其他变量初始化
    • 只能使用不会出现损失的类型转换（小的赋给大的）
      • char c='a'; short s=c; 报错，因为char的范围无符号16位，short范围为有符号16位
      • short s=123; char c=s; 报错，因为char的范围无符号16位，short范围为有符号16位
  • 使用类似于+=进行计算（编译优化）
    • 直接进行类型转换
    • byte b1=100; b1+=1+1; b1+=100000 正确
    • byte b1=100, b2=100; b1+=b2 正确
  • 进行计算（+-*/）时
    • 只有整数：
      • 所有低于int都会转换为int或者最大的类型short s1=2, s2=1; short s3=s1-s2;报错
      • /运算为整除运算
    • 整数浮点数混合
      • 如果不存在double，存在float，所有的值将转换为float：
        • float f1=1; float f2=f1+1L;正确
        • float f1=1; long d=1L;float f2=f1+d;正确
      • 如果存在double，所有转换为double
      • /为浮点数除法

隐式转换总结

  • 类型符合规则的自动转换（若类型不符合，即使值转换不发生精度丢失或损失，也不允许）
    • 赋值：一般情况下，从小的转换为大的，byte→short(char)→int→long→float→double
    • 计算：一般情况下，转换为int及更大：(byte,short,char)→int→long→float→double
  • 值符合规则的转换（只要值转换不发生精度丢失或损失即可）
    • 赋值：字面量赋值
    • 计算：字面量计算（这种计算发生在编译期，一种编译优化）
  • 直接允许溢出的转换计算
    • +=
    • -=
    • *=
    • ++
    • --

（4）重写和重载

重载 overloading

同名函数，处理不同类型

重写overriding

父子类同名方法相关的概念

（4）Java switch 类型

byte、short、char、int、enum（Java 5）、String(Java 7)

（5）Java异常机制

根据官方的JVM规范：

如果try语句里有return，返回的是try语句块中变量值。 详细执行过程如下：

  • 如果有返回值，就把返回值保存到局部变量中；
  • 执行jsr指令跳到finally语句里执行；
  • 执行完finally语句后，返回之前保存在局部变量表里的值。

如果try，finally语句里均有return，忽略try的return，而使用finally的return.

（6）重定向和转发

  • 重定向（redirect） 返回给浏览器302
  • 转发（forward） 服务器内部行为

（7）Java常用容器

  • java.util.concurrent.LinkedBlockingQueue<E> 线程安全、用于实现生产者和消费者模型，不接受null
  • java.util.PriorityQueue<E>优先队列，不支持null和不可比较对象，非线程安全；此实现提供了O（log(n)）的时间入队和出队方法（ offer ， poll ， remove()和add ）; remove(Object)和contains(Object)方法的线性时间; 和恒定时间检索方法（ peek ， element和size ）。使用堆实现。
  • java.util.concurrent.ConcurrentLinkedQueue<E> 一个基于链接节点的无界线程安全队列。不允许使用 null 元素。size复杂度O(n)

（8）Java动态代理

JDK使用

  • 被代理类必须实现一个接口
  • 创建一个实现InvocationHandler接口的类，实现代理逻辑
  • 使用Object Proxy.newProxyInstance(ClassLoader, Class[], InvocationHandler);创建代理类，并强转为接口类型
  • 想使用正常类一样使用代理对象

CGLib使用

  • 创建 net.sf.cglib.proxy.Enhancer 对象
  • 设置需要代理的类（不允许是final） enhancer.setSuperclass(MyClass.class);
  • 创建实现MethodInterceptor接口的类，实现代理逻辑
  • 设置代理逻辑 enhancer.setCallback()
  • 创建代理对象 MyClass my = (MyClass)enhancer.create(); 并强转成被代理类型
  • 想使用正常类一样使用代理对象

原理

利用运行时编译+反射技术。动态创建代理类，代理类通过反射实现被代理对象的方法调用

  • JDK使用 sun.misc.ProxyGenerator动态生成相关字节码
  • CGLIB使用ASM动态生成字节码

（9）类加载

作用

  • 将class文件读进虚拟机，生成class对象
  • 通过自定义类加载器实现完全同名类的隔离

使用类加载器机制的原因

  • 可以灵活而安全的从网络或其他途径动态的加载一个接口的实现类
  • 将Java代码加密

内置的三级加载器

  • 引导类加载器 BootStrap加载 jre/lib/rt.jar
  • 扩展类加载器 ExtClassLoader加载 JRE/lib/ext/*.jar
  • 应用类加载器(系统类加载器) AppClassLoader 负责加载 SystemClassLoader 和 CLASSPATH指定的所有jar或目录

双亲委派模型

  • 向上层询问是否已加载或者可以加载否则再自己加载

3、python

4、javascript

（1）js的基本数据类型

ES6 后新增了一类数据类型 ：Symbol ，根据 JavaScript 高程, ES5 中的基本数据类型有 5 种：Undefined、Null、Boolean、Number、String.而 Object 是属于复杂数据类型，所以我认为这里说的 6 种基本数据类型是指：Undefined、Null、Boolean、Number、String 与 Symbol.

5、html/css

（1）html元素优先级

在html中，帧元素（frameset）的优先级最高，表单元素比非表单元素的优先级要高。 表单元素包括：文本输入框，密码输入框，单选框，复选框，文本输入域，列表框等等； 非表单元素包括：连接（a），div,table,span等。 所有的html元素又可以根据其显示分成两类：有窗口元素以及无窗口元素。有窗口元素总是显示在无窗口元素的前面。 有窗口元素包括：select元素，object元素，以及frames元素等等。 无窗口元素：大部分html元素都是无窗口元素。

二、计算机基础

1、网络基础

（1）ICMP协议

ICMP协议是一种面向无连接的协议，用于传输出错报告控制信息。属于网络层协议，主要用于在主机与路由器之间传递控制信息，包括报告错误、交换受限控制和状态信息等。当遇到IP数据无法访问目标、IP路由器无法按当前的传输速率转发数据包等情况时，会自动发送ICMP消息。ICMP报文在IP帧结构的首部协议类型字段（Protocol 8bit)的值=1.

ping所使用的协议

2、数据库

（1）数据库设计范式

参考

综述

  • 数据库范式分为1NF，2NF，3NF，BCNF，4NF，5NF。一般在我们设计关系型数据库的时候，最多考虑到BCNF就够。
  • 符合高一级范式的设计，必定符合低一级范式，例如符合2NF的关系模式，必定符合1NF。

1NF

1NF的定义为：符合1NF的关系中的每个属性都不可再分

2NF

2NF在1NF的基础之上，消除了非主属性对于码（主键）的部分函数依赖 其中：

  • 函数依赖：若在一张表中，在属性（或属性组）X的值确定的情况下，必定能确定属性Y的值，那么就可以说Y函数依赖于X，写作 X → Y，类似于数学的存在必然函数关系，y = f(x)，在x的值确定的情况下，y的值一定是确定的。
  • 非主属性：包含在任何一个码（主键）中的属性成为主属性。

3NF

第三范式（3NF） 3NF在2NF的基础之上，消除了非主属性对于码的传递函数依赖。 其中：

  • 传递函数依赖：对于学生表，主码为学号，主属性为学号，非主属性为姓名、系名和系主任。因为 学号 → 系名，同时 系名 → 系主任，所以存在非主属性系主任对于码学号的传递函数依赖，所以学生表的设计，不符合3NF的要求。。

BCNF

主属性对于码的部分与传递函数依赖。

不符合BCNF、符合3NF的表：仓库（仓库名，管理员，物品名，数量） 符合BCNF：

  • 仓库（仓库名，管理员）
  • 库存（仓库名，物品名，数量）

（2）sql组成

  • DML（data manipulation language）数据操纵语言：
    • 它们是SELECT、UPDATE、INSERT、DELETE，就象它的名字一样，这4条命令是用来对数据库里的数据进行操作的语言
  • DDL（data definition language）数据定义语言：
    • DDL比DML要多，主要的命令有CREATE、ALTER、DROP等，DDL主要是用在定义或改变表（TABLE）的结构，数据类型，表之间的链接和约束等初始化工作上，他们大多在建立表时使用
  • DCL（Data Control Language）数据控制语言：、
    • 是数据库控制功能。是用来设置或更改数据库用户或角色权限的语句，包括（grant,deny,revoke等）语句。在默认状态下，只有sysadmin,dbcreator,db_owner或db_securityadmin等人员才有权力执行DCL
  • DQL（data query language）数据查询语言
    • 即select。

3、操作系统

unix高级编程

4、加密和安全

5、编程基础

6、编译和体系结构

7、思想与方法论

（1）面向对象七大设计原则

  • 单一职责原则（Single Responsibility Principle） 每一个类应该专注于做一件事情。
  • 里氏替换原则（Liskov Substitution Principle） 超类存在的地方，子类是可以替换的。
  • 依赖倒置原则（Dependence Inversion Principle） 实现尽量依赖抽象，不依赖具体实现。
  • 接口隔离原则（Interface Segregation Principle） 应当为客户端提供尽可能小的单独的接口，而不是提供大的总的接口。
  • 迪米特法则（Law Of Demeter） 又叫最少知识原则，一个软件实体应当尽可能少的与其他实体发生相互作用。
  • 开闭原则（Open Close Principle） 面向扩展开放，面向修改关闭。
  • 组合/聚合复用原则（Composite/Aggregate Reuse Principle CARP） 尽量使用合成/聚合达到复用，尽量少用继承。原则： 一个类中有另一个类的对象。

8、数据结构

（1）树的度

表述的是树的子树的数目例如二叉树的度的可选值为（0,1,2）

（2）常见排序算法性的性质

排序方式平均时间复杂度最坏时间复杂度最好时间复杂度稳定性空间复杂度
冒泡排序O(n2)O(n2)O(n) 设置一个标志：当一趟没有发生改变直接结束稳定O(1)
插入排序O(n2)O(n2)O(n) 当要插入的元素就在当前位置就不需要比较了稳定O(1)
选择排序O(n2)O(n2)O(n2)不稳定O(1)
快速排序O(nlogn)O(n2)O(nlogn)不稳定O(1)
堆排序O(nlogn)O(nlogn)O(nlogn)不稳定O(1)
归并排序O(nlogn)O(nlogn)O(nlogn)稳定O(n)
希尔排序O(n2)不稳定O(1)
基数排序O(d(n+radix))稳定2*radix
  • 冒泡排序：两两比较交换
  • 插入排序：将该元素插入已排好的数组中，设计数组搬移
  • 选择排序：每次在剩余无序的元素中选择最小的与首部交换（涉及无序交换所以不稳定）
  • 快速排序：每次选择一个分界点，将数组划分为两个部分，左边比右边的小，然后递归这个过程。如果分界点在正中间则时间达到O(nlog)，若分界点在两边时间为O(n2)（涉及无序交换所以不稳定）
  • 堆排序：建立最大堆或者最小堆，然后将堆顶与最后一个元素交换，再重建堆（堆：根大于或小于所有子树的所有节点叫大根堆或小根堆）
  • 归并排序：分治法，将数组一分为二递归再分一直到只有一个元素，递归返回后将者两个部分合并成有序数组一直到顶。在合并的过程中需要一个临时数组拷贝用，所以空间复杂度为O(n)
  • 希尔排序：存在一个增量这位gap初始值为len/2，将所有元素分为len/2个组，分别对五组进行直接插入排序，然后让gap /= 2再分组，再排序，直到gap==0为止
  • 基数排序：选择一个基数radix例如10，将数组按照各位数字进行分组，然后合并，然后在按照十位数字进行分组，依次类推

（2）链表编程题的一般原则

  • 一般思路为遍历链表的同时改变next指针的指向
  • 链表进行操作有保护链表的根节点
  • 设置游标指针
  • 在While判断语句中，仅判断游标本身是否为NULL
  • 在纸上模拟终止条件（最多就1到2种情况）

（3）HashTable

处理冲突的方式

  • 分离链接法
  • 开放定址法（当发生冲突后，探测寻找第n+f(n)个位置是否有元素如果没有放入，否则在探测）
    • 线性探测法（f(n)=1）
    • 平方探测法（f(n)=n^2）
    • 双散列（f(n)=i*hash2(key)）
  • 再散列（当装载因子大于指定阈值之后，重新申请比当前大的空间，然后将旧的元素重新放入恰当的位置，若还发生冲突就在以上方案中选择1个处理：Java HashMap的算法）

可扩散列

主要用于数据库索引的实现，减少磁盘IO，并提高读写效率

  • 比如说关键字为长度为6的二进制数
  • 类似于B-Tree，根节点使用最高两位作为区分值，所以共需要2^2个指针
  • 当叶子放不下了后，根节点进行分裂，选择最高三位作为区分值，所以共需要2^3个指针，但是可以使用lazy策略进行分裂。也就是说在插入的时候检查是否需要进行分裂，再做分裂

散列和查找树

散列：

  • 当装载因子合理小时，时间复杂度可达O(1)
  • 但是需要谨慎的设计散列函数
  • 对于空间紧凑型应用不合适使用
  • 快速查询最值

散列的应用

  • 编译器符号表
  • 图论节点查找
  • 游戏基于位置的查找表
  • 拼写检查

二叉查找树

  • 平均查找时间为 O(logn)，并不比散列差多少（试想下log(INT_MAXN)==32）
  • 不需要计算散列耗时的乘除法
  • 但是二叉查找树对输入序列敏感，可能导致树失衡，而维持数平衡又要付出很大的代价

（4）优先队列（堆）

要求

  • 可以插入
  • 可以快速的找到最小的元素
  • 可以快速删除最小的元素

实现方式

堆

（最小）堆的定义

  • 一颗完全二叉树
  • 根结点的值小于所有子树的值
  • 所有子树满足以上条件

基本实现方式

创建一个数组，元素从下表1（从零也可以）的位置存储，把这个数组当做一个完全二叉树，有以下性质

  • 下标为i结点的左孩子的下标为2*i，右孩子的下标为2*i+1
  • 最后一个非叶子节点下标为len/2，且1~len/2都为非叶子结点

插入——使用上浮shiftUp

  • 未插入之前，该容器是符合堆定义的
  • 在最后一个结点的下一个位置创建一个空穴，空穴元素为插入的元素
  • 找到他的父节点比较，若空穴位置填上空穴元素，该容器是否满足堆定义
    • 满足：则将元素插到空穴的位置
    • 不满足：将空穴与空穴的父节点交换位置，然后执行在执行第三步，直到达到根为止
  • len++;

查找最小的

  • 返回下标为1的位置

删除最小的——使用下沉shiftDown

  • 将根位置设为空穴，最后一个元素设为空穴元素，len--
  • 找到空穴的两个孩子，若空穴位置填上空穴元素，该容器是否满足堆定义
    • 满足：则将元素插到空穴的位置
    • 不满足：将空穴与空穴合适的孩子节点交换位置，然后执行在执行上一步，直到达到叶子节点为止

给n个元素初始化堆

  • 从最后一个非叶子节点到根节点依次执行下沉操作

堆排序

  • 确保是一个堆
  • 大根堆——从小到大，小根堆从大到小
  • 将根与最后一个元素交换，以根为节点空穴，根节点现在的元素为空穴元素，堆的尺寸为原来尺寸-1，进行下沉操作

（5）给定一个第二趟排序后结果，选择是那种排序

  • 对于冒泡、选择来说。第n趟后，前n个元素或者后n个元素是最大或最小的，而且是有序的，而且和最后的结果是一致的
  • 二路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。
  • 对于插入来说，前n个元素是有序的
  • 快排来说，第n次排序之后最少有 n 个元素在正确的位置

（6）基于比较的排序和非比较排序

基于比较的排序：

  • 选择排序
  • 冒泡排序
  • 插入排序
  • 希尔排序
  • 归并排序
  • 快速排序
  • 堆排序

非基于比较的排序算法

  • 计数排序
  • 桶排序
  • 基数排序

外部排序：

一般使用归并的原理

（7）图论算法

表示方式

  • 邻接矩阵（不适用于边稀疏的情况）
  • 邻接表（类似于散列表的结构，使用vector<list<node>>存储）

拓扑排序

问题：给一个无环图，得到一个序列，满足其前驱关系（比如大学课程前后学习安排） 方案：

  • 将所有入度为0的节点放入一个队列或者栈
  • while(若队列不为空)
    • 将队列的头的节点删除并放入输出中，并将该节点的后继的入度减一，并将入度为0的节点放入队列
  • 返回

最短路径

使用广度优先搜索，有三个辅助数组

  • known[] 表示节点是否遍历过
    • known[i]=0 表示i节点没有到达过
    • known[i]=1 表示i节点已经到达了
  • d[i] 表示遍历到目前为止起点到i节点最小权值
  • p[i] 记录最短路径的前驱

所有点间的最短路径：网络流

未知

最小生成树

  • Prim算法——从已连接的节点中的所有边中选择最小的边的节点放入集合
    • 选择一个起始点，标记为已遍历
    • 将起始点的所有边加入容器（堆）
    • while(所有节点已被标记)
      • 选择最小的边，将这个边的未被标记的节点设为标记，将这个节点的相关联的边放入容器
    • 完成
  • Kruskal算法——从最小权值的边遍历
    • 对边集进行排序
    • 遍历加入并查集