【導(dǎo)讀】思路：將x轉(zhuǎn)化為2進(jìn)制，看含有的1的個(gè)數(shù)。申明和使用“引用”要注意哪些問題？申明一個(gè)引用的時(shí)候，切記要對(duì)其進(jìn)行初始化。引用聲明完畢后，相當(dāng)于目標(biāo)變量名有兩個(gè)名稱，引用本身不占存儲(chǔ)單元，系統(tǒng)也不給引用分配存儲(chǔ)單元。不能建立數(shù)組的引用。傳遞引用給函數(shù)與傳遞指針的效果是一樣的。這時(shí)，被調(diào)函數(shù)的形參就成為原來主調(diào)函數(shù)。量的副本；如果傳遞的是對(duì)象，還將調(diào)用拷貝構(gòu)造函數(shù)。因此，當(dāng)參數(shù)傳遞的數(shù)據(jù)較大時(shí)，用引。引用型參數(shù)應(yīng)該在能被定義為const的情況下，盡量定義為const。變量會(huì)在函數(shù)返回后被銷毀，因此被返回的引用就成為了"無所指"的引用，程序會(huì)進(jìn)入未知狀態(tài)。又面臨其它尷尬局面。例如，被函數(shù)返回的引用只是作為一個(gè)臨時(shí)變量出現(xiàn)，而沒有被賦予一。主要原因是這四個(gè)操作符沒有sideeffect，

　　

【正文】 e *next 。 }。 typedef struct Node Node 。 (1)已知鏈表的頭結(jié)點(diǎn) head,寫一個(gè)函數(shù)把這個(gè)鏈表逆序 ( Intel) Node * ReverseList(Node *head) //鏈表逆序 { if ( head == NULL || headnext == NULL ) return head。 Node *p1 = head 。 Node *p2 = p1next 。 Node *p3 = p2next 。 p1next = NULL 。 while ( p3 != NULL ) { p2next = p1 。 p1 = p2 。 p2 = p3 。 p3 = p3next 。 } p2next = p1 。 head = p2 。 return head 。 } (2)已知兩個(gè)鏈表 head1 和 head2 各自有序，請(qǐng)把它們合并成一個(gè)鏈表依然有序。 (保留所有結(jié)點(diǎn)，即便大小相同） Node * Merge(Node *head1 , Node *head2) { if ( head1 == NULL) return head2 。 if ( head2 == NULL) return head1 。 Node *head = NULL 。 Node *p1 = NULL。 Node *p2 = NULL。 if ( head1data head2data ) { head = head1 。 p1 = head1next。 p2 = head2 。 } else { head = head2 。 p2 = head2next 。 p1 = head1 。 } Node *pcurrent = head 。 while ( p1 != NULL amp。amp。 p2 != NULL) { if ( p1data = p2data ) { pcurrentnext = p1 。 pcurrent = p1 。 p1 = p1next 。 } else { pcurrentnext = p2 。 pcurrent = p2 。 p2 = p2next 。 } } if ( p1 != NULL ) pcurrentnext = p1 。 if ( p2 != NULL ) pcurrentnext = p2 。 return head 。 } (3)已知兩個(gè)鏈表 head1 和 head2 各自有序，請(qǐng)把它們合并成一個(gè)鏈表依然有序，這次要求用遞歸方法進(jìn)行。 (Autodesk) 答案： Node * MergeRecursive(Node *head1 , Node *head2) { if ( head1 == NULL ) return head2 。 if ( head2 == NULL) return head1 。 Node *head = NULL 。 if ( head1data head2data ) { head = head1 。 headnext = MergeRecursive(head1next,head2)。 } else { head = head2 。 headnext = MergeRecursive(head1,head2next)。 } return head 。 } 41. 分析一下這段程序的輸出 (Autodesk) class B { public: B() { coutdefault constructorendl。 } ~B() { coutdestructedendl。 } B(int i):data(i) //B(int) works as a converter ( int instance of B) { coutconstructed by parameter data endl。 } private: int data。 }。 B Play( B b) { return b 。 } (1) results: int main(int argc, char* argv[]) constructed by parameter 5 { destructed B(5)形參 析構(gòu) B t1 = Play(5)。 B t2 = Play(t1)。 destructed t1形參析構(gòu) return 0。 destructed t2 注意順序！ } destructed t1 (2) results: int main(int argc, char* argv[]) constructed by parameter 5 { destructed B(5)形參 析構(gòu) B t1 = Play(5)。 B t2 = Play(10)。 constructed by parameter 10 return 0。 destructed B(10)形參 析構(gòu) } destructed t2 注意順序！ destructed t1 42. 寫一個(gè)函數(shù)找出一個(gè)整數(shù)數(shù)組中，第二大的數(shù) （ microsoft） 答案： const int MINNUMBER = 32767 。 int find_sec_max( int data[] , int count) { int maxnumber = data[0] 。 int sec_max = MINNUMBER 。 for ( int i = 1 。 i count 。 i++) { if ( data[i] maxnumber ) { sec_max = maxnumber 。 maxnumber = data[i] 。 } else { if ( data[i] sec_max ) sec_max = data[i] 。 } } return sec_max 。 } 43. 寫一個(gè)在一個(gè)字符串 (n)中尋找一個(gè)子串 (m)第一個(gè)位置的函數(shù)。 KMP算法效率最好，時(shí)間復(fù)雜度是Ｏ (n+m)。 44. 多 重繼承的內(nèi)存分配問題： 比如有 class A : public class B, public class C {} 那么 A 的內(nèi)存結(jié)構(gòu)大致是怎么樣的？ 這個(gè)是 pilerdependent的 , 不同的實(shí)現(xiàn)其細(xì)節(jié)可能不同。 如果不考慮有虛函數(shù)、虛繼承的話就相當(dāng)簡單；否則的話，相當(dāng)復(fù)雜。 可以參考《深入探索 C++對(duì)象模型》，或者： 45. 如何判斷一個(gè)單鏈表是有環(huán)的？（注意不能用標(biāo)志位，最多只能用兩個(gè)額外指針） struct node { char val。 node* next。} bool check(const node* head) {} //return false : 無環(huán)； true: 有環(huán) 一種 O（ n）的辦法就是（搞兩個(gè)指針，一個(gè)每次遞增一步，一個(gè)每次遞增兩步，如果有環(huán)的話兩者必然重合，反之亦然）： bool check(const node* head) { if(head==NULL) return false。 node *low=head, *fast=headnext。 while(fast!=NULL amp。amp。 fastnext!=NULL) { low=lownext。 fast=fastnextnext。 if(low==fast) return true。 } return false。 }