演算法題1.鍊錶和陣列的區別在**？
answer 主要在基本概念上的理解。但是最好能考慮的全面一點，現在公司招人的競爭可能就在細節上產生，誰比較仔細，誰獲勝的機會就大。
1）陣列在記憶體中是逐個存放的，也就是說倘若陣列的第乙個元素在位址a,則陣列第二個元素就在位址a+1。而鍊錶則不是，鍊錶每個節點沒有相對固定的位置關係。某個節點在位址a其後的節點不一定是a+1,而在記憶體的其他空閒區域，呈現一種隨機的狀態。
2）陣列一旦顯式的被申明後，其大小就固定了，不能動態進行擴充。而鍊錶則可以，可以動態生成節點並且新增到已有的鍊錶後面。
3) …… （大家一起想想）
2.編寫實現鍊錶排序的一種演算法。說明為什麼你會選擇用這樣的方法？
answer 鍊錶通常是插入排序,為什麼呢？在陣列中插入排序實現時會大量的移動資料從而刪除位置不正確的元素，這是順序表刪除操作的低效性。從數學的角度，順序表（即陣列）的刪除操作是o(n).
鍊錶就不同，由於其儲存位置的不固定性，其刪除固定位置的元素只需要o(1)的時間，所以整體效能上獲得比較大的提高。
3.編寫實現陣列排序的一種演算法。說明為什麼你會選擇用這樣的方法？
answer 排序演算法非常成熟了，實際上排序是研究演算法的很有效例子。回答的時候盡量找一些比較有技術性的演算法，比如堆排序或者快速排序，如果寫冒泡什麼的，別人都會寫，也就顯示不出你的優秀了。當然一定要注意給定的條件。
不至於三個數讓你排序，你搞個快排，這就有點「宰牛刀殺雞」了。
4.請編寫能直接實現strstr()函式功能的**。
answer 首先要知道strstr()這個函式是幹什麼的，自己去查查c語言的書，一般附錄後面會給出c語言標準庫的。這個題目實際上也是一類重要的演算法門類，叫做「字串的模式匹配」。它有很多的現成演算法，其中最簡單的要數樸素的匹配演算法，還有kmp,bm這些高階演算法，筆試估計是來不及寫的。
下面給出樸素的匹配演算法。
int stringmatching(char* pattern,char* text)
return -1; // not found}或者
char * strstr(const char *s1,const char *s2)
return null;
}5.編寫反轉字串的程式，要求優化速度、優化空間。
answer:迴圈當然是最簡單的。
void reversestring(char* str)
}6.在煉表裡如何發現迴圈鏈結？
answer: 顯然只需要判斷是否存在回溯指標就行了。判斷，是否存在某個節點的後繼指向其前面位置的指標。
具體實現的時候可以模仿dfs中的訪問標誌陣列的方法，我們可以在struct node中設計該節點的乙個訪問標誌位，設為visited 。每訪問乙個節點就將其visited域置為1。這樣的話，一次遍歷下來，如果發現某個後續節點的visited域已經是1，那麼就可以判定其存在迴圈鏈結。
具體的**就不寫了，太簡單了。
7.寫乙個函式，檢查字元是否是整數，如果是，返回其整數值。（或者：怎樣只用4行**編寫出乙個從字串到長整形的函式？）
分析 ：簡單！掃瞄一遍，每次生成對應整數的最高位。一行也就搞定了！
long convert(char* s_string,long s_integer)
8.給出乙個函式來輸出乙個字串的所有排列。
answer 簡單的回溯就可以實現了。當然排列的產生也有很多種演算法，去看看組合數學，還有逆序生成排列和一些不需要遞迴生成排列的方法。印象中knuth的第一卷裡面深入講了排列的生成。
這些演算法的理解需要一定的數學功底，也需要一定的靈感，有興趣最好看看。
void permstr(char* str,int i) }}
9.給出乙個函式來複製兩個字串a和b。字串a的後幾個位元組和字串b的前幾個位元組重疊。
answer 記住，這種題目往往就是考你對邊界的考慮情況。程式設計除了技術上的熟練以外，細心也是非常重要的。其實很多程式設計的大師可能並不是有特別的技術，往往就是他們非常的耐心和細心，記住：
程式設計是電腦科學中最基本的工作，它是最容易去掌握的，耐心點，細心點你一定能夠學好它。**看下面：
char* mystrcpy(char* s,char* a,char* b,char n)
10.怎樣編寫乙個程式，把乙個有序整數陣列放到二叉樹中？
answer :二叉搜尋樹的建樹方法。簡單的遞迴結構。
實在不理解，乾脆記下來好了。關於樹的演算法設計一定要聯想到遞迴，因為樹本身就是遞迴的定義。這裡的遞迴應該是理所當然的吧，不過，學會把遞迴改稱非遞迴也是一種必要的技術。
畢竟，遞迴會造成棧溢位，關於系統底層的程式中不到非不得以最好不要用。但是對某些數學問題，就一定要學會用遞迴去解決。
void insertnode(btree** root,int val)
11.怎樣從頂部開始逐層列印二叉樹結點資料？請程式設計。
answer 二叉樹的層次遍歷沒什麼好說的，如果你不會還是早點把基礎複習一下。乙個勁的往後學，才會發現原來最最重要的還是以前最基礎最簡單的。
typedef struct mybinarytree
btree;
struct myqueen
binqueue; // global var
void initqueue()
int enqueue(btree* newnode)
{ if(binqueue.front >= 1)
binqueue.que[binqueue.front--] = newnode;
else return 0;
return 1;
微軟面試題目
智力題1 燒一根不均勻的繩子，從頭燒到尾總共需要1個小時，問如何用燒繩子的方法來確定半小時的時間呢？2 10個海盜搶到了100顆寶石，每一顆都一樣大小且價值連城。他們決定這麼分 1 抽籤決定自己的號碼 1 10 2 首先，由1號提出分配方案，然後大家表決，當且僅當超過半數的人同意時，按照他的方案進行...
微軟面試中的過橋問題
作者 林革 學苑創造 c版 2011年第06期 這是世界著名的微軟公司招聘人才時的兩道面試題。其中蘊含的統籌優化的數學思想方法，應該引起我們的關注和重視。因為培養自身在生產生活實際中尋求合理方案和最優解答的能力，是現代人至關重要的必備素質。過橋問題1 小明一家過一座橋，過橋時是黑夜，所以必須有燈。現...
微軟面試符串中刪除特定的字元
題目 輸入兩個字串，從第一字串中刪除第二個字串中所有的字元。例如，輸入 they are students.和 aeiou 則刪除之後的第乙個字串變成 thy r stdnts.分析 這是一道微軟面試題。在微軟的常見面試題中，與字串相關的題目佔了很大的一部分，因為寫程式操作字串能很好的反映我們的程式...