課程**：21049
適用專業：計算機應用、計算機網路
串講教師：北京航空航天大學唐髮根
考試題型
第一部分選擇題
一、單項選擇題 (每小題2分，共20分)
第二部分非選擇題
二、填空題 (每空2分，共20分)
三、簡答題 (15分)
四、問題求解題 (每小題10分，共20分)
五、演算法填空題 (25分)
第一章緒論
主要分為線性結構和非線性結構。線性表屬於線性結構；非線性結構包括樹和圖。
結構是資料元素之間的邏輯關係。結構分為邏輯結構與物理結構。邏輯結構(線性關係、非線性關係)，物理結構(儲存結構) 主要有順序結構和鏈式結構。
演算法就是解決問題的方法。演算法與程式都能表示出完成的過程，而演算法獨立於具體的計算機，與實現的機器、實現的語言無關。
演算法分析作用是評價演算法質量的優劣，目的是改進演算法。
演算法分析的前提是演算法必須正確，主要從時間複雜度、空間複雜度以及其他方面進行演算法分析。
第二章線性表
線性關係是有前後順序，一一對應的關係。
線性表的儲存結構有順序結構、鏈式結構、索引結構、雜湊結構。
線性表的基本運算包括：插入、刪除、查詢、排序。
線性表順序儲存結構的構造特點：在儲存器中有一片位址連續的空間。會根據公式loc(ai)=loc(a1)+(i-1)*k求位址。
線性表的插入、刪除操作步驟及應考慮的問題：是否滿表或空表。
線性表的鏈式儲存方式包括：單鏈表、迴圈鍊錶和雙向鍊錶。各種鍊錶的構造原理以及之間的區別。
順序儲存結構的特點。優點：儲存密度大、簡單。
資料元素的位址可以通過公式計算。缺點：插入、刪除操作效率低，儲存空間需要按最大需求事先分配，且要求一片連續的儲存空間，容易造成浪費。
鏈式儲存結構的特點。優點：儲存空間按需分配，實報實銷，結構空間；插入、刪除操作效率高。缺點：鍊錶中的結點需要儲存指標，構造本身比順序儲存結構大。
本章將有演算法題出現。
第三章陣列
陣列是定長結構的線性表。
陣列的操作：訪問、修改、檢索、排序。陣列沒有插入和刪除操作。
特殊矩陣的壓縮儲存：對稱矩陣、對角矩陣、稀疏矩陣。
稀疏矩陣的三元組表示(將作為第八章的問題求解題的已知條件出現)。
第四章堆疊和佇列
堆疊和佇列是線性表操作的子集，操作受到限制。它們的邏輯關係均為線性關係。
堆疊不空可以刪除元素。
堆疊和佇列的結構、操作。
順序結構和鏈式結構的構造
堆疊和佇列的插入、刪除演算法設計。要注意是否為空或是否溢位。
本章將有演算法題出現。
第五章廣義表
廣義表的基本概念，廣義表是允許表中套表的表。
會求廣義表的深度和長度。
第六章串
串的定義。
串的模式匹配。
空串與由空格組成的串的區別。
第七章樹與二叉樹
樹的結構是層次結構。
樹的特點。樹的度。
滿二叉樹與完全二叉樹的定義、關係。
二叉樹的性質，其中性質三要求會推導。
二叉樹的二叉鍊錶儲存結構。
二叉樹的前序、中序、後序及按層次遍歷要會求解相關問題及掌握演算法。
由遍歷序列恢復二叉樹。
什麼是二叉排序樹？二叉排序樹的作用是進行排序。二叉排序樹的建立方法。
如何用二叉排序樹進行排序，排序結果是對二叉樹進行中序遍歷的結果。
二叉排序樹的查詢方法。掌握演算法。
哈夫曼樹沒有度為1的結點。
本章將有問題求解題及演算法題出現。
第八章圖
圖的結構為網狀結構。
什麼叫做頂點的度？只有頂點的度，沒有圖的度。
無向圖的定義為g=，它是非空有窮集合。
無向圖度數之和的一半等於邊數。
圖的鄰接矩陣與鄰接表儲存。
圖的深度優先搜尋與廣度優先搜尋。
最小生成樹的求解。
aov網與拓撲排序、aoe網與關鍵路徑。
本章將有問題求解題出現。
題目中的圖不會以「圖」的方式給出，而是以三元組表、圖的定義或鄰接表等方式給出。
第九章檔案及查詢
什麼叫做檔案的邏輯結構？
檔案的基本操作，最主要的是什麼操作？
順序檔案的分類。
連續順序檔案的順序查詢演算法、折半查詢演算法。
索引檔案分為哪兩部分？索引表是系統自動建立的，表項按關鍵字值排序。
稠密索引檔案與非稠密索引檔案的定義。
b+樹的查詢方法，兩個頭指標的位置。
has**件、hash函式的選擇、處理衝突的方法。
has**件的開放位址法與鏈位址法問題求解題。
本章將有問題求解題及演算法題出現。
第十章內排序
只要求會排序(排序趟數)即可，不要求演算法。
能根據定義敘述或幾趟的排序過程判斷是什麼排序方法。
掌握以下內排序方法：選擇、插入、泡、希爾、快速、堆。
本章將有問題求解題出現。
郝斌老師資料結構筆記
資料結構概述 定義 我們如何把現實中大量而複雜的問題已特定的 資料型別和特定的儲存結構儲存到主儲存器 記憶體 中，以及 在此基礎上位實現某個功能二執行的相應操作，這個相應的操作也叫演算法。資料結構解決儲存問題，演算法解決資料間的關係。資料結構 個體 個體的關係 演算法 對儲存資料的操作。狹義的演算法...
資料結構與拓撲資料結構
資料結構在gis中對於資料的採集 儲存 查詢 檢索和應用分析等操作方式有著重要的影響，一種高效率的資料結構應該具備以下幾個要求 1 組織的資料能夠表示要素之間的層次關係，便於不同資料聯絡於覆蓋 2 正確反映地理實體之間的空間排列方式和各實體之間的相互關係 3 便於訪問與檢索 4 節省儲存空間，減少資...
《資料結構》作業
本課程作業由兩部分組成。第一部分為 客觀題部分 由選擇題組成，每題1分，共15分。第二部分為 主觀題部分 由簡答題和應用題組成，共15分。作業總分30分，將作為平時成績記入課程總成績。客觀題部分 一 選擇題 每題1分，共10題 1 順序儲存結構中資料元素之間的邏輯關係是由 表示的。a.線性結構 b....