第一章知識點
p3 ·資料結構從邏輯上劃分為：（1）線性結構 （2）非線性結構: 樹型結構和圖型結構
p4 ·從儲存結構（物理結構）上劃分：
（1）順序結構 ：所有元素存放在一片連續的儲存單元中，邏輯上相鄰的元素存放到計算機記憶體中仍然相鄰
（2）鏈式結構：所有元素存放在可以不連續的儲存單元中，但元素之間的關係可以通過位址確定，邏輯上相鄰的元素存放到計算機記憶體後不一定是相鄰的。
p5 ·演算法的五大特性：（1）輸入（2）輸出 （3）有窮性 （4）確定性（5）可行性（可執行）
p6 ·演算法分析的任務/方面：
（1）時間複雜度 （重點是計算時間複雜度[p9 1-5 p10 1-12）
（2）空間複雜度（性）：乙個演算法在執行時所占有的記憶體開銷，稱為空間頻度
課後部分習題解釋：
1-2簡述下列概念：資料、資料元素、資料型別、資料結構、邏輯結構、儲存結構、線性結構、非線性結構。
◆ 資料：指能夠被計算機識別、儲存和加工處理的資訊載體。
◆ 資料元素：就是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理
◆ 資料型別：是乙個值的集合以及在這些值上定義的一組操作的總稱。
◆ 資料結構：指的是資料之間的相互關係，即資料的組織形式。一般包括三個方面的內容:資料的邏輯結構、儲存結構和資料的運算。
◆ 邏輯結構：指各資料元素之間的邏輯關係。
◆ 儲存結構：就是資料的邏輯結構用計算機語言的實現。
◆ 線性結構：資料邏輯結構中的一類，它的特徵是若結構為非空集，則該結構有且只有乙個開始結點和乙個終端結點，並且所有結點都最多只有乙個直接前趨和乙個直接後繼。線性表就是乙個典型的線性結構。
◆ 非線性結構：資料邏輯結構中的另一大類，它的邏輯特徵是乙個結點可能有多個直接前驅和直接後繼。
補充習題
⑴（ ）是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。
【解答】資料元素
⑶ 從邏輯關係上講，資料結構主要分為和（ ）。
【解答】集合，線性結構，樹型結構，圖型結構
⑶ 演算法指的是（ ）。
a 對特定問題求解步驟的一種描述，是指令的有限序列。
b 電腦程式 c 解決問題的計算方法 d 資料處理
【解答】a
【分析】電腦程式是對演算法的具體實現；簡單地說，演算法是解決問題的方法；資料處理是通過演算法完成的。所以，只有a是演算法的準確定義。
⑷ 下面（ ）不是演算法所必須具備的特性。
a 有窮性 b 確切性 c 高效性 d 可行性
【解答】c
【分析】高效性是好演算法應具備的特性。
⑸ 演算法分析的目的是（ ），演算法分析的兩個主要方面是（ ）。
a 找出資料結構的合理性 b 研究演算法中輸入和輸出的關係
c 分析演算法的效率以求改進 d 分析演算法的易讀性和文件性
e 空間效能和時間效能 f 正確性和簡明性
g 可讀性和文件性 h 資料複雜性和程式複雜性
【解答】c，e
6. 對下列用二元組表示的資料結構,試分別畫出對應的邏輯結構圖，並指出屬於何種結構。
⑴ a=(d，r)， 其中d=，r=
⑵ b=(d，r)， 其中d=，r=
⑶ c=( d，r)，其中d=，r=
⑷ d=(d，r)， 其中d=，
r= 【解答】⑴ 屬於集合，其邏輯結構圖如圖1-4(a)所示；⑵ 屬於線性結構，其邏輯結構圖如圖1-4(b)所示；⑶ 屬於樹結構，其邏輯結構圖如圖1-4(c)所示；⑷ 屬於圖結構，其邏輯結構圖如圖1-4(d)所示。
第二章知識點
p16 ·利用線性表來儲存線性表，表中相鄰的元素儲存在計算機內的位置也相鄰
p21 ·線性表的鏈式儲存結構，也稱為鍊錶。其儲存方式是：在記憶體中利用儲存單元（可以不連續）來存放元素值及它在記憶體中的位址，各個元素的存放順序及位置都可以以任意順序進行
p25 ·單鏈表上的插入運算
(1)s->next=p->next;
(2)p->next=s;
p26 ·單鏈表上的刪除運算
（1）q->next=p->next;
（2）delete(p);
補充習題：
（1）順序表中第乙個元素的儲存位址是100，每個元素的長度為2，則第5個元素的儲存位址是（ ）。
【解答】108
【分析】第5個元素的儲存位址=第1個元素的儲存位址＋(5－1)×2=108
（2） 設單鏈表中指標p 指向結點a，若要刪除a的後繼結點（假設a存在後繼結點），則需修改指標的操作為（ ）。
【解答】p->next=(p->next)->next
（3）線性表的順序儲存結構是一種（ ）的儲存結構，線性表的鏈結儲存結構是一種（ ）的儲存結構。
a 隨機訪問 b 順序訪問 c 索引訪問 d 雜湊訪問
【解答】a，b
（4） 線性表採用鏈結儲存時，其位址（ ）。
a 必須是連續的 b 部分位址必須是連續的
c 一定是不連續的 d 連續與否均可以
【解答】d
【分析】線性表的鏈結儲存是用一組任意的儲存單元儲存線性表的資料元素，這組儲存單元可以連續，也可以不連續，甚至可以零散分布在記憶體中任意位置。
⑾ 在乙個單鏈表中，已知q所指結點是p所指結點的直接前驅，若在q和p之間插入s所指結點，則執行（ ）操作。
a s->next=p->next; p->next=s; b q->next=s; s->next=p;
c p->next=s->next; s->next=p; d p->next=s; s->next=q;
【解答】b
【分析】注意此題是在q和p之間插入新結點，所以，不用考慮修改指標的順序。
⑿ 在迴圈雙鏈表的p所指結點後插入s所指結點的操作是（ ）。
a p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
b p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
c s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
d s->prior=p; s->next=p->next; p->next->prior=s; p->next=s
【解答】d
【分析】在鍊錶中，對指標的修改必須保持線性表的邏輯關係，否則，將違背線性表的邏輯特徵，圖2-10給出備選答案c和d的**。
第三章知識點
p40 ·棧棧是一種後進先出的線性表，簡稱lifo表。
p52 ·佇列先進先出，fifo表
重點習題：課本p58-59:
3-1: 進乙個出乙個，abcd
先進兩個，ab進，進c出c,進d出d，出b出a，cdba
進a進b，進c進d，出d出c出b出a，dcba
下面的不解釋了，不明白你再問
bcda,bdca,bcad,badc,bacd,
前三個一起進
cbad,cbda,cdba
第乙個進去就出來
adcb,acdb,acbd
一共14種
3-2; 3-3
資料結構知識點
第二章線性表是n個型別相同的資料元素的有限序列，對n 0,除第乙個元素無直接前驅，最後乙個元素無直接後繼外，其餘的每個資料元素只有乙個直接前驅和乙個直接後繼。1 同一性 線性表有同類元素資料組成，每乙個必須屬於同一資料型別。2 有窮性 線性表由有限個資料元素組成，表長就是表中資料元素的個數。3 有序...
資料結構知識點總結
第一章緒論 1.資料結構 data structure 是指相互之間具有 存在 一定聯絡 關係 的資料元素的集合。元素之間的相互聯絡 關係 稱為邏輯結構。資料元素之間的邏輯結構有四種基本型別 集合 結構中的資料元素除了 同屬於乙個集合 外，沒有其它關係。線性結構 結構中的資料元素之間存在一對一的關係...
資料結構課後習題及解析第三章
第三章習題 1.按圖3.1 b 所示鐵道 兩側鐵道均為單向行駛道 進行車廂排程，回答 如進站的車廂序列為123，則可能得到的出站車廂序列是什麼？如進站的車廂序列為123456，能否得到435612和135426的出站序列，並說明原因。即寫出以 s 表示進棧 以 x 表示出棧的棧操作序列 2.設佇列中...