數(shù)據(jù)結構與算法面試題80道-資料下載頁
2025-03-26 00:52本頁面
【正文】 身，A為1，J為11，Q為12，K為13，而大小王可以看成任意數(shù)字。把n個骰子扔在地上，所有骰子朝上一面的點數(shù)之和為S。輸入n，打印出S的所有可能的 出現(xiàn)的概率。題目:輸入一個正整數(shù)數(shù)組，將它們連接起來排成一個數(shù)，輸出能排出的所有數(shù)字中最小的一個。例如輸入數(shù)組{32,321}，則輸出這兩個能排成的最小數(shù)字32132。請給出解決問題的算法，并證明該算法。分析:這是09年6月份百度的一道面試題，從這道題我們可以看出百度對應聘者在算法方面有很高的要求。題目:把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉。輸入一個排好序的數(shù)組的一個旋轉，輸出旋轉數(shù)組的最小元素。例如數(shù)組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個旋轉，該數(shù)組的最小 為1。分析:這道題最直觀的解法并不難。從頭到尾遍歷數(shù)組一次，就能找出最小的元素，時間復雜度顯然是O(N)。但這個思路沒有利用輸入數(shù)組的特性，我們應該能找到更好的解法。ANSWER 簡單的回溯就可以實現(xiàn)了。當然排列的產生也有很多種算法，去看看組合數(shù)學，還有逆序生成排列和一些不需要遞歸生成排列的方法。印象中Knuth的TAOCP第一卷里面深入講了排列的生成。這些算法的理解需要一定的數(shù)學功底，也需要一定的靈感，有興趣最好看看。 的整數(shù)次方。題目:實現(xiàn)函數(shù)double Power(double base, int exponent)，求base的exponent次方。不需要考慮溢出。分析:這是一道看起來很簡單的問題?？赡苡胁簧俚娜嗽诳吹筋}目后30秒寫出如下的代碼:double Power(double base, int exponent){ double result = 。 for(int i = 1。 i = exponent。 ++i) result *= base。 return result。}72.題目:設計一個類，我們只能生成該類的一個實例。分析:只能生成一個實例的類是實現(xiàn)了Singleton模式的類型。題目:輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。比如輸入字符串“google”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出4。分析:可能很多人都寫過判斷一個字符串是不是對稱的函數(shù)，這個題目可以看成是該函數(shù)的加強版。題目:數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組長度的一半，找出這個數(shù)字。分析:這是一道廣為流傳的面試題，包括百度、微軟和Google在內的多家公司都曾經采用過這個題目。要幾十分鐘的時間里很好地解答這道題，除了較好的編程能力之外，還需要較快的反應和較強的邏輯思維能力。題目:二叉樹的結點定義如下:struct TreeNode{ int m_nvalue。 TreeNode* m_pLeft。 TreeNode* m_pRight。}。輸入二叉樹中的兩個結點，輸出這兩個結點在數(shù)中最低的共同父結點。分析:求數(shù)中兩個結點的最低共同結點是面試中經常出現(xiàn)的一個問題。這個問題至少有兩個變種。題目:有一個復雜鏈表，其結點除了有一個m_pNext指針指向下一個結點外，還有一個m_pSibling指向鏈表中的任一結點或者NULL。其結點的C++定義如下:struct ComplexNode{ int m_nValue。 ComplexNode* m_pNext。 ComplexNode* m_pSibling。}。下圖是一個含有5個結點的該類型復雜鏈表。圖中實線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。為簡單起見，指向NULL的指針沒有畫出。請完成函數(shù)ComplexNode* Clone(ComplexNode* pHead)，以復制一個復雜鏈表。分析:在常見的數(shù)據(jù)結構上稍加變化，這是一種很新穎的面試題。要在不到一個小時的時間里解決這種類型的題目，我們需要較快的反應能力，對數(shù)據(jù)結構透徹的理解以及扎實的編程功底。:，檢測是否有環(huán)。使用兩個指針p1,p2從鏈表頭開始遍歷，p1每次前進一步，p2每次前進兩步。如果p2到達鏈表尾部，說明無環(huán)，否則pp2必然會在某個時刻相遇(p1==p2)，從而檢測到鏈表中有環(huán)。(head1, head2)，檢測兩個鏈表是否有交點，如果有返回第一個交點。如果head1==head2，那么顯然相交，直接返回head1。否則，分別從head1,head2開始遍歷兩個鏈表獲得其長度len1與len2，假設len1=len2，那么指針p1由head1開始向后移動len1len2步，指針p2=head2，下面pp2每次向后前進一步并比較p1p2是否相等，如果相等即返回該結點，否則說明兩個鏈表沒有交點。(head)，如果有環(huán)的話請返回從頭結點進入環(huán)的第一個節(jié)點。運用題一，我們可以檢查鏈表中是否有環(huán)。如果有環(huán)，那么p1p2重合點p必然在環(huán)中。從p點斷開環(huán)，方法為:p1=p, p2=pnext, pnext=NULL。此時，原單鏈表可以看作兩條單鏈表，一條從head開始，另一條從p2開始，于是運用題二的方法，我們找到它們的第一個交點即為所求。(并非最后一個結點，即pnext!=NULL)指針，刪除該結點。辦法很簡單，首先是放p中數(shù)據(jù),然后將pnext的數(shù)據(jù)copy入p中，接下來刪除pnext即可。(非空結點)，在p前面插入一個結點。辦法與前者類 ，首先分配一個結點q，將q插入在p后，接下來將p中的數(shù)據(jù)copy入q中，然后再將要插入的數(shù)據(jù)記錄在p中。?分析:主要在基本概念上的理解。但是最好能考慮的全面一點，現(xiàn)在公司招人的競爭可能就在細節(jié)上產生，誰比較仔細，誰獲勝的機會就大。79.。說明為什么你會選擇用這樣的方法?。說明為什么你會選擇用這樣的方法?()函數(shù)功能的代碼。問題描述:12個高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對應的第一排的人高,問排列方式有多少種?這個筆試題,很YD,因為把某個遞歸關系隱藏得很深。
畢業(yè)設計相關推薦
鄂ICP備17016276號-1