16.有兩個(gè)單向鏈表，表頭pHeader1，pHeader2，請(qǐng)寫一個(gè)函數(shù)判斷這兩個(gè)鏈表是否有交叉.如果有交叉，給出交叉點(diǎn).程序不能改變鏈表的內(nèi)容，可以使用額外的空間，時(shí)間復(fù)雜度盡量小，最好給出兩種解.(雙重循環(huán)的解由于時(shí)間復(fù)雜度高，不算正解).

　　1.移動(dòng)鏈表指針，如果最終

　　17.編寫程序，將一棵樹從根節(jié)點(diǎn)到葉子的所有最長路徑都打印出來.比如一棵樹從跟到最末端的葉子最遠(yuǎn)要經(jīng)

　　過4個(gè)節(jié)點(diǎn)，那么就把到所有要經(jīng)過4個(gè)節(jié)點(diǎn)才能到達(dá)的葉子的搜索路徑(所有途徑節(jié)點(diǎn))都分別打印出來.

　　18.請(qǐng)分別對(duì)一個(gè)鏈表和一個(gè)數(shù)組進(jìn)行排序，并指出你排序的算法名稱以及為何選擇該算法

　　數(shù)組可用交換法排序

　　19.有單向鏈表，其中節(jié)點(diǎn)結(jié)構(gòu)為Node{int value;Node pNext};只知道指向某個(gè)節(jié)點(diǎn)的指針pCurrent;并且知道該節(jié)點(diǎn)不是尾節(jié)點(diǎn)，有什么辦法把他刪除嗎?要求不斷鏈.

　　從鏈表頭開始，找到pCurrent上一個(gè)結(jié)點(diǎn)pPrev，然后 pPrev->pNext = pCurrent->pNext;

　　20.問題A:用什么方法避免c/c++編程中的頭文件重復(fù)包含?問題B:假設(shè)解決了重復(fù)包含問題，但是又需要在兩個(gè)不同的頭文件中引用各申明的類，應(yīng)該如何處理?具體代碼如下:

　　在頭文件Man.h中

　　….

　　Class Cman

　　{

　　….

　　CFace m_face;

　　};

　　….

　　在頭文件Face.h中

　　…

　　Class CFace

　　{

　　…

　　Cman m_owner;

　　};

　　….

　　這樣類CMan.CFace就相互引用了，該如何處理呢?

　　1.#ifndef ….

　　#define …..

　　2.類的前向聲明

　　21.多線程和單線程各自分別在什么時(shí)候效率更高?

　　多線程在并發(fā)，并且各線程無需訪問共享數(shù)據(jù)情況詳細(xì)最高

　　如果多線程過于頻繁切換，或共享數(shù)據(jù)很多情況下，使用單線程較好

　　22.在程序設(shè)計(jì)中，對(duì)公共資源(比如緩沖區(qū)等)的操作和訪問經(jīng)常需要使用鎖來進(jìn)行保護(hù)，但在大并發(fā)系統(tǒng)中過多的鎖會(huì)導(dǎo)致效率很低，通常有那些方法可以盡量避免或減少鎖的使用?

　　減少鎖的粒度，每次盡可能減少鎖范圍

　　采用隊(duì)列處理，這樣無需使用鎖.

　　23.請(qǐng)?jiān)敿?xì)闡述如何在release版本(windows程序或linux程序都可以)中，查找段錯(cuò)誤問題.

　　可以用編譯器生成map文件來定位源碼.通過地址反查源碼

　　24.假設(shè)你編譯鏈接release版本后得到一個(gè)可執(zhí)行程序(由多個(gè)cpp文件和H文件編譯)，結(jié)果可執(zhí)行程序文件非常大，你如何找到造成文件太大的可能原因，可能的原因是什么?

　　使用一個(gè)已經(jīng)初始化的巨大的全局?jǐn)?shù)組

　　25.在編寫C++賦值運(yùn)算符時(shí)有哪些要注意的地方?

　　返回值，參數(shù)最好用引用

　　減少友元函數(shù)使用，移植有問題.

　　26.假設(shè)你是參與設(shè)計(jì)嫦娥衛(wèi)星的嵌入式單板軟件工程師，其中有一個(gè)快速搜索可能要用到哈希變或者平衡二叉樹，要求不管什么條件下，單板必須在指定的短時(shí)間內(nèi)有輸出，你會(huì)采取那種算法?為什么用這種算法，為什么不用另一種算法?

　　HASH.HASH訪問速度較快.

　　27.strcpy()容易引起緩沖區(qū)溢出問題，請(qǐng)問有什么函數(shù)可以替代以減少風(fēng)險(xiǎn)，為什么?

　　strncpy

　　28.請(qǐng)指出spinlock，mutex，semaphore，critical section的作用與區(qū)別，都在哪些場(chǎng)合使用.

　　spin_lock Linux 內(nèi)核自旋鎖. Mutex Windows 互質(zhì)量， semaphore 　POSIX　，critical section　Windows

　　29.在哪些方法使阻塞模式的recv函數(shù)在沒有收到數(shù)據(jù)的情況下返回(不能將socket修改為非阻塞模式)請(qǐng)描述得詳細(xì)點(diǎn).

　　使用select

　　30.有3個(gè)紅色球，2個(gè)白色球，1個(gè)綠色球.取出兩個(gè)不同顏色的球就能變成兩個(gè)第三種顏色的球(比如:取出1紅球，1白球，就能變成2個(gè)綠球).問，最少幾次變化能將所有球都變成同一顏色，說明步驟和原因?

　　31.單向鏈表的反轉(zhuǎn)是一個(gè)經(jīng)常被問到的一個(gè)面試題，也是一個(gè)非常基礎(chǔ)的問題。比如一個(gè)鏈表是這樣的：1->2->3->4->5 通過反轉(zhuǎn)后成為5->4->3->2->1。

　　最容易想到的方法遍歷一遍鏈表，利用一個(gè)輔助指針，存儲(chǔ)遍歷過程中當(dāng)前指針指向的下一個(gè)元素，然后將當(dāng)前節(jié)點(diǎn)元素的指針反轉(zhuǎn)后，利用已經(jīng)存儲(chǔ)的指針往后面繼續(xù)遍歷。源代碼如下：

　　struct linka {

　　int data;

　　linka next;

　　};

　　void reverse(linka& head) {

　　if(head ==NULL)

　　return;

　　linka P， cur， ne;

　　P=head;

　　cur=head->next;

　　while(cur)

　　{

　　ne = cur->next;

　　cur->next = P;

　　P = cur;

　　cur = ne;

　　}

　　head->next = NULL;

　　head = P;

　　}

　　還有一種利用遞歸的方法。這種方法的基本思想是在反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)之前先調(diào)用遞歸函數(shù)反轉(zhuǎn)后續(xù)節(jié)點(diǎn)。源代碼如下。不過這個(gè)方法有一個(gè)缺點(diǎn)，就是在反轉(zhuǎn)后的最后一個(gè)結(jié)點(diǎn)會(huì)形成一個(gè)環(huán)，所以必須將函數(shù)的返回的節(jié)點(diǎn)的next域置為NULL。因?yàn)橐�改變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); // 通用構(gòu)造函數(shù)

　　String(const String &another); // 拷貝構(gòu)造函數(shù)

　　~ String(); // 析構(gòu)函數(shù)

　　String & operater =(const String &rhs); // 賦值函數(shù)

　　private:

　　char m_data; // 用于保存字符串

　　};

　　嘗試寫出類的成員函數(shù)實(shí)現(xiàn)。

　　答案：

　　String::String(const char str)

　　{

　　if ( str == NULL ) //strlen在參數(shù)為NULL時(shí)會(huì)拋異常才會(huì)有這步判斷

　　{

　　m_data = new char ;

　　m_data[0] = ‘\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; //刪除原來的數(shù)據(jù)，新開一塊內(nèi)存

　　m_data = new char[strlen(rhs.m_data) + 1];

　　strcpy(m_data，rhs.m_data);

　　return this ;

　　}

　　String::~String()

　　{

　　delete []m_data ;

　　}

　　33.求下面函數(shù)的返回值(微軟)

　　int func(x)

　　{

　　int countx = 0;

　　while(x)

　　{

　　countx ++;

　　x = x&(x-1);

　　}

　　return countx;

　　}

　　假定x = 9999。 答案：8

　　思路：將x轉(zhuǎn)化為2進(jìn)制，看含有的1的個(gè)數(shù)。

　　34. 什么是“引用”?申明和使用“引用”要注意哪些問題?

　　答：引用就是某個(gè)目標(biāo)變量的“別名”(alias)，對(duì)應(yīng)用的操作與對(duì)變量直接操作效果完全相同。申明一個(gè)引用的時(shí)候，切記要對(duì)其進(jìn)行初始化。引用聲明完畢后，相當(dāng)于目標(biāo)變量名有兩個(gè)名稱，即該目標(biāo)原名稱和引用名，不能再把該引用名作為其他變量名的別名。聲明一個(gè)引用，不是新定義了一個(gè)變量，它只表示該引用名是目標(biāo)變量名的一個(gè)別名，它本身不是一種數(shù)據(jù)類型，因此引用本身不占存儲(chǔ)單元，系統(tǒng)也不給引用分配存儲(chǔ)單元。不能建立數(shù)組的引用。