更新时间：2018-11-22 16:16作者：才子老师
16.有两个单向链表，表头pHeader1，pHeader2，请写一个函数判断这两个链表是否有交叉.如果有交叉，给出交叉点.程序不能改变链表的内容，可以使用额外的空间，时间复杂度尽量小，最好给出两种解.(双重循环的解由于时间复杂度高，不算正解).
1.移动链表指针，如果最终
17.编写程序，将一棵树从根节点到叶子的所有最长路径都打印出来.比如一棵树从跟到最末端的叶子最远要经
过4个节点，那么就把到所有要经过4个节点才能到达的叶子的搜索路径(所有途径节点)都分别打印出来.
18.请分别对一个链表和一个数组进行排序，并指出你排序的算法名称以及为何选择该算法
数组可用交换法排序
19.有单向链表，其中节点结构为Node{int value;Node *pNext};只知道指向某个节点的指针pCurrent;并且知道该节点不是尾节点，有什么办法把他删除吗?要求不断链.
从链表头开始，找到pCurrent上一个结点pPrev，然后 pPrev->pNext = pCurrent->pNext;
20.问题A:用什么方法避免c/c++编程中的头文件重复包含?问题B:假设解决了重复包含问题，但是又需要在两个不同的头文件中引用各申明的类，应该如何处理?具体代码如下:
在头文件Man.h中
….
Class Cman
{
….
CFace m_face;
};
….
在头文件Face.h中
…
Class CFace
{
…
Cman *m_owner;
};
….
这样类CMan.CFace就相互引用了，该如何处理呢?
1.#ifndef ….
#define …..
2.类的前向声明
21.多线程和单线程各自分别在什么时候效率更高?
多线程在并发，并且各线程无需访问共享数据情况详细最高
如果多线程过于频繁切换，或共享数据很多情况下，使用单线程较好
22.在程序设计中，对公共资源(比如缓冲区等)的操作和访问经常需要使用锁来进行保护，但在大并发系统中过多的锁会导致效率很低，通常有那些方法可以尽量避免或减少锁的使用?
减少锁的粒度，每次尽可能减少锁范围
采用队列处理，这样无需使用锁.
23.请详细阐述如何在release版本(windows程序或linux程序都可以)中，查找段错误问题.
可以用编译器生成map文件来定位源码.通过地址反查源码
24.假设你编译链接release版本后得到一个可执行程序(由多个cpp文件和H文件编译)，结果可执行程序文件非常大，你如何找到造成文件太大的可能原因，可能的原因是什么?
使用一个已经初始化的巨大的全局数组
25.在编写C++赋值运算符时有哪些要注意的地方?
返回值，参数最好用引用
减少友元函数使用，移植有问题.
26.假设你是参与设计嫦娥卫星的嵌入式单板软件工程师，其中有一个快速搜索可能要用到哈希变或者平衡二叉树，要求不管什么条件下，单板必须在指定的短时间内有输出，你会采取那种算法?为什么用这种算法，为什么不用另一种算法?
HASH.HASH访问速度较快.
27.strcpy()容易引起缓冲区溢出问题，请问有什么函数可以替代以减少风险，为什么?
strncpy
28.请指出spinlock，mutex，semaphore，critical section的作用与区别，都在哪些场合使用.
spin_lock Linux 内核自旋锁. Mutex Windows 互质量， semaphore POSIX ，critical section Windows
29.在哪些方法使阻塞模式的recv函数在没有收到数据的情况下返回(不能将socket修改为非阻塞模式)请描述得详细点.
使用select
30.有3个红色球，2个白色球，1个绿色球.取出两个不同颜色的球就能变成两个第三种颜色的球(比如:取出1红球，1白球，就能变成2个绿球).问，最少几次变化能将所有球都变成同一颜色，说明步骤和原因?
31.单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。
最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：
struct linka {
int data;
linka* next;
};
void reverse(linka*& head) {
if(head ==NULL)
return;
linka *pre， *cur， *ne;
pre=head;
cur=head->next;
while(cur)
{
ne = cur->next;
cur->next = pre;
pre = cur;
cur = ne;
}
head->next = NULL;
head = pre;
}
还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：
linka* reverse(linka* p，linka*& head)
{
if(p == NULL || p->next == NULL)
{
head=p;
return p;
}
else
{
linka* tmp = reverse(p->next，head);
tmp->next = p;
return p;
}
}
32.已知String类定义如下：
class String
{
public:
String(const char *str = NULL); // 通用构造函数
String(const String &another); // 拷贝构造函数
~ String(); // 析构函数
String & operater =(const String &rhs); // 赋值函数
private:
char *m_data; // 用于保存字符串
};
尝试写出类的成员函数实现。
答案：
String::String(const char *str)
{
if ( str == NULL ) //strlen在参数为NULL时会抛异常才会有这步判断
{
m_data = new char[1] ;
m_data[0] = ‘ ′ ;
}
else
{
m_data = new char[strlen(str) + 1];
strcpy(m_data，str);
}
}
String::String(const String &another)
{
m_data = new char[strlen(another.m_data) + 1];
strcpy(m_data，other.m_data);
}
String& String:#FormatImgID_0# perator =(const String &rhs)
{
if ( this == &rhs)
return *this ;
delete []m_data; //删除原来的数据，新开一块内存
m_data = new char[strlen(rhs.m_data) + 1];
strcpy(m_data，rhs.m_data);
return *this ;
}
String::~String()
{
delete []m_data ;
}
33.求下面函数的返回值(微软)
int func(x)
{
int countx = 0;
while(x)
{
countx ++;
x = x&(x-1);
}
return countx;
}
假定x = 9999。 答案：8
思路：将x转化为2进制，看含有的1的个数。
34. 什么是引用?申明和使用引用要注意哪些问题?
答：引用就是某个目标变量的别名(alias)，对应用的操作与对变量直接操作效果完全相同。申明一个引用的时候，切记要对其进行初始化。引用声明完毕后，相当于目标变量名有两个名称，即该目标原名称和引用名，不能再把该引用名作为其他变量名的别名。声明一个引用，不是新定义了一个变量，它只表示该引用名是目标变量名的一个别名，它本身不是一种数据类型，因此引用本身不占存储单元，系统也不给引用分配存储单元。不能建立数组的引用。