本複習大綱按章分別敘述三方面的內容：
1、考試大綱要求， 2、複習考試知識點，3、應用舉例。
為了方便考生複習，知識點還給出較詳細的描述內容，舉例題型也給出具體的分析過程和完整的參***。
第一章緒論
考綱要求：
1.資料的四種邏輯結構與四種儲存結構（理解） 2. 時間複雜度的估算及比較（掌握）
知識點：
1 、資料結構：研究是是資料元素之間抽象化的相互關係和這種關係在計算機中的存貯表示，並對每種結構定義各自的運算，設計出相應的演算法，而且經過運算後所得的新結構一般仍然是原來的結構型別。
2、資料的四類基本組成形式：集合中任何兩個結點之間都沒有邏輯關係，組成形式鬆散。線性結構中結點按邏輯關係一次排列形成一條「鎖鏈」。
樹形結構具有分支、層次特性，其形態有點像自然界中的樹。圖狀結構最複雜，其中的各個結點按邏輯關係互相纏繞，任何兩個結點都可以鄰接。
演算法：是執行特定計算的有窮過程。特點：·動態有窮·確定性·輸入·輸出·可行性。
1、以演算法在所有輸入下的計算量的最大值作為演算法的計算量，這種計算量稱為演算法的最壞時間複雜性或最壞時間複雜度。
2、以演算法在所有輸入下的計算量的加權平均值作為演算法的計算量，這種計算量稱為演算法的平均時間複雜性或者平均時間複雜度。
3. 時間複雜度從好到壞的級別依次是:
常量階o(1),對數階o(log2n),線性階o(n), 優化的平方階o(n*log2n),平方階o(n2),立方階o(n3),指數階o(2),階乘階o(n!)
4、資料結構的基本任務可以概括為資料結構的設計和實現。
應用舉例：
設n為正整數，利用大"o"記號，將下列程式段的執行時間表示為n的函式。
(1) i=1; k=0;
while(i第二章線性表:
考綱要求：
1線性表的順序儲存、鏈式儲存的各種演算法（掌握） 2 線性表的插入、刪除演算法（掌握），3 雙向鍊錶及迴圈鍊錶的插入、刪除過程（掌握）
知識點：
1、線性結構是n(n>=0)個結點的有窮序列。
線性表:n(n≥0)個結點組成的有限序列
線性結構中的元素是有序的，元素個數可以為0 — 空表
元素的個數是有限的
同一線性表中的元素的型別,長度相同.
2、每個結點至多只有乙個之間前趨和乙個直接後趨，**性結構中這種關係是1對1的。
3、線性表的邏輯結構是線性結構。所含結點的個數稱為線性表的長度（簡稱表長）。表長為0的線性表為空表。
4、順序表是線性表的順序儲存結構，即按順序儲存方式構造的線性表的儲存結構。
5、第i個結點ai的儲存位址為b+（i－1）×l （l為記憶體所佔單元/表長。b是順序表的第乙個儲存結點的第乙個單元的記憶體位址。）
6、線性表採用鏈式儲存結構時，要求記憶體中可用儲存單元的位址連不連續都可以。
7、求表長和讀表元演算法的時間複雜性為o（1），從量級上來說已經達到最低水平即最高效率。
8、順序表要求占用連續的空間，為克服順序表的這一缺點，可採用鏈結方式來儲存線性表，通常我們將鏈結方式儲存的線性表稱為鍊錶。
9、線性表的常見鏈式儲存結構有單鏈表、迴圈表和雙鏈表，最簡單的是單鏈表。
10、定位運算在順序表和單鏈表上的實現演算法的時間複雜性是同量級的，均為o（n）。
11. 線性結構的邏輯表示如下:
l1=() l1是乙個空的線性結構;
l2=(a,b,c,d,e) l2線性結構中有5個元素,a是起始元素,e是終端元素,c的直接前驅元素是b,c的直接後繼元素是d,a元素的序號是1,c元素的序號是3.
l1=() l1線性表的長度為零
l2=(a,b,c,d,e) l2線性表的長度為5
12 鍊錶中的元素順序用結點中的指標給出,即用指標表示結點間的邏輯關係, 元素順序與邏輯順序一致.採用順序訪問方式.
. 鍊錶的長度是可變的
應用舉例：
1、下述演算法的功能是什麼?
linklist demo(linklist l)
return l;
}// demo
答： 該演算法的功能是：將開始結點摘下鏈結到終端結點之後成為新的終端結點，而原來的第二個結點成為新的開始結點，返回新鍊錶的頭指標。
2. 設順序表l是乙個遞增有序表，試寫一演算法，將x插入l中，並使l仍是乙個有序表。
答： 因已知順序表l是遞增有序表，所以只要從順序表終端結點（設為i位置元素）開始向前尋找到第乙個小於或等於x的元素位置i後插入該位置即可。
在尋找過程中，由於大於x的元素都應放在x之後，所以可邊尋找，邊後移元素，當找到第乙個小於或等於x的元素位置i時，該位置也空出來了。
演算法如下：
//順序表儲存結構如題2.7
void insertincreaselist( seqlist *l , datatype x )
第三章棧與佇列:
考綱要求：
1 棧的儲存及運算實現（掌握） ,2 棧的應用：表示式求值（理解）
3 棧與遞迴的實現（理解） ,4 佇列的定義及儲存實現（掌握）
知識點：
1. 棧:棧是限定僅在一端進行插入,刪除的特殊線性表.，棧屬於加了限定條件的線性結構，棧是後進先出的線性表
(1) 進棧和出棧端稱為棧頂,另一端稱為棧底
(2) 棧中元素個數為0時為空棧.
(3) 棧中的元素個數為有限多個
(4) 同乙個棧中的元素的型別,長度相同
新進棧的元素稱為棧頂元素
(5) 棧的順序實現:使用乙個陣列data,棧底元素存放在data(0)中,top值為棧內元素個數及位置,空棧時top=-1
(6) 使用乙個結構體變數表示乙個棧元素:其中乙個域為陣列data,另乙個為top
(7) 棧的鏈結實現:使用鍊錶實現棧的儲存
(8) 鏈棧:鍊錶的首元素定為棧頂元素,尾元素為棧底.
2、佇列也可以看成是一種運算受限的線性表，在這種線性表中允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。佇列又稱為先進先出線性表。
(1)、隊滿的條件為：（隊尾指標+1）%長度= =隊內指標如：（（sq.rear+1）%maxsize）= =sq.front
隊空的條件為：sq.rear= =sq.front
(2).佇列:限定僅能在一端進隊,另一端出隊的特殊線性表
(3) 加限制的線性結構，先進先出表
(4) 進隊在隊尾,出隊在隊首(頭)，可以是空隊
(5) 佇列中的元素個數是有限的,可變的，元素的型別,長度相同
應用舉例：
1、指出下述程式段的功能是什麼?
(4)void demo3( cirqueue *q)
while (! stackempty( &s))
}// demo3
功能是：程式段的功能是將乙個迴圈佇列q經過s棧的處理，反向排列，原來的隊頭變成隊尾，原來的隊尾變成隊頭。
2. 設將整數1，2，3，4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請分析 1，2 ，3 ，4 的24種排列中，哪些序列是可以通過相應的入出棧操作得到的。
答： 在1，2 ，3 ，4 的24種排列中，可通過相應入出棧操作得到的序列是：
1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321
不能得到的序列是：
1423,2413,3124,3142,3412,4123,4132,4213,4231,4312
第四章串,
考綱要求：
1 串的模式匹配演算法（理解）
知識點：
1、串是由零個或多個字元組成的有窮序列。含零個字元的串稱為空串，用表示。
2. 串（又稱字串）是一種特殊的線性表，它的每個結點僅由乙個字元組成。串（string）是零個或多個字元組成的有限序列。一般記為s="a1a2……an"
將串值括起來的雙引號本身不屬於串,它的作用是避免串與常數或與識別符號混淆。
3. 長度為零的串稱為空串（empty string），它不包含任何字元。 僅由乙個或多個空格組成的串稱為空白串（blank string）。
″ ″和″″分別表示長度為1的空白串和長度為0的空串。
4. 串中任意個連續字元組成的子串行稱為該串的子串。包含子串的串相應地稱為主串。
①空串是任意串的子串 ②任意串是其自身的子串。
5. 通常在程式中使用的串可分為：串變數和串常量。
串變數和其它型別的變數一樣，其取值是可以改變的。串常量和整常數、實常數一樣，在程式中只能被引用但不能改變其值。即只能讀不能寫。
6. 對於某乙個i,0 i n-m,將目標串的子串t[i..i+m-1]和模式串p[0..m-1]進行比較,若相等,則稱匹配成功
位置i 稱為位移
舉例：4.2 假設有如下的串說明： char s1[30]="stocktom,ca", s2[30]="march 5 1999", s3[30], *p;
(1)在執行如下的每個語句後p的值是什麼?
p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');
(2)在執行下列語句後，s3的值是什麼?
strcpy(s3,s1); strcat(s3,","); strcat(s3,s2);
解： (1) stchr(*s,c)函式的功能是查詢字元c在串s中的位置，若找到，則返回該位置，否則返回null。
因此:執行p=stchr(s1,'t');後p的值是指向第乙個字元t的位置, 也就是p==&s1[1]。
執行p=strchr(s2,'9');後p的值是指向s2串中第乙個9所在的位置,也就是p==&s2[9]。
` 執行p=strchr(s2,'6');之後，p的返回值是null。
(2)strcpy函式功能是串拷貝，strcat函式的功能是串聯接。所以:
在執行strcpy(s3,s1); 後，s3的值是"stocktom,ca"
在執行strcat(s3,","); 後，s3的值變成"stocktom,ca,"
在執行完strcat(s3,s2);後，s3的值就成了"stocktom,ca,march 5,1999"
資料結構複習大綱
5.單鏈表中結點的結構，每個域的定義及作用，即lnode型別的定義及結構。6.帶表頭附加結點的鍊錶 迴圈鍊錶 雙向鍊錶的結構特點。7.線性表的每一種運算在單鏈表上實現的演算法及相應的時間複雜度。8.在順序儲存或鏈結儲存的線性表上實現指定功能的演算法的分析和設計。9 josephus問題的求解過程。1...
資料結構去年大綱
2014年研究生入學考試自命題科目 資料結構 考試大綱 第一部分考試說明 一 考試性質 資料結構是計算機學院軟體工程專業的碩士研究生入考試專業基礎課。二 考試形式與試卷結構 一 答卷方式 閉卷，筆試 二 答題時間 180分鐘 三 考試題型 試卷共150分，基本的考試題型有 1 單項選擇題和多項選擇題...
資料結構考試大綱
複習大綱 緒論部分 基本概念掌握 資料結構，邏輯結構，儲存結構 資料型別 演算法 t n s n 的理解。要學習的資料結構定義形式 n n 0 個資料元素的有限集合。將約束 1 資料元素本身。2 資料元素之間的關係。3 操作子集。大多有兩種儲存 表示 實現 方式 1 順序儲存。2 鏈式儲存。一 線性...