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

　　1.移動鏈表指針，如果最終

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

　　過4個節(jié)點，那么就把到所有要經過4個節(jié)點才能到達的葉子的搜索路徑(所有途徑節(jié)點)都分別打印出來.

　　18.請分別對一個鏈表和一個數組進行排序，并指出你排序的算法名稱以及為何選擇該算法

　　數組可用交換法排序

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

　　從鏈表頭開始，找到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.多線程和單線程各自分別在什么時候效率更高?

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

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

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

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

　　采用隊列處理，這樣無需使用鎖.

　　23.請詳細闡述如何在release版本(windows程序或linux程序都可以)中，查找段錯誤問題.

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

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

　　使用一個已經初始化的巨大的全局數組

　　25.在編寫C++賦值運算符時有哪些要注意的地方?

　　返回值，參數最好用引用

　　減少友元函數使用，移植有問題.

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

　　HASH.HASH訪問速度較快.

　　27.strcpy()容易引起緩沖區(qū)溢出問題，請問有什么函數可以替代以減少風險，為什么?

　　strncpy

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

　　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。

　　最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當前指針指向的下一個元素，然后將當前節(jié)點元素的指針反轉后，利用已經存儲的指針往后面繼續(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;

　　}

　　還有一種利用遞歸的方法。這種方法的基本思想是在反轉當前節(jié)點之前先調用遞歸函數反轉后續(xù)節(jié)點。源代碼如下。不過這個方法有一個缺點，就是在反轉后的最后一個結點會形成一個環(huán)，所以必須將函數的返回的節(jié)點的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 ;

　　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; //刪除原來的數據，新開一塊內存

　　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)，對應用的操作與對變量直接操作效果完全相同。申明一個引用的時候，切記要對其進行初始化。引用聲明完畢后，相當于目標變量名有兩個名稱，即該目標原名稱和引用名，不能再把該引用名作為其他變量名的別名。聲明一個引用，不是新定義了一個變量，它只表示該引用名是目標變量名的一個別名，它本身不是一種數據類型，因此引用本身不占存儲單元，系統也不給引用分配存儲單元。不能建立數組的引用。