IT軟件開發(fā)筆試面試題

1、計算機筆試 / 面試題【字符串】1 、輸入一個字符串，打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc ，則輸出由字符a、b 、c 所能排列出來的所有字符串bca 、 cab 和 cba 。abc、acb、bac、2 、有一個由大小寫組成的字符串，現(xiàn)在需要對他進(jìn)行修改，將其中的所有小寫字母排在大寫字母的前面（大寫或小寫字母之間不要求保持原來次序），如有可能盡量選擇時間和空間效率高的算法。c 語言函數(shù)原型void proc（ char *str），也可以采用你自己熟悉的語言。3 、編寫反轉(zhuǎn)字符串的程序，要求優(yōu)化速度、優(yōu)化空間。4 、用C 語言實現(xiàn)函數(shù)void * memmove(void *

2、dest, const void *src, size_t n)。memmove函數(shù)的功能是拷貝src所指的內(nèi)存內(nèi)容前n 個字節(jié)到dest所指的地址上。分析：由于可以把任何類型的指針賦給 void 類型的指針，這個函數(shù)主要是實現(xiàn)各種數(shù)據(jù)類型的拷貝。5 、編程找出兩個字符串中最大公共子字符串,如 "abccade", "dgcadde"的最大子串為"cad" 。6 、輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。比如輸入字符串"google"，由于該字符串里最長的對稱子字符串是"goog"

3、;，因此輸出4 。7 、字符串原地壓縮。題目描述：“ eeeeeaaaff"壓縮為"e5a3f2"，請編程實現(xiàn)。8 、請以回溯與不回溯算法實現(xiàn)字符串匹配。9 、輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開。為簡單起見，標(biāo)點符號和普通字母一樣處理。例如：輸入 "I am a student." ，則輸出"student. a am I"。10 、在一個字符串中找到第一個只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b 。11 、寫一個函數(shù)，它的原形是int continumax(c

4、har *outputstr,char *intputstr)功能：在字符串中找出連續(xù)最長的數(shù)字串，并把這個串的長度返回，并把這個最長數(shù)字串付給其中一個函數(shù)參數(shù)outputstr所指內(nèi)存。例如： "abcd12345ed125ss"的首地址傳給intputstr后，函數(shù)將返回9 ， outputstr指的值為。所12 、定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個字符移動到字符串的尾部。如：把字符串a(chǎn)bcdef左旋轉(zhuǎn) 2 位得到字符串cdefab。請實現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。要求時間對長度為n 的字符串操作的復(fù)雜度為O(n) ，輔助內(nèi)存為O(1) 。13 、有n個長為m+1的

5、字符串，如果某個字符串的最后m 個字符與某個字符串的前m 個字符匹配，則兩個字符串可以聯(lián)接。問這 n 個字符串最多可以連成一個多長的字符串，如果出現(xiàn)循環(huán)，則返回錯誤。14 、如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。請編寫一個函數(shù)，輸入兩個字符串，求它們的最長公共子串，并打印出最長公共子串。例如：輸入兩個字符串 BDCABA 和 ABCBDAB ，字符串 BCBA 和 BDAB 都是是它們的最長公共子串，則輸出它們的長度4 ，并打印任意一個子串。分析：求最長公共子串（Long

6、est Common Subsequence, LCS）是一道非常經(jīng)典的動態(tài)規(guī)劃題。15 、輸入兩個字符串，從第一字符串中刪除第二個字符串中所有的字符。例如，輸入 "They are students."和 "aeiou"，則刪除之后的第一個字符串變成"Thy rstdnts." 。16、一個文件，內(nèi)含一千萬行字符串，每個字符串在1K以內(nèi)，要求找出所有相反的串對，如abc 和 cba 。17、給出一個函數(shù)來復(fù)制兩個字符串A 和 B 。字符串 A 的后幾個字節(jié)和字符串B 的前幾個字節(jié)重疊。18、已知一個字符串，比如asderwsde,

7、尋找其中的一個子字符串比如sde的個數(shù)，如果沒有返回 0 ，有的話返回子字符串的個數(shù)。19、求最大連續(xù)遞增數(shù)字串（如"ads3slDF3456ld345AA"中的 "" ）。20、實現(xiàn) strstr 功能，即在父串中尋找子串首次出現(xiàn)的位置。21 、編碼完成下面的處理函數(shù)。函數(shù)將字符串中的字符'*' 移到串的前部分，前面的非'*' 字符后移， 但不能改變非'*' 字符的先后順序，函數(shù)返回串中字符'*' 的數(shù)量。如原始串為：ab*cd*e*12，處理后為 *abcde12，函數(shù)并返回值為5。（要

8、求使用盡量少的時間和輔助空間）22 、刪除字符串中的數(shù)字并壓縮字符串。如字符串” abc123de4fg56處”理后變?yōu)椤?abcdefg?！弊⒁饪臻g和效率。23 、求兩個串中的第一個最長子串的最大子串為"actyet"。（神州數(shù)碼以前試題）。如 "abractyeyt"，"dgdsaeactyey"【棧、鏈表、樹、圖】1 、編寫一個程序，把一個有序整數(shù)數(shù)組放到二叉樹中。2 、編程實現(xiàn)從頂部開始逐層打印二叉樹節(jié)點數(shù)據(jù)。 參考 3 、編程實現(xiàn)單鏈表逆轉(zhuǎn)。4、設(shè)計一個算法，找出二叉樹上任意兩個結(jié)點的最近共同父結(jié)點。復(fù)雜度不能為O(n2)

9、。5、二叉排序樹中，令f = ( 最大值 + 最小值 ) / 2，設(shè)計一個算法，找出距離f 值最近、大于 f值的結(jié)點。復(fù)雜度不能為O(n2) 。6 、有雙向循環(huán)鏈表結(jié)點定義為： struct nodeint data;struct node *front,*next;有兩個雙向循環(huán)鏈表 A ，B ，知道其頭指針為： pHeadA 、pHeadB ，請寫一函數(shù)將兩鏈表中 data 值相同的結(jié)點刪除。7 、輸入一個鏈表的頭結(jié)點，從尾到頭反過來輸出每個結(jié)點的值。鏈表結(jié)點定義如下：struct ListNodeintm_nKey;ListNode* m_pNext;8 、輸入一棵二元查找樹，將該二元查

10、找樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。10/ 6 14/481216轉(zhuǎn)換成雙向鏈表4=6=8=10=12=14=16首先我們定義的二元查找樹。節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：struct BSTreeNodeint m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nodeBSTreeNode *m_pRight; / right child of node;參考9 、設(shè)計包含min函數(shù)的棧。定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min函數(shù)，能夠得到棧的最小元素。要求函數(shù)min 、 push以及 pop的

11、時間復(fù)雜度都是O(1) 。10 、輸入一個整數(shù)和一棵二元樹。從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所經(jīng)過的所有結(jié)點形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。例如輸入整數(shù)22 和如下二元樹10/ 5 12/ 47則打印出兩條路徑： 10, 12和 10,5,7 。二元樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義為：struct BinaryTreeNode / a node in the binary treeint m_nValue; / value of nodeBinaryTreeNode *m_pLeft; / left child of nodeBinaryTreeNode *m_pRight; / ri

12、ght child of node;11 、給出倆個單向鏈表的頭指針，比如h1 ， h2 ，判斷這倆個鏈表是否相交。為了簡化問題，我們假設(shè)倆個鏈表均不帶環(huán)。問題擴展：(1) 如果鏈表可能有環(huán)列 ?(2) 如果需要求出倆個鏈表相交的第一個節(jié)點列?12 、輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。如果是返回 true ，否則返回 false 。例如輸入 5 、 7 、 6 、 9、 11 、 10 、 8 ，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果：8/ 6 10/ / 57 911因此返回true。如果輸入7 、 4 、 6 、 5，沒有哪棵樹的后序遍歷的結(jié)果是這個序列，因此

13、返回false。13 、如果我們把二叉樹看成一個圖，父子節(jié)點之間的連線看成是雙向的，我們姑且定義"距離"為兩節(jié)點之間邊的個數(shù)。寫一個程序，求一棵二叉樹中相距最遠(yuǎn)的兩個節(jié)點之間的距離。14 、輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k 個結(jié)點。鏈表的倒數(shù)第0 個結(jié)點為鏈表的尾指針。鏈表結(jié)點定義如下：struct ListNodeint m_nKey;ListNode* m_pNext;15 、輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點都大于右子樹的結(jié)點。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。例如輸入：8/ 610/57911輸出：8/ 106

14、/11 975定義二元查找樹的結(jié)點為：struct BSTreeNodeint m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nodeBSTreeNode *m_pRight; / right child of node; 參考 16 、求一個二叉樹中任意兩個節(jié)點間的最大距離，兩個節(jié)點的距離的定義是這兩個節(jié)點間邊的個數(shù)。比如某個孩子節(jié)點和父節(jié)點間的距離是1 ，和相鄰兄弟節(jié)點間的距離是2，優(yōu)化時間空間復(fù)雜度。17 、求一個有向連通圖的割點，割點的定義是，如果除去此節(jié)點和與其相關(guān)的邊，有向圖不再連通，描述算法。18 、設(shè)

15、計一個棧結(jié)構(gòu)，滿足一下條件：min ， push ， pop 操作的時間復(fù)雜度為 O(1) 。19 、請修改 append 函數(shù)，利用這個函數(shù)實現(xiàn)：兩個非降序鏈表的并集，1->2->3和 2->3->5并為1->2->3->5另外只能輸出結(jié)果，不能修改兩個鏈表的數(shù)據(jù)。20 、遞歸和非遞歸倆種方法實現(xiàn)二叉樹的前序遍歷。21 、輸入一棵二元樹的根結(jié)點，求該樹的深度。從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點（含根、葉結(jié)點）形成樹的一條路徑，最長路徑的長度為樹的深度。22 、用倆個棧實現(xiàn)隊列，某隊列的聲明如下：template<typename T> cla

16、ss CQueuepublic: CQueue() CQueue() void appendTail(const T& node); / append a element to tail void deleteHead(); / remove a element from headprivate:T m_stack1; T m_stack2;23 、給定鏈表的頭指針和一個結(jié)點指針，在O(1) 時間刪除該結(jié)點。鏈表結(jié)點的定義如下：struct ListNodeint m_nKey;ListNode* m_pNext;函數(shù)的聲明如下：void DeleteNode(ListNode* pL

17、istHead, ListNode*pToBeDeleted);24 、兩個單向鏈表，找出它們的第一個公共結(jié)點。鏈表的結(jié)點定義為：struct ListNodeintm_nKey;ListNode*m_pNext;25 、用遞歸顛倒一個棧。例如輸入棧1, 2, 3, 4, 5， 1 在棧頂。顛倒之后的棧為5, 4, 3, 2,1 ， 5 處在棧頂。26 、二叉樹的結(jié)點定義如下：struct TreeNodeint m_nvalue;TreeNode* m_pLeft;TreeNode* m_pRight;輸入二叉樹中的兩個結(jié)點，輸出這兩個結(jié)點在數(shù)中最低的共同父結(jié)點。27 、有一個復(fù)雜鏈表，其結(jié)

18、點除了有一個m_pNext指針指向下一個結(jié)點外，還有一個m_pSibling指向鏈表中的任一結(jié)點或者NULL 。其結(jié)點的C+定義如下：struct ComplexNodeint m_nValue;ComplexNode* m_pNext;ComplexNode* m_pSibling;下圖是一個含有5 個結(jié)點的該類型復(fù)雜鏈表。圖中實線箭頭表示 m_pNext 指針，虛線箭頭表示 m_pSibling 指針。為簡單起見，指向 NULL 的指針沒有畫出。請完成函數(shù)ComplexNode* Clone(ComplexNode* pHead)，以復(fù)制一個復(fù)雜鏈表。28 、給定單鏈表、檢測是否有環(huán)。29

19、 、給定兩個單鏈表 (head1, head2)，檢測兩個鏈表是否有交點，如果有返回第一個交點。30 、給定單鏈表 (head) ，如果有環(huán)的話請返回從頭結(jié)點進(jìn)入環(huán)的第一個節(jié)點。31 、只給定單鏈表中某個結(jié)點p( 并非最后一個結(jié)點，即 p->next!=NULL)指針，刪除該結(jié)點。32 、只給定單鏈表中某個結(jié)點p( 非空結(jié)點 ) ，在 p 前面插入一個結(jié)點。33 、編寫實現(xiàn)鏈表排序的一種算法。說明為什么你會選擇用這樣的方法？34 、編寫實現(xiàn)數(shù)組排序的一種算法。說明為什么你會選擇用這樣的方法？35 、怎樣編寫一個程序，把一個有序整數(shù)數(shù)組放到二叉樹中？【數(shù)組和集合】1 、有一個整數(shù)數(shù)組，請求

20、出兩兩之差絕對值最小的值。2 、一個整數(shù)數(shù)列，元素取值可能是 1N （ N 是一個較大的正整數(shù)）中的任意一個數(shù)，相同數(shù)值不會重復(fù)出現(xiàn)。設(shè)計一個算法， 找出數(shù)列中符合條件的數(shù)對的個數(shù)，滿足數(shù)對中兩數(shù)的和等于N+1 。復(fù)雜度不能為 O(n2) 。3、給定一個集合A=0,1,3,8(該集合中的元素都是在0 ， 9 之間的數(shù)字，但未必全部包含) ，指定任意一個正整數(shù)K ，請用 A 中的元素組成一個大于K 的最小正整數(shù)。比如，A=1,0 K=21那么輸出結(jié)構(gòu)應(yīng)該為100。4、一個有序數(shù)列， 序列中的每一個值都能夠被2或者3或者 5所整除， 1是這個序列的第一個元素。求第 1500個值是多少？5、1-10

21、00 放在含有 1001 個元素的數(shù)組中， 只有唯一的一個元素值重復(fù)，其它均只出現(xiàn)一次。每個數(shù)組元素只能訪問一次，設(shè)計一個算法，將它找出來，不用輔助存儲空間。6、一個含 n 個元素的整數(shù)數(shù)組至少存在一個重復(fù)數(shù)，請編程實現(xiàn)，在O （ n ）時間內(nèi)找出其中任意一個重復(fù)數(shù)。7、輸入 a1,a2,.,an,b1,b2,.,bn,在 O(n) 的時間 ,O(1) 的空間將這個序列順序改為a1,b1,a2,b2,a3,b3,.,an,bn，且不需要移動，通過交換完成，只需一個交換空間。8 、給定一個存放整數(shù)的數(shù)組，重新排列數(shù)組使得數(shù)組左邊為奇數(shù)，右邊為偶數(shù)。要求：空間復(fù)雜度O(1) ，時間復(fù)雜度為O （

22、n ）。9 、輸入一個整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有一個和。求所有子數(shù)組的和的最大值。要求時間復(fù)雜度為例如：輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5此輸出為該子數(shù)組的和18 。O(n) 。，和最大的子數(shù)組為3, 10, -4, 7, 2，因10 、輸入一個已經(jīng)按升序排序過的數(shù)組和一個數(shù)字，在數(shù)組中查找兩個數(shù)，使得它們的和正好是輸入的那個數(shù)字。要求：時間復(fù)雜度是O(n) 。如果有多對數(shù)字的和等于輸入的數(shù)字，輸出任意一對即可。例如：輸入數(shù)組1 、2 、4 、7 、11 、15 和數(shù)字 15 。由于 4+11=15，因

23、此輸出4 和 11 。11 、有兩個序列a,b ，大小都為n, 序列元素的值任意整數(shù)，無序；要求：通過交換a,b 中的元素，使 序列 a 元素的和 與 序列 b 元素的和 之間的差最小。例如 :var a=100,99,98,1,2, 3;var b=1, 2, 3, 4,5,40;12 、求一個矩陣中最大的二維矩陣(元素和最大) 。如 :120342345111530中最大的是 :4 55 3要求： (1) 寫出算法 ;(2)分析時間復(fù)雜度;(3)用 C 寫出關(guān)鍵代碼。13 、一個整數(shù)數(shù)組，長度為n ，將其分為m 份，使各份的和相等，求m 的最大值。比如 3 ， 2 ， 4 ， 3 ， 6可

24、以分成 3 ， 2， 4 ， 3 ， 6 m=1;3,62,4,3 m=23,32,46 m=3所以 m 的最大值為314、求一個數(shù)組的最長遞減子序列比如 9，4 ，3，2，5 ，4，3 ，2 的最長遞減子序列為9，5，4 ，3 ，215、如何對 n 個數(shù)進(jìn)行排序，要求時間復(fù)雜度O(n)，空間復(fù)雜度 O(1) 。16、輸入一個正數(shù)n ，輸出所有和為n 連續(xù)正數(shù)序列。例如：輸入15 ，由于 1+2+3+4+5=4+5+6=7+8=15，所以輸出3 個連續(xù)序列1-5、4-6和7-8。17 、給定一個存放整數(shù)的數(shù)組，重新排列數(shù)組使得數(shù)組左邊為奇數(shù)，右邊為偶數(shù)。要求：空間復(fù)雜度 O(1) ，時間復(fù)雜度

25、為 O （ n ）。18 、一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。要求時間復(fù)雜度是O(n) ，空間復(fù)雜度是O(1) 。19 、輸入一個正整數(shù)數(shù)組，將它們連接起來排成一個數(shù)，輸出能排出的所有數(shù)字中最小的一個。例如輸入數(shù)組32,321，則輸出這兩個能排成的最小數(shù)字32132。請給出解決問題的算法，并證明該算法。20 、把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個排好序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組 3, 4, 5, 1, 2為 1, 2, 3, 4, 5的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。21 、數(shù)

26、組中有一個數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組長度的一半，找出這個數(shù)字。22 、一個 int數(shù)組，里面數(shù)據(jù)無任何限制，要求求出所有這樣的數(shù)ai ，其左邊的數(shù)都小于等于它，右邊的數(shù)都大于等于它。能否只用一個額外數(shù)組和少量其它空間實現(xiàn)。23 、在一個int數(shù)組里查找這樣的數(shù)，它大于等于左側(cè)所有數(shù)，小于等于右側(cè)所有數(shù)。24、求隨機數(shù)構(gòu)成的數(shù)組中找到長度大于=3 的最長的等差數(shù)列，輸出等差數(shù)列由小到大。格式：輸入 1,3,0,5,-1,6輸出 -1,1,3,5要求時間復(fù)雜度，空間復(fù)雜度盡量小。25、遞歸法求數(shù)組中的最大值。參考 26、用遞歸的方法判斷整數(shù)組aN 是不是升序排列。27、計算數(shù)組中連續(xù)元素和的最大值。

27、參考【其它】1 、 1024 ！末尾有多少個0？ 參考 2 、編程實現(xiàn)兩個正整數(shù)的除法（不能用除法操作符）。3 、請定義一個宏，比較兩個數(shù)a 、 b 的大小，不能使用大于、小于、if 語句。4 、兩個數(shù)相乘，小數(shù)點后位數(shù)沒有限制，請寫一個高精度算法。5 、編程實現(xiàn)把十進(jìn)制數(shù)(long型 ) 分別以二進(jìn)制和十六進(jìn)制形式輸出，不能使用printf系列。6 、輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數(shù)字。例如：如果輸入如下矩陣：12345678910111213141516則依次打印出數(shù)字1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10。7、用 1、2 、2、3 、4、5這六個數(shù)字，寫一個main 函數(shù)，打印出所有不同的排列。如：、等，要求："4