一、数据结构（+算法）

数组
1. 寻找数组中第二小的元素：设置$Firstmin$和$Secondmin$更新时分类讨论即可
2. 找到数组中第一个不重复出现的整数：Hashmap+$O(n)$暴力统计
栈
1. 2个栈模拟1个队列：push暂时存s1，s2里pop；s2被pop为空时将s1的全部push到s2，再在s2里pop
队列

链表

反转链表：新建一个链表用头插法，返回一个全新的链表L2
1
2
3
temp.init(p);
temp->next = L2->next;
L2->next = temp
检测链表中的环：快慢指针p1和p2，若有环则迟早相遇。
返回倒数第$k$个元素：让指针p1比p2早走$k-1$步，p2到最后一个节点（p2->next==NULL)时，p1所指即是目标元素

无序链表去重$O(n^2)$

void del_multielem(Node *L)
{
    Node *cur = L->nxt, *p, *q;
    while (cur)
    {
        p = cur;
        q = cur->nxt;
        while (q)
        {
            if (abs(q->val) == abs(cur->val))//删除q所指的元素
            {
                p->nxt = q->nxt;
                q = q->nxt;
            }
            else
            {
                q = q->nxt;
                p = p->nxt;
            }
        }
        cur = cur->nxt;
    }
}

树
1. 检测图是否为树：基图连通、每个结点的父节点只能有一个
图

字典树

简单实现：

struct Trie
{
    int nxt[2], v;
    void init(){
        for (int i = 0; i < 2; ++i)
            nxt[i] = -1;
        v = 0;
    }
} L[N];
int sz;

inline int newnode(){
    L[sz].init();
    return sz++;
}
void ins(char s[], int len, int v){
    int u = 0;
    for (int i = 0; i < len; ++i){
        int v = s[i]-'0';
        if (L[u].nxt[v] == -1){
            L[u].nxt[v] = newnode();
        }
        u = L[u].nxt[v];
        L[u].cnt = 1;
    }
}
int query(int val)//查询异或最大值{
    bitset<31>s(val);
    int u = 0;
    for (int i = 30; i >= 0; --i){
        int v = s[i];
        if (L[L[u].nxt[v ^ 1]].cnt)
            u = L[u].nxt[v ^ 1];
        else
            u = L[u].nxt[v];
    }
    return L[u].v;//返回能与val异或得到最大值的拎一个数L[u].v
}

压缩存储BitMap

简单实现

struct BitMap
{
    int bit[N];
    void init() {
        clr(bit, 0);
    }
    void insert(int x) {
        bit[x >> 5] |= (1 << (x & 31));
    }
    int query(int x) {
        return bit[x >> 5] & (1 << (x & 31));
    }
    vector<int> getall() {
        vector<int>ret;
        fl(i, 0, N) {
            fl(j, 0, 32) {
                if (bit[i] & (1 << j)) {
                    ret.pb((i << 5) + j);
                }
            }
        }
        return ret;
    }
}bitmap;

二、计算机组成原理

RISC与CISC指令集

从硬件角度来看CISC处理的是不等长指令集，RISC执行的是等长精简指令集
流水线技术

流水线技术是一种将每条指令分解为多步，并让各步操作重叠，从而实现几条指令并行处理的技术。
存储器层次结构

随机访问存储器：
1. SRAM（双稳态触发器存储、易失、速度快）
2. DRAM（栅极电容存储、易失、地址复用技术）
局部性原理
1. 时间局部性（Temporal Locality）：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。程序循环、堆栈等是产生时间局部性的原因。
2. 空间局部性（Spatial Locality）：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。
虚拟存储器：为了给大的程序提供方便，使它们摆脱主存容量的限制，可以由操作系统把主存和辅存这两级存储系统管理起来，实现自动覆盖。
中断
1. 基本概念：执行现行程序时出现异常情况或特殊请求，CPU暂时中止转而去处理这些紧急情况，处理完毕后继续执行原程序
2. 中断大概阶段：中断请求、中断判优、中断响应、中断处理和中断返回。
3. 断点：断点是一个信号，它通知调试器，在某个特定点上暂时将程序执行挂起（进入中断状态）

三、操作系统

进程：并发执行的程序在执行过程中分配和管理资源的基本单位，是一个动态概念。
线程：是进程的一个执行单元，是进程内调度实体。比进程更小的独立运行的基本单位。线程也被称为轻量级进程。
死锁：
死锁是指一组进程中的各个进程均占有不会释放的资源，但因互相申请被其他进程所占用不会释放的资源而处于的一种永久等待状态
1. 产生死锁的四个必要条件：
  1. 互斥条件：一个资源每次只能被一个进程使用。
  2. 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
  3. 不剥夺条件：进程已获得的资源，在未使用完之前，不能强行剥夺。
  4. 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。
2. 避免死锁的方法：银行家算法
进程的三种状态
1. 就绪状态：进程已获得除处理机以外的所需资源，等待分配处理机资源
2. 运行状态：占用处理机资源运行，处于此状态的进程数小于等于CPU数
3. 阻塞状态：进程等待某种条件，在条件满足之前无法执行
页面置换算法
1. FIFO算法：淘汰最早调入的页面（队列思想）
2. OPT（MIN）：选未来最远将使用的页淘汰，是一种最优的方案，可以证明缺页数最小（不可实现）
3. LRU（Least recently use）最近最少使用算法：根据使用时间到现在的长短来判断；
4. LFU（Least frequently use）最少使用次数算法：根据使用次数来判断；
进程间的通信的几种方式
1. 管道（pipe）及命名管道（named pipe）：管道可用于具有亲缘关系的父子进程间的通信，有名管道除了具有管道所具有的功能外，它还允许无亲缘关系进程间的通信；
2. 信号（signal）：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生；
3. 消息队列：消息队列是消息的链接表，它克服了上两种通信方式中信号量有限的缺点，具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；
线程同步的方式
1. 互斥量 Synchronized/Lock：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问
2. 信号量 Semphare：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
3. 事件(信号) Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作

四、计算机网络

TCP/IP五层模型
1. 物理层：
  负责比特流的透明传输。
2. 链路层：
  负责传输网络层交下来的数据，有封装成帧、透明传输、差错检测三大问题。ARP、RARP协议
3. 网络层:
  负责为分组交换网上的不同主机提供通信服务。IP、ICMP、IGMP、RIP、OSPF
4. 运输层：
  负责向两个主机中进程之间的通信提供服务。TCP、UDP
5. 应用层：
  直接为用户的应用进程提供服务（例如电子邮件、文件传输和终端仿真）HTTP、FTP、TELNET
RIP协议
原理：采用距离向量路由协议 ，周期性的发送自己的全部的路由信息，进行路由更新时传递路由表
OSPF协议
原理：采用链路状态路由协议，周期性的发送链路状态信息，使得区域内所有路由器最终都能形成一个跟踪网络链路状态的链路状态数据库
TCP 与 UDP 的区别
1. UDP是面向无连接的，不可靠的数据报服务；
2. TCP是面向连接的，可靠的字节流服务。
TCP 的可靠性如何保证？
TCP的可靠性是通过顺序编号和确认（ACK）来实现的。
路由设备与相关层
1. 物理层：中继器（Repeater，也叫放大器），集线器。
2. 数据链路层：网桥，交换机。
3. 网络层：路由器。
4. 网关：网络层以上的设备。

五、软件工程

瀑布模型：
特点：阶段间具有顺序性和依赖性
优点：有质量保证
缺点：开始需要把需求做到最全，需求变更麻烦
螺旋模型：
特点：强调风险分析，适应于内部的大规模软件开发
优点：设计灵活、客户始终参与每个阶段的开发
缺点：开发周期长
增量模型
特点：将待开发的软件系统模块化和组件化
优点：人员分配灵活，刚开始不用投入大量人力资源
缺点：加入构件必须不破坏已构造好的系统部分，这需要软件具备开放式的体系结构
快速原型模型
特点：迅速建造一个可以运行的软件原型
优点：克服瀑布模型的缺点,减少由于软件需求不明确带来的开发风险
缺点：快速建立起来的系统结构加上连续的修改可能会导致产品质量低下
喷泉模型
特点：开发阶段可以交互进行
优点：提高开发效率，适合面向对象的软件开发过程
缺点：要求严格管理文档，不利于项目的管理
软件生命周期：一个软件从提出开发要求开始直到该软件报废为止的整个时期。
软件设计的基本原理：模块化、抽象、信息屏蔽、模块独立性
面向对象的特征是：对象唯一性、分类性、继承性、多态性
黑盒测试和白盒测试有何区别，黑盒测试有哪些常用方法：前者基于功能，后者基于结构；黑盒测试常用方法有：边界值、等价类、因果图、错误推测法等
软件测试要经过的步骤是：单元测试→集成测试→确认测试→系统测试
软件生命周期划分为哪几个阶段？
1. 软件生命周期分为三个时期八个阶段：
2. 软件定义：问题定义、可行性研究；
3. 软件开发：需求分析、概要设计、详细设计、编码、测试；
4. 软件运行：软件维护
简述三种面向对象模型的主要功能？
1. 对象模型：表示了静态的结构化的系统数据性质，描绘了系统的静态结构，从客观世界实体的对象关系角度来描绘对象。
2. 动态模型：该模型描述了系统的控制结构，它表示了瞬间的、行为化的系统控制性质，它关心的是系统的控制及操作的执行顺序，它从对象的事件和状态的角度出发，表现了对象的交互行为。
3. 功能模型：表示变化的系统“功能”性质，它指明系统应该“做什么”，因此功能模型更直接的反映了用户对目标系统的要求。

六、数据库

视图和表的区别：
1. 数据都是存储在表中的，而视图只是一个或多个表依照某个条件组合而成的结果集，一般来说你可以用update，insert，delete等sql语句修改表中的数据，而对视图只能进行select操作。
事务的ACID特性：
1. 原子性（Atomicity）
  事务是一个不可再分割的工作单位
2. 一致性（Consistency）
  执行一个事务前和后，数据库的完整性约束没有没有被破坏
3. 隔离性（lsolation）
  多个事务并发时，每个事务应该是隔离的
4. 持久性（Durability）
  事务执行完成后，事务对数据库的更改便持久到了数据库中，这个更改是永久的
数据库的锁
1. 行级锁：是一种排他锁，防止其他事务修改此行
2. 表级锁：
  1. 行共享 (ROW SHARE) – 禁止排他锁定表
  2. 行排他(ROW EXCLUSIVE) – 禁止使用排他锁和共享锁
  3. 共享锁(SHARE) - 锁定表，对记录只读不写，多个用户可以同时在同一个表上应用此锁
  4. 共享行排他(SHARE ROW EXCLUSIVE) – 比共享锁更多的限制，禁止使用共享锁及更高的锁
  5. 排他(EXCLUSIVE) – 限制最强的表锁，仅允许其他用户查询该表的行。禁止修改和锁定表。
什么是存储过程？有哪些优缺点？

存储过程是一些预编译的SQL语句，执行效率比较高，安全性高；开发调试复杂。
索引是什么？有什么作用以及优缺点？

索引是对数据库表中一或多个列的值进行排序的结构，是帮助MySQL高效获取数据的数据结构
什么是事务？

并发控制的基本单位，一个操作序列，一个不可分割的工作单位。
数据库的乐观锁和悲观锁是什么？

悲观锁：假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作

乐观锁：假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。
简单说一说drop、delete与truncate的区别

delete和truncate只删除表的数据不删除表的结构
速度,一般来说: drop> truncate >delete

delete语句是dml,这个操作会放到rollback segement中,事务提交之后才生效;

如果有相应的trigger,执行的时候将被触发. truncate,drop是ddl, 操作立即生效,原数据不放到rollback segment中,不能回滚. 操作不触发trigger.
超键、候选键、主键、外键分别是什么？
1. 超键：在关系中能唯一标识元组的属性集称为关系模式的超键。一个属性可以为作为一个超键，多个属性组合在一起也可以作为一个超键。超键包含候选键和主键。
2. 候选键：是最小超键，即没有冗余元素的超键。
3. 主键：数据库表中对储存数据对象予以唯一和完整标识的数据列或属性的组合。一个数据列只能有一个主键，且主键的取值不能缺失，即不能为空值（Null）。
4. 外键：在一个表中存在的另一个表的主键称此表的外键。
三个范式
1. 第一范式（1NF）：数据库表中的字段都是单一属性的，不可再分。这个单一属性由基本类型构成，包括整型、实数、字符型、逻辑型、日期型等。
2. 第二范式（2NF）：数据库表中不存在非关键字段对任一候选关键字段的部分函数依赖（部分函数依赖指的是存在组合关键字中的某些字段决定非关键字段的情况），也即所有非关键字段都完全依赖于任意一组候选关键字。
3. 第三范式（3NF）：在第二范式的基础上，数据表中如果不存在非关键字段对任一候选关键字段的传递函数依赖则符合第三范式。所谓传递函数依赖，指的是如果存在”A → B → C”的决定关系，则C传递函数依赖于A。因此，满足第三范式的数据库表应该不存在如下依赖关系：关键字段 → 非关键字段 x → 非关键字段y。

七、编译原理

编译过程四个阶段:

（.c）>预处理（.i）>编译（.s）>汇编（.o）>链接（.exe）
1. 预处理：展开头文件/宏替换/去掉注释/条件编译（test.i, main.i）
2. 编译：检查语法，生成汇编（test.s main.s）
3. 汇编：汇编代码转换机器码（test.o main.o）
4. 链接：链接到一起生成可执行程序（a.out）

Blackops

HDU复试七门知识点个人版整理

一、数据结构（+算法）

二、计算机组成原理

三、操作系统

四、计算机网络

五、软件工程

六、数据库

七、编译原理