百度2013研发工程师笔试卷B
产生死锁的原因主要是：
互斥条件：一个资源每次只能被一个进程使用。 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。 3 有20个数组，每个数组有500个元素，并且是有序排列好的，现在在这20*500个数中找出排名前500的数。
TOP-K问题，用个数为K的最小堆归并处理
reverse(pszString, pszString + len - 1); reverse(pszString, pszString + nCharsRotate); reverse(pszString + nCharsRotate + 1, pszString + len - 1); return pszString; }
现在有一个手机，手机上的键盘上有这样的对应关系，2对应”abc”,3对应”def”…..手机里面有一个userlist用户列表，当我们输入942的时候出来拼音的对应可能是“xia”，“zha”，“xi”，“yi”等，当我们输入9264的时候出来是yang，可能是“样”，“杨”，“往”等，现在我们输入一个字符串数字，比如926等，要在电话簿userlist中查找出对应的用户名和电话号码并返回结果。
#define N 4 char c[][10] = {"","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};//存储各个数字所能代表的字符 int number[N] = {2, 4 ,7, 9}; //存储电话号码 int total[10] = {0, 0, 3, 3, 3, 3, 3, 4, 3, 4}; //各个数组所能代表的字符总数 int answer[N]; //数字目前所代表的字符在其所能代表的字符集中的位置,初始为0 void Search(int *number, int n); //非递归的办法 void RecursiveSearch(int *number, int cur, char *ps, int n); //递归的办法 int main() Search(number, N); // char ps[N+1] = {0}; // RecursiveSearch(number, 0, ps, N); return 0; void Search(int *number, int n) while (1) for (int i = 0; i i++) cout c[number[i]][answer[i]]; cout endl; int k = n - 1; while (k = 0) if (answer[k] total[number[k]] - 1) answer[k]++; break; else answer[k] = 0; k--; if (k 0) break; //递归的解法: number为存储电话号码的数组,pos为当前处理的数字在number中的下标,初始为0 //ps为一外部数组,用于存放字母,n代表电话号码的长度(个数) //此递归的方法好理解,比上面非递归的办法好写易懂 void RecursiveSearch(int *number, int pos, char *ps, int n) for (int i = 0; i total[number[pos]]; i++) ps[pos] = c[number[pos]][i]; if (pos == n - 1) cout ps endl; else RecursiveSearch(number, pos + 1, ps, n); }
6 现在有100个灯泡，每个灯泡都是关着的，第一趟把所有的灯泡灯泡打开，第二趟把偶数位的灯泡制反（也就是开了的关掉，关了的打开），第三趟让第3,6,9….的灯泡制反…….第100趟让第100个灯泡制反，问经过一百趟以后有多少灯泡亮着。
答案：
1．对于每盏灯，拉动的次数是奇数时，灯就是亮着的，拉动的次数是偶数时，灯就是关着的。
2．每盏灯拉动的次数与它的编号所含约数的个数有关，它的编号有几个约数，这盏灯就被拉动几次。
3．1——100这100个数中有哪几个数，约数的个数是奇数。我们知道一个数的约数都是成对出现的，只有完全平方数约数的个数才是奇数个。 所以这100盏灯中有10盏灯是亮着的。 它们的编号分别是： 1、4、9、16、25、36、49、64、81、100。
分页存储管理基本思想：
用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。
分段存储管理基本思想：
将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。
段页式存储管理基本思想：
分页系统能有效地提高内存的利用率，而分段系统能反映程序的逻辑结构，便于段的共享与保护，将分页与分段两种存储方式结合起来，就形成了段页式存储管理方式。
在段页式存储管理系统中，作业的地址空间首先被分成若干个逻辑分段，每段都有自己的段号，然后再将每段分成若干个大小相等的页。对于主存空间也分成大小相等的页，主存的分配以页为单位。
段页式系统中，作业的地址结构包含三部分的内容：段号 页号 页内位移量
程序员按照分段系统的地址结构将地址分为段号与段内位移量，地址变换机构将段内位移量分解为页号和页内位移量。
为实现段页式存储管理，系统应为每个进程设置一个段表，包括每段的段号，该段的页表始址和页表长度。每个段有自己的页表，记录段中的每一页的页号和存放在主存中的物理块号。
1、一个单词单词字母交换，可得另一个单词，如army- mary，成为兄弟单词。提供一个单词，在字典中找到它的兄弟。
1、static关键字，static全局变量与普通全局变量的区别，static局部变量与普通变量的区别，static函数与普通函数的区别。
1、为分析用户行为，系统常需存储用户的一些 query ，但因 query 非常多，故系统不能全存，设系统每天只存 m 个 query ，现设计一个算法，对用户请求的 query 进行随机选择 m 个，请给一个方案，使得每个 query 被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用户的总请求量。
1. extern”C”{}的作用好应用场景； 2.写出两者你熟悉的设计模式，及应用场景，可以给出伪代码； 3.TCP中time_wait是表示那种状态，及应用场景，以及起好处和坏处； 二、算法题40分 1. 有一个任务执行机，任务数N 1000，该机器每次只能执行一个任务，而任务之间存在依赖关系， 但是任务之间没有循环依赖，请给出适