本文共 2783 字，大约阅读时间需要 9 分钟。

41、怎么避免死锁？

1. 有序资源分配法，就是大家申请资源时都按照相同的顺序来；
2. 使用银行家算法，进程首次申请资源时测试该进程对资源的最大需求量，若系统现有资源可以满足，则按照当前申请量分配，否则推迟分配。当进程在执行中继续申请资源时，先测试该进程，本次申请的资源数是否超过该资源所剩总量，满足则分配，否则推迟分配。

42、实现斐波列算法

       斐波列函数：

int fibo(int n)	{   		if (n <= 2)			return 1;		else			return fibo(n-1)+fibo(n-2);	}

       数组法：

       根据n来new一个n大小的数组，知道数组第一个数为1，第二个数也为1，再根据循环求后面的数。

43、写程序将I love English转换为English love I

       算法：先将整个句子反转，再对每个单词反转

       异或：^ 值相同为0，不同为1.

#include 
   
    	#include 
    
     	using namespace std;	void inverseString(char* p, char* q)	{   		while(q-p >=1)		{   			*p = *p ^ *q;			*q = *p ^ *q;			*p = *p ^ *q;			p++;			q--;		}	}	int main()	{   		char str[] = “I come from tianjian”;		int iStrlen = strlen(str);		inverseString(str, str+iStrlen-1);		char* p = str;		char* q = str;		while(*p != ‘\0’)		{   			if (*p == ‘ ‘)			{   				inverseString(q, p-1);				q = p+1;			}			p++;		}		printf(“%s\n”, str);		return 0;	}
    
   

44、c++中如何捕捉异常，是引用还是值？哪个成员函数用于从异常中获取错误信息？

       直接捕捉的值，捕捉用的成员函数是catch。

45、std::string::find()的返回类型是什么？如果没有找到该函数返回值是什么？

       返回类型是size_type，没找到返回值是string::npos。

46、std::vector的运算符[]和at()有什么区别？

       at()返回元素数据，如果越界，跑出out_of_range，[]返回容器中指定位置的一个引用。

47、什么是const成员函数？

       const成员函数不允许修改类的数据成员，只有被声明为const的成员函数才能被一个const类对象调用。

48、请使用fabs和DBL_EPSILON写一个简单函数比较double dVal和0.45是否相等，相等返回true，不等返回false；

bool CheckDblEq(double dVal)	{   		if (fabs(dVal-0,45) < DBL_EPSILON)			return true;		else			return false;	}

49、多个集合合并成没有交集的集合

给定一个字符串的集合，格式如：{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{dddhhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaabbbcccdddhhh}，{eeefff}，{ggg}。

　　（1）请描述你解决这个问题的思路； 　　（2）请给出主要的处理流程，算法，以及算法的复杂度 　　（3）请描述可能的改进。 回答： 　　集合使用hash_set来表示，这样合并时间复杂度比较低。 　　1)给每个集合编号为0，1，2，3… 　　2)创建一个hash_map，key为字符串，value为一个链表，链表节点为字符串所在集合的编号。遍历所有的集合，将字符串和对应的集合编号插入到hash_map中去。 　　3)创建一个长度等于集合个数的int数组，表示集合间的合并关系。例如，下标为5的元素值为3，表示将下标为5的集合合并到下标为3的集合中去。开始时将所有值都初始化为-1，表示集合间没有互相合并。在集合合并的过程中，我们将所有的字符串都合并到编号较小的集合中去。 　 遍历第二步中生成的hash_map，对于每个value中的链表，首先找到最小的集合编号（有些集合已经被合并过，需要顺着合并关系数组找到合并后的集合编号），然后将链表中所有编号的集合都合并到编号最小的集合中（通过更改合并关系数组）。 　　4)现在合并关系数组中值为-1的集合即为最终的集合，它的元素来源于所有直接或间接指向它的集合。 　　算法的复杂度为O(n)，其中n为所有集合中的元素个数。 　　题目中的例子： 　　0:{aaabbbccc} 　　1:{bbbddd} 　　2:{eeefff} 　　3:{ggg} 　　4:{dddhhh} 　　生成的hash_map，和处理完每个值后的合并关系数组分别为 　　aaa:0。[-1,-1,-1,-1,-1] 　　bbb:0,1。[-1,0,-1,-1,-1] 　　ccc:0。[-1,0,-1,-1,-1] 　　ddd:1,4。[-1,0,-1,-1,0] 　　eee:2。[-1,0,-1,-1,0] 　　fff:2。[-1,0,-1,-1,0] 　　ggg:3。[-1,0,-1,-1,0] 　　hhh:4。[-1,0,-1,-1,0] 　　所以合并完后有三个集合，第0，1，4个集合合并到了一起，

50、求某数是否在40亿个整数中

给40亿个不重复的unsigned int的整数，没排过序的，然后再给几个数，如何快速判断这几个数是否在那40亿个数当中?

答案：        unsigned int的取值范围是0到2^{32-1。我们可以申请连续的2}32/8=512M的内存，用每一个bit对应一个unsigned int数字。首先将512M内存都初始化为0，然后每处理一个数字就将其对应的bit设置为1。当需要查询时，直接找到对应bit，看其值是0还是1即可。        怎么将对应的bit设为1？         也许通过结构体里面设置占用bit位为1，然后以该结构体去申请512M的空间，这样就相当于对数组操作了。        解法二：        将要判断的几个数放到一个hash中，然后遍历40亿个数，看是否有数包含在数组里面，若有则将该数删掉并记录下来。        这样占用内存就很小，但是如果要判断的数有变化，那么就要重新做hash，重新遍历40亿个数了。        思路：通过bit位来解决问题。