http://blog.csdn.net/zhaojinjia/article/details/12649823
面试官当时只给了一个小时的时间,只写了一个链表反转的程序还问了其他一些,列举下来,希望网友看看下面,有新思路,请交流一下,谢谢。
1:实现带头结点的链表反转问题
两种方法:递归和非递归实现
[cpp] view plaincopyprint?
- struct ListNode
- {
- int m_nKey;
- ListNode* m_pNext;
- };
-
- //非递归实现
- ListNode* ListReverse(ListNode* pHead)
- {
- if ( !pHead->m_pNext )
- return pHead; //如果链表只有头结点,直接返回头结点
- ListNode *p1 = pHead->m_pNext;
- ListNode *p2 = p1->m_pNext;
- ListNode *p3;
-
- p1->m_pNext = NULL; //这一步我面试时写程序落下了------注意一下
-
- while ( p2 )
- {
- p3 = p2->m_pNext; //先保存p2的next指针,防止丢失
- p2->m_pNext = p1; //修改p2的next指针,改为指向p1
-
- p1 = p2; //p1向前移动
- p2 = p3; //p2向前移动
- }
- pHead->m_pNext = p1;
- return pHead;
- }
- //递归求链表反转,返回值当前链表的最后一个结点
- ListNode* RecursiveListReverse(ListNode* pNode, ListNode*& pHead)
- {
- if ( !pNode ) //当没有元素时处理
- {
- return pNode;
- }
-
- if (!pNode->m_pNext) //当当前结点为最后一个结点时,找到头结点,固定不动
- {
- pHead->m_pNext = NULL;
- pHead = pNode;
- return pNode;
- }
- else
- {
- ListNode* temp = RecursiveListReverse(pNode->m_pNext, pHead);
- temp->m_pNext = pNode;
- temp = pNode;
- return temp;
- }
- }
-
- void Traverse(ListNode* pHead)
- {
- ListNode* pTemp = pHead->m_pNext;
- cout <<"output the list: ";
-
- if (!pTemp)
- {
- cout <<"空链表"<<endl;
- return;
- }
-
- while (pTemp)
- {
- cout << pTemp->m_nKey <<" ";
- pTemp = pTemp->m_pNext;
- }
- cout << endl;
- }
-
- //创建一个带头结点的链表
- ListNode* CreateList()
- {
- cout<<"输入空格间隔,-1为结束表示 "<<endl;
- ListNode* pHead = new ListNode; //建一个头结点
- pHead->m_pNext = NULL;
- ListNode* p = pHead;
- int data;
- while ( cin>>data && data!=-1 )
- {
- ListNode* pNew = new ListNode;
- pNew->m_nKey = data;
- pNew->m_pNext = NULL;
-
- p->m_pNext = pNew;
- p = p->m_pNext;
- }
- return pHead;
- }
-
- int _tmain(int argc, _TCHAR* argv[])
- {
- ListNode* pHead = CreateList(); //建立
- Traverse(pHead); //输出
-
- pHead = ListReverse(pHead); //链表反转
- Traverse(pHead); //输出
-
- RecursiveListReverse(pHead->m_pNext,pHead->m_pNext); //递归链表反转
- Traverse(pHead);
-
- return 0;
- }
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?
- class A
- {
- int a;
- static int b;
- virtual void f();
- static void g();
- void h();
- };
计算sizeof(A)=8
9:未排序的两个数组合并成一个数组。
求更高效方法
方法一:将两数排序,用二路归并进行处理
方法二: