面試?？嫉臄?shù)據(jù)結(jié)構(gòu)題

1、面試?？嫉臄?shù)據(jù)結(jié)構(gòu)題      為了能進(jìn)微軟江西的暑假實(shí)訓(xùn)班,猛補(bǔ)了一下數(shù)據(jù)結(jié)構(gòu)的知識(shí)，現(xiàn)在總結(jié)一下?？嫉臄?shù)據(jù)結(jié)構(gòu)的知識(shí)吧。      知識(shí)點(diǎn)：1鏈表  2二叉樹(shù) 3排序 4查找1.判斷鏈表是否存在環(huán)型鏈表問(wèn)題：判斷一個(gè)鏈表是否存在環(huán)，例如下面這個(gè)鏈表就存在一個(gè)環(huán)：例如N1->N2->N3->N4->N5->N2就是一個(gè)有環(huán)的鏈表，環(huán)的開(kāi)始結(jié)點(diǎn)是N5這里有一個(gè)比較簡(jiǎn)單的解法。設(shè)置兩個(gè)指針p1，p2。每次循環(huán)p1向前走一步，p2向前走兩步。直到p2碰到NULL指針或者

2、兩個(gè)指針相等結(jié)束循環(huán)。如果兩個(gè)指針相等則說(shuō)明存在環(huán)。 struct link      int data;      link* next; bool IsLoop(link* head)      link* p1=head, *p2 = head;       if (head =NULL | head->next =NULL)     

3、                 return false;             do          p1= p1->next;         

4、 p2 = p2->next->next;      while(p2 && p2->next && p1!=p2);              if(p1 = p2)              return true;  

5、60;    else              return false;2,鏈表反轉(zhuǎn) 單向鏈表的反轉(zhuǎn)是一個(gè)經(jīng)常被問(wèn)到的一個(gè)面試題，也是一個(gè)非常基礎(chǔ)的問(wèn)題。比如一個(gè)鏈表是這樣的： 1->2->3->4->5 通過(guò)反轉(zhuǎn)后成為5->4->3->2->1。最容易想到的方法遍歷一遍鏈表，利用一個(gè)輔助指針，存儲(chǔ)遍歷過(guò)程中當(dāng)前指針指向的下一個(gè)元素，然后將當(dāng)前節(jié)點(diǎn)元素的指針?lè)崔D(zhuǎn)后，利用已經(jīng)存儲(chǔ)的指針往

6、后面繼續(xù)遍歷。源代碼如下： struct linka        int data;       linka* next; void reverse(linka*& head)       if(head =NULL)            return;   

7、;    linka*pre, *cur, *ne;       pre=head;       cur=head->next;       while(cur)                   ne = cu

8、r->next;            cur->next = pre;            pre = cur;            cur = ne;         &

9、#160;    head->next = NULL;       head = pre;還有一種利用遞歸的方法。這種方法的基本思想是在反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)之前先調(diào)用遞歸函數(shù)反轉(zhuǎn)后續(xù)節(jié)點(diǎn)。源代碼如下。不過(guò)這個(gè)方法有一個(gè)缺點(diǎn)，就是在反轉(zhuǎn)后的最后一個(gè)結(jié)點(diǎn)會(huì)形成一個(gè)環(huán)，所以必須將函數(shù)的返回的節(jié)點(diǎn)的next域置為NULL。因?yàn)橐淖僪ead指針，所以我用了引用。算法的源代碼如下： linka* reverse(linka* p,linka*& head)    

10、60;  if(p = NULL | p->next = NULL)                   head=p;            return p;            

11、0; else                   linka* tmp = reverse(p->next,head);            tmp->next = p;           

12、return p;       3,判斷兩個(gè)數(shù)組中是否存在相同的數(shù)字 給定兩個(gè)排好序的數(shù)組，怎樣高效得判斷這兩個(gè)數(shù)組中存在相同的數(shù)字？這個(gè)問(wèn)題首先想到的是一個(gè)O(nlogn)的算法。就是任意挑選一個(gè)數(shù)組，遍歷這個(gè)數(shù)組的所有元素，遍歷過(guò)程中，在另一個(gè)數(shù)組中對(duì)第一個(gè)數(shù)組中的每個(gè)元素進(jìn)行binary search。用C+實(shí)現(xiàn)代碼如下： bool findcommon(int a,int size1,int b,int size2)       int i;  &

13、#160;    for(i=0;i<size1;i+)                   int start=0,end=size2-1,mid;            while(start<=end)      

14、;                       mid=(start+end)/2;                 if(ai=bmid)       

15、60;              return true;                 else if (ai<bmid)               

16、;       end=mid-1;                 else                      start=mid+1;  

17、                        return false;后來(lái)發(fā)現(xiàn)有一個(gè) O(n)算法。因?yàn)閮蓚€(gè)數(shù)組都是排好序的。所以只要一次遍歷就行了。首先設(shè)兩個(gè)下標(biāo)，分別初始化為兩個(gè)數(shù)組的起始地址，依次向前推進(jìn)。推進(jìn)的規(guī)則是比較兩個(gè)數(shù)組中的數(shù)字，小的那個(gè)數(shù)組的下標(biāo)向前推進(jìn)一步，直到任何一個(gè)數(shù)組的下標(biāo)到達(dá)數(shù)組末尾時(shí)，如果這時(shí)還沒(méi)碰到相同的數(shù)字，說(shuō)明數(shù)組中沒(méi)有相同的數(shù)字。 bool fi

18、ndcommon2(int a, int size1, int b, int size2)       int i=0,j=0;       while(i<size1 && j<size2)                   if(ai=bj)   

19、;                return true;            if(ai>bj)                 j+;   

20、;         if(ai<bj)                 i+;              return false;4,最大子序列 問(wèn)題：給定一整數(shù)序列A1， A2，. An （可能有負(fù)數(shù)），求A1An的一個(gè)子序列Ai

21、Aj，使得Ai到Aj的和最大例如：整數(shù)序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和為21。對(duì)于這個(gè)問(wèn)題，最簡(jiǎn)單也是最容易想到的那就是窮舉所有子序列的方法。利用三重循環(huán)，依次求出所有子序列的和然后取最大的那個(gè)。當(dāng)然算法復(fù)雜度會(huì)達(dá)到O(n3)。顯然這種方法不是最優(yōu)的，下面給出一個(gè)算法復(fù)雜度為O(n)的線性算法實(shí)現(xiàn)，算法的來(lái)源于Programming Pearls一書。 在給出線性算法之前，先來(lái)看一個(gè)對(duì)窮舉算法進(jìn)行優(yōu)化的算法，它的算法復(fù)雜度為O(n2)。其實(shí)這個(gè)算法只是對(duì)對(duì)窮舉算法稍微做了一些修改：其實(shí)子序列的和我們并不需要每次都重新計(jì)算一遍。假設(shè)S

22、um(i, j)是Ai . Aj的和，那么Sum(i, j+1) = Sum(i, j) + Aj+1。利用這一個(gè)遞推，我們就可以得到下面這個(gè)算法： int max_sub(int a,int size)       int i,j,v,max=a0;       for(i=0;i<size;i+)               &

23、#160;   v=0;            for(j=i;j<size;j+)                             v=v+aj;/Sum(i, j+1) = Sum(

24、i, j) + Aj+1                 if(v>max)                      max=v;       

25、0;                  return max;那怎樣才能達(dá)到線性復(fù)雜度呢？這里運(yùn)用動(dòng)態(tài)規(guī)劃的思想。先看一下源代碼實(shí)現(xiàn)： int max_sub2(int a, int size)       int i,max=0,temp_sum=0;       for(i=0;i<size;i+) 

26、0;                 temp_sum+=ai;            if(temp_sum>max)                 max=temp_s

27、um;            else if(temp_sum<0)                 temp_sum=0;              return max;在這一遍掃描數(shù)組當(dāng)中，從左到右

28、記錄當(dāng)前子序列的和temp_sum，若這個(gè)和不斷增加，那么最大子序列的和max也不斷增加(不斷更新max)。如果往前掃描中遇到負(fù)數(shù)，那么當(dāng)前子序列的和將會(huì)減小。此時(shí)temp_sum 將會(huì)小于max，當(dāng)然max也就不更新。如果temp_sum降到0時(shí)，說(shuō)明前面已經(jīng)掃描的那一段就可以拋棄了，這時(shí)將temp_sum置為0。然后，temp_sum將從后面開(kāi)始將這個(gè)子段進(jìn)行分析，若有比當(dāng)前max大的子段，繼續(xù)更新max。這樣一趟掃描結(jié)果也就出來(lái)了。5, 找出單向鏈表的中間結(jié)點(diǎn) 這道題和解判斷鏈表是否存在環(huán)，我用的是非常類似的方法，只不過(guò)結(jié)束循環(huán)的條件和函數(shù)返回值不一樣罷了。設(shè)置兩個(gè)指針p1，p2。每次循環(huán)p1向前走一步，p2向前走兩步。當(dāng)p2到達(dá)鏈表的末尾時(shí)，p1指向的時(shí)鏈表的中間。 link* mid(link* head)         link* p1,*p2;         p1=p2=head;         if(head=NULL | head->next=NULL)   &#