第一章1. 計算機解決問題的步驟：
1) 首先要從具體問題抽象出乙個適當的數學模型
2) 然後設計乙個解此數學模型的演算法
3) 最後編出程式
4) 進行測試、調整直至得到最終解答
2. 資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和操作等的學科
3. 資料：對客觀事物的符號表示，在電腦科學中是指所有能輸入到計算機中並被電腦程式處理的符號的總稱
4. 資料元素：資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理
5. 資料物件：性質相同的資料元素的集合，是資料的乙個子集
6. 資料結構是相互之間存在一種或多種特定關係的資料元素的集合。具有四類基本結構：集合、線性結構（一對一）、樹形結構（一對多）、圖狀結構（多對多）
邏輯結構：資料結構是乙個二元組（d,s），d是資料元素的有限集，s是d上關係的有限集。
物理結構：又稱儲存結構，是資料結構在計算機中的表示（又稱映像）。可分為：
1) 順序儲存結構：把結點儲存在物理上相鄰的一組儲存單位元裡，結點之間的關係由儲存單元的鄰接關係來體現
2) 鏈式儲存結構：對結點所佔的儲存單元分為兩部分，一部分存放結點本身的資訊，另一部分存放該結點的後繼結點所對應的儲存單元的位址
7. 資料型別是乙個值的集合和定義在這個值集上的一組操作的總稱。具體可分為：
1) 原子型別：值不可分解
2) 結構型別：值由若干成分按某種結構組成，成分可以是結構的，也可以是非結構的
引入「資料結構」的目的：
1) 硬體的角度：是作為解釋計算機記憶體中資訊含義的一種手段
2) 使用者的角度：實現了資訊的隱蔽，即將一切使用者不必了解的細節都封裝在型別中
8. 抽象資料型別（adt）：乙個數學模型以及定義在該模型上的一組操作。
可用三元組（d,s,p）表示，d是資料物件，s是d上的關係集，p是對d的基本操作集。「抽象」的意義在於資料型別的數學抽象特性。可分為：
1) 原子型別：值不可分解
2) 固定聚合型別：值由確定數目的成份按某種結構組成
3) 可變聚合型別：值的成分的數目不確定
9. 多行資料型別：其值的成分不確定的資料型別
10. 動態分配和靜態分配是用以控制程式可使用的記憶體數量的兩種基本管理方法。靜態分配是指在應用程式執行之前記憶體就已經分配完畢；動態分配是指在應用程式執行過程中向作業系統申請一塊記憶體
11. 演算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每個條指令表示乙個或者多個操作。特性：有窮性、可行性、確定性、輸入、輸出
12. 演算法設計要求：
1) 正確性
2) 可讀性
3) 健壯性
4) 效率與低儲存量需求
13. 度量效率的方法：事後統計、事前分析估算
14. 演算法的漸近時間複雜度：隨問題規模n的增大，演算法執行時間的增長率和f(n)的增長率相同，記作t(n)=o(f(n))；演算法的空間複雜度：s(n)=o(f(n))
15. 語句的頻度：該語句重複執行的次數
16. 增長率排序：常數階o(1)《對數階o()《線性階o(n)《線性對數階o()《平方階o()《立方階o()17. 儲存空間需求：① 指令、常數、變數
② 輸入資料
③ 對資料進行操作的工作單元
④ 為實現計算機所需資訊的輔助空間
第二章1. 線性表是n個資料元素的有限序列。
特點：1)同一線性表中的元素必定具有相同特性，即屬同一資料物件
2)相鄰資料元素之間存在著序偶關係
3)線性表中元素的個數n（n≥0）定義為其長度，n=0時為空表
2. 常見的線性結構有：線性表、棧、佇列。線性結構的特點：在資料元素非空有限集中，
1) 存在唯一的乙個被稱作「第乙個」的資料元素
2) 存在唯一的乙個被稱作「最後乙個」的資料元素
3) 除第乙個之外，集合中的每個資料元素均只有乙個前驅
4) 除最後乙個之外，集合中每個資料元素均只有乙個後繼
5) 棧具有「後進先出」的特點；佇列具有「先進先出」的特點
3. 線性表順序表示的優缺點：
優點：邏輯關係上相鄰的兩個元素在物理位置上也相鄰，可以隨機訪問表中任一元素，它的儲存位置可用乙個簡單、直觀的公式來表示
缺點：在作插入或刪除操作時，需移動大量元素
4. 常見的儲存表示方法：順序儲存和鏈式儲存
順序儲存：在計算機中用一組位址連續的儲存單元依次儲存線性表的各個資料元素,稱作線性表的順序儲存結構
鏈式儲存：在計算機中用一組任意的儲存單元儲存線性表的資料元素(這組儲存單元可以是連續的,也可以是不連續的)
5. 頭指標：指向開始結點的指標（沒有頭結點時）
開始結點：鍊錶中的第乙個結點，也就是沒有直接前驅的結點
頭結點：附設於單鏈表的第乙個節點之前的乙個結點
6. 幾種鍊錶：
1) 線性鍊錶
2) 迴圈鍊錶：最後乙個結點的指標域指向頭結點
3) 雙向鍊錶：乙個結點有兩個指標域，乙個指向直接後繼，另乙個指向直接前驅
第三章1. 棧：限定僅在表尾進行插入或刪除操作的線性表。特點：先進後出。注：非空棧的棧頂指標始終在棧頂元素的下乙個位置上
2. 佇列：佇列是一種先進先出的線性表。它只允許在表的一端進行插入，而在另一端刪除元素；迴圈佇列：將順序佇列臆造為乙個環狀的空間稱之為迴圈佇列
3. 常見的溢位現象：
1) 下溢：當隊列為空時，作出隊運算產生的溢位現象
2) 真上溢：當隊列為滿時，作進隊運算產生空間溢位的現象
3) 假上溢：當佇列中實際元素個數遠小於空間規模時，由於尾指標已超過空間的上界，而不能作入隊操作的現象
4. 克服溢位的方法：
1) 另設乙個標誌位以區別佇列是「空」還是「滿」
2) 少用乙個元素空間，約定以「佇列頭指標在佇列尾指標的下一位置（指環狀的下一位置）上」作為佇列呈「滿」狀態的標誌
3) 使用乙個計數器來記錄佇列中元素的總數
第六章1. 樹：樹是n（n≥0）個結點的有限集。
在任意一棵非空樹種：1)有且僅有乙個根結點
2)當n>1時，其餘結點可分為m個互不相交的有限集，其中每乙個集合本身又是一棵樹，並且稱為根的子樹
2. 基本術語：
1) 結點：包含乙個資料元素及若干指向其子樹的分支
2) 結點的度：結點擁有的子樹數
3) 葉子：度為0的結點
4) 樹的度：樹內各結點的度的最大值
5) 孩子：結點的子樹的根。該結點稱為孩子的雙親
6) 兄弟：同一雙親的孩子之間互稱兄弟
7) 堂兄弟：其雙親在同一層的結點互稱堂兄弟
8) 祖先：從根到該結點所經分支上的所有結點
9) 子孫：以某結點為根的子樹中的任一節點
10) 森林：m棵互不相交的樹的集合
3. 二叉樹：
1) 定義：二叉樹是另一種樹型結構，它的特點是每個結點至多只有兩棵子樹。並且，二叉樹的子樹有左右之分，其次序不能任意顛倒
2) 性質：①在二叉樹的第i層上至多有個結點（i≥1）
②深度為k的二叉樹至多有個結點（k≥1）
③若二叉樹葉子結點數為，度為2的結點數為，則
3) 滿二叉樹：深度為k且有個結點的二叉樹
完全二叉樹：深度為k，有n個結點的二叉樹，每乙個結點都與深度為k的滿二叉樹中的結點編號對應
4) 儲存結構：
①順序②鏈式：資料域、左指標域、右指標域、（雙親結點的指標域）
5) 遍歷二叉樹：
①先序：根結點→左子樹→右子樹
②中序：左子樹→根結點→右子樹
③後序：左子樹→右子樹→根結點
④層序：從上到下，從左到後
4. 樹的儲存結構：
1) 雙親表示法：該結點+該結點的雙親結點的位置
2) 孩子表示法：該結點+該結點的孩子結點的位置
5. 樹與二叉樹的轉換：
1) 樹→二叉樹：加線→抹線→旋轉
2) 二叉樹→樹：加線→抹線→規整化
資料結構考試重點
資料結構 第一章緒論 1 資料結構的定義 按照某種邏輯關係組織起來的資料集 2 資料主要分為兩大類 數值型資料和非數值型別資料。數值型資料主要包括整數 實數和複數等 非數值型別資料報括字元 字串 文字 聲音 圖形 影象等。3 資料結構的邏輯結構是指資料元素的集合以及定義在該集合上的資料元素之間的一種...
09級資料結構試卷 A
2011 2012學年第2學期閩江學院考試試卷 考試課程 資料結構 試卷類別 a卷 b卷 考試形式 閉卷 開卷 適用專業年級 09地理資訊班 09級資源環境 班級姓名學號 1 在建立某高校 時，為方便瀏覽，建立了校 系 教研室的鏈結，則這資料結構屬於 a 線性結構 b 樹結構 c 圖結構 d 集合結...
資料結構2019級期末考試 A
2010級夜大資料結構期末考試試題 a卷 姓名學號序號 成績 注意事項 本試卷滿分100分，考試時間120分鐘 一.單項選擇題，每題有乙個正確選擇。每題2分，共20分 1.下列資料結構中是線性結構。a二叉樹 b 樹 c佇列 d 圖 2.以下關於演算法的說法不正確的是 a 乙個演算法應包含有限個步驟 ...