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

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

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

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

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

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

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

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

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

　　在頭文件Man.h中

　　….

　　Class Cman

　　{

　　….

　　CFace m_face;

　　};

　　….

　　在頭文件Face.h中

　　…

　　Class CFace

　　{

　　…

　　Cman m_owner;

　　};

　　….

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

　　1.#ifndef ….

　　#define …..

　　2.類的前向聲明

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

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

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

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

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

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

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

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

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

　　使用一個已經(jīng)初始化的巨大的全局數(shù)組

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

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

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

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

　　HASH.HASH訪問速度較快.

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

　　strncpy

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

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

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

　　使用select

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

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

　　最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當(dāng)前指針指向的下一個元素，然后將當(dāng)前節(jié)點元素的指針反轉(zhuǎn)后，利用已經(jīng)存儲的指針往后面繼續(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ào)用遞歸函數(shù)反轉(zhuǎn)后續(xù)節(jié)點。源代碼如下。不過這個方法有一個缺點，就是在反轉(zhuǎn)后的最后一個結(jié)點會形成一個環(huán)，所以必須將函數(shù)的返回的節(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); // 通用構(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ù)實現(xiàn)。

　　答案：

　　String::String(const char str)

　　{

　　if ( str == NULL ) //strlen在參數(shù)為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; //刪除原來的數(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進制，看含有的1的個數(shù)。

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

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