计算机基础知识总结

总结算法和数据结构，还有计算机网络，操作系统的知识。

算法和数据结构

堆区：分配方式类似链表。C语言中由malloc分配，free释放，C++中由new分配，delete释放。

牛客网的编程题

数组

每行从左到右，每列从上到下递增的二维数组中，判断某个数是否存在（剑指 offer 第 3 题）

思想：首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。不断缩小范围，直到找到要查找的数字。否则不存在。

递增排序数组的旋转数组求最小值（剑指offer第8题）

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/?tab=Description
思想：二分查找。
旋转后的数组实际上可以划分为两个排序数组，最小的元素是这俩个子数组的分界线。
两个指针，一个指向第一个元素，一个指向最后一个元素，找到中间元素。
如果中间元素比第一个大，则到后一段中找；
如果中间元素比最后一个小，则到前一段中找。不断缩小，直到两个指针相邻，第二个指针所指向的就是最小的值，循环结束。
特例：1）前面0个元素移到后面，即排序数组本身。（）
2）{1，0，1，1，1}和数组{1，1，1，0，1}是递增数组{0，1，1，1，1}的旋转，只能采取顺序查找的方法。

旋转数组求查找某个值是否存在

https://leetcode.com/problems/search-in-rotated-sorted-array/?tab=Description
思想：同上：二分法

数组中出现次数超过一半的数字（剑指offer第29题）

解法一：快速排序。O(n)
解法二：这个数字出现的次数比其他所有数字出现的次数的和还要多。遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1，如果不同，则次数减1。如果次数为0，则保存在一个数字，并把次数设为1，要找的数字肯定是最后一次把次数设为1的对应的数字。

最小的k个数(最大的K个数)

思想：解法一：快速排序，基于数组的第K个数字来调整，使得比第K个数字小的所有数字都位于数组的左边，比第K个数字大的所有数字都位于数组的右边。左边的K个数字为最小的K个数字。时间复杂度O(n).
此方法的限制：要一次性读入所有数，而且修改输入的数组。
解法二：堆排序。适合处理海量数据。
首先我们读入K个数创建一个大小为K的大根堆，然后我们依次读入剩余数据，如果当前数据比大根堆的堆顶小，则用这个数替换当前的堆顶，并调整堆使其保持大根堆的性质。如果当前数据比大根堆的堆顶大，则不可能是最小的K个整数之一。时间复杂度：O(nlogk)
注意：当求最小的K个数的时候是建立大根堆，当求最大的K个数的时候是建立小根堆。
或者：红黑树，STL中的set和multiset。

【扩展】
第 k 大的数
https://leetcode.com/problems/kth-largest-element-in-an-array/?tab=Description

有序数组中某个数字出现的次数（二分查找）

由于数组有序，所以使用二分查找方法定位k的第一次出现位置和最后一次出现位置。

2. 先二分找到第一个k下标first，再二分找到最后一个k下标last，
3. last-first+1即为所求。
4. 复杂度，O(lgN) + O(lgN) = O(lgN)
   复杂度：时间：O(lgN)；空间O(1)

求两个等长、有序数组的中位数（二分法）

就是比较两个区间的中位数，如果第一个区间的中位数比第二个大，那么就把第一个区间的范围缩小至它的前半段，把第二个区间缩小至它的后半段，然后重复上述过程。
算法复杂度(O(lgn))。

设置a[0..n-1]的中位数是 m1，b[0..n-1]的中位数为 m2
如果 m1=m2，则 m1 则为 2n 个数的中位数
如果 m1>m2，则 2n 个数的中位数一定在 a[0..2/n]和 b[n/2..n]，在求这两个子数组的中位数 
如果 m1<m2，则 2n 个数的中位数一定在 a[n/2..n]和 b[0..2/n]，在求这两个子数组的中位数。

求两个不等长、有序数组的中位数

解法：http://blog.csdn.net/ojshilu/article/details/15027309

调整数组顺序是奇数位于偶数前面

思路:解法一：扫描这个数组，如果发现有偶数出现在奇数的前面，我们可以交换它们的顺序。维护两个指针，第一个指针在数组的一个数字，向后移动，第二个指针在数组的最后一个数值，向前移动。
解法二：把整个函数解耦成两部分：一判断数字应该在数组前半部分还是后半部分的标准，二是拆分数组的操作。

和为S的两个数字VS和为S的连续正数序列（41）

题目：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字，输出一对序列。
思路:定义两个指针，一个指向第一个元素，第二个指针指向最后一个元素，看这两个数字的和>S，则大数–；如果和<S，则小数++；

判断数组中是否有重复值，空间复杂度O(n)

没有空间复杂度的限制用哈希表
有的话先排序再判断，用非递归的堆排序。

荷兰国旗问题

只包含0，1，2的整数数组进行排序，使用交换、原地排序。
与快排的划分类似。时间O(N),空间O(1),
{} 1 1 0 0 2 1 1 0 {}

前面为0区，后面为2区，若是1，向后移指针，若是0与前交换，放入0区，若是2与后交换，放入2区。当前位置和2区重合的时候，停止。

需要排序的最短子数组的长度

排序后相邻两数的最大差值

字符串

字符串转换为数字（49）

思想：依次扫描字符串，每扫描到一个字符，我们把在之前得到的数字乘以10在加上当前字符表示的数字。
遇到“+”号向前走，遇到“-”号，表明这个数是负数。
考虑非法输入：需要判断这个指针是不是为空。
输入的字符串可能含有不是数字的字符，每当碰到非法的字符，转换停止。
溢出问题，若溢出，则返回0.

翻转字符串(42)

思想：第一步翻转句子中所有的字符。第二步再翻转每个单词中字符的顺序。

【扩展】左旋转字符串
翻转字符串前面N个字符，再翻转字符串后面的部分，最后翻转整个字符串。

替换空格(4)

思想：先遍历一次字符串，统计出空格的总数，计算出替换以后的字符串的总长度，每替换一个空格，长度增加2.
从字符串后面开始复制和替换。先准备两个指针P1和P2，P1指向原始字符串的末尾，P2指向替换之后的字符串的末尾，
向前移动P1，逐个把它指向的字符串复制到P2所指向的位置，直到碰到第一个空格的时候，把P1向前移动一个，P2向前移动3格并插入“%20”。继续往前走，直到P1和P2指向同一个位置。
时间复杂度：O(n)

字符串包含（KMP算法）

在给定字符串A中查找一个子字符串B。
KMP算法：利用不匹配字符的前面那一段字符的最长前后缀来尽可能地跳过最大的距离。

字符串的排列

输入一个字符串，打印出字符串的所有排列
输入：abc，输出：acb,bac,cab,cba.
思想：首先求所有可能出现在第一个位置的字符。把第一个字符和后面的所有字符交换。
第二步固定一个字符，求后面所有字符的排列。
输入：abc,输出：a,b,c,ab,ac,bc,abc.

【扩展】求字符的所有组合

第一个只出现一个的字符（35）

利用哈希表，哈希表的Key是字符，value是该字符出现的次数。
从头开始扫描字符串两次，第一次扫描字符串的时候，每扫描到一个字符串就在哈希表的对应项中把次数加1，第二次扫描的时候就能从哈希表中得到该字符串出现的次数。

最长不重复子串

var lengthOfLongestSubstring = function(s) {
    let i=0, res=0, n=0;
    for (let j = 0; j < s.length; j++){
        n = s.slice(i,j).indexOf(s[j])
        if (n == -1){
            res = Math.max(res,j+1-i);
        }else{
            i += n+1;
        }
    }
    return res;
};

链表

单链表

1. 定义

struct Node{
    int data;
    Node* next;
};

2. 头插法建立单链表

LinkList CreateList1(LinkList &L){
    //从表尾到表头逆向建立单链表，每次均在头结点之后插入元素
    LNode *s;int x;
    L=(LinkList)malloc(sizeof(LNode));//创建头结点
    L->next= NULL;//初始为空链表
    scanf("%d",x);
    while (x!=9999) {//创建新结点
        s=(LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
} 
时间复杂度：O(n)

3. 尾插法建立单链表

LinkList CreateList2(LinkList &L){
    //从表尾到表头逆向建立单链表，每次均在头结点之后插入元素
    int x;
    L=(LinkList)malloc(sizeof(LNode));//创建头结点
    LNode *s,*r=L;
    scanf("%d",x);
    while (x!=9999) {//创建新结点
        s=(LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next=s;
        r=s;//r指向新的表尾结点
        scanf("%d",&x);
    }
    r->next=NUll;
    return L;
}

4. 按序号查找表结点值

LNode *GetElem(LinkList L,int i){
    int j=1;
    LNode *p=L->next;
    if(i==0)return L;
    if (i<1)return NUll;
    while (p&&j<i) {
        p=p->next;
        j++;
    }
    return p;
}

单链表的建立：头插法和尾插法。头插法常用在将一个已存在的链表逆序。
单链表的插入、删除：O(n),读取的时间复杂度也是O(n).
双链表的插入：
双链表的删除：

在O(1)时间删除链表节点（13）

思想：把下一个结点的内容复制到需要删除的结点上覆盖原有的内容，再把下一个结点删除，就相当于把当前需要删除的结点删除了,不是尾结点。

//O(1)时间删除链表节点，从无头单链表中删除节点
void deleteRandomNode(Node *cur)
{
    assert(cur != NULL);
    assert(cur->next != NULL);    //不能是尾节点
    Node* pNext = cur->next;
    cur->data = pNext->data;
    cur->next = pNext->next;
    delete pNext;
}

单链表的逆转（16）

输入一个单向链表，输出逆序反转后的链表的头结点。
链表的转置是一个很常见、很基础的数据结构题了，非递归的算法很简单，用三个临时指针 pre、head、next 在链表上循环一遍即可。递归算法也是比较简单的，但是如果思路不清晰估计一时半会儿也写不出来吧。
非递归:

Node* reverseByLoop(Node *head)
{	
	if(head == NULL||head->next==NULL) return head;
	Node *pre = NULL;
	Node *next = NULL;
	while(head!=NULL){
		next = head->next;
		
		head->next = pre;
		pre = head;
		head = next;
	}
	return pre;
}

递归：

Node* reverseByRecursion(Node *head)
{
	if(head == NULL || head->next == NULL) return head;
	Node *newHead = reverseByRecursion(head->next);
	
	head->next->next = head;
	head->next = NULL;
	
	return newHead;
}

判断链表是否有环（快慢指针），若有环,找出环的入口结点（剑指offer的第56）

题目描述：输入一个单向链表，判断链表是否有环？

分析：通过两个指针，分别从链表的头节点出发，一个每次向后移动一步，另一个移动两步，两个指针移动速度不一样，如果存在环，那么两个指针一定会在环里相遇。

//判断单链表是否存在环,参数circleNode是环内节点，后面的题目会用到
bool hasCircle(Node *head,Node *&circleNode)
{
    Node *slow,*fast;
    slow = fast = head;
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            circleNode = fast;
            return true;
        }
    }

    return false;
}

如果链表存在环，如何找到环的入口点？

按照 p2 每次两步，p1 每次一步的方式走，发现 p2 和 p1 重合，确定了单向链表有环路了。接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当 p1 和 p2 再次相遇的时候，就是环路的入口了。

为什么？：假定起点到环入口点的距离为 a，p1 和 p2 的相交点M与环入口点的距离为b，环路的周长为L，当 p1 和 p2 第一次相遇的时候，假定 p1 走了 n 步。那么有：

p1走的路径： a+b ＝ n；
p2走的路径： a+b+kL = 2n； p2 比 p1 多走了k圈环路，总路程是p1的2倍

根据上述公式可以得到 k*L=a+b=n显然，如果从相遇点M开始，p1 再走 n 步的话，还可以再回到相遇点，同时p2从头开始走的话，经过n步，也会达到相遇点M。

显然在这个步骤当中 p1 和 p2 只有前 a 步走的路径不同，所以当 p1 和 p2 再次重合的时候，必然是在链表的环路入口点上。

//找到环的入口点
Node* findLoopPort(Node *head)
{
//如果head为空，或者为单结点，则不存在环
if(head == NULL || head->next == NULL) return NULL;

Node *slow,*fast;
slow = fast = head;

//先判断是否存在环
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
break;
}

if(fast != slow) return NULL; //不存在环

fast = head; //快指针从头开始走，步长变为1
while(fast != slow) //两者相遇即为入口点
{
fast = fast->next;
slow = slow->next;
}

return fast;
}

判断两个链表是否相交,两链表相交的第一个公共节点

给出两个单向链表的头指针（如下图所示）

比如h1、h2，判断这两个链表是否相交。这里为了简化问题，我们假设两个链表均不带环。

思想一：那么，我们只要判断两个链表的尾指针是否相等。相等，则链表相交；否则，链表不相交。
所以，先遍历第一个链表，记住最后一个节点。然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则，不相交。时间复杂度，它为O((Length(h1) + Length(h2))，而且只用了一个额外的指针来存储最后一个节点。这个方法时间复杂度为线性O(N)，空间复杂度为O(1)

思想二：计算两个链表的长度 L1 , L2，分别用两个指针 p1 , p2 指向两个链表的头，然后将较长链表的 p1（假设为 p1）向后移动L2 - L1个节点，然后再同时向后移动p1 , p2，直到 p1 = p2。相遇的点就是相交的第一个节点。

//求两链表相交的第一个公共节点
Node* findIntersectNode(Node *h1,Node *h2)
{
int len1 = listLength(h1); //求链表长度
int len2 = listLength(h2);
//对齐两个链表
if(len1 > len2)
{
for(int i=0;i<len1-len2;i++)
h1=h1->next;
}
else
{
for(int i=0;i<len2-len1;i++)
h2=h2->next;
}

while(h1 != NULL)
{
if(h1 == h2)
return h1;
h1 = h1->next;
h2 = h2->next;
}
return NULL;
}

链表中倒数第 k 个节点（15）

设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，然后 p1 向前走 k-1 步，这样 p1 和 p2 之间就间隔 k 个节点，最后 p1 和 p2 同时向前移动，直至 p2 走到链表末尾。当第一个指针到达链表的结尾的时候，第二个指针刚好是倒数第K个结点。

//倒数第k个节点
Node* theKthNode(Node *head,int k)
{
    if(k < 0) return NULL;    //异常判断

    Node *slow,*fast;
    slow = fast = head;
    int i = k;
    for(;i>0 && fast!=NULL;i--)
    {
        fast = fast->next;
    }

    if(i > 0)    return NULL;    //考虑k大于链表长度的case

    while(fast != NULL)
    {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

两个有序链表合并(17)

比较两个头结点的值，得到两个链表中值较小的头结点并把它链接到可以合并的链表之后，两个链表剩余的结点依然是排序的，递归。
当一个头结点是空，第一个链表是空链表，合并后返回的就是第二个链表。

复杂链表的复制(26)

思想1：用空间换时间
第一步：复制原始链表上的每个结点N创建N‘，然后把这些创建出来的结点用m_pNext连接起来。同时我们把<N,N’>的配对信息放到一个哈希表中。
第二步：设置复制链表上每个结点的m_pSibling.如果在原始链表中结点N的m_pSibling指向结点S.那么在复制链表中，N’指向S’，有了哈希表，我们就可以在O(1)的时间根据S找到S‘。

思想2：复制原始链表上的每个结点N创建N‘，把N’链接在N的后面。
把这个长链表拆分成两个链表，奇数位置上的结点组成原始链表，偶数位置上的结点组成复制出来的链表。

删除链表中重复节点(57)

排序链表中，如何删除重复的结点？
思想：第一步;确定删除函数的参数，当然这个函数需要输入待删除链表的头结点。头结点可能与后面的结点重复，也就是说头结点也可能被删除，因此删除函数应该声明为void deleteDuplication(ListNode **pHead)而不是void deleteDuplication(ListNode *pHead);
第二步;从头遍历整个链表，如果当前结点的值和下一个结点的值相同，那么它们就是重复结点，都可以被删除。为了保证不断开，我们要把当前结点的前一个结点和后面值比当前结点的值要大的结点相连。

求链表的中间节点

题目描述：求链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。

分析：此题的解决思路和第3题「求链表的倒数第 k 个节点」很相似。可以先求链表的长度，然后计算出中间节点所在链表顺序的位置。但是如果要求只能扫描一遍链表，如何解决呢？最高效的解法和第3题一样，通过两个指针来完成。用两个指针从链表头节点开始，一个指针每次向后移动两步，一个每次移动一步，直到快指针移到到尾节点，那么慢指针即是所求。

//求链表的中间节点
Node* theMiddleNode(Node *head)
{
    if(head == NULL)
        return NULL;
    Node *slow,*fast;
    slow = fast = head;
    //如果要求在链表长度为偶数的情况下，返回中间两个节点的第一个，可以用下面的循环条件
    //while(fast && fast->next != NULL && fast->next->next != NULL)
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

栈与队列

顺序栈

1. 初始化
   void InitStack(&S){
   s.top=-1;//将栈顶指针置为空
   }
2. 判断栈空
   bool empty(S){
   if (s.top==-1) return true;//栈空
   else return false;
   }
3. 进栈
   bool push(x){
   if (S.top==MaxSize-1) return false;//栈满，报错
   S.data[++S.top]=x;//指针先加1，再入栈
   return true;
   }
4. 出栈
   bool pop(x){
   if (S.top==-1) return false;//栈空，报错
   x=S.data[S.top–];//先出栈，指针再减1
   return true;
   }
5. 读栈顶元素
   void GetTop(x){
   if (S.top==-1)return false;//栈空，报错
   x= S.data[S.top];//x记录栈顶元素
   return false;
   }

用两个栈实现队列(7)

用两个栈，当进队列的时候向一个栈中push进去，当出队列的时候，把元素弹出到栈2，然后在pop，顺序一样。
【扩展】用两个队列实现栈

实现一个栈，可以用常数级时间找出栈中的最小值

判断栈的压栈、弹栈序列是否合法（剑指offer 第 22 题）

树

【3】根据中序和后序遍历结果重建二叉树、
【3】根据中序和前序遍历结果重建二叉树
【2】翻转二叉树
【2】从上往下打印二叉树 (BFS 的思想)
【3】判断某个数组是不是二叉树的后序遍历结果 (剑指 offer 第 24 题)
【3】二叉树中和为某个值的路径
【3*】二叉树中某个节点的下一个节点 (强烈推荐准备一下，剑指 offer 第 58 题)

查找

位运算

给一个十进制数字，求它的二进制表示中，有多少个 1 （10）

(n &= n - 1)
把一个整数减去1，再和原整数做与运算，会把该整数最右边的1变成0.那么一个整数的二进制中表示中有多少个1，就可以进行多少次这样的操作。

给一个数组，所有数字都出现了偶数次，只有一个出现了一次，找出这个数

从头到尾依次异或数组中的每一个数字，最终得到的结果就是这个数字。

给一个数组，所有数组都出现了偶数次，只有两个数字出现了一次，找出这两个数

从头到尾依次异或数组中的每一个数字，最终得到的结果就是这两个数字异或的结果，，在结果数字中找到第一个为1的位的位置，记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组。重复上面过程。
数组：{2，4，3，6，3，2，5，5}最终得到结果就是4和6的异或结果，0100^0110=0010,然后根据第二位是不是1分为2个数字，第一个子数组{2，3，6，3，2}中所有数字的倒数第二位都是1，而第二个子数组{4，5，5}中所有数字的倒数第二位都是0、分别异或，就得到了6和4.

不用加减乘除做加法

【补充】不用中间变量,用两种方法交换A和B的值

或者使用位运算符异或
A = A^B;
B = A^B;
A = A^B;

动态规划

一种用来解决最优化问题的思想。动态规划将一个复杂的问题分解成若干个简单的子问题，通过综合子问题的求解结果来得到原问题的解。
本质:通过记录曾经计算过的内容，来避免重复计算。
1>递归
斐波那契数列

2>递推
数塔DP问题：将一些数字排成数塔形状，其中第一层有一个数字，第二层有两个数字。。。。。第N层有N个数字，形状要从第一层走到第N层，每次只能走向下一层连接的两个数字中的一个，问最后将路径上所以数字相加后得到的和最大是多少？

最大连续子序列和(31)

题目：输入一个数字序列a1,a2,求i,j（1<=i<=j<=n）,使得ai+…….aj最大，输出最大和。

思想：扫描数组，从左到右记录当前子序列的和 ThisSum，若返个和不断增加，那么最大子序列的和 MaxSum 也不断增加(不断更新 MaxSum)。如果往前扫描中遇到负数，那么当前子序列的和将会减小。此时 ThisSum 将会小于 MaxSum，当然 MaxSum 也就不断更新。如果 ThisSum 降到 0 时， 说明前面已经扫描的那一段就可以抛弃了，这时将 ThisSum 置为 0。然后，ThisSum 将从后面开始将这个子段进行分析，若有比当前 MaxSum 大的子段，继续更新 MaxSum。这样一趟扫描结果也就出来了。

【扩展】和最接近 0 的子序列：
【扩展】环形数组的最大子序列和:将环形数组首尾拼接成一个 2n 的线型数组(如环形数组 0 1 2， 可以 拼接成 0 1 2 0 1 2)，按1的方法可以找到最大连续子序列和

0-1背包问题

题目：有N件物品，每件物品的重量为W[i],价值为C[i],现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的价值最大，其中每种物品都只有一件。

最长不下降子序列

最长公共子序列（LCS）

题目：给定两个字符串A和B，求一个字符串，使得这个字符串是A和B的最长公共部分

最长回文字串

连续子数组的最大和

实现简单的正则表达式匹配

操作系统

进程和线程

进程和线程的区别？

1. 调度：进程：拥有资源的基本单位。线程：独立调度的基本单位。在同一进程中，线程的切换不会引起进程切换。在不同进程中进行线程切换，则会引起进程切换。线程可以共享其隶属进程的系统资源。
2. 并发性：进程和线程都可以并发执行，从而使操作系统具有更好的并发性，大大提高了系统吞吐量
3. 系统开销：创建和撤销进程时，系统都要为之分配或回收资源，如：内存空间、I/O设备。线程只需要保存和设置少量寄存器内容，系统所付出的开销远大于创建或撤销线程的开销。
4. 地址空间和其他资源：进程的地址空间之间相互独立，同一进程的各线程间共享进程的资源，某进程内的线程对于其他进程不可见。
5. 通信方面：进程间通信需要借助操作系统，而线程间可以直接读/写进程数据段（如：全局变量）来进行通信。

Linux系统进程间的通信：管道(Pipe)、信号（signal）、消息队列（Message）、共享内存、信号量、套接口。
Linux线程间的通信：互斥体（互斥量）、信号量、条件变量。
Windows进程间通信：管道(Pipe)、消息队列（Message）、共享内存、信号量、套接口。
Windows线程间通信：临界区(Critical Section)、互斥量（Mutex）、信号量（信号灯）、事件（Event）

5. 操作系统中的进程的存储结构；
   一个正在运行着的进程在内存空间中的内存结构有：代码区、静态数据区、未初始化数据区、堆区和栈区5个部分.

调度算法

调度的基本准则：CPU利用率、系统吞吐量（单位时间内CPU完成作业的数量）、周转时间（作业完成时间-作业到达时间）、等待时间、响应时间。
典型的调度算法：先来先服务（FCFS）、短作业优先（SJF）、优先级调度算法、高响应比优先、时间片轮转、多级反馈队列调度算法。（短作业优先的平均等待时间、平均周转时间最少）（高响应比优先既有利于短作业又兼顾长作业）。

死锁

死锁产生的原因：

1. 系统资源的竞争
2. 进程推进顺序非法

死锁产生的必要条件：
互斥条件、不剥夺条件、请求和保持条件、循环等待条件

死锁的处理
死锁的预防：破坏四个必要条件中的一个
避免死锁：银行家算法
死锁的检测：资源分配图
死锁的解除：资源剥夺法、撤销进程法、进程回退法。

内存管理

内存分配管理方式

连续分配方式：单一连续分配、固定分区分配、动态分区分配

非连续分配方式：分页存储管理方式（基本分页存储和请求分页存储管理方式）、分段存储管理方式

虚拟内存管理

虚拟存储器：并不存在，只是由于系统提供了部分装入、请求调入和置换功能后（对用户完全透明），给用户感觉是好像存在一个比实际物理内存大的多的存储器。
实现方式：

1. 请求分页
2. 请求分段
3. 请求段页式

请求分页管理方式

常见的置换算法：最佳置换算法、先进先出页面置换算法、最近最久未使用置换算法（LRU）。

最佳置换算法： 所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面。

先进先出页面置换算法：淘汰最早进入内存的页面

最近最久未使用置换算法：淘汰最近最长时间未访问的页面

内存抖动：频繁的换页活动。

11. 文件结构是用哪种数据结构实现的，树还是图，
    答案是B+树；

C++

函数

参数传递

发生函数调用的时候，主调函数把实参的值传送给被调函数的形参，从而实现主调函数向被调函数的数据传送。

C++中的三种传递方法：

• 值传递
• 指针传递
• 引用传递

内联函数

1. 成员函数成为内联函数
   类中成员函数全部默认为内联函数。
   类外定义该成员函数加inline也可成为内联函数

2. 普通函数成为内联函数
   普通函数声明或定义前加inline使其成为内联函数。

函数重载

在同一作用域中，可以有一组具有相同函数名，不同参数列表的函数。这组函数被称为重载函数。

用来命名一组功能相似的函数。

进行函数重载时，要求同名函数在参数个数上不同，或者参数类型上不同。

函数模板与泛型

泛型编程：以独立于任何特定类型的方式编写代码。依赖于某种形式的多态性。标准库用独立于类型的方式定义每个容器、迭代器和算法是泛型编程的例子。

模板是泛型编程的基础。模板是创建类或函数的蓝图或公式。以template.

【宏定义和内联函数的区别】宏定义是在预处理阶段进行代码替换，内联函数是在编译阶段进行代码替换。宏定义没有类型检查，内联函数有类型检查。

类

类成员

成员函数：形参this初始化为调用函数的对象的地址

构造函数：是特殊的成员函数，与类同名，没有返回类型。一个类可以有多个构造函数，每个构造函数必须有与其他构造函数不同数目或类型的形参。

拷贝构造函数：只要单个形参，而且该形参是对本类类型对象的引用（常用const修饰）由编译器隐式调用。
可用于：

• 根据另一个同类型的对象初始化一个对象
• 复制一个对象，将她作为实参传给一个函数或从函数返回时复制一个对象。
• 初始化顺序容器中的元素
• 根据元素初始化式列表初始化数组元素

析构函数：当对象超出作用域或动态分配的对象被删除时，将自动应用析构函数，可以用来释放对象构造时活在对象的生命期中所获取的资源。

构造函数不能被定义为虚函数，析构函数可以被定义为虚函数

成员函数的重载、覆盖于隐藏

面向对象编程

继承

虚函数多态

多态性：一个接口，多个方法。函数重载就是简单的多态，一个函数名(调用接口)对应着几个不同的函数原型(方法)

静态多态：函数重载和操作符重载

动态多态：虚函数

虚函数：在成员函数原型前加virtual。如果基类的成员函数为虚函数，它在所有派生类中也保持虚函数。

哪些函数不能为虚函数：普通函数、静态成员函数、构造函数、友元函数。

虚函数表指针(vptr):

• 每一个类产生出一堆指向virtual functions的指针，放在表格中，这个表成为虚函数表
• 每个对象被添加了一个指针，指向相关的virtual table。这个指针被称为虚函数表指针。

虚基类表指针(bptr)
在虚拟继承基类的子类中，子类会增加某种形式的指针，或者指向虚基类子对象，或者指向一个相关的表格；表格中存放的不是虚基类子对象的地址，就是其偏移量，这个指针成为虚基类表指针。

纯虚函数

• 是一种特殊的虚函数。凡是含有纯虚函数的类称为抽象类。这种类不能声明对象，只是作为基类为派生类服务。除非在派生类中完全实现基类中的所有纯虚函数，否则，派生类也是抽象类，不能实例化对象。
• 只定义了protected型构造函数的类也是抽象类，没有提供public构造函数，无论是在外部还是在派生类中都不能创建该类的对象，但可以由派生出新的类。

动态运行时类型标识与显式转换

大数据

100亿个整数，如何找到中位数

首先数没有这么多，内存能放下，用quickSort的思想，找第K大的数放在它的右边。
现在内存放不下，用什么？

1. 用二分法。整数的范围就是[-2^32,2^32-1]。有了范围后就对这个范围进行二分，然后找多少个数小于Mid，多少数大于Mid，然后递归。
2. 分桶法。化大为小，把所有的数划分到各个小区间[-2^32,-2^16],[-2^16,0]……..。把每个数映射到对应的区间里，对每个区间中数的个数进行计数。数一遍各个区间，看看中位数落在那个区间。若够小，使用基于内存的算法，否则继续划分。