剛剛畢業(yè)找工作時(shí)毅桃，整理了一些C/C++基礎(chǔ)問題和答案爱榔，有些是日常遇到的問題，有些是網(wǎng)上其他人的分享泊窘，其中涉及到程序輸出的問題我都親自編程驗(yàn)證過，在問題后面也用紅色字體標(biāo)注了“驗(yàn)證by云峰小羅”像寒。最近應(yīng)該還有些畢業(yè)生還在找工作，所以分享出來瓜贾，希望能有些幫助诺祸。畢竟我當(dāng)年畢業(yè)時(shí)就是對(duì)這些題目特別留心，然后順利校招進(jìn)入鵝廠的祭芦。本文介紹關(guān)于計(jì)算機(jī)筷笨、網(wǎng)絡(luò)、操作系統(tǒng)原理和彻昃ⅲ考算法胃夏，關(guān)于C/C++語法類原理類題目請參考：C/C++基礎(chǔ)問題和答案匯總（一）
1、為什么內(nèi)存對(duì)齊可以提高訪問內(nèi)存的速度昌跌？
一個(gè)周期存取一個(gè)字長（32位機(jī)就是32位）仰禀，但是這個(gè)字長，是對(duì)齊的蚕愤，就是只能從00－01等等答恶，所以要是一個(gè)單位跨了兩個(gè)這樣的單元，就要多讀一次萍诱。
例如：大家都知道一個(gè)byte是8個(gè)bit悬嗓，而現(xiàn)在流行的32位機(jī)指的是一次可以存取32個(gè)bit，也就是4個(gè)byte裕坊，在這種情況下包竹，最有效率的作法當(dāng)然是一次讀4個(gè)byte。也就是即便你只取一個(gè)byte的內(nèi)容，實(shí)際上周瞎，機(jī)器一次也是取了4個(gè)byte悟狱，然后把其中的一個(gè)byte給你。當(dāng)然取4個(gè)byte并不是隨機(jī)組合的堰氓，而是按照一定的次序挤渐，比如一次取0、1双絮、2浴麻、3四個(gè)單元的內(nèi)容，下次訪問就是4囤攀、5软免、6、7焚挠。由此膏萧，如果你的數(shù)據(jù)恰好在0、1蝌衔、2榛泛、3，則機(jī)器只需訪問一次噩斟，就可以把所有的內(nèi)容取出來曹锨，然而，如果你的數(shù)據(jù)跨越了這個(gè)邊界剃允，比如在2沛简、3、4斥废、5椒楣，機(jī)器在第一次訪問的時(shí)候，只能取出2牡肉、3的內(nèi)容捧灰，還需要進(jìn)行一次訪問才能將4、5的內(nèi)容取出荚板。如此一來凤壁，必須進(jìn)行兩次訪問才能取出，所以效率當(dāng)然會(huì)降低跪另。如果讀一個(gè)數(shù)據(jù)值(32bit)要讀兩次cache或者要讀兩個(gè)頁拧抖，甚至引發(fā)缺頁中斷，是非常劃不來的,計(jì)算機(jī)系統(tǒng)的設(shè)計(jì)中要盡量避免可能導(dǎo)致執(zhí)行時(shí)間不確定的情況免绿。
2唧席、全局變量和局部變量
一個(gè)程序?qū)⒉僮飨到y(tǒng)分配給其運(yùn)行的內(nèi)存塊分為4個(gè)區(qū)域：
(1)代碼區(qū)，存放程序的代碼，即程序中的各個(gè)函數(shù)代碼塊淌哟。
(2)全局?jǐn)?shù)據(jù)區(qū)迹卢，存放程序的全局?jǐn)?shù)據(jù)和靜態(tài)數(shù)據(jù)。
(3)堆區(qū)徒仓，存放程序的動(dòng)態(tài)數(shù)據(jù)腐碱。
(4)棧區(qū)，存放程序的局部數(shù)據(jù)掉弛，即各個(gè)函數(shù)中的數(shù)據(jù)症见。
全局變量是整個(gè)程序都可訪問的變量，誰都可以訪問殃饿，生存期在整個(gè)程序從運(yùn)行到結(jié)束(在程序結(jié)束時(shí)所占內(nèi)存釋放)谋作；而局部變量存在于模塊(子程序，函數(shù))中乎芳，只有所在模塊可以訪問遵蚜，其他模塊不可直接訪問，模塊結(jié)束(函數(shù)調(diào)用完畢)奈惑，局部變量消失吭净，所占據(jù)的內(nèi)存釋放。操作系統(tǒng)和編譯器携取，可能是通過內(nèi)存分配的位置來知道的攒钳，全局變量分配在全局?jǐn)?shù)據(jù)段并且在程序開始運(yùn)行的時(shí)候被加載.局部變量則分配在堆棧里面。
3雷滋、什么是預(yù)編譯？
預(yù)編譯又稱為預(yù)處理,是做些代碼文本的替換工作文兢。處理#開頭的指令,比如拷貝#include包含的文件代碼晤斩，#define宏定義的替換,條件編譯等，就是為編譯做的預(yù)備工作的階段姆坚，主要處理#開始的預(yù)編譯指令澳泵，預(yù)編譯指令指示了在程序正式編譯前就由編譯器進(jìn)行的操作，可以放在程序中的任何位置兼呵。編譯系統(tǒng)在對(duì)程序進(jìn)行通常的編譯之前兔辅，先進(jìn)行預(yù)處理。提供的預(yù)處理功能主要有以下三種：1）宏定義2）文件包含 3）條件編譯
4击喂、堆棧溢出一般是什么原因?qū)е碌模?/b>
1维苔、沒有對(duì)數(shù)組進(jìn)行邊界檢查，數(shù)組越界訪問懂昂；
2介时、沒有回收垃圾資源導(dǎo)致內(nèi)存泄露，最后內(nèi)存耗盡
3、循環(huán)的遞歸調(diào)用或者太深層次的遞歸調(diào)用
4沸柔、如果使用占用內(nèi)存過大的數(shù)據(jù)結(jié)構(gòu)的局部變量循衰，導(dǎo)致堆棧溢出
5、堆與棧的去區(qū)別
A.申請方式不同
Stack由系統(tǒng)自動(dòng)分配褐澎，而heap需要程序員自己申請会钝，并指明大小。
B.申請后系統(tǒng)的響應(yīng)不同
棧：只要棧的剩余空間大于申請空間工三，系統(tǒng)就為程序提供內(nèi)存迁酸，否則將拋出棧溢出異常。堆：當(dāng)系統(tǒng)收到程序申請時(shí)徒蟆，先遍歷操作系統(tǒng)中記錄空閑內(nèi)存地址的鏈表胁出，尋找第一個(gè)大于所申請空間的堆結(jié)點(diǎn)，然后將該結(jié)點(diǎn)從空間結(jié)點(diǎn)鏈表中刪除段审，并將該結(jié)點(diǎn)的空間分配給程序全蝶。另外，大多數(shù)系統(tǒng)還會(huì)在這塊內(nèi)存空間中的首地址處記錄本次分配的大小寺枉，以便于delete語句正確釋放空間抑淫。而且，由于找到的堆結(jié)點(diǎn)的大小不一定正好等于申請的大小姥闪，系統(tǒng)會(huì)自動(dòng)將多余的那部分重新放入空閑鏈表始苇。
C.申請大小限制的不同
Stack：在windows下，棧的大小是2M（也可能是1M它是一個(gè)編譯時(shí)就確定的常數(shù)）筐喳，如果申請的空間超過棧的剩余空間時(shí)催式，將提示overflow。因此避归，能從棧獲得的空間較小荣月。堆：堆是向高地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是不連續(xù)的內(nèi)存區(qū)域梳毙。這是由于系統(tǒng)是用鏈表來存儲(chǔ)的空閑內(nèi)存地址的哺窄，自然是不連續(xù)的，而鏈表的遍歷方向是由低地址向高地址账锹。堆的大小受限于計(jì)算機(jī)系統(tǒng)中有效的虛擬內(nèi)存萌业。由此可見，堆獲得的空間比較靈活奸柬，也比較大生年。
D.申請效率的比較：
棧由系統(tǒng)自動(dòng)分配，速度較快鸟缕。但程序員是無法控制的晶框。堆是由new分配的內(nèi)存排抬，一般速度比較慢，而且容易產(chǎn)生內(nèi)存碎片,不過用起來最方便授段。另外蹲蒲，在WINDOWS下，最好的方式是用VirtualAlloc分配內(nèi)存侵贵，他不是在堆届搁，也不是在棧是直接在進(jìn)程的地址空間中保留一快內(nèi)存，雖然用起來最不方便窍育。但是速度快卡睦，也最靈活。
E.堆和棧中的存儲(chǔ)內(nèi)容
棧：在函數(shù)調(diào)用時(shí)漱抓，第一個(gè)進(jìn)棧的是主函數(shù)中后的下一條指令（函數(shù)調(diào)用語句的下一條可執(zhí)行語句）的地址表锻，然后是函數(shù)的各個(gè)參數(shù)，在大多數(shù)的C編譯器中乞娄，參數(shù)是由右往左入棧的瞬逊，然后是函數(shù)中的局部變量。注意靜態(tài)變量是不入棧的仪或。當(dāng)本次函數(shù)調(diào)用結(jié)束后确镊，局部變量先出棧，然后是參數(shù)范删，最后棧頂指針指向最開始存的地址蕾域，也就是主函數(shù)中的下一條指令，程序由該點(diǎn)繼續(xù)運(yùn)行到旦。堆：一般是在堆的頭部用一個(gè)字節(jié)存放堆的大小旨巷。堆中的具體內(nèi)容有程序員安排。
6添忘、不用數(shù)組契沫，輸出二進(jìn)制數(shù)。
//以下兩種解法都在VC++6.0中驗(yàn)證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！的末尾有幾個(gè)0.
（用素?cái)?shù)相乘的方法來做拴清，如72=2*2*2*3*3）;只要求出1靶病，2，口予。娄周。。沪停，1000中含因子2的個(gè)數(shù)比含5的個(gè)數(shù)多煤辨，一個(gè)2和一個(gè)5相乘得一個(gè)0裳涛，所以求出所有含因子5的個(gè)數(shù)，相加就行了众辨。
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驗(yàn)證 by云峰小羅
8、不用任何局部和全局變量（遞歸）實(shí)現(xiàn)int strlen(char *a)
int strlen(char *a)
{
? ? ? ? if('\\\\\\\\0' == *a)
? ? ? ? ? ? ? return 0;
? ? ? ? ?else
? ? ? ? ? ? ? ?return 1 + strlen(a + 1);
}//VC++6.0驗(yàn)證 by云峰小羅
9鹃彻、實(shí)現(xiàn)任意長度的整數(shù)相加或者相乘功能
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驗(yàn)證 by云峰小羅
10郊闯、寫一算法檢測單向鏈表中是否存在環(huán)。
注意蛛株，要求算法復(fù)雜度是O(n)并只使用常數(shù)空間团赁。你只知道一個(gè)指向單向鏈表頭的指針。鏈表的長度是不定的谨履，而且環(huán)出現(xiàn)的地方也是不定的欢摄，環(huán)有可能在頭，有可能在中間笋粟。而且要求是檢測,不能破壞環(huán)的結(jié)構(gòu).
答：用兩個(gè)指針來遍歷這個(gè)單向鏈表怀挠，第一個(gè)指針p1，每次走一步矗钟；第二個(gè)指針p2唆香，每次走兩步；當(dāng)p2指針追上p1的時(shí)候吨艇，就表明鏈表當(dāng)中有環(huán)路了躬它。
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; //無環(huán)
? ? ? ? ? ? ? ? if (t1 == t2)
? ? ? ? ? ? ? ? ? ?return 1;
? ? ? ? ? ? }
? ? ? ? ? return 0;
}//VC++6.0驗(yàn)證 by云峰小羅
如果要定位環(huán)路在鏈表當(dāng)中的開始點(diǎn)，發(fā)現(xiàn)p2和p1重合东涡，確定了單向鏈表有環(huán)路了冯吓。接下來，讓p2回到鏈表的頭部疮跑，重新走组贺，P1也繼續(xù)走，每次步長都走1祖娘，那么當(dāng)p1和p2再次相遇的時(shí)候失尖，就是環(huán)路的入口了。
微信公眾號(hào)：云峰小羅渐苏，分享 編程.生活.段子
