5. 單鏈表中結點的結構，每個域的定義及作用，即lnode型別的定義及結構。
6. 帶表頭附加結點的鍊錶、迴圈鍊錶、雙向鍊錶的結構特點。
7. 線性表的每一種運算在單鏈表上實現的演算法及相應的時間複雜度。
8. 在順序儲存或鏈結儲存的線性表上實現指定功能的演算法的分析和設計。
9．josephus問題的求解過程。
10．順序表和線性鍊錶的效能比較及各自使用背景。
對於本章的其餘內容均作一般掌握。
第四章棧和佇列
重點掌握的內容：
1. 棧的定義和抽象資料型別的描述，棧中每一種操作的功能，對應的函式名、返回值型別和參數列中每個引數的作用。
2. 棧的順序儲存結構的型別定義，即stack型別的定義和每個域的定義及作用。
3．棧的每一種運算在順序儲存結構上實現的演算法，及相應的時間複雜度。
4. 棧的每一種運算在鏈結儲存結構上實現的演算法及相應的時間複雜度。
5. 算術表示式的中綴表示和字尾表示，以及相互轉換的規則，字尾表示式求值的方法。
6．給定n個棧元素, 出棧可能或不可能的序列數。
7. 佇列的定義和抽象資料型別的描述，佇列中每一種操作的功能，對應的函式名、返回值型別和參數列中每個引數的作用。
8. 佇列的順序儲存結構的型別定義，即queue型別的定義和每個域的定義及作用。
9. 佇列的每一種運算在順序儲存結構上實現的演算法及相應的時間複雜度。
10. 利用棧和佇列解決簡單問題的演算法分析和設計。
11．雙端隊的概念及可能出隊序列。
12．隊和棧的應用背景，如cpu隊、程序隊、印表機隊。
13．鏈隊的各種儲存表示。
一般掌握的內容：
1. 字尾表示式求值的演算法，把中綴表示式轉換為字尾表示式的演算法。
2. 佇列的鏈結儲存結構，以及實現每一種佇列運算的演算法和相應的時間複雜度。
對於本章的其餘內容均作一般了解。
第六章樹和二叉樹
重點掌握的內容：
1. 樹和二叉樹的定義，對於一棵具體樹和二叉樹的二元組表示及廣義表表示。
2. 樹和二叉樹的概念，如結點的度、樹的度、樹葉、分枝結點、樹的層數、樹的深度等。
3．不同結點數的樹和二叉樹的形態。
4. 樹和二叉樹的性質，如已知樹或二叉樹的深度h可求出相應的最多結點數，已知結點數n可求出對應樹或二叉樹的最大和最小高度。
5. 二叉樹中結點的編號規則和對應的順序儲存結構。
6. 二叉樹的鏈結儲存結構及儲存結點的型別定義，即btreenode型別的定義和每個域的定義及作用。
7. 二叉樹的先序、中序、後序、遍歷的遞迴過程和遞迴演算法，中序遍歷的非遞迴演算法，按層遍歷的過程和演算法，每種演算法的時間複雜度。
8．二叉樹的先序、中序、後序遍歷序列，唯一確定一棵二叉樹的原則。
9．算術表示式的二叉樹表示及逆波蘭表示式、中綴表示。
一般掌握的內容：
1. 普通樹的鏈結儲存結構，gtreenode型別的定義和每個域的定義及作用。
2．普通樹的先根、後根和按層遍歷的過程及演算法。
3. 在鏈結儲存的二叉樹上實現指定功能的演算法分析和設計。
對於本章的其餘內容均作一般了解。
第七章圖
重點掌握的內容：
1. 圖的頂點集和邊集的表示。
2. 圖的一些概念的含義，如頂點、邊、度、完全圖、子圖、路徑、路徑長度、連通圖、權、網等。
3. 圖的鄰接矩陣、鄰接表、鄰接多重表和十字鍊錶四種儲存結構及相應的空間複雜度。
4. 儲存圖使用的vexlist, adjmatrix, adjlist, edgenode, edgeset, edge等型別的定義及用途。
5. 圖的深度優先和廣度優先搜尋遍歷的過程。
6. 對分別用鄰接矩陣和用鄰接表表示的圖進行深度優先搜尋遍歷的過程、演算法描述以及相應的時間複雜度。
7. 對分別用鄰接矩陣和用鄰接表表示的圖進行廣度優先搜尋遍歷的過程、演算法描述以及相應的時間複雜度。
8. 圖的生成樹（若乙個具有n個頂點，e條邊的無向圖是乙個森林（n＞e），則該森林中必有多少棵樹。）、深度優先生成樹和廣度優先生成樹、生成樹的權、最小生成樹等的定義。
9. 根據普里姆演算法求圖的最小生成樹的過程。
10．根據克魯斯卡爾演算法求圖的最小生成樹的過程。
11. 圖的拓撲序列和拓撲排序的概念，求圖的拓撲序列的方法，對用鄰接表表示的圖進行拓撲排序的過程。
12．強連通圖的最少邊數。
一般掌握的內容：
1．根據普里姆演算法求圖的最小生成樹的演算法描述。
2．根據克魯斯卡爾演算法求圖的最小生成樹的演算法描述。
3. 對用鄰接表表示的圖進行拓撲排序的和演算法描述。
對本章的其餘內容均作一般了解。
頭指標頭結點
（ × ）1. 鍊錶的每個結點中都恰好包含乙個指標。
錯，鍊錶中的結點可含多個指標域，分別存放多個指標。例如，雙向鍊錶中的結點可以含有兩個指標域，分別存放指向其直接前驅和直接後繼結點的指標。
（ × ）2. 鍊錶的物理儲存結構具有同煉表一樣的順序。
錯，鍊錶的儲存結構特點是無序，而鍊錶的示意圖有序。
（ × ）3. 鍊錶的刪除演算法很簡單，因為當刪除鏈中某個結點後，計算機會自動地將後續的各個單元向前移動。
錯，鍊錶的結點不會移動，只是指標內容改變。
（ × ）4. 順序表結構適宜於進行順序訪問，而鍊錶適宜於進行隨機訪問。
錯，正好說反了。順序表才適合隨機訪問，鍊錶恰恰適於「順藤摸瓜」。
（ × ）5. 順序儲存方式的優點是儲存密度大，且插入、刪除運算效率高。
錯，前一半正確，但後一半說法錯誤，那是鏈式儲存的優點。順序儲存方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除乙個資料元素，平均需移動表長一半個數的資料元素。
（ × ）6. 順序儲存方式只能用於儲存線性結構。
錯誤。順序儲存方式不僅能用於儲存線性結構，還可以用來存放非線性結構，例如完全二叉樹是屬於非線性結構，但其最佳儲存方式是順序儲存方式。
資料結構和資料型別兩個概念之間有區別嗎？
答：簡單地說，資料結構定義了一組按某些關係結合在一起的陣列元素。資料型別不僅定義了一組帶結構的資料元素，而且還在其上定義了一組操作。
試比較順序儲存結構和鏈式儲存結構的優缺點。在什麼情況下用順序錶比鍊錶好？
答：① 順序儲存時，相鄰資料元素的存放位址也相鄰（邏輯與物理統一）；要求記憶體中可用儲存單元的位址必須是連續的。
優點：儲存密度大（＝1？），儲存空間利用率高。缺點：插入或刪除元素時不方便。
②鏈式儲存時，相鄰資料元素可隨意存放，但所佔儲存空間分兩部分，一部分存放結點值，另一部分存放表示結點間關係的指標
優點：插入或刪除元素時很方便，使用靈活。缺點：儲存密度小（<1），儲存空間利用率低。
順序表適宜於做查詢這樣的靜態操作；鍊錶宜於做插入、刪除這樣的動態操作。
若線性表的長度變化不大，且其主要操作是查詢，則採用順序表；
若線性表的長度變化較大，且其主要操作是插入、刪除操作，則採用鍊錶。
描述以下三個概念的區別：頭指標、頭結點、首元結點（第乙個元素結點）。在單鏈表中設定頭結點的作用是什麼？
答：首元結點是指煉表中儲存線性表中第乙個資料元素a1的結點。為了操作方便，通常在鍊錶的首元結點之前附設乙個結點，稱為頭結點，該結點的資料域中不儲存線性表的資料元素，其作用是為了對鍊錶進行操作時，可以對空表、非空表的情況以及對首元結點進行統一處理。
頭指標是指向鍊錶中第乙個結點（或為頭結點或為首元結點）的指標。若煉表中附設頭結點，則不管線性表是否為空表，頭指標均不為空。否則表示空表的鍊錶的頭指標為空。
這三個概念對單鏈表、雙向鍊錶和迴圈鍊錶均適用。是否設定頭結點，是不同的儲存結構表示同一邏輯結構的問題。
頭結點頭指標首元結點
簡而言之，
頭指標是指向鍊錶中第乙個結點（或為頭結點或為首元結點）的指標；
頭結點是在鍊錶的首元結點之前附設的乙個結點；資料域內只放空表標誌和表長等資訊（內放頭指標？那還得另配乙個頭指標！！！）
首元素結點是指煉表中儲存線性表中第乙個資料元素a1的結點。
單鏈表1、鏈結儲存方法
鏈結方式儲存的線性表簡稱為鍊錶（linked list）。
鍊錶的具體儲存表示為：
① 用一組任意的儲存單元來存放線性表的結點（這組儲存單元既可以是連續的，也可以是不連續的）
② 鍊錶中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關係，在儲存每個結點值的同時，還必須儲存指示其後繼結點的位址（或位置）資訊（稱為指標（pointer）或鏈(link)）
注意： 鏈式儲存是最常用的儲存方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的資料結構。
2、鍊錶的結點結構
┌──┬──┐
|data | next│
└──┴──┘
data域--存放結點值的資料域
next域--存放結點的直接後繼的位址（位置）的指標域（鏈域）
注意： ①鍊錶通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈結在一起的。
②每個結點只有乙個鏈域的鍊錶稱為單鏈表（single linked list）。
【例】線性表（bat，cat，eat，fat，hat，jat，lat，mat）的單鏈表示如示意圖
3、頭指標head和終端結點指標域的表示
單鏈表中每個結點的儲存位址是存放在其前趨結點next域中，而開始結點無前驅，故應設頭指標head指向開始結點。
注意： 鍊錶由頭指標唯一確定，單鏈表可以用頭指標的名字來命名。
【例】頭指標名是head的鍊錶可稱為表head。
終端結點無後繼，故終端結點的指標域為空，即null。
4、單鏈表的一般圖示法
由於我們常常只注重結點間的邏輯順序，不關心每個結點的實際位置，可以用箭頭來表示鏈域中的指標，線性表（bat，cat，fat，hat，jat，lat，mat）的單鏈表就可以表示為下圖形式。
5、單鏈表型別描述
typedef char datatype; /* 假設結點的資料域型別為字元 */
typedef struct node listnode;
typedef listnode *linklist;
listnode *p;
linklist head;
注意：①linklist和listnode *是不同名字的同乙個指標型別（命名的不同是為了概念上更明確）
②linklist型別的指標變數head表示它是單鏈表的頭指標
③listnode *型別的指標變數p表示它是指向某一結點的指標
6、指標變數和結點變數
指標變數結點變數 │
│ 定義 │在變數說明部分顯式定義 │在程式執行時，通過標準 │
│││函式malloc生成│
│ 取值 │ 非空時，存放某型別結點 │實際存放結點各域內容 │
│ │ 的位址 | │
│操作方式│ 通過指標變數名訪問 │通過指標生成、訪問和釋放 │
①生成結點變數的標準函式
p = malloc( sizeof(listnode) );
/* 函式malloc分配乙個型別為listnode的結點變數的空間,並將其首位址放入指標變數p中 */
②釋放結點變數空間的標準函式
free(p); /* 釋放p所指的結點變數空間 */
③結點分量的訪問
利用結點變數的名字*p訪問結點分量
方法一：(*p).data和(*p).next
方法二：p-﹥data和p-﹥next
④指標變數p和結點變數*p的關係
指標變數p的值——結點位址
結點變數*p的值——結點內容
(*p).data的值——p指標所指結點的data域的值
(*p).next的值——*p後繼結點的位址
*((*p).next)——*p後繼結點
《資料結構》考前複習大綱
本複習大綱按章分別敘述三方面的內容 1 考試大綱要求，2 複習考試知識點，3 應用舉例。為了方便考生複習，知識點還給出較詳細的描述內容，舉例題型也給出具體的分析過程和完整的參 第一章緒論 考綱要求 1.資料的四種邏輯結構與四種儲存結構 理解 2.時間複雜度的估算及比較 掌握 知識點 1 資料結構 研...
資料結構去年大綱
2014年研究生入學考試自命題科目 資料結構 考試大綱 第一部分考試說明 一 考試性質 資料結構是計算機學院軟體工程專業的碩士研究生入考試專業基礎課。二 考試形式與試卷結構 一 答卷方式 閉卷，筆試 二 答題時間 180分鐘 三 考試題型 試卷共150分，基本的考試題型有 1 單項選擇題和多項選擇題...
資料結構考試大綱
複習大綱 緒論部分 基本概念掌握 資料結構，邏輯結構，儲存結構 資料型別 演算法 t n s n 的理解。要學習的資料結構定義形式 n n 0 個資料元素的有限集合。將約束 1 資料元素本身。2 資料元素之間的關係。3 操作子集。大多有兩種儲存 表示 實現 方式 1 順序儲存。2 鏈式儲存。一 線性...