第一章緒論
一、填空題（每空1分，共33分）
1. 乙個計算機系統包括硬體系統和軟體系統兩大部分。
2. 一台計算機中全部程式的集合，稱為這台計算機的軟體資源 /（系統） 。
3. 計算機軟體可以分為系統軟體和應用軟體兩大類。科學計算程式包屬於應用軟體 ，診斷程式屬於系統軟體（工具） 。
4. 一種用助憶符號來表示機器指令的操作符和運算元的語言是組合語言 。
5. 資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。
6. 資料結構被形式地定義為（d, r），其中d是資料元素的有限集合，r是d上的關係有限集合。
7. 資料結構包括資料的邏輯結構 、資料的儲存結構和資料的運算這三個方面的內容。
8. 資料結構按邏輯結構可分為兩大類，它們分別是線性結構和非線性結構 。
9. 線性結構中元素之間存在一對一關係，樹形結構中元素之間存在一對多關係，圖形結構中元素之間存在多對多關係。
10． **性結構中，第乙個結點沒有前驅結點，其餘每個結點有且只有 1個前驅結點；最後乙個結點沒有後續結點，其餘每個結點有且只有1個後續結點。
11. 在樹形結構中，樹根結點沒有前驅結點，其餘每個結點有且只有 1 個前驅結點；葉子結點沒有後續結點，其餘每個結點的後續結點數可以任意多個 。
12. 在圖形結構中，每個結點的前驅結點數和後續結點數可以任意多個 。
13．資料的儲存結構可用四種基本的儲存方法表示，它們分別是順序 、 鏈式 、 索引和雜湊 。
14. 資料的運算最常用的有5種，它們分別是插入 、 刪除、修改、 查詢 、排序。
15. 乙個演算法的效率可分為時間效率和空間效率。
16. 〖00年省統考〗任何乙個c程式都由乙個主函式和若干個被呼叫的其它函式組成。
17. 【00年省統考題】變數一經說明，就確定該變數的取值範圍（即儲存單元）及確定變數所允許的運算 。
二、單項選擇題（每小題1分，共15分）
（ b ） 1. 通常所說的主機是指∶
a) cpu b) cpu和記憶體 c) cpu、記憶體與外存 d) cpu、記憶體與硬碟
（ c ）2. 在計算機內部，一切資訊的訪問、處理和傳送的形式是∶
a) acsii碼 b) bcd碼 c)二進位制 d)十六進製制
（ d ）3. 軟體與程式的區別是∶
a) 程式**便宜、軟體**昂貴；
b) 程式是使用者自己編寫的，而軟體是由廠家提供的；
c) 程式是用高階語言編寫的，而軟體是由機器語言編寫的；
d) 軟體是程式以及開發、使用和維護所需要的所有文件的總稱，而程式只是軟體的一部分。
（ c ）4. 所謂「裸機」是指∶
a) 微控制器 b)單板機 c) 不裝備任何軟體的計算機 d) 只裝備作業系統的計算機
（ d ）5. 應用軟體是指∶
a)所有能夠使用的軟體b) 能被各應用單位共同使用的某種軟體
c)所有微機上都應使用的基本軟體 d) 專門為某一應用目的而編制的軟體
（ ＊a ）6. 〖00年省統考〗c語言中的常量可分為整型常量、實型常量、字元型常量及 (列舉) 四種。
（a） 符號常量 （b）長整型常量 （c） 邏輯常量 （d）二進位制整數
（ ＊c ）7. 編譯程式的功能是∶
a)發現源程式中的語法錯誤b)改正源程式中的語法錯誤
c)將源程式編譯成目標程式d)將某一高階語言程式翻譯成另一種高階語言程式
（ a ）8. 系統軟體中最重要的是∶
a) 作業系統 b) 語言處理系統 c) 工具軟體d) 資料庫管理系統
（ c ）9. 可移植性最好的計算機語言是∶
a) 機器語言 b)組合語言 c) 高階語言 d) 自然語言
（ b ）10. 非線性結構是資料元素之間存在一種：
a）一對多關係 b）多對多關係 c）多對一關係 d）一對一關係
（ c ）11. 資料結構中，與所使用的計算機無關的是資料的結構；
a) 儲存 b) 物理 c) 邏輯d) 物理和儲存
（ c ）12. 演算法分析的目的是：
a) 找出資料結構的合理性 b) 研究演算法中的輸入和輸出的關係
c) 分析演算法的效率以求改進 d) 分析演算法的易懂性和文件性
（ a ）13. 演算法分析的兩個主要方面是：
a) 空間複雜性和時間複雜性 b) 正確性和簡明性
c) 可讀性和文件性d) 資料複雜性和程式複雜性
（ c ）14. 計算機演算法指的是：
a) 計算方法 b) 排序方法 c) 解決問題的有限運算序列 d) 排程方法
（ b ）15. 計算機演算法必須具備輸入、輸出和等5個特性。
a) 可行性、可移植性和可擴充性 b) 可行性、確定性和有窮性
c) 確定性、有窮性和穩定性d) 易讀性、穩定性和安全性
第2章線性表答案
一、填空（每空1分，共13分）
1. 【嚴題集2.2①】在順序表中插入或刪除乙個元素，需要平均移動表中一半元素，具體移動的元素個數與表長和該元素在表中的位置有關。
2. 線性表中結點的集合是有限的，結點間的關係是一對一的。
3. 向乙個長度為n的向量的第i個元素(1≤i≤n+1)之前插入乙個元素時，需向後移動 n-i+1 個元素。
4. 向乙個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動 n-i 個元素。
5. 在順序表中訪問任意一結點的時間複雜度均為 o(1) ，因此，順序表也稱為隨機訪問的資料結構。
6. 【嚴題集2.2①】順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。
7. 【嚴題集2.2①】在單鏈表中，除了首元結點外，任一結點的儲存位置由其直接前驅結點的鏈域的值指示。
8． 在n個結點的單鏈表中要刪除已知結點*p，需找到它的前驅結點的位址，其時間複雜度為o（n）。
二、判斷正誤（在正確的說法後面打勾，反之打叉）（每小題1分，共10分）
（ × ）1. 鍊錶的每個結點中都恰好包含乙個指標。
答：錯誤。鍊錶中的結點可含多個指標域，分別存放多個指標。例如，雙向鍊錶中的結點可以含有兩個指標域，分別存放指向其直接前趨和直接後繼結點的指標。
（ × ）2. 鍊錶的物理儲存結構具有同煉表一樣的順序。錯，鍊錶的儲存結構特點是無序，而鍊錶的示意圖有序。
（ × ）3. 鍊錶的刪除演算法很簡單，因為當刪除鏈中某個結點後，計算機會自動地將後續的各個單元向前移動。錯，鍊錶的結點不會移動，只是指標內容改變。
（ × ）4. 線性表的每個結點只能是乙個簡單型別，而鍊錶的每個結點可以是乙個複雜型別。
錯，混淆了邏輯結構與物理結構，鍊錶也是線性表！且即使是順序表，也能存放記錄型資料。
（ × ）5. 順序表結構適宜於進行順序訪問，而鍊錶適宜於進行隨機訪問。
錯，正好說反了。順序表才適合隨機訪問，鍊錶恰恰適於「順藤摸瓜」
（ × ）6. 順序儲存方式的優點是儲存密度大，且插入、刪除運算效率高。
錯，前一半正確，但後一半說法錯誤，那是鏈式儲存的優點。順序儲存方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除乙個資料元素，平均需移動表長一半個數的資料元素。
（ × ）7. 線性表在物理儲存空間中也一定是連續的。
錯，線性表有兩種儲存方式，順序儲存和鏈式儲存。後者不要求連續存放。
（ × ）8. 線性表在順序儲存時，邏輯上相鄰的元素未必在儲存的物理位置次序上相鄰。
錯誤。線性表有兩種儲存方式，在順序儲存時，邏輯上相鄰的元素在儲存的物理位置次序上也相鄰。
（ × ）9. 順序儲存方式只能用於儲存線性結構。
錯誤。順序儲存方式不僅能用於儲存線性結構，還可以用來存放非線性結構，例如完全二叉樹是屬於非線性結構，但其最佳儲存方式是順序儲存方式。（後一節介紹）
（ × ）10. 線性表的邏輯順序與儲存順序總是一致的。
錯，理由同7。鏈式儲存就無需一致。
三、單項選擇題（每小題1分，共10分）
（ c ）1．資料在計算機儲存器內表示時，實體地址與邏輯位址相同並且是連續的，稱之為：
（a）儲存結構 （b）邏輯結構 （c）順序儲存結構 （d）鏈式儲存結構
（ b ）2.乙個向量第乙個元素的儲存位址是100，每個元素的長度為2，則第5個元素的位址是
（a）110 （b）108c）100 （d）120
（ a ）3. 在n個結點的順序表中，演算法的時間複雜度是o（1）的操作是：
（a） 訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n）
（b） 在第i個結點後插入乙個新結點（1≤i≤n）
（c） 刪除第i個結點（1≤i≤n）
（d） 將n個結點從小到大排序
（ b ）4. 向乙個有127個元素的順序表中插入乙個新元素並保持原來順序不變，平均要移動個元素
（a）8 （b）63.5c）63 （d）7
（ a ）5. 鏈結儲存的儲存結構所佔儲存空間：
（a） 分兩部分，一部分存放結點值，另一部分存放表示結點間關係的指標
（b） 只有一部分，存放結點值
（c） 只有一部分，儲存表示結點間關係的指標
（d） 分兩部分，一部分存放結點值，另一部分存放結點所佔單元數
（ b ）6. 鍊錶是一種採用儲存結構儲存的線性表；
資料結構整理
else 二 二叉樹 1.二叉樹的前中後層4種遍歷 前序 template void bitree preorder binode root 中序 2 1 3 後序 2 3 1 層序 了解即可 template void bitree levelorder binode root 2.二叉樹的應用 ...
資料結構整理
第四章串 1 下面關於串的的敘述中，哪個是不正確的？a 串是字元的有限序列 b 空串是由空格構成的串 c 模式匹配是串的一種重要運算 d 串既可以採用順序儲存，也可以採用鏈式儲存 2串是一種特殊的線性表，下面哪個敘述體現這種特殊性？a.資料元素是乙個字元 b.可以順序儲存 c.資料元素可以是多個字元...
資料結構整理
20 用鄰接表表示圖進行廣度優先遍歷時，通常採用 來實現演算法。21 用鄰接表表示圖進行深度優先遍歷時，通常採用 來實現演算法。22 在乙個圖中，所有頂點的度數之和等於所有邊數和的 倍 23 在乙個有向圖中，所有頂點的入度之和等於所有頂點的出度之和的 倍。24 乙個有n個頂點的無向圖最多有 條邊 2...