第一章概論自測題答案
一、填空題
1. 資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。
2. 資料結構被形式地定義為（d, r），其中d是資料元素的有限集合，r是d上的關係有限集合。
3. 資料結構包括資料的邏輯結構 、資料的儲存結構和資料的運算這三個方面的內容。
4. 資料結構按邏輯結構可分為兩大類，它們分別是線性結構和非線性結構 。
5. 線性結構中元素之間存在一對一關係，樹形結構中元素之間存在一對多關係，圖形結構中元素之間存在多對多關係。
6． **性結構中，第乙個結點沒有前驅結點，其餘每個結點有且只有 1個前驅結點；最後乙個結點沒有後續結點，其餘每個結點有且只有1個後續結點。
7. 在樹形結構中，樹根結點沒有前驅結點，其餘每個結點有且只有 1 個前驅結點；葉子結點沒有後續結點，其餘每個結點的後續結點數可以任意多個 。
8. 在圖形結構中，每個結點的前驅結點數和後續結點數可以任意多個 。
9．資料的儲存結構可用四種基本的儲存方法表示，它們分別是順序 、 鏈式 、 索引和雜湊 。
10. 資料的運算最常用的有5種，它們分別是插入 、 刪除、修改、 查詢 、排序。
11. 乙個演算法的效率可分為時間效率和空間效率。
二、單項選擇題
（ b ）1. 非線性結構是資料元素之間存在一種：
a）一對多關係 b）多對多關係 c）多對一關係 d）一對一關係
（ c ）2. 資料結構中，與所使用的計算機無關的是資料的結構；
a) 儲存 b) 物理 c) 邏輯d) 物理和儲存
（ c ）3. 演算法分析的目的是：
a) 找出資料結構的合理性 b) 研究演算法中的輸入和輸出的關係
c) 分析演算法的效率以求改進 d) 分析演算法的易懂性和文件性
（ a ）4. 演算法分析的兩個主要方面是：
a) 空間複雜性和時間複雜性 b) 正確性和簡明性
c) 可讀性和文件性d) 資料複雜性和程式複雜性
（ c ）5. 計算機演算法指的是：
a) 計算方法 b) 排序方法 c) 解決問題的有限運算序列 d) 排程方法
（ b ）6. 計算機演算法必須具備輸入、輸出和等5個特性。
a) 可行性、可移植性和可擴充性 b) 可行性、確定性和有窮性
c) 確定性、有窮性和穩定性d) 易讀性、穩定性和安全性
三、簡答題
2.【嚴題集1.2②】資料結構和資料型別兩個概念之間有區別嗎？
答：簡單地說，資料結構定義了一組按某些關係結合在一起的陣列元素。資料型別不僅定義了一組帶結構的資料元素，而且還在其上定義了一組操作。
3. 簡述線性結構與非線性結構的不同點。
答：線性結構反映結點間的邏輯關係是一對一的，非線性結構反映結點間的邏輯關係是多對多的。
四、【嚴題集1.8④】分析下面各程式段的時間複雜度
五、設有資料邏輯結構s=（d,r），試按各小題所給條件畫出這些邏輯結構的圖示，並確定相對於關係r，哪些結點是開始結點，哪些結點是終端結點？
1. 【嚴蔚敏習題集p7 1.3②】
d=答： d1→d2→d3→d4 d1—無直接前驅，是首結點 d4—無直接後繼是尾結點
2。d=
r=答： 此圖為樹形結構 d1—無直接前驅，是根結點 d2,d5,d7,d9—無直接後繼是葉子結點
3．d=
r=答： 此圖為圖形結構 d1，d2—無直接前驅，是開始結點 d6,d7—無直接後繼是終端結點
(23)
資料結構練習
華東理工大學網路學院 資料結構 ch1緒論和ch2線性表 班級學號姓名成績 一 名詞解釋 每小題2分，共10分 1.資料結構 2.線性結構 3.儲存結構 4.邏輯結構 5.非線性結構 答 1.資料結構 指的是資料之間的相互關係，即資料的組織形式。一般包括三個方面的內容 資料的邏輯結構 儲存結構和資料...
資料結構答案
1 有乙個帶頭指標的單鏈表，寫出在值為x的結點之後插入m個結點的演算法 int insertm linklist l,int x,int m p next q連線斷點 3 假設乙個長度大於1的單迴圈鍊錶既無頭結點也無頭指標，s為指向鍊錶中某個結點的指標，試設計刪除結點s的直接前驅結點的演算法 voi...
資料結構練習二
一 選擇 1 用單鏈表方式儲存的線性表,儲存每個結點需要兩個域,乙個是資料域,另乙個是 b a.當前結點所在位址域.b.指標域.c.空指標域.d.空閒域.2 在具有n個結點的單鏈表中,實現 a 的操作,其演算法的時間複雜度是o n a.遍歷鍊錶和求鍊錶的第i個結點.b.在位址為p的結點之後插入乙個結...