百度面试总结

http://blog.csdn.net/zhaojinjia/article/details/12649823

面试官当时只给了一个小时的时间，只写了一个链表反转的程序还问了其他一些，列举下来，希望网友看看下面，有新思路，请交流一下，谢谢。

1：实现带头结点的链表反转问题

     两种方法：递归和非递归实现

[cpp] view plaincopyprint?

1. struct ListNode  
2. {  
3. int m_nKey;  
4.     ListNode* m_pNext;  
5. };  
7. //非递归实现
8. ListNode* ListReverse(ListNode* pHead)  
9. {  
10. if ( !pHead->m_pNext )  
11. return pHead;       //如果链表只有头结点，直接返回头结点
12.     ListNode *p1 = pHead->m_pNext;  
13.     ListNode *p2 = p1->m_pNext;  
14.     ListNode *p3;  
16.     p1->m_pNext = NULL;      //这一步我面试时写程序落下了------注意一下
18. while ( p2 )  
19.     {  
20.         p3 = p2->m_pNext;    //先保存p2的next指针，防止丢失
21.         p2->m_pNext = p1;    //修改p2的next指针，改为指向p1
23.         p1 = p2;            //p1向前移动
24.         p2 = p3;            //p2向前移动
25.     }  
26.     pHead->m_pNext = p1;  
27. return pHead;  
28. }  
29. //递归求链表反转，返回值当前链表的最后一个结点
30. ListNode* RecursiveListReverse(ListNode* pNode, ListNode*& pHead)  
31. {  
32. if ( !pNode )   //当没有元素时处理
33.     {  
34. return pNode;  
35.     }  
37. if (!pNode->m_pNext) //当当前结点为最后一个结点时，找到头结点，固定不动
38.     {  
39.         pHead->m_pNext = NULL;  
40.         pHead = pNode;  
41. return pNode;  
42.     }  
43. else
44.     {  
45.         ListNode* temp = RecursiveListReverse(pNode->m_pNext, pHead);  
46.         temp->m_pNext = pNode;  
47.         temp = pNode;  
48. return temp;  
49.     }  
50. }  
52. void Traverse(ListNode* pHead)  
53. {  
54.     ListNode* pTemp = pHead->m_pNext;  
55.     cout <<"output the list:   ";  
57. if (!pTemp)  
58.     {  
59.         cout <<"空链表"<<endl;  
60. return;  
61.     }  
63. while (pTemp)  
64.     {  
65.         cout << pTemp->m_nKey <<" ";  
66.         pTemp = pTemp->m_pNext;  
67.     }  
68.     cout << endl;  
69. }  
71. //创建一个带头结点的链表
72. ListNode* CreateList()  
73. {  
74.     cout<<"输入空格间隔，-1为结束表示 "<<endl;  
75.     ListNode* pHead = new ListNode;     //建一个头结点
76.     pHead->m_pNext = NULL;  
77.     ListNode* p = pHead;  
78. int data;  
79. while ( cin>>data && data!=-1 )  
80.     {  
81.         ListNode* pNew = new ListNode;  
82.         pNew->m_nKey = data;  
83.         pNew->m_pNext = NULL;  
85.         p->m_pNext = pNew;  
86.         p = p->m_pNext;  
87.     }  
88. return pHead;  
89. }  
91. int _tmain(int argc, _TCHAR* argv[])  
92. {  
93.     ListNode* pHead = CreateList();     //建立
94.     Traverse(pHead);                    //输出
96.     pHead = ListReverse(pHead);         //链表反转
97.     Traverse(pHead);                    //输出
99.     RecursiveListReverse(pHead->m_pNext,pHead->m_pNext);  //递归链表反转
100.     Traverse(pHead);  
102. return 0;  
103. }  

2：一个数组长度为N，且每个元素的范围是1到N+2，且不重复出现，那么1到N+2中肯定会有两个数字没有出现，要求用时间复杂度为O(n)，空间复杂度为O(1)找出来。

     利用解方程思想：X+Y=一数，  X*Y=一数，可求出X和Y，但是当N较大时，这个方法不可取，求高效方法

3：虚拟内存（虚拟存储器）

     背景：常规存储器管理方式的特征：一次性和驻留性。

     虚拟内存提出原因：1：有些作业很大，无法一下全部装入内存；2：作业量很大，内存无法容纳所有这些作业，只能将少数作业装入内存，而将其他大量作业留在外存上。

虚拟内存是从逻辑上扩充内存容量解决问题的。

定义：具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近内存速度。

理论依据--->时间局部性：如果程序某条指令被指向，则不久以后该指令会再次执行；如果某数据被访问，则不久可能会被再次访问。原因：程序中存在大量循环操作。空间局限性：一旦访问了某个存储单元，不久后，其附近的存储单元也将被访问，由于程序一般是顺序执行。     

     实现方法：有两种  分页请求系统   请求分段系统-------重点

     虚拟存储器的特征： 多次性、对换性、虚拟性

     页面置换算法：最佳置换算法、先进先出页面置换算法、LRU置换算法、clock置换算法、

4：存储器管理

存储层次至少应具有三级：CPU寄存器、主存(高速缓存，主存，磁盘缓存)、辅存。

用户源程序到内存中可执行程序分两步：编译（将用户源代码编译成若干个目标模块），链接（将目标模块以及所需要的库函数链接，形成完整装入模块），装入（完整模块装入内存）

     程序装入方式：绝对装入、可重定位装入、动态运行时装入

     程序链接方式：静态链接、装入时动态链接、运行时动态链接

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

内存管理方式：基本分页存储管理方式、基本分段存储管理方式、段页式存储管理方式

5：文件管理

6：OSI七层协议，网络层有哪些协议，TCP/Ip协议

7：已知有大量字符串，找出可以唯一标识每个字符串的前缀

例如：字符串为：abe、adef、aeg、ebg，那么它们的唯一标识前缀分别为：ab、ad、ae、e；

方法一：按照字符顺序排序，通过与其前后字符串比较计算其唯一标识前缀；

方法二：建立trie树

8：static virtual 类大小问题

[cpp] view plaincopyprint?

1. class A  
2. {  
3. int a;  
4. static int b;  
5. virtual void f();  
6. static void g();  
7. void h();  
8. };  

计算sizeof(A)=8

9：未排序的两个数组合并成一个数组。

求更高效方法

方法一：将两数排序，用二路归并进行处理

方法二：