算法題
1.鏈表和數組的區別在哪里？
ANSWER 主要在基本概念上的理解。但是最好能考慮的全面一點(diǎn)，現在公司招人的競爭可能就在細節上產(chǎn)生，誰(shuí)比較仔細，誰(shuí)獲勝的機會(huì )就大。
1）數組在內存中是逐個(gè)存放的，也就是說(shuō)倘若數組的第一個(gè)元素在地址A,則數組第二個(gè)元素就在地址A+1。而鏈表則不是，鏈表每個(gè)節點(diǎn)沒(méi)有相對固定的位置關(guān)系。某個(gè)節點(diǎn)在地址A其后的節點(diǎn)不一定是A+1,而在內存的其他空閑區域，呈現一種隨機的狀態(tài)。
2）數組一旦顯式的被申明后，其大小就固定了，不能動(dòng)態(tài)進(jìn)行擴充。而鏈表則可以，可以動(dòng)態(tài)生成節點(diǎn)并且添加到已有的鏈表后面。
3) …… （大家一起想想）
2.編寫(xiě)實(shí)現鏈表排序的一種算法。說(shuō)明為什么你會(huì )選擇用這樣的方法？
ANSWER 鏈表通常是插入排序,為什么呢？在數組中插入排序實(shí)現時(shí)會(huì )大量的移動(dòng)數據從而刪除位置不正確的元素，這是順序表刪除操作的低效性。從數學(xué)的角度，順序表（即數組）的刪除操作是O(n).鏈表就不同，由于其存儲位置的不固定性，其刪除固定位置的元素只需要O(1)的時(shí)間，所以整體性能上獲得比較大的提高。
3.編寫(xiě)實(shí)現數組排序的一種算法。說(shuō)明為什么你會(huì )選擇用這樣的方法？
ANSWER 排序算法非常成熟了，實(shí)際上排序是研究算法的很有效例子?；卮鸬臅r(shí)候盡量找一些比較有技術(shù)性的算法，比如堆排序或者快速排序，如果寫(xiě)冒泡什么的，別人都會(huì )寫(xiě)，也就顯示不出你的優(yōu)秀了。當然一定要注意給定的條件。不至于三個(gè)數讓你排序，你搞個(gè)快排，這就有點(diǎn)“宰牛刀殺雞”了。
4.請編寫(xiě)能直接實(shí)現strstr()函數功能的代碼。
ANSWER 首先要知道strstr()這個(gè)函數是干什么的，自己去查查C語(yǔ)言的書(shū)，一般附錄后面會(huì )給出C語(yǔ)言標準庫的。這個(gè)題目實(shí)際上也是一類(lèi)重要的算法門(mén)類(lèi)，叫做“字符串的模式匹配”。它有很多的現成算法，其中最簡(jiǎn)單的要數樸素的匹配算法，還有KMP,BM這些高級算法，筆試估計是來(lái)不及寫(xiě)的。下面給出樸素的匹配算法。
int stringMatching(char* pattern,char* text)
{
int pLen = strlen(pattern),tLen = strlen(text);
for(int i = 0;i <= tLen - pLen;i++){
for(int j = 0; pattern[j] == text[i + j];j++);
if(j == pLen) return i;
}
return -1; // Not found
}
5.編寫(xiě)反轉字符串的程序，要求優(yōu)化速度、優(yōu)化空間。
ANSWER:循環(huán)當然是最簡(jiǎn)單的。
void reverseString(char* str)
{
int n = strlen(str);
for(int i = 0;i < n/2;i++)
{int t = str[i];str[i] = str[n - i - 1];str[n - i - 1] = t;}
}
6.在鏈表里如何發(fā)現循環(huán)鏈接？
ANSWER: 顯然只需要判斷是否存在回溯指針就行了。判斷，是否存在某個(gè)節點(diǎn)的后繼指向其前面位置的指針。具體實(shí)現的時(shí)候可以模仿DFS中的訪(fǎng)問(wèn)標志數組的方法，我們可以在struct node中設計該節點(diǎn)的一個(gè)訪(fǎng)問(wèn)標志位，設為visited 。每訪(fǎng)問(wèn)一個(gè)節點(diǎn)就將其visited域置為1。這樣的話(huà)，一次遍歷下來(lái)，如果發(fā)現某個(gè)后續節點(diǎn)的visited域已經(jīng)是1，那么就可以判定其存在循環(huán)鏈接。具體的代碼就不寫(xiě)了，太簡(jiǎn)單了。
7.寫(xiě)一個(gè)函數，檢查字符是否是整數，如果是，返回其整數值。（或者：怎樣只用4行代碼編寫(xiě)出一個(gè)從字符串到長(cháng)整形的函數？）
分析 ：簡(jiǎn)單！掃描一遍，每次生成對應整數的最高位。一行也就搞定了！
long convert(char* s_string,long s_integer)
{
for(int sLen = strlen(s_string), i = 0; i < sLen;s_integer += (s_string[i++] - ‘0‘)*pow(10,sLen - i - 1));
return s_integer;
}
8.給出一個(gè)函數來(lái)輸出一個(gè)字符串的所有排列。
ANSWER 簡(jiǎn)單的回溯就可以實(shí)現了。當然排列的產(chǎn)生也有很多種算法，去看看組合數學(xué)，還有逆序生成排列和一些不需要遞歸生成排列的方法。印象中Knuth的<TAOCP>第一卷里面深入講了排列的生成。這些算法的理解需要一定的數學(xué)功底，也需要一定的靈感，有興趣最好看看。
void permStr(char* str,int i)
{
if(i == strlen(str) - 1)
printf("%s\n",str);
else
{
for(int j = i;j < strlen(str);j++)
{
swap(&str[i],&str[j]);
permStr(str,i + 1);
swap(&str[i],&str[j]);
}
}
}
9.給出一個(gè)函數來(lái)復制兩個(gè)字符串A和B。字符串A的后幾個(gè)字節和字符串B的前幾個(gè)字節重疊。
anSwer 記住，這種題目往往就是考你對邊界的考慮情況。編程除了技術(shù)上的熟練以外，細心也是非常重要的。其實(shí)很多編程的大師可能并不是有特別的技術(shù)，往往就是他們非常的耐心和細心，記?。壕幊淌怯嬎銠C科學(xué)中最基本的工作，它是最容易去掌握的，耐心點(diǎn)，細心點(diǎn)你一定能夠學(xué)好它。代碼看下面：
char* myStrcpy(char* s,char* a,char* b,char n)
{
int aLen = strlen(a),bLen = strlen(b);
if(n > aLen || n > bLen)
return NULL; // Error
for(int i = 0;i < aLen + bLen - n;i++)
if(i < aLen - n) s[i] = a[i];
else s[i] = b[i - aLen + n];
s[i] = ‘\0‘;
return s;
}
10.怎樣編寫(xiě)一個(gè)程序，把一個(gè)有序整數數組放到二叉樹(shù)中？
ANSWER :二叉搜索樹(shù)的建樹(shù)方法。簡(jiǎn)單的遞歸結構。實(shí)在不理解，干脆記下來(lái)好了。關(guān)于樹(shù)的算法設計一定要聯(lián)想到遞歸，因為樹(shù)本身就是遞歸的定義。這里的遞歸應該是理所當然的吧，不過(guò)，學(xué)會(huì )把遞歸改稱(chēng)非遞歸也是一種必要的技術(shù)。畢竟，遞歸會(huì )造成棧溢出，關(guān)于系統底層的程序中不到非不得以最好不要用。但是對某些數學(xué)問(wèn)題，就一定要學(xué)會(huì )用遞歸去解決。
void insertNode(bTree** root,int val)
{
bTree* newNode = (bTree* ) malloc(sizeof(bTree));
newNode->data = val;
newNode->lChild = NULL;
newNode->rChild = NULL;
if(!(*root))
*root = newNode;
else if(newNode->data < (*root)->data)
insertNode(&(*root)->lChild,val);
else
insertNode(&(*root)->rChild,val);
}
11.怎樣從頂部開(kāi)始逐層打印二叉樹(shù)結點(diǎn)數據？請編程。
ANSWER 二叉樹(shù)的層次遍歷沒(méi)什么好說(shuō)的，如果你不會(huì )還是早點(diǎn)把基礎復習一下。一個(gè)勁的往后學(xué)，才會(huì )發(fā)現原來(lái)最最重要的還是以前最基礎最簡(jiǎn)單的。
typedef struct myBinaryTree
{
int data;
struct myBinaryTree* lChild;
struct myBinaryTree* rChild;
} bTree;
struct myQueen
{
bTree* que[QSIZE];
int front;
int rear;
} binQueue; // Global var
void initQueue()
{
// front == real makes the queue empty
binQueue.rear = QSIZE - 1;
binQueue.front = binQueue.rear;
for(int i = 0;i < QSIZE;i++)
binQueue.que[i] = NULL;
}
int enQueue(bTree* newNode)
{
if(binQueue.front >= 1)
binQueue.que[binQueue.front--] = newNode;
else return 0;
return 1;
}
bTree* deQueue()
{
int t;
if(binQueue.front != binQueue.rear){
t = binQueue.rear;
binQueue.rear--;
return binQueue.que[t];
}
else return NULL;
}
int levelTraversal(bTree** root)
{
initQueue();
bTree* lc = (bTree* ) malloc(sizeof(bTree));
bTree* rc = (bTree* ) malloc(sizeof(bTree));
bTree* p = (bTree* ) malloc(sizeof(bTree));
if((!lc) || (!rc) || (!p)){
printf("OVERFLOW\n");
exit(OVERFLOW); // Allocation Error
}
p = *root;
if(!p) {
printf("Empty Tree,build it first !\n");
return 0;
}
enQueue(p); // enqueue the root of the tree
while (binQueue.front != binQueue.rear){
p = deQueue();
printf("%d ",p->data);
lc = p->lChild;
rc = p->rChild;
if(lc != NULL)
enQueue(lc);
if(rc != NULL)
enQueue(rc);
}
printf("\n");
return 1;
}
12.怎樣把一個(gè)鏈表掉個(gè)順序（也就是反序，注意鏈表的邊界條件并考慮空鏈表）？
ANSWER 前面說(shuō)了，最基本的是最重要的。線(xiàn)性數據結構是學(xué)習數據結構的入門(mén)，一定要掌握好。微軟的題目還是跟國內的公司不一樣。國內的一上來(lái)就是些概念，跟考歷史一樣。
typedef struct listNode
{
struct listNode* link;
int data;
}node;
node* getNode(node* newNode,int val)
{
if(!newNode)
exit(OVERFLOW);
newNode->link = NULL;
newNode->data = val;
return newNode;
}
/*
Insert a new node after p
*/
int insertNode(node* prev,node* newNode)
{
if(!prev) return 0;
newNode->link = prev->link;
prev->link = newNode;
return 1;
}
/*
delete the node after the node prev
*/
int eraseNode(node*prev,node* p)
{
if(p == NULL)
return 0;
prev->link = p->link;
free(p);
return 1;
}
void buildList(node* head)
{
int value;
node* newNode = (node* ) malloc(sizeof(node));
node* p = head;
scanf("%d",&value);
while(value != -1){
newNode = getNode(newNode,value);
insertNode(p,newNode);
p = p->link;
newNode = (node* ) malloc(sizeof(node));
scanf("%d",&value);
}
}
int reverseList(node* head)
{
node* p = head->link;
node* q = p->link;
if(p == NULL){
printf("The list is empty!\n");
return 0;
}
while(q != NULL){
node* newNode = (node* ) malloc(sizeof(node));
newNode = getNode(newNode,q->data);
insertNode(head,newNode);
eraseNode(p,q);
q = (node* ) malloc(sizeof(node)); // Allocate again
q = p->link;
}
p->link = NULL;
return 1;
}
聯(lián)系客服
