經(jīng)典數(shù)據(jù)結構面試題含答案-文庫吧資料
2025-06-25 07:56本頁面
【正文】 for(i=0,j=len1。 strcpy(restr,str)。 int len = strlen(str)。char* reverse_word(const char* str){其實按照單詞反轉的話可以在第一遍遍歷的基礎上，再遍歷一遍字符串，對每一個單詞再反轉一次。}6,按單詞反轉字符串 并不是簡單的字符串反轉，而是按給定字符串里的單詞將字符串倒轉過來，就是說字符串里面的單詞還是保持原來的順序，這里的每個單詞用空格分開。 temp_sum=0。 else if(temp_sum0) max=temp_sum。 if(temp_summax) temp_sum+=a[i]。isize。 int i,max=0,temp_sum=0。先看一下源代碼實現(xiàn)： int max_sub2(int a[], int size){ return max。 } } max=v。 v=v+a[j]。 {jsize。 {i++) for(i=0。假設Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。 在給出線性算法之前，先來看一個對窮舉算法進行優(yōu)化的算法，它的算法復雜度為O(n^2)。當然算法復雜度會達到O(n^3)。對于這個問題，最簡單也是最容易想到的那就是窮舉所有子序列的方法。 return false。 } { jsize2) while(isize1 amp。推進的規(guī)則是比較兩個數(shù)組中的數(shù)字，小的那個數(shù)組的下標向前推進一步，直到任何一個數(shù)組的下標到達數(shù)組末尾時，如果這時還沒碰到相同的數(shù)字，說明數(shù)組中沒有相同的數(shù)字。所以只要一次遍歷就行了。}后來發(fā)現(xiàn)有一個 O(n)算法。 else else if (a[i]b[mid]) if(a[i]==b[mid]) while(start=end) int start=0,end=size21,mid。isize1。 int i。用C++實現(xiàn)代碼如下： bool findmon(int a[],int size1,int b[],int size2){ }}3,判斷兩個數(shù)組中是否存在相同的數(shù)字 給定兩個排好序的數(shù)組，怎樣高效得判斷這兩個數(shù)組中存在相同的數(shù)字？這個問題首先想到的是一個O(nlogn)的算法。 { else } { if(p == NULL || pnext == NULL) head){因為要改變head指針，所以我用了引用。源代碼如下。}還有一種利用遞歸的方法。 headnext = NULL。 } { while(cur) pre=head。 return。 void reverse(linka*amp。 linka* next。最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當前指針指向的下一個元素，然后將當前節(jié)點元素的指針反轉后，利用已經(jīng)存儲的指針往后面繼續(xù)遍歷。}2,鏈表反轉 單向鏈表的反轉是一個經(jīng)常被問到的一個面試題，也是一個非?；A的問題。 return true。 if(p1 == p2) amp。amp。 do{ return false。 { if (head ==NULL || headnext ==NULL) bool IsLoop(link* head){ link* next。 int data。如果兩個指針相等則說明存在環(huán)。每次循環(huán)p1向前走一步，p2向前走兩步。 D．DEBFCA：判斷一個鏈表是否存在環(huán)，例如下面這個鏈表就存在一個環(huán)：例如N1N2N3N4N5N2就是一個有環(huán)的鏈表，環(huán)的開始結點是N5這里有一個比較簡單的解法。 D．棧38. 設有下列二叉樹，對此二叉樹中序遍歷的結果是（B）A．ABCDEF D．循環(huán)鏈表31. 以下數(shù)據(jù)結構屬于非線性數(shù)據(jù)結構的是（C）A．隊列 B．雙向鏈表 D．所需空間與線性表長度成正比30. 在（D）中，只要指出表中任何一個結點的位置，就可以從它出發(fā)依次訪問到表中其他所有結點。 B．線性表中至少要有一個元素C．表中諸元素的排列順序必須是由小到大或由大到小D．除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件，要求內(nèi)存中可用存儲單元的地址（連續(xù)不連續(xù)都可以） 27. 鏈表不具有的特點是（B）A．不必事先估計存儲空間 D．隊列是先進后出的線性表，正確的是（D）A．線性鏈表中的各元素在存儲空間中的位置必須是連續(xù)的B．線性鏈表中的表頭元素一定存儲在其他元素的前面 C．線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，但表頭元素一定存儲在其他元素的前面 D．線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，且各元素的存儲順序也是任意的（A）A．線性表是線性結構 D．棧是先進后出的線性表20. 由兩個棧共享一個存儲空間的好處是（節(jié)省存儲空間，降低上溢發(fā)生的機率） 21. 應用程
法律信息相關推薦
鄂ICP備17016276號-1