面试必备之C/C++基础问题和答案汇总（二）
云峰小罗手机拍摄
刚刚毕业找工作时，整理了一些C/C++基础问题和答案，有些是日常遇到的问题，有些是网上其他人的分享，其中涉及到程序输出的问题我都亲自编程验证过，在问题后面也用红色字体标注了“验证by云峰小罗”。最近应该还有些毕业生还在找工作，所以分享出来，希望能有些帮助。毕竟我当年毕业时就是对这些题目特别留心，然后顺利校招进入鹅厂的。本文介绍关于计算机、网络、操作系统原理和常考算法，关于C/C++语法类原理类题目请参考：C/C++基础问题和答案汇总（一）
1、为什么内存对齐可以提高访问内存的速度？
一个周期存取一个字长（32位机就是32位），但是这个字长，是对齐的，就是只能从00－01等等，所以要是一个单位跨了两个这样的单元，就要多读一次。
例如：大家都知道一个byte是8个bit，而现在流行的32位机指的是一次可以存取32个bit，也就是4个byte，在这种情况下，最有效率的作法当然是一次读4个byte。也就是即便你只取一个byte的内容，实际上，机器一次也是取了4个byte，然后把其中的一个byte给你。当然取4个byte并不是随机组合的，而是按照一定的次序，比如一次取0、1、2、3四个单元的内容，下次访问就是4、5、6、7。由此，如果你的数据恰好在0、1、2、3，则机器只需访问一次，就可以把所有的内容取出来，然而，如果你的数据跨越了这个边界，比如在2、3、4、5，机器在第一次访问的时候，只能取出2、3的内容，还需要进行一次访问才能将4、5的内容取出。如此一来，必须进行两次访问才能取出，所以效率当然会降低。如果读一个数据值(32bit)要读两次cache或者要读两个页，甚至引发缺页中断，是非常划不来的,计算机系统的设计中要尽量避免可能导致执行时间不确定的情况。
2、全局变量和局部变量
一个程序将操作系统分配给其运行的内存块分为4个区域：
程序内存空间示意
(1)代码区，存放程序的代码，即程序中的各个函数代码块。
(2)全局数据区，存放程序的全局数据和静态数据。
(3)堆区，存放程序的动态数据。
(4)栈区，存放程序的局部数据，即各个函数中的数据。
全局变量是整个程序都可访问的变量，谁都可以访问，生存期在整个程序从运行到结束(在程序结束时所占内存释放)；而局部变量存在于模块(子程序，函数)中，只有所在模块可以访问，其他模块不可直接访问，模块结束(函数调用完毕)，局部变量消失，所占据的内存释放。操作系统和编译器，可能是通过内存分配的位置来知道的，全局变量分配在全局数据段并且在程序开始运行的时候被加载.局部变量则分配在堆栈里面。
3、什么是预编译？
预编译又称为预处理,是做些代码文本的替换工作。处理#开头的指令,比如拷贝#include包含的文件代码，#define宏定义的替换,条件编译等，就是为编译做的预备工作的阶段，主要处理#开始的预编译指令，预编译指令指示了在程序正式编译前就由编译器进行的操作，可以放在程序中的任何位置。编译系统在对程序进行通常的编译之前，先进行预处理。提供的预处理功能主要有以下三种：1）宏定义2）文件包含 3）条件编译
4、堆栈溢出一般是什么原因导致的？
1、没有对数组进行边界检查，数组越界访问；
2、没有回收垃圾资源导致内存泄露，最后内存耗尽
3、循环的递归调用或者太深层次的递归调用
4、如果使用占用内存过大的数据结构的局部变量，导致堆栈溢出
5、堆与栈的去区别
A.申请方式不同
Stack由系统自动分配，而heap需要程序员自己申请，并指明大小。
B.申请后系统的响应不同
栈：只要栈的剩余空间大于申请空间，系统就为程序提供内存，否则将抛出栈溢出异常。堆：当系统收到程序申请时，先遍历操作系统中记录空闲内存地址的链表，寻找第一个大于所申请空间的堆结点，然后将该结点从空间结点链表中删除，并将该结点的空间分配给程序。另外，大多数系统还会在这块内存空间中的首地址处记录本次分配的大小，以便于delete语句正确释放空间。而且，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动将多余的那部分重新放入空闲链表。
C.申请大小限制的不同
Stack：在windows下，栈的大小是2M（也可能是1M它是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
D.申请效率的比较：
栈由系统自动分配，速度较快。但程序员是无法控制的。堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便。另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度快，也最灵活。
E.堆和栈中的存储内容
栈：在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。
6、不用数组，输出二进制数。
//以下两种解法都在VC++6.0中验证by云峰小罗
解1：int main()
{
int n;
cout << "input n:";
cin >> n;
for(int i=1; i<=32; i++){
cout << (n<0?1:0) << (i%8==0?" ":"");
n = n<<1;
}
解2：void bit_print(int a)
{
int i;
int n = sizeof(int) * CHAR_BIT;
int mask = 1 << (n - 1);
for(i = 1; i <= n; ++i)
{
putchar(((a & mask) == 0) ? '0' : '1');
a <<= 1;
if(i % CHAR_BIT == 0 && i < n)
putchar(' ');
}
}
7、求1000！的末尾有几个0.
（用素数相乘的方法来做，如72=2*2*2*3*3）;只要求出1，2，。。。，1000中含因子2的个数比含5的个数多，一个2和一个5相乘得一个0，所以求出所有含因子5的个数，相加就行了。
int find5(int x)
{
int num=0;
while (x%5==0)
{
num++;
x/=5;
}
return num;
}
void main()
{
int result=0;
for(int i=5;i<=1000;i+=5)
result+=find5(i);
cout<<result<<endl;
}
//输出249，VC++6.0验证 by云峰小罗
8、不用任何局部和全局变量（递归）实现int strlen(char *a)
int strlen(char *a)
{
if('\\\\\\\\0' == *a)
return 0;
else
return 1 + strlen(a + 1);
}//VC++6.0验证 by云峰小罗
9、实现任意长度的整数相加或者相乘功能
void bigadd(char* num,char* str,int len)
{
for(int i=len;i>0;i--)
{
num[i] += str[i];
int j = i;
while(num[j]>=10)
{
num[j--] -= 10;
num[j] += 1;
}
}
}//VC++6.0验证 by云峰小罗
10、写一算法检测单向链表中是否存在环。
注意，要求算法复杂度是O(n)并只使用常数空间。你只知道一个指向单向链表头的指针。链表的长度是不定的，而且环出现的地方也是不定的，环有可能在头，有可能在中间。而且要求是检测,不能破坏环的结构.
答：用两个指针来遍历这个单向链表，第一个指针p1，每次走一步；第二个指针p2，每次走两步；当p2指针追上p1的时候，就表明链表当中有环路了。
int testLinkRing(Link *head)
{
Link *t1=head,*t2=head;
while( t1->next && t2->next)
{
t1 = t1->next;
if (NULL == (t2 = t2->next->next))
return 0; //无环
if (t1 == t2)
return 1;
}
return 0;
}//VC++6.0验证 by云峰小罗
如果要定位环路在链表当中的开始点，发现p2和p1重合，确定了单向链表有环路了。接下来，让p2回到链表的头部，重新走，P1也继续走，每次步长都走1，那么当p1和p2再次相遇的时候，就是环路的入口了。
