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 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;

　　}

　　還有一種利用遞歸的方法。這種方法的基本思想是在反轉當前節點之前先調用遞歸函數反轉后續節點。源代碼如下。不過這個方法有一個缺點，就是在反轉后的最后一個結點會形成一個環，所以必須將函數的返回的節點的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)，對應用的操作與對變量直接操作效果完全相同。申明一個引用的時候，切記要對其進行初始化。引用聲明完畢后，相當于目標變量名有兩個名稱，即該目標原名稱和引用名，不能再把該引用名作為其他變量名的別名。聲明一個引用，不是新定義了一個變量，它只表示該引用名是目標變量名的一個別名，它本身不是一種數據類型，因此引用本身不占存儲單元，系統也不給引用分配存儲單元。不能建立數組的引用。