linux c/c++ 面试题目整理(五)

2018-06-19 本文已影响21人 cpp加油站

41、怎么避免死锁？

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

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 <iostreaaam>
    #include <string>
    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位来解决问题。