【字串】
1、輸入乙個字串，列印出該字串中字元的所有排列。
例如輸入字串abc，則輸出由字元a、b、c所能排列出來的所有字串abc、acb、bac、bca、cab和cba。
2、有乙個由大小寫組成的字串，現在需要對他進行修改，將其中的所有小寫字母排在大寫字母的前面
（大寫或小寫字母之間不要求保持原來次序），如有可能盡量選擇時間和空間效率高的演算法。
c語言函式原型void proc（char *str），也可以採用你自己熟悉的語言。
3、編寫反轉字串的程式，要求優化速度、優化空間。
4、用c語言實現函式void * memmove(void *dest, const void *src, size_t n)。
memmove函式的功能是拷貝src所指的記憶體內容前n個位元組到dest所指的位址上。
分析：由於可以把任何型別的指標賦給void型別的指標，這個函式主要是實現各種資料型別的拷貝。
5、程式設計找出兩個字串中最大公共子字串,如"abccade", "dgcadde"的最大子串為"cad"。
6、輸入乙個字串，輸出該字串中對稱的子字串的最大長度。
比如輸入字串"google"，由於該字串裡最長的對稱子字串是"goog"，因此輸出4。
7、字串原地壓縮。題目描述：「eeeeeaaaff" 壓縮為 "e5a3f2"，請程式設計實現。
8、請以回溯與不回溯演算法實現字串匹配。
9、輸入乙個英文句子，翻轉句子中單詞的順序，但單詞內字元的順序不變。句子中單詞以空格符隔開。
為簡單起見，標點符號和普通字母一樣處理。
例如：輸入"i am a student."，則輸出"student. a am i"。
10、在乙個字串中找到第乙個只出現一次的字元。如輸入abaccdeff，則輸出b。
11、寫乙個函式，它的原形是int continumax(char *outputstr,char *intputstr)
功能：在字串中找出連續最長的數字串，並把這個串的長度返回，並把這個最長數字串付給其中乙個函式引數outputstr所指記憶體。
例如："abcd12345ed125ss123456789"的首位址傳給intputstr後，函式將返回9，outputstr所指的值為123456789。
12、定義字串的左旋轉操作：把字串前面的若干個字元移動到字串的尾部。
如：把字串abcdef左旋轉2位得到字串cdefab。請實現字串左旋轉的函式。
要求時間對長度為n的字串操作的複雜度為o(n)，輔助記憶體為o(1)。
13、有n個長為m+1的字串，如果某個字串的最後m個字元與某個字串的前m個字元匹配，則兩個字串可以聯接。
問這n個字串最多可以連成乙個多長的字串，如果出現迴圈，則返回錯誤。
14、如果字串一的所有字元按其在字串中的順序出現在另外乙個字串二中，則字串一稱之為字串二的子串。
注意，並不要求子串（字串一）的字元必須連續出現在字串二中。
請編寫乙個函式，輸入兩個字串，求它們的最長公共子串，並列印出最長公共子串。
例如：輸入兩個字串bdcaba和abcbdab，字串bcba和bdab都是是它們的最長公共子串，
則輸出它們的長度4，並列印任意乙個子串。
分析：求最長公共子串（longest common subsequence, lcs）是一道非常經典的動態規劃題。
15、輸入兩個字串，從第一字串中刪除第二個字串中所有的字元。
例如，輸入"they are students."和"aeiou"，則刪除之後的第乙個字串變成"thy r stdnts."。
16、乙個檔案，內含一千萬行字串，每個字串在1k以內，要求找出所有相反的串對，如abc和cba。
17、給出乙個函式來複製兩個字串a和b。字串a的後幾個位元組和字串b的前幾個位元組重疊。
18、已知乙個字串，比如asderwsde,尋找其中的乙個子字串比如sde的個數，如果沒有返回0，有的話返回子字串的個數。
19、求最大連續遞增數字串（如"ads3sl456789df3456ld345aa"中的"456789"）。
20、實現strstr功能，即在父串中尋找子串首次出現的位置。
21、編碼完成下面的處理函式。
函式將字串中的字元'*'移到串的前部分，前面的非'*'字元後移，但不能改變非'*'字元的先後順序，函式返回串中字元'*'的數量。
如原始串為：ab**cd**e*12，處理後為*****abcde12，函式並返回值為5。（要求使用盡量少的時間和輔助空間）
22、刪除字串中的數字並壓縮字串。如字串」abc123de4fg56」處理後變為」abcdefg」。注意空間和效率。
23、求兩個串中的第乙個最長子串（神州數碼以前試題）。如"abractyeyt"，"dgdsaeactyey"的最大子串為"actyet"。
【棧、鍊錶、樹、圖】
1、編寫乙個程式，把乙個有序整數陣列放到二叉樹中。
2、程式設計實現從頂部開始逐層列印二叉樹節點資料。[參考]
3、程式設計實現單鏈表逆轉。
4、設計乙個演算法，找出二叉樹上任意兩個結點的最近共同父結點。複雜度不能為o(n2)。
5、二叉排序樹中，令f = (最大值+最小值) / 2，設計乙個演算法，找出距離f值最近、大於f值的結點。複雜度不能為o(n2)。
6、有雙向迴圈鍊錶結點定義為：
struct node
;有兩個雙向迴圈鍊錶a，b，知道其頭指標為：pheada、pheadb，請寫一函式將兩煉表中data值相同的結點刪除。
7、輸入乙個鍊錶的頭結點，從尾到頭反過來輸出每個結點的值。鍊錶結點定義如下：
struct listnode
;8、輸入一棵二元查詢樹，將該二元查詢樹轉換成乙個排序的雙向鍊錶。
要求不能建立任何新的結點，只調整指標的指向。
10/ \
6 14
/ \ / \
4 8 12 16
轉換成雙向鍊錶
4=6=8=10=12=14=16。
首先我們定義的二元查詢樹節點的資料結構如下：
struct bstreenode
; [參考]
9、設計包含min函式的棧。
定義棧的資料結構，要求新增乙個min函式，能夠得到棧的最小元素。
要求函式min、push以及pop的時間複雜度都是o(1)。
10、輸入乙個整數和一棵二元樹。從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。
列印出和與輸入整數相等的所有路徑。
例如輸入整數22和如下二元樹
10 / \
5 12
/ \4 7則列印出兩條路徑：10, 12和10, 5, 7。
二元樹節點的資料結構定義為：
struct binarytreenode // a node in the binary tree
;11、給出倆個單向鍊錶的頭指標，比如h1，h2，判斷這倆個鍊錶是否相交。為了簡化問題，我們假設倆個鍊錶均不帶環。
問題擴充套件：
(1) 如果鍊錶可能有環列?
(2) 如果需要求出倆個鍊錶相交的第乙個節點列?
12、輸入乙個整數陣列，判斷該陣列是不是某二元查詢樹的後序遍歷的結果。
如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由於這一整數序列是如下樹的後序遍歷結果：
8/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果輸入7、4、6、5，沒有哪棵樹的後序遍歷的結果是這個序列，因此返回false。
13、如果我們把二叉樹看成乙個圖，父子節點之間的連線看成是雙向的，我們姑且定義"距離"為兩節點之間邊的個數。
寫乙個程式，求一棵二叉樹中相距最遠的兩個節點之間的距離。
14、輸入乙個單向鍊錶，輸出該鍊錶中倒數第k個結點。鍊錶的倒數第0個結點為鍊錶的尾指標。
鍊錶結點定義如下：
struct listnode
;15、輸入一顆二元查詢樹，將該樹轉換為它的映象，即在轉換後的二元查詢樹中，左子樹的結點都大於右子樹的結點。
用遞迴和迴圈兩種方法完成樹的映象轉換。
例如輸入：
8/ \
6 10
/\ /\
5 7 9 11
輸出：8
/ \10 6
/ \/ \
11 97 5
定義二元查詢樹的結點為：
struct bstreenode
; [參考]
16、求乙個二叉樹中任意兩個節點間的最大距離，兩個節點的距離的定義是這兩個節點間邊的個數。
比如某個孩子節點和父節點間的距離是1，和相鄰兄弟節點間的距離是2，優化時間空間複雜度。
17、求乙個有向連通圖的割點，割點的定義是，如果除去此節點和與其相關的邊，有向圖不再連通，描述演算法。
18、設計乙個棧結構，滿足一下條件：min，push，pop操作的時間複雜度為o(1)。
19、請修改append函式，利用這個函式實現：
兩個非降序鍊錶的並集，1->2->3 和 2->3->5 並為 1->2->3->5
另外只能輸出結果，不能修改兩個鍊錶的資料。
資料結構演算法面試題
微軟的22道資料結構演算法面試題 含答案 1 反轉乙個鍊錶。迴圈演算法。1 list reverse list l 13 return tmp 14 2 反轉乙個鍊錶。遞迴演算法。1 list resverse list l 8 return n 9 3 廣度優先遍歷二叉樹。1 void bst t...
資料結構 演算法面試題
資料結構 演算法面試100題 摘自csdn，作者july 高天的日誌 1.把二元查詢樹轉變成排序的雙向鍊錶 樹 題目 輸入一棵二元查詢樹，將該二元查詢樹轉換成乙個排序的雙向鍊錶。要求不能建立任何新的結點，只調整指標的指向。10 6 14 4 8 12 16 轉換成雙向鍊錶 4 6 8 10 12 1...
22道資料結構演算法面試題
微軟的22道資料結構演算法面試題 含答案 1 反轉乙個鍊錶。迴圈演算法。1 list reverse list l 13 return tmp 14 2 反轉乙個鍊錶。遞迴演算法。1 list resverse list l 8 return n 9 3 廣度優先遍歷二叉樹。1 void bst t...