腾讯篇
1.求一个论坛的在线人数，假设有一个论坛，其注册ID有两亿个，每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间，要求写一个算法统计一天中论坛的用户在线分布，取样粒度为秒
一天总共有3600*24=86400秒。
定义一个长度为86400的整数数组intdelta[86400]，每个整数对应这一秒的人数变化值，可能为正也可能为负。开始时将数组元素都初始化为0。
然后依次读入每个用户的登录时间和退出时间，将与登录时间对应的整数值加1，将与退出时间对应的整数值减1。
这样处理一遍后数组中存储了每秒中的人数变化情况。
定义另外一个长度为86400的整数数组intonline_num[86400]，每个整数对应这一秒的论坛在线人数。
假设一天开始时论坛在线人数为0，则第1秒的人数online_num[0]=delta[0]。第n+1秒的人数online_num[n]=online_num[n-1]+delta[n]。
这样我们就获得了一天中任意时间的在线人数。
2.有序链表合并
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) {
return l2;
} else if (l2 == NULL) {
return l1;
} else {
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
}
};
3.牛妹有剪刀，石头，布（以0，1，2表示）三种卡片无限张。现在牛妹拿出n张排成一排。然后你也拿出n张牌一一对应比对。若赢一局则获得一分。若你想得k分。现在输入n，k和牛妹的n张牌分别是什么，你想要恰好得k分，有多少种方法
很容易想到答案跟牛妹每一张牌是什么没有关系。没一张牌只需要考虑赢、不赢。
赢k分，那就是从n张牌中拿出k张赢，
其他输，所以组合数c(n,k).对于赢了答k张，只有一种方法，但是对于剩下的n-k张，都有平局和输掉两种情况，所以是2的n-k次方。
两者相乘就是答案。
结果很大对mod=1e9+7取余，用到同余定理。
求2的幂直接暴力求（当然也可以快速幂）
求组合数的时候用到除法，
又要取余，所以用到逆元。所以用到逆元公式（当然还有其他求法）:pow(x,mod-2)%mod;
但是mod=1e9+7，所以暴力求幂会超时，
方法是用快速求幂法压缩时间（快速幂就不贴代码了）
typedef long long ll;
ll fast(ll a,ll n) // 快速幂 pow(a,n)
ll inv(ll x, ll mod)
{
return fast(x,mod-2);
}
4.TCP三次握手的过程, accept发生在三次握手哪个阶段？
accept发生在三次握手之后。
第一次握手:客户端发送syn包(syn=j)到服务器。
第二次握手:服务器收到syn包,必须确认客户的sY(ack=j+1),同时自己也发送一个ASK包(ask=k)。
第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包ACK(ack=k+1)。
握手完成后,客户端和服务器就建立了tcp连接。这时可以调用 accept函数获得此连接
5.用UDP协议道讯时怎样得知目标机是否获得了数据包 ?
可以在每个数据包中插入一个唯一的ID,比如 timestamp或者递增的int。
发送方在发送数据时将此ID和发送时间记录在本地。
接收方在收到数据后将ID再发给发送方作为回应。
发送方如果收到回应,则知道接收方已经收到相应的数据包;如果在指定时间内没有收到回应,则数据包可能丢失,需要重复上面的过程重新发送一次,直到确定对方收到。
6.从10G个数中找到中数在一个文件中有10G个整数,乱序排列,要求找出中位数。内存限制为2G
不妨假设10G个整数是64bit的。
2G内存可以存放256M个64bit整数。
我们可以将64bit的整数空间平均分成256M个取值范围,用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后,我们便知道中数在那个范围内出现,以及这个范围内总共出现了多少个整数。
如果中数所在范围出现的整数比较少,我们就可以对这个范围内的整数进行排序,找到中数。如果这个范围还可以采用同样的方法将此范围再次分成多个更小的范围(256M-228,所以最多需要3次就可以将此范围缩小到1,也就找到了中数)
7.找出1到10w中没有出现的两个数字有1到10w这10w个数,去除2个并打乱次序,如何找出那两个数?
申请10w个bit的空间,每个bit代表一个数字是否出现过。
开始时将这10个bit都初始化为0,表示所有数字都没有出现过。
然后依次读入已经打乱循序的数字,并将对应的bit设为1。
处理完所有数字后,根据为0的bi得出没有出现的数字。
首先计算1到10w的和,平方和。
然后计算给定数字的和,平方和。
两次的到的数字相减,可以得到这两个数字的和,平方和。
所以我们有
x + y = n
x^2 + y^2 = m
解方程可以得到x和y的值。
8.如何输出源文件的标题和目前执行行的行数?
printf("The file name:%dn", __FILE__);
printf("The current line No: %d\n", __LINE__);
ANSI C标准预定义宏;
__LINE__
__FILE__
__DATE__
__TIME__
__STDC__ 当要求程序严格遵循ANSC标准时该标识符被赋值为1
__cplusplus__ 当编写C+程序时该标识符被定义
9.腾讯服务器每秒有2W个QQ号同时上线,找出5min内重新登入的qq号并打印出来
如果空间足够大,可以定义一个大的数组a[qq号],初始为零然后.这个qq号登陆了
就a[qq号]++
最后统计大于等于2的QQ号
这个用空间来代替时间
不成熟的想法
2w x 300s
所以用6000.000个桶。刪除超时的算法后面说,所以平均桶的大小是1
假设qq号码一共有10^10个,所以每个桶装的q号码是10^10/(6*10~6)个,
这个是插入时候的最坏效率(插入同个桶的时候是顺序查找插入位置的)
qq的节点结构和上面大家讨论的基本一样,增加一个指针指
向输出列表,后面说
struct QQstruct {
num_type qqnum,
timestamp last_logon_time,
QQstruct *pre,
QQstruct *next,
OutPutlist *out //用于free节点的时候,顺便更新下输出列表
}
另外增加两个指针列表
第一个大小300的循环链表,自带一个指向 QQStruct的域,循环存300秒内的qq指针。
时间一过就fee掉,所以保证所有桶占用的空闾在2wX30以内.
第二个是输出列表,就是存放题目需要输出的节点。
如果登陆的用户,5分钟内完全没有重复的话,每秒free2w个节点
不过在free的时候,要判断一下时间是不是真的超时,因为把节点入桶的时候,遇到重复的,
会更新一下最后登陆的时间。当然啦,这个时候,要把这个q号码放到需要输出的列表里面
10.给一个奇数阶N幻方,填入数字1,2,3.N^N,使得橫竖斜方向上的和都相同
#inc1ude<iostream>
#include<iomanip>
#include<cmath>
usingnamespace std;
int main()
{
int n;
cin>>n;
int i;
int **Matr = new int *[n]; //动态分配二维数组
for(i=0;i<n;++i)
Matr[i]=new int[n]: //动态分配二维
数组
//j=n/2代表首行中间数作为起点,即1所在位置
int j=n/2,num=1: //初始值
i=0;
while(num!=n*n+1) {
//往右上角延升, 若超出则用%转移到左下角
Matr [(i%n+n)%n][(j%n+n)%n]=num;
//斜行的长度和n是相等的,超出则转至下一写信.
if (num%n==0) {
i++;
} else {
i--;
j++;
}
num++;
}
for (i=0;i<n;i++) {
for (j=0;j<n;++j) {
cout << setw((int)log10(n*n)+4)<<Matr[i][j]; //格式控制
cout <<endl<<endl;//格式控制
}
}
for (i=0; i<n; ++i) {
delete [] Matr[i];
}
return 1;
}
阿里篇
1.设计高并发系统数据库层面该如何设计？ 数据库锁有哪些类型？如何实现？
1. 分库分表：同样量的数据平均存储在不同数据库相同表（或不同表）中，减轻单表压力，如果还是很大，就可以每个库在分多张表，根据hash取值或者其他逻辑判断将数据存储在哪张表中
2. 读写分离：数据库原本就有主从数据库之分，查询在从服务器，增删改在主服务器，
3. 归档和操作表区分：建一张归档表，将历史数据放入，需要操作的表数据单独存储
4. 索引啊之类的创建，对于数据量很大，百万级别以上的单表，如果增删改操作不频繁的话， 可以创建bitMap索引，速度要快得多
1. 共享锁：要等第一个人操作完，释放锁，才能操作
2. 更新锁：解决死锁，别人可以读，但不能操作
3. 排他锁：读写都被禁用
4. 意向锁（xlock）：对表中部分数据加锁，查询时，可以跳过
5. 计划锁：操作时，别的表连接不了这张表，
2.数据库事务有哪些？
原子性： 所有操作要么全部成功，要么全部失败
一致性： 例如转账，一个事务执行前和执行后必须一致
隔离性： 防止脏读， 重复读问题
持久性： 永久性提交数据库
3.Oracle常用函数有哪些？
Concat: 字符串拼接， 或者 ||
MConcat: 字符串拼接， 或者 ||
Instr: 指定字符串位置
Length: 长度
Trim: 去空格
Lower: 小写
Upper:大写
Nvl: 判断空
Replace: 替换
Substr: 截取
Floor: 向下取整
To_number:
To_char:
To_date:
Decode: 判断函数等等
4.Sql中哪些情况可能不会走索引？
1. 查询谓词没有使用索引的主要边界,换句话说就是select *，可能会导致不走索引
2. 单键值的b树索引列上存在null值，导致COUNT(*)不能走索引。索引列存在空值
3. 索引列上有函数运算，导致不走索引
4. 隐式类型转换导致不走索引。
5. 表的数据库小或者需要选择大部分数据，不走索引
6. ！=或者<>(不等于），可能导致不走索引
7. 表字段的属性导致不走索引，字符型的索引列会导致优化器认为需要扫描索引大部分数据且聚簇因子很大，最终导致弃用索引扫描而改用全表扫描方式，
8. 使用like, in 等， 可能导致不走索引
5.NIO和IO的区别？
第一点，NIO少了1次从内核空间到用户空间的拷贝。
ByteBuffer.allocateDirect()分配的内存使用的是本机内存而不是Java堆上的内存，和网络或者磁盘交互都在操作系统的内核空间中发生。allocateDirect()的区别在于这块内存不由java堆管理, 但仍然在同一用户进程内。
第二点，NIO以块处理数据，IO以流处理数据
第三点，非阻塞，NIO1个线程可以管理多个输入输出通道
6.Redis内存数据上升到一定大小会执行数据淘汰策略，Redis提供了哪6种数据淘汰策略?
LRU：从已设置过期时间的数据集合中挑选最近最少使用的数据淘汰
random：从已设置过期时间的数据中挑选任意数据淘汰
ttl：从已设置过期时间的数据集合中挑选将要过期的数据淘汰。
notenvision：禁止驱逐数据
如mysql中有2千万数据，redis只存储20万的热门数据。LRU或者TTL都满足热点数据读取较多，不太可能超时特点。
redis特点：速度块，O(1)，丰富的数据类型，支持事物原子性，可用于缓存，比memecache速度块，可以持久化数据。
常见问题和解决：Master最好不做持久化如RDB快照和AOF日志文件；如果数据比较重要，某分slave开启AOF备份数据，策略为每秒1次，为了主从复制速度及稳定，MS主从在同一局域网内；主从复制不要用图状结构，用单向链表更为稳定 M-S-S-S-S。。。。；redis过期采用懒汉+定期，懒汉即get/set时候检查key是否过期，过期则删除key，定期遍历每个DB，检查制定个数个key；结合服务器性能调节并发情况。
过期淘汰，数据写入redis会附带1个有效时间，这个有效时间内该数据被认为是正确的并不关心真实情况，例如对支付等业务采用版本号实现，redis中每一份数据都维持1个版本号，DB中也维持1份，只有当redis的与DB中的版本一致时，才会认为redis为有效的，不过仍然每次都要访问DB，只需要查询version版本字段即可。
7.请描述MyISM和InnoDB?
MyISM采用表级锁，对Myism表读不会阻塞读，会阻塞同表写，对Myism写则会阻塞读和写，即一个线程获得1个表的写锁后，只有持有锁的线程可以对表更新操作，其他线程的读和写都会等待。
InnoDB，采用行级锁，支持事务，例如只对a列加索引，如果update ...where a=1 and b=2其实也会锁整个表， select 使用共享锁，update insert delete采用排它锁，commit会把锁取消，当然select by id for update也可以制定排它锁。
8.讲一下NIO和网络传输.
NIO Reactor反应器模式，例如汽车是乘客访问的实体reactor，乘客上车后到售票员处Acceptor登记，之后乘客 便可休息睡觉了，到达乘客目的地后，售票员Aceptor将其唤醒即可。持久TCP长链接每个client和server之间有存在一 个持久连接，当CCU（用户并发数量）上升，阻塞server无法为每个连接运行1个线程，自己开发1个二进制协议，将 message压缩至3-6倍，传输双向且消息频率高，假设server链接了2000个client，每个client平均每分钟传输1-10个 message，1个messaged的大小为几百字节/几千字节，而server也要向client广播其他玩家的当前信息，需要高速处 理消息的能力。Buffer，网络字节存放传输的地方，从channel中读写，从buffer作为中间存储格式，channel是网络连 接与buffer间数据通道，像之前的socket的stream。
9.ZooKeeper分布式是如何做到高可用?
ZooKeeper 运行期间，集群中至少有过半的机器保存了最新数据。集群超过半数的机器能够正常工作，集群就能够对外提供服务。
zookeeper可以选出N台机器作主机，它可以实现M:N的备份；keepalive只能选出1台机器作主机，所以keepalive只能实现M:1的备份。
通常有以下两种部署方案：双机房部署（一个稳定性更好、设备更可靠的机房，这个机房就是主要机房，而另外一个机房则更加廉价一些，例如，对于一个由 7 台机器组成的 ZooKeeper 集群，通常在主要机房中部署 4 台机器，剩下的 3 台机器部署到另外一个机房中）；三机房部署（无论哪个机房发生了故障，剩下两个机房的机器数量都超过半数。在三个机房中都部署若干个机器来组成一个 ZooKeeper 集群。假设机器总数为 N，各机房机器数：N1 = (N-1)/2 ，N2=1~(N-N1)/2 ，N3 = N - N1 - N2 ）。
水平扩容就是向集群中添加更多机器，Zookeeper2种方式（不完美），一种是集群整体重启，另外一种是逐台进行服务器的重启。
10.Https工作流程？
a、客户端发送自己支持的加密规则给服务器，代表告诉服务器要进行连接了
b、服务器从中选出一套加密算法和hash算法以及自己的身份信息(地址等)以证书的形式发送给浏览器，证书中包含服务器信息，加密公钥，证书的办法机构
c、客户端收到网站的证书之后要做下面的事情：
c1、验证证书的合法性
c2、如果验证通过证书，浏览器会生成一串随机数作为密钥K，并用证书中的公钥进行加密
c3、用约定好的hash算法计算握手消息，然后用生成的密钥K进行加密，然后一起发送给服务器
d、服务器接收到客户端传送来的信息，要求下面的事情：
d1、用私钥解析出密码，用密码解析握手消息，验证hash值是否和浏览器发来的一致
d2、使用密钥加密消息，回送
如果计算法hash值一致，握手成功
百度篇
1.输入 www.baidu.com 在浏览器的完整过程，越详细越好。
浏览器获取输入的域名www.baidu.com
浏览器向域名系统DNS请求解析www.baidu.com的IP地址
DNS解析出百度服务器的IP地址
浏览器与服务器建立TCP连接（默认端口80）
浏览器发出HTTP请求，请求百度首页
服务器通过HTTP请求把首页文件发给浏览器
TCP连接释放
浏览器解析首页文件，展示web界面
2.快速排序的思想、时间复杂度、实现以及优化方法?
快速排序的三个步骤
(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 "基准"（pivot）；
(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大；
(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
基准的选择：
对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。
即：同一数组，时间复杂度最小的是每次选取的基准都可以将序列分为两个等长的；时间复杂度最大的是每次选择的基准都是当前序列的最大或最小元素；
快排代码实现：
我们一般选择序列的第一个作为基数，那么快排代码如下：
void quicksort(vector<int> &v,int left, int right)
{
if(left < right)//false则递归结束
{
int key=v[left];//基数赋值
int low = left;
int high = right;
while(low < high) //当low=high时，表示一轮分割结束
{
while(low < high && v[high] >= key)//v[low]为基数，从后向前与基数比较
{
high--;
}
swap(v[low],v[high]);
while(low < high && v[low] <= key)//v[high]为基数，从前向后与基数比较
{
low++;
}
swap(v[low],v[high]);
}
//分割后，对每一分段重复上述操作
quicksort(v,left,low-1);
quicksort(v,low+1,right);
}
}
注：上述数组或序列v必须是引用类型的形参，因为后续快排结果需要直接反映在原序列中；
优化：
上述快排的基数是序列的第一个元素，这样的对于有序序列，快排时间复杂度会达到最差的o(n^2)。所以，优化方向就是合理的选择基数。
常见的做法“三数取中”法（序列太短还要结合其他排序法，如插入排序、选择排序等），如下：
①当序列区间长度小于 7 时，采用插入排序；
②当序列区间长度小于 40 时，将区间分成2段，得到左端点、右端点和中点，我们对这三个点取中数作为基数；
③当序列区间大于等于 40 时，将区间分成 8 段，得到左三点、中三点和右三点，分别再得到左三点中的中数、中三点中的中数和右三点中的中数，再将得到的三个中数取中数，然后将该值作为基数。
具体代码只是在上一份的代码中将“基数赋值”改为①②③对应的代码即可：
int key=v[left];//基数赋值
if (right-left+1<=7) {
insertion_sort(v,left,right);//插入排序
return;
}else if(right-left+1<=8){
key=SelectPivotOfThree(v,left,right);//三个取中
}else{
//三组三个取中，再三个取中（使用4次SelectPivotOfThree，此处不具体展示）
}
需要调用的函数：
void insertion_sort(vector<int> &unsorted,int left, int right) //插入排序算法
{
for (int i = left+1; i <= right; i++)
{
if (unsorted[i - 1] > unsorted[i])
{
int temp = unsorted[i];
int j = i;
while (j > left && unsorted[j - 1] > temp)
{
unsorted[j] = unsorted[j - 1];
j--;
}
unsorted[j] = temp;
}
}
}
int SelectPivotOfThree(vector<int> &arr,int low,int high)
//三数取中，同时将中值移到序列第一位
{
int mid = low + (high - low)/2;//计算数组中间的元素的下标
//使用三数取中法选择枢轴
if (arr[mid] > arr[high])//目标: arr[mid] <= arr[high]
{
swap(arr[mid],arr[high]);
}
if (arr[low] > arr[high])//目标: arr[low] <= arr[high]
{
swap(arr[low],arr[high]);
}
if (arr[mid] > arr[low]) //目标: arr[low] >= arr[mid]
{
swap(arr[mid],arr[low]);
}
//此时，arr[mid] <= arr[low] <= arr[high]
return arr[low];
//low的位置上保存这三个位置中间的值
//分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了
}
这里需要注意的有两点：
①插入排序算法实现代码；
②三数取中函数不仅仅要实现取中，还要将中值移到最低位，从而保证原分割函数依然可用。
3.实践中如何优化MySQL?
四条从效果上第一条影响最大，后面越来越小。
① SQL语句及索引的优化
② 数据库表结构的优化
③ 系统配置的优化
④ 硬件的优化
4.如何设计一个高并发的系统?
① 数据库的优化，包括合理的事务隔离级别、SQL语句优化、索引的优化；
② 使用缓存，尽量减少数据库 IO；
③ 分布式数据库、分布式缓存；
④ 服务器的负载均衡；
5.overload、override、overwrite的介绍
（1）overload（重载），即函数重载：
①在同一个类中；
②函数名字相同；
③函数参数不同（类型不同、数量不同，两者满足其一即可）；
④不以返回值类型不同作为函数重载的条件。
（2）override（覆盖，子类改写父类的虚函数），用于实现C++中多态：
①分别位于父类和子类中；
②子类改写父类中的virtual方法；
③与父类中的函数原型相同。
（3）overwrite（重写或叫隐藏，子类改写父类的非虚函数，从而屏蔽父类函数）：
①与overload类似，但是范围不同，是子类改写父类；
②与override类似，但是父类中的方法不是虚函数。
6.请描述长连接与短连接.
（1）就是TCP长连接和TCP短连接：
①TCP长连接：TCP长连接指建立连接后保持连接而不断开。若一段时间内没有数据传输，服务器会发送心跳包给客户端，判断客户端是否还在线，叫做TCP长连接中的keep alive。一般步骤：连接→数据传输→保持连接(心跳)→数据传输→保持连接(心跳)→……→关闭连接；
②TCP短连接：指连接建立并传输数据完成后，就断开连接。一般步骤：连接→数据传输→关闭连接；
③使用场景：长连接适合单对单通信且连接数不太多的情况；短连接适合连接数多且经常更换连接对象的；
（2）HTTP是什么连接：
①在HTTP/1.0中，默认使用的是短连接。但从 HTTP/1.1起，默认使用长连接，用以保持连接特性。使用长连接的HTTP协议，会在响应头有加入这行代码：
Connection:keep-alive
注意：此处的keep-alive和上述TCP长连接原理介绍中的keep alive不是一个意思：此处表示告知服务器本http请求是长连接模式，而TCP长连接中的keep alive表示对客户端的保活检测。
②http长连接并不是一直保持连接
http的长连接也不会是永久保持连接，它有一个保持时间如20s（从上一次数据传输完成开始计时），可以在不同的服务器软件（如Apache）中设定这个时间，若超过该时间限制仍然无数据通信传输，服务器就主动关闭该连接。注：实现长连接要客户端和服务端都支持长连接。
③http连接实质：http的长连接/短连接实质上就是TCP的长/短连接。
7.C和C++有什么不同?
从机制上:c是面向过程的(但C也可以编写面向对象的程序)。c++是面向对象的,提供了类。
但是,c++编写面向对象的程序比c容易。
从适用的方向:c适合要求代码体积小的,效率高的场合,如嵌入式;c-适合更上层的复杂的; linux核心
大部分是c写的,因为它是系统软件,效率要求极高从名称上也可以看出,c++比c多了+说明
c++是c的超集;那为什么不叫c+而叫c++呢,是因为c++比C来说扩充的东西太多了,所以就
在c后面放上两个+;于是就成了C++。
C语言是结构化编程语言,C++是面向对象编程语言。LUPA开源社区}n*r2C/M8f
C++侧重于对象而不是过程,侧重于类的设计而不是逻辑设计.
8.死锁产生的条件，以及如何避免死锁，银行家算法，产生死锁后如何解决?
产生死锁的四个必要条件（互请不循）：
（1） 互斥条件：一个资源每次只能被一个进程使用。
（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3） 不剥夺条件：进程已获得的资源，在末使用完之前，不能强行剥夺。
（4） 循环等待条件：若干进程之间形成一种头尾相接的【循环等待资源】关系。
避免死锁：
(1).按同一顺序访问对象。(注：避免出现循环)
(2).避免事务中的用户交互。(注：减少持有资源的时间，较少锁竞争)
(3).保持事务简短并处于一个批处理中。(注：同(2)，减少持有资源的时间)
(4).使用较低的隔离级别。(注：使用较低的隔离级别（例如已提交读）比使用较高的隔离级别（例如可序列化）持有共享锁的时间更短，减少锁竞争)
(5).使用基于行版本控制的隔离级别：
银行家算法
银行家算法是一个避免死锁的著名算法，它是以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
总之：
当一个进程申请使用资源的时候，银行家算法通过【先 试探 分配给该进程资源】，然后【通过安全性算法判断分配后的系统是否处于安全状态】，若不安全则试探分配作废，让该进程继续等待。
当一进程提出资源申请时，银行家算法执行下列步骤以决定是否向其分配资源：
1）检查该进程所需要的资源是否已超过它所宣布的最大值。
2）检查系统当前是否有足够资源满足该进程的请求。
3）系统试探着将资源分配给该进程，得到一个新状态。
4）执行安全性算法，若该新状态是安全的，则分配完成；若新状态是不安全的，则恢复原状态，阻塞该进程。
假设资源P1申请资源，银行家算法先试探的分配给它（当然先要看看当前资源池中的资源数量够不够），【若申请的资源数量小于等于Available，然后接着判断分配给P1后剩余的资源，能不能使进程队列的某个进程执行完毕】，【若没有进程可执行完毕，则系统处于不安全状态】（即此时没有一个进程能够完成并释放资源，随时间推移，系统终将处于死锁状态）。
若有进程可执行完毕，则假设回收已分配给它的资源（剩余资源数量增加），把这个进程标记为可完成，并继续判断队列中的其它进程，若所有进程都可执行完毕，则系统处于安全状态，并根据可完成进程的分配顺序生成安全序列（如{P0，P3，P2，P1}表示将申请后的剩余资源Work先分配给P0–>回收（Work+已分配给P0的A0=Work）–>分配给P3–>回收（Work+A3=Work）–>分配给P2–>······满足所有进程）。
9.将“引用”作为函数参数有哪些特点?
1)传递引用给函数与传递指针的效果是一样的。这时,被调函数的形参就成为原来主调函数中的实参变里或对象的一个别名来使用,所以在被调函数中对形参变里的操作就是对相应的目标对象(在主调函数中)的操作。
2)使用引用传递函数的参数,在内存中并没有产生实参的副本,它是直接对实参操作量传递函数当发生函数调用时,需要给形参分配存储单元是实参变里的副本;如果传递的是对象,还将调用拷贝构造函数。因此,当参数传递的数据较大时,用引用比用一般变量传递参数的效率和所占空间都好。(3)使用指针作为函数的参数虽然也能达到与使用引用的效果,但是,在被调函数中同样要给形参分配存储单元,且需要重复使用指针变里名的形式进行运算,这很容易产生错误且程序的阅读性较差;另一方面,在主调函数的调用点处,必须用变里的地址作为实参。而引用更容易使用，更清晰。
10.二叉树先序遍历（递归与非递归）及C语言实现
二叉树先序遍历的实现思想是：
访问根节点；
访问当前节点的左子树；
若当前节点无左子树，则访问当前节点的右子树；
以图1 为例，采用先序遍历的思想遍历该二叉树的过程为：
访问该二叉树的根节点，找到 1；
访问节点 1 的左子树，找到节点 2；
访问节点 2 的左子树，找到节点 4；
由于访问节点 4 左子树失败，且也没有右子树，因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树，因此现在开始遍历，即访问节点 5；
由于节点 5 无左右子树，因此节点 5 遍历完成，并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1 ，并开始遍历该节点的右子树，即访问节点 3；
访问节点 3 左子树，找到节点 6；
由于节点 6 无左右子树，因此节点 6 遍历完成，回到节点 3 并遍历其右子树，找到节点 7；
节点 7 无左右子树，因此以节点 3 为根节点的子树遍历完成，同时回归节点 1。由于节点 1 的左右子树全部遍历完成，因此整个二叉树遍历完成；
因此，图 1 中二叉树采用先序遍历得到的序列为： 1 2 4 5 3 6 7
递归实现:
二叉树的先序遍历采用的是递归的思想，因此可以递归实现。
#include <stdio.h>
#include <string.h>
#define TElemType int
//构造结点的结构体
typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
*T=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->data=1;
(*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->data=2;
(*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild->data=5;
(*T)->lchild->rchild->lchild=NULL;
(*T)->lchild->rchild->rchild=NULL;
(*T)->rchild->data=3;
(*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->lchild->data=6;
(*T)->rchild->lchild->lchild=NULL;
(*T)->rchild->lchild->rchild=NULL;
(*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->rchild->data=7;
(*T)->rchild->rchild->lchild=NULL;
(*T)->rchild->rchild->rchild=NULL;
(*T)->lchild->lchild->data=4;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;
}
//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){
printf("%d ",elem->data);
}
//先序遍历
void PreOrderTraverse(BiTree T){
if (T) {
displayElem(T);//调用操作结点数据的函数方法
PreOrderTraverse(T->lchild);//访问该结点的左孩子
PreOrderTraverse(T->rchild);//访问该结点的右孩子
}
//如果结点为空，返回上一层
return;
}
int main() {
BiTree Tree;
CreateBiTree(&Tree);
printf("先序遍历: ");
PreOrderTraverse(Tree);
}
运行结果：
先序遍历: 1 2 4 5 3 6 7
非递归实现:
而递归的底层实现依靠的是栈存储结构，因此，二叉树的先序遍历既可以直接采用递归思想实现，也可以使用栈的存储结构模拟递归的思想实现。
#include <stdio.h>
#include <string.h>
#define TElemType int
int top=-1;//top变量时刻表示栈顶元素所在位置
//构造结点的结构体
typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
*T=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->data=1;
(*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->data=2;
(*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild->data=5;
(*T)->lchild->rchild->lchild=NULL;
(*T)->lchild->rchild->rchild=NULL;
(*T)->rchild->data=3;
(*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->lchild->data=6;
(*T)->rchild->lchild->lchild=NULL;
(*T)->rchild->lchild->rchild=NULL;
(*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->rchild->data=7;
(*T)->rchild->rchild->lchild=NULL;
(*T)->rchild->rchild->rchild=NULL;
(*T)->lchild->lchild->data=4;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;
}
//前序遍历使用的进栈函数
void push(BiTNode** a,BiTNode* elem){
a[++top]=elem;
}
//弹栈函数
void pop( ){
if (top==-1) {
return ;
}
top--;
}
//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){
printf("%d ",elem->data);
}
//拿到栈顶元素
BiTNode* getTop(BiTNode**a){
return a[top];
}
//先序遍历非递归算法
void PreOrderTraverse(BiTree Tree){
BiTNode* a[20];//定义一个顺序栈
BiTNode * p;//临时指针
push(a, Tree);//根结点进栈
while (top!=-1) {
p=getTop(a);//取栈顶元素
pop();//弹栈
while (p) {
displayElem(p);//调用结点的操作函数
//如果该结点有右孩子，右孩子进栈
if (p->rchild) {
push(a,p->rchild);
}
p=p->lchild;//一直指向根结点最后一个左孩子
}
}
}
int main(){
BiTree Tree;
CreateBiTree(&Tree);
printf("先序遍历: ");
PreOrderTraverse(Tree);
}
运行结果
先序遍历: 1 2 4 5 3 6 7
微信扫一扫，分享2020年更多、更全、更新大厂面试资料！
