程序員面試寶典(C++例題)

1、第3章 鏈表3.4 堆棧的實現(xiàn)說明：請對堆棧這種數(shù)據(jù)結(jié)構(gòu)做出評論。用C+語言來實現(xiàn)一個堆棧，你可以選用鏈表或動態(tài)數(shù)組來實現(xiàn)你的堆棧；并請對你的決定做出解釋。你為堆棧設(shè)計的程序接口必須完備、規(guī)范、和易于使用。解答：堆棧是一種先入后出、后入先出的數(shù)據(jù)結(jié)構(gòu)。class IntStackstruct Nodeint idata;Node* pnext;public:IntStack ():isize(0),phead(NULL) IntStack ()while(phead!=NULL)Node*p = phead;phead = phead-pnext;delete p;isize = 0;void

2、 Push(int i)Node* p = new Node;p-idata = i;p-pnext = phead;phead = p;+isize;bool Pop(int& iout) bool ret = false;if(isize0)iout = phead-idata;Node* p = phead;phead = phead-pnext;delete p;-isize; ret = true;return ret;int Size()return isize;private:int isize;Node* phead;templateclass Stackstruct Node

3、Type idata;Node* pnext;public:Stack():isize(0),phead(NULL)Stack()while(phead!=NULL)Node*p = phead;phead = phead-pnext;delete p;isize = 0;void Push(Type& i)Node* p = new Node;p-idata = i;p-pnext = phead;phead = p;+isize;bool Pop(Type& tout) bool ret = false;if(isize0)tout = phead-idata;Node* p = phea

4、d;phead = phead-pnext;delete p;-isize; ret = true; return ret;int Size()return isize;private:int isize;Node* phead;3.5 鏈表的尾指針說明：有一個單向鏈表，它的元素全都是些整數(shù)。head和tail分別指向該鏈表第一個元素（即頭元素）和最后一個元素（即尾元素）的全局性指針。請實現(xiàn)調(diào)用接口如下所示的兩個C語言函數(shù)：int Delete(element *elem);int InsertAfter(element *elem, int data);Delete函數(shù)只有一個輸入?yún)?shù)，他就

5、是那個將被刪除的元素。InsertAfter函數(shù)由兩個輸入?yún)?shù)，第二個輸入?yún)?shù)給出了新元素的取值，它將被插入到第一個輸入?yún)?shù)所指定的元素的后面。當(dāng)需要把新元素插入到鏈表的開頭作為新的頭元素時，函數(shù)InsertAfter的第一個輸入?yún)?shù)（即被聲明為element類型的那個輸入?yún)?shù)）將被設(shè)置為NULL。如果執(zhí)行成功，這兩個函數(shù)將返回“1”；如果不成功，將返回“0”。element *head, *tail;int Delete(element* elem) int ret = 0; if(elem=NULL) return ret; if(elem=head) if(head=tail) head

6、=(tail=NULL); else head = head-next; delete elem; ret = 1; return ret; element* p0=NULL,*p1 = head; while(p1!=NULL) if(p1=elem) break; else p0 = p1; p1 = p1-next; if(p1!=NULL) p0-next = p1-next; delete p1; ret = 1; return ret;element *head,*tail;int InsertAfter(element* elem, int data) int ret = 0;

7、element *p = new element; p-data = data; p-next = NULL; if(elem=NULL) if(head=NULL) head = (tail=p); else p-next = head; head = p; ret = 1; return ret; else element* p1=head; while(p1!=NULL) if(p1=elem) break; else p1=p1-next; if(p1!=NULL) p-next = p1-next; p1-next = p; ret = 1; return ret;3.6 對Remo

8、veHead函數(shù)進行糾錯說明：下面是一個用來刪除單向鏈表的頭元素的函數(shù)。請找出其中的程序漏洞并加以糾正。void RemoveHead(node *head)free(head);head = head-next;解答：void RemoveHead(node *&head)if(head=NULL) return;node* p = head;head = head-next;free(p);3.7 鏈表中的倒數(shù)第m個元素說明：給定一個單向鏈表，請設(shè)計一個既節(jié)省時間又節(jié)省空間的算法來找出該鏈表中的倒數(shù)第m個元素。實現(xiàn)這個算法，并為可能出現(xiàn)的特例情況安排好處理措施?！暗箶?shù)第m個元素”是這樣規(guī)定

9、的：當(dāng)m=0時，鏈表的最后一個元素（尾元素）將被返回。解答：node* FindInvM(node* head, int m)if(head=NULL) return NULL;node* pm=head,*p=head;int ipm=0;while(p-next!=NULL)p = p-next;if(ipmnext;if(ipm=m) return pm;else return NULL;3.8 鏈表的扁平化說明：給定一個雙向鏈表。這個雙向鏈表中的每一個元素除固有的后指針和前指針外，還有子指針，每個子指針可能指向也可能不指向另一個雙向鏈表。而那些子雙向鏈表本身還可能有一個或者多個子雙向鏈

10、表，從而形成一種多層次的數(shù)據(jù)結(jié)構(gòu)，如圖所示：對這個鏈表進行扁平化，使全體節(jié)點都出現(xiàn)在一個只有一個層次的雙向鏈表里。已知條件只有原多層次雙向鏈表的第一層次的頭指針和尾指針。下面是各節(jié)點的+語言struct定義：struct nodenode *next;node *prev;node *child;int value; ;void ExpandList(node* pnode)while(pnode!=NULL)if(pnode-child!=NULL)node* p0=pnode-child,*p1=p0;while(p1-next!=NULL) p1 = p1-next;node*pp1 =

11、 pnode-next;pnode-next = p0; p1-next = pp1;if(pp1!=NULL) pp1-prev = p1; p0-prev = pnode;pnode = pnode-next;3.9 空鏈表與循環(huán)鏈表bool IsLoopLink(node* head)node* p = head;if(p=NULL) return false;stl:set pset;stl:pairstl:set:iterator, bool pl;pl = pset.insert(p);while(p-next!=NULL)p=p-next;pl = pset.insert(p);

12、if(pl.second=false) return true;return false;第4章 樹和圖4.3 二叉樹：左遍歷可使用遞歸。4.4 二叉樹：左遍歷，不使用遞歸使用堆棧緩存子節(jié)點。4.5 二叉樹：最低公共祖先找出根節(jié)點到子節(jié)點的路徑數(shù)組，兩個數(shù)組中最后一個相同的節(jié)點就是最低公共祖先。第5章 數(shù)組與字符串5.3 第一個無重復(fù)字符（1）以字母為Key建立hash數(shù)組，第一遍+hash數(shù)組，第二遍找數(shù)組為1的字母，O（2n）；（2）從首字母開始，判斷其是否還有相同字母，類似排序，O(n2)5.4 刪除特定字符對remove建立hash數(shù)組，字符為key；遍歷str字符串，如果字符在rem

13、ove中則不拷貝，否則拷貝前移。效率在O（n+m）。5.5 顛倒單詞的出現(xiàn)順序?qū)ψ址M行反向遍歷，找到空格則復(fù)制單詞。5.6 整數(shù)/字符串之間的轉(zhuǎn)換主要是判斷+-號和計算字符串長度，其他好做。第6章 遞歸算法6.1 二分法搜索6.2 字符串的全排列6.3 字符串的全組合6.4 電話鍵單詞第7章 其他程序設(shè)計問題7.5 繪制八分之一圓形7.6 矩形是否重疊7.7 字節(jié)的升序存儲和降序存儲方式7.8 “1”的個數(shù)7.9 簡單的SQL查詢7.10 公司和員工數(shù)據(jù)庫7.11 最大值，不允許使用統(tǒng)計功能7.12 生產(chǎn)者/消費者問題第8章 與技術(shù)、測量、排序有關(guān)的智力題8.1 開鎖ANS: take a

14、n example of 10, emulate the open and close, and then find the rule.You will find that all the opened number is a square number, so the opened number is:1,4,9,16,25,36,49,64,81,100.8.2 三個開關(guān)ANS: you need to touch the lamp. Firstly open the lamp for 1minute, then closed it, and open the next one. You

15、should go to the room and touch the closed lamp to determine which the first warm lamp is.8.3 過橋ANS: (2+1)(1)(5+10)(2)(2+1)=178.4 找石頭ANS: 3 3 2第9章 與圖形和空間有關(guān)的智力題9.1 船和碼頭ANS: 繩子rope9.2 數(shù)方塊ANS: 3*3*3-1*1*1=8ANS: 4*4*4-2*2*2 = 569.3 狐貍與鴨子ANS: the duck could fly.9.4 導(dǎo)火索ANS: burn wire1 from 2 endpoint and

16、burn wire2 from 1 endpoint meanwhile,When the wire1 burn out, burn wire2 the other endpoint.It will spend 45 minutes when the wire2 burn out.9.5 躲火車ANS: 第10章 計算機基礎(chǔ)知識10.3 C+和Java10.4 頭文件10.5 C存儲類別10.6 Friend類10.7 類與結(jié)構(gòu)的區(qū)別10.8 父類與子類10.9 參數(shù)傳遞10.10 宏與Inline函數(shù)10.11 繼承10.12 面向?qū)ο蟮某绦蛟O(shè)計10.13 與線程有關(guān)的程序設(shè)計問題10.14 廢棄內(nèi)存的自動回收10.1