考試題型：
選擇題（24 ) 填空題（20 ) 解析題（10 ) 運算題（10 ) 簡答題（10 ) 演算法填空（10 )
演算法設計（14 )
第一章緒論
1 ．資料結構的凡個方面，什麼是邏輯結構，什麼是儲存結構。常見的運算有哪些。
答：資料元素之間的邏輯關係，即資料的邏輯結構。
資料元素及其關係在計算機儲存器中的儲存方式，即資料的儲存結構，也稱為資料的物理結構。常見的運算有：檢索、插入、刪除、更新、排序等。
2 . 4 種邏輯結構型別是哪些，4 種儲存結構型別是哪些？
答：邏輯結構型別：集合、線性結構、樹形結構、圖形結構。儲存結構：順序儲存結構、鏈式儲存結構、索引儲存結構、雜湊（或雜湊）儲存結構。
3 ．什麼是抽象資料型別，它包括哪凡個部分？
答：，而不考慮計算機的具體儲存結構和運算的具體實現演算法。它包括資料物件（即資料元素的集合）、資料關係和基本運算三方面的內容。
4 ．演算法的5 個特性是什麼？
答：有窮性、確定性、可行性、有輸入、有輸出。
第二章線性表（imp0rtant )
1 ．線性表的邏輯結構及其特點是什麼？
答：線性表的特點：線性表中的資料元素是各種各樣的，但同一線性表中的元素必定具有相同特性，即屬於同一資料物件；相鄰資料元素之間存在序偶關係，（a1,a2,......
,ai+1,......,an)ai-1是ai的直接前驅元素，ai+1是ai的直接後繼元素；相當靈活，長度可以增長或縮短。
2 ．線性表的順序儲存結構－－一順序表
l ）順序儲存結構是怎樣儲存線性表的？
答：把線性表中的所有元素按照其邏輯順序依次儲存在計算機儲存器中指定儲存位置開始的一塊連續儲存空間中。
2 ）順序儲存型別定義（即結構體定義）是怎樣的？
typedef struct
sqlist；
3 ）順序表的基本運算：建立，輸出，查詢，插入，些運算的時間複雜度是怎樣的？p31-p34
答：建立的時間複雜度:o(n);
輸出的時間複雜度:o(l->length);
查詢的時間複雜度：o(l->length);
插入的時間複雜度：o(n)
3 ．線性表的鏈式儲存結構－－一鍊錶
l ）鏈式儲存結構的特點，它是怎樣儲存線性表的；單鏈表和雙鏈表的區別，各自的特點如何？（演算法關鍵步驟）。
答：在每個結點中除包含有資料域外，只設定乙個指標域，用以指向其直接後繼結點，這種構成的鏈式表稱為線性單向連線表，簡稱單鏈表。在每個結點中除包含有數值域外，設定有兩個指標域，分別用以指向其直接前驅結點和直接後繼結點，這種鍊錶稱為雙鏈表。
單鏈表的特點：在單鏈表中，由於每個結點只包含有乙個指向後繼結點的指標，所以當訪問過乙個結點後，只能接著訪問它的後繼結點，而無法訪問它的前驅結點。
雙鏈表的特點：在雙鏈表中，由於每個結點既包含有乙個指向後繼結點的指標，又包含有乙個指向前驅結點的指標，所以當訪問過乙個結點後，既可以依次向後訪問每乙個結點，也可以依次向前訪問每乙個結點。
2 )單鏈表的型別定義是怎樣的？
typedef struct lnode
linklist；
3 )單鏈表的基本運算：建立、插入、刪除、查詢、輸出等是怎樣進行的（演算法關鍵步驟）。這些運算的時間複雜度是怎樣的？
尤其要弄清楚在單鏈表和雙鏈表插入和刪除某個結點的指標操作，要對教材上的圖2 . 16 和圖2 . 17 有透徹深刻的理解和掌握！
p39—p47
答：建立的時間複雜度:o(n);
輸出的時間複雜度:o(n)；
查詢的時間複雜度:o(n);
插入的時間複雜度;o(n)
4.了解迴圈鍊錶的特點
答：迴圈鍊錶是另一種形式的鏈式儲存結構，它的特點是表中尾結點的指標域不再是空，而是指向頭結點，整個鍊錶形成乙個環。
第三章棧和佇列
1 ．棧的定義，棧這種資料結構的操作特點是什麼？
答：棧是一種只能在一端進行插入或刪除操作的線性表。「後進先出」是棧的主要特點。
2 ．什麼是棧頂，什麼棧底；進棧操作，出棧操作怎樣進行？教材上的相關例題，課件上的相關例題弄明白。
答：表中允許進行插入、刪除操作的一端稱為棧頂。表的另一端稱為棧底。每次進棧的資料元素都放在原當前棧頂元素之前成為新的棧頂元素，每次出棧的資料元素都是原當前棧頂元素。
3 ．棧這種邏輯結構的儲存結構有哪些？順序棧的型別定義、進棧操作、出棧操作是怎樣實現的？
答：順序儲存和鏈式儲存。
typedef struct
sqstack;
在棧不滿的條件下，先將棧頂指標增1，然後在該位置上插入元素e。
在棧不為空的條件下，先將棧頂元素賦給e，然後將棧頂指標減1。
4 ．佇列的定義，佇列這種資料結構的操作特點是什麼？
答：它是一種操作受限的線性表，其限制為僅允許在表一端進行插入，而在表的另一端進行刪除。
5 ．什麼是隊首，什麼是隊尾；進隊、出隊操作是怎樣進行的？
答：把進行插入的一端稱做隊尾，進行刪除的一端稱做隊尾或隊頭。
在對不滿的條件下，先將隊尾指標rear迴圈增1，然後將元素新增到該位置。
在佇列q不為空的條件下，將隊首指標front迴圈增1，並將該位置的元素值賦給e。
第四章串
1 ．串的定義是什麼，什麼是子串，子串的個數怎樣求？
答：串是由零個或多個字元組成的有限序列。乙個串中任意連續字元組成的序列稱為該串的子串。例如：「a」,「ab」,「abc」和「abcd」都是「abce」的子串。
2 ．怎樣判斷兩個串相等？
答：當且僅當兩個串的長度相等並且各個對應位置上的字元都相同時，這兩個串才相等。
3 ．串的長度的定義是什麼？4 ．串的儲存結構有哪些？
答：串中所含字元的個數稱為該串的長度。答：順序串和鏈串。
第七章樹和二叉樹（imp0rtant )
1 ．樹的定義是什麼？
答：樹是由n（n>=0）個結點組成的有限集合（記為t）。
2 ．樹的7 個基本術語
答：（1）結點的度和樹的度。（2）分支結點和葉子結點。
（3）路徑和路徑長度。（4）孩子結點、雙親結點和兄弟結點。（5）結點的層次和樹的高度。
（6）有序樹和無序樹。（7）森林。3 ．二叉樹的定義是怎樣的，二叉樹和樹的區別是什麼？
答：二叉樹也稱為二分樹，它是有限的結點集合，這個集合或者是空，或者由乙個根結點和兩棵互不相交的稱為左子樹和右子樹組成。二叉樹和度為2的樹是不同的，其差別表現在，對於非空樹：
度為2的樹中至少有乙個結點的度為2，而二叉樹沒有這種要求；度為2的樹不區分左、右子樹，而二叉樹是嚴格區分左、右子樹的。
4 ．二叉樹的5 條性質？
答：1：非空二叉樹上葉子結點數等於雙分支結點數加1； 性質2 非空二叉樹上第i層上至多有2i-1個結點，這裡應有i≥1。
性質3 高度為h的二叉樹至多有2h-1個結點(h≥1)。
性質4 對完全二叉樹中編號為i的結點(、（1≤i≤n，n≥1，n為結點數）有：
(1) 若i≤ n/2 ，即2i≤n，則編號為i的結點為分支結點，否則為葉子結點。
(2) 若n為奇數，則每個分支結點都既有左孩子結點，也有右孩子結點；若n為偶數，則編號最大的分支結點（編號為n/2）只有左孩子結點，沒有右孩子結點，其餘分支結點都有左、右孩子結點。
(3) 若編號為i的結點有左孩子結點，則左孩子結點的編號為2i；若編號為i的結點有右孩子結點，則右孩子結點的編號為(2i+1)。
(4) 除樹根結點外，若乙個結點的編號為i，則它的雙親結點的編號為 i/2 ，也就是說，當i為偶數時，其雙親結點的編號為i/2，它是雙親結點的左孩子結點，當i為奇數時，其雙親結點的編號為(i-1)/2，它是雙親結點的右孩子結點。
性質5 具有n個(n＞0)結點的完全二叉樹的高度為 log2n+1 或 log2n +1。
5 ．什麼是滿二叉樹，它有怎樣的特點？
答：在一棵二叉樹中，如果所有分支結點都有左孩子結點和右孩子結點，並且葉結點都集中在二叉樹的最下一層，這樣的二叉樹稱為滿二叉樹。可以對滿二叉樹的結點進行連續編號，約定編號從樹根為1開始，按照層數從小到大、同一層從左到右的次序進行。
6 ．什麼是完全二叉樹，它有怎樣的特點？已知乙個完全二叉樹的高度，它最多能有多少結點，最少能有多少結點？
答：若二叉樹中最多只有最下面兩層的結點的度數可以小於2，並且最下面一層的葉結點都依次排列在該層最左邊的位置上，則這樣的二叉樹稱為完全二叉樹。
7 . p 156 頁二叉樹的5 個性質，結論！（同上4）
8 ．二叉樹的兩種儲存結構是什麼？
答：順序儲存結構和鏈式儲存結構。
9 ．二叉鏈的型別定義是怎樣的？
答： typedef struct node
elemtype data;
struct node *lchild,*rchild;
} btnode;
10 ．二叉樹的遍歷是怎樣進行的：先序遍歷，中序遍歷，後序遍歷？
答：1. 先序遍歷(1) 訪問根結點；(2) 先序遍歷左子樹；(3) 先序遍歷右子樹。
2. 中序遍歷(1) 中序遍歷左子樹；(2) 訪問根結點；(3) 中序遍歷右子樹。
3. 後序遍歷(1) 後序遍歷左子樹；(2) 後序遍歷右子樹；(3) 訪問根結點。
11 ．二叉樹遍歷的遞迴演算法（對**有要求）p166 。
12 ．二叉樹的構造方法p176 ，不需要你掌握具體的**，關鍵是構造的步驟。圖7.15一定要看懂，習題7 . 2 一定要會做，大家明白了吧③
13 ．什麼是哈夫曼樹，哈夫曼樹是怎樣構造（即怎樣畫）的，它的帶權路徑長度怎樣求？
答：具有最小帶權路徑長度的二叉樹稱為哈夫曼樹。那麼如何構造一棵哈夫曼樹呢?
其方法如下:(1)由給定的n個權值構造n棵只有乙個葉子結點的二叉樹,從而得到乙個二叉樹的集合f=;(2)在f中選取根結點的權值最小和次小的兩棵二叉樹作為左、右子樹構造一棵新的二叉樹,這棵新的二叉樹根結點的權值為其左、右子樹根結點權值之和; (3)在集合f中刪除作為左、右子樹的兩棵二叉樹,並將新建立的二叉樹加入到集合f中; (4)重複(2)、(3)兩步,當f中只剩下一棵二叉樹時,這棵二叉樹便是所要建立的哈夫曼樹。
資料結構複習指導
1.資料結構是指 a a.資料元素的組織形式 b.資料型別 c.資料儲存結構d.資料定義 2.資料在計算機儲存器內表示時，實體地址與邏輯位址不相同的，稱之為 c a.儲存結構b.邏輯結構 c.鏈式儲存結構d.順序儲存結構 3.樹形結構是資料元素之間存在一種 d a.一對一關係 b.多對多關係 c.多...
資料結構複習指導
elemtype data struct btnode lchild,rchild,parent btnode,bintree 例 用二叉鍊錶儲存n個結點的二叉樹 n 0 共有 n 1 個空指標域 採用三叉鍊錶儲存，共有 n 2 個空指標域。空樹 bt null 左右子樹均空 bt lchild n...
《資料結構》複習指導
自學考試 資料結構 複習指導 第一章 緒論 一 概念 資料結構 是一門研究程式設計中計算機操作的物件以及它們之間的關係和運算的一門學科。資料 是描述額觀事物的數 字元以及所有能輸入到計算機中被電腦程式加工處理的資訊的集合。資料元素 資料元素是資料的基本單位。乙個資料項或多個資料項 域 資料項是資料的...