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

1、第3章 鏈表3.4 堆棧(duzhn)的實(shí)現(xiàn)說明：請對堆棧這種數(shù)據(jù)結(jié)構(gòu)(sh j ji u)做出評論。用C+語言來實(shí)現(xiàn)一個堆棧，你可以選用鏈表或動態(tài)數(shù)組來實(shí)現(xiàn)你的堆棧；并請對你的決定做出解釋。你為堆棧設(shè)計(jì)的程序接口必須完備(wnbi)、規(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

2、;delete p;isize = 0;void 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;templa

3、teclass Stackstruct NodeType 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 = ph

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

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

6、) return ret; if(elem=head) if(head=tail) head=(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 Inse

7、rtAfter(element* elem, int data) int ret = 0; 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-ne

8、xt; p1-next = p; ret = 1; return ret;3.6 對RemoveHead函數(shù)進(jìn)行(jnxng)糾錯說明(shumng)：下面是一個用來刪除單向鏈表的頭元素的函數(shù)。請找出其中的程序漏洞并加以糾正。void RemoveHead(node *head)free(head);head = head-next;解答(jid)：void RemoveHead(node *&head)if(head=NULL) return;node* p = head;head = head-next;free(p);3.7 鏈表中的倒數(shù)第m個元素說明：給定一個單向鏈表，請?jiān)O(shè)計(jì)一個既節(jié)省

9、時間又節(jié)省空間的算法來找出該鏈表中的倒數(shù)第m個元素。實(shí)現(xiàn)這個算法，并為可能出現(xiàn)的特例情況安排好處理措施?！暗箶?shù)第m個元素”是這樣規(guī)定的：當(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、除固有的后指針和前指針外，還有子指針，每個子指針可能指向也可能不指向另一個雙向鏈表。而那些子雙向鏈表本身(bnshn)還可能有一個或者多個子雙向鏈表，從而形成一種多層次的數(shù)據(jù)結(jié)構(gòu)，如圖所示：對這個鏈表進(jìn)行扁平化，使全體節(jié)點(diǎn)都出現(xiàn)在一個只有一個層次的雙向鏈表里。已知條件只有原多層次雙向鏈表的第一層次的頭指針(zhzhn)和尾指針。下面是各節(jié)點(diǎn)的+語言(yyn)struct定義：struct nodenode *next;node *prev;node *child;int value; ;void ExpandList(node* pnode)while(pnode!=NULL)if(pnode

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

12、l:set:iterator, bool pl;pl = pset.insert(p);while(p-next!=NULL)p=p-next;pl = pset.insert(p);if(pl.second=false) return true;return false;第4章 樹和圖4.3 二叉樹：左遍歷(bin l)可使用(shyng)遞歸。4.4 二叉樹：左遍歷(bin l)，不使用遞歸使用堆棧緩存子節(jié)點(diǎn)。4.5 二叉樹：最低公共祖先找出根節(jié)點(diǎn)到子節(jié)點(diǎn)的路徑數(shù)組，兩個數(shù)組中最后一個相同的節(jié)點(diǎn)就是最低公共(gnggng)祖先。第5章 數(shù)組與字符串5.3 第一個無重復(fù)(chngf)字符（1

13、）以字母(zm)為Key建立hash數(shù)組，第一遍+hash數(shù)組，第二遍找數(shù)組為1的字母，O（2n）；（2）從首字母開始，判斷其是否還有相同字母，類似排序，O(n2)5.4 刪除特定字符對remove建立hash數(shù)組，字符為key；遍歷str字符串，如果字符在remove中則不拷貝，否則拷貝前移。效率在O（n+m）。5.5 顛倒單詞的出現(xiàn)順序?qū)ψ址M(jìn)行(jnxng)反向遍歷，找到空格則復(fù)制單詞。5.6 整數(shù)(zhngsh)/字符串之間的轉(zhuǎn)換主要是判斷+-號和計(jì)算(j sun)字符串長度，其他好做。第6章 遞歸算法6.1 二分法搜索6.2 字符串的全排列6.3 字符串的全組合(zh)6.4 電話

14、(dinhu)鍵單詞第7章 其他程序設(shè)計(jì)(chn x sh j)問題7.5 繪制八分之一圓形7.6 矩形是否(sh fu)重疊7.7 字節(jié)(z ji)的升序存儲和降序存儲方式7.8 “1”的個數(shù)7.9 簡單(jindn)的SQL查詢7.10 公司(n s)和員工數(shù)據(jù)庫7.11 最大值，不允許(ynx)使用統(tǒng)計(jì)功能7.12 生產(chǎn)者/消費(fèi)者問題(wnt)第8章 與技術(shù)(jsh)、測量、排序有關(guān)的智力題8.1 開鎖ANS: take an example of 10, emulate the open and close, and then find the rule.You will find t

15、hat 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)(kigun)ANS: you need to touch the lamp. Firstly open the lamp for 1minute, then closed it, and open the next one. You should go to the room and touch the closed lamp to determine which the first

16、 warm lamp is.8.3 過橋(u qio)ANS: (2+1)(1)(5+10)(2)(2+1)=178.4 找石頭(sh tou)ANS: 3 3 2第9章 與圖形和空間(kngjin)有關(guān)的智力題9.1 船和碼頭ANS: 繩子rope9.2 數(shù)方塊ANS: 3*3*3-1*1*1=8ANS: 4*4*4-2*2*2 = 569.3 狐貍(h li)與鴨子ANS: the duck could fly.9.4 導(dǎo)火索ANS: burn wire1 from 2 endpoint and burn wire2 from 1 endpoint meanwhile,When the w

17、ire1 burn out, burn wire2 the other endpoint.It will spend 45 minutes when the wire2 burn out.9.5 躲火車(huch)ANS: 第10章 計(jì)算機(jī)基礎(chǔ)知識10.3 C+和Java10.4 頭文件10.5 C存儲(cn ch)類別10.6 Friend類10.7 類與結(jié)構(gòu)(jigu)的區(qū)別10.8 父類與子類10.9 參數(shù)傳遞10.10 宏與Inline函數(shù)(hnsh)10.11 繼承(jchng)10.12 面向?qū)ο蟮某绦蛟O(shè)計(jì)(chn x sh j)10.13 與線程有關(guān)的程序設(shè)計(jì)問題10.14 廢棄內(nèi)存的自動回收10.15 32位操作系統(tǒng)(co zu x tn)10.16 網(wǎng)絡(luò)(wnglu)性能10.17 高速(o s)磁盤緩存10.18 數(shù)據(jù)庫的優(yōu)點(diǎn)10.19 加密技術(shù)10.20 新的加密算法10.21 哈希表與二元搜索樹第11章 非技術(shù)問題11.2 你打算從事(cngsh)哪方面的工作？11.3 你最喜歡的程序設(shè)計(jì)語言(yyn)是哪一種？11.4 你的工作習(xí)慣(xgun)是怎樣的