為了能進微軟江西的暑假實訓班,猛補了一下資料結構的知識，現在總結一下常考的資料結構的知識吧。
知識點：1鍊錶 2二叉樹 3排序 4查詢
1.判斷鍊錶是否存在環型鍊錶問題：判斷乙個鍊錶是否存在環，例如下面這個鍊錶就存在乙個環：
例如n1->n2->n3->n4->n5->n2就是乙個有環的鍊錶，環的開始結點是n5這裡有乙個比較簡單的解法。設定兩個指標p1，p2。每次迴圈p1向前走一步，p2向前走兩步。
直到p2碰到null指標或者兩個指標相等結束迴圈。如果兩個指標相等則說明存在環。
struct link
;bool isloop(link* head)
do while(p2 && p2->next && p1!=p2);
if(p1 == p2)
return true;
else
return false;
}2,鍊錶反轉單向鍊錶的反轉是乙個經常被問到的乙個面試題，也是乙個非常基礎的問題。比如乙個鍊錶是這樣的： 1->2->3->4->5 通過反轉後成為5->4->3->2->1。
最容易想到的方法遍歷一遍鍊錶，利用乙個輔助指標，儲存遍歷過程中當前指標指向的下乙個元素，然後將當前節點元素的指標反轉後，利用已經儲存的指標往後面繼續遍歷。源**如下：
struct linka ;
void reverse(linka*& head)
head->next = null;
head = pre;
}還有一種利用遞迴的方法。這種方法的基本思想是在反轉當前節點之前先呼叫遞迴函式反轉後續節點。源**如下。
不過這個方法有乙個缺點，就是在反轉後的最後乙個結點會形成乙個環，所以必須將函式的返回的節點的next域置為null。因為要改變head指標，所以我用了引用。演算法的源**如下：
linka* reverse(linka* p,linka*& head)
else }
3,判斷兩個陣列中是否存在相同的數字給定兩個排好序的陣列，怎樣高效得判斷這兩個陣列中存在相同的數字？
這個問題首先想到的是乙個o(nlogn)的演算法。就是任意挑選乙個陣列，遍歷這個陣列的所有元素，遍歷過程中，在另乙個陣列中對第乙個陣列中的每個元素進行binary search。用c++實現**如下：
bool findcommon(int a,int size1,int b,int size2)
} return max;
}那怎樣才能達到線性複雜度呢？這裡運用動態規劃的思想。先看一下源**實現：
int max_sub2(int a, int size)
return max;
}在這一遍掃瞄陣列當中，從左到右記錄當前子串行的和temp_sum，若這個和不斷增加，那麼最大子串行的和max也不斷增加(不斷更新max)。如果往前掃瞄中遇到負數，那麼當前子串行的和將會減小。此時temp_sum 將會小於max，當然max也就不更新。
如果temp_sum降到0時，說明前面已經掃瞄的那一段就可以拋棄了，這時將temp_sum置為0。然後，temp_sum將從後面開始將這個子段進行分析，若有比當前max大的子段，繼續更新max。這樣一趟掃瞄結果也就出來了。
5, 找出單向鍊錶的中間結點這道題和解判斷鍊錶是否存在環，我用的是非常類似的方法，只不過結束迴圈的條件和函式返回值不一樣罷了。設定兩個指標p1，p2。每次迴圈p1向前走一步，p2向前走兩步。
當p2到達鍊錶的末尾時，p1指向的時鍊錶的中間。
link* mid(link* head)
while(p2 && p2->next);
return p1;
}氣泡排序演算法具體**
#include
void bubblesort(int* pdata,int count) }
} }void main()
; bubblesort(data,7);
for (int i=0;i<7;i++)
cout< cout<<"\n"; } …… 少了二叉樹的遍歷及其查詢的一些演算法。有些是直接從網上找的，對第一作者敬禮，感謝你們的無私奉獻。俺分享啦………… a a和 b a,b,c,d 和 c a,b,c,d 和 d a和d 10 乙個深度為k的滿二叉樹有 b 個結點 a 2kb 2k 1c 2k 1 d 2k 1 二 判斷題 1 資料結構主要指物理結構。f 2 空串與空格串是相同的。f 3 乙個廣義表的表頭總是乙個廣義表。f 4 二叉樹按某種順序線索... 選擇題1 下述哪一條是順序儲存結構的優點？a a 儲存密度大 b 插入運算方便 c 刪除運算方便 d 可方便地用於各種邏輯結構的儲存表示 2 下面關於線性表的敘述中，錯誤的是哪乙個？b a 線性表採用順序儲存，必須占用一片連續的儲存單元。b 線性表採用順序儲存，便於進行插入和刪除操作。c 線性表採用... 第一章概論自測題 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的以及它們之間的和運算等的學科。2.資料結構被形式地定義為 d,r 其中d是的有限集合，r是d上的有限集合。3.資料結構包括資料的資料的和資料的這三個方面的內容。4.資料結構按邏輯結構可分為兩大類，它們分別是和 5....資料結構題
資料結構選擇題
資料結構自測題