第一章複習題
一、選擇
1、計算機演算法指的是（1），它必須具備_ c ___（2） 這三個特性__ b ___
(1) a．計算方法 b. 排序方法 c. 解決問題的步驟序列 d. 排程方法
(2) a．可執行性、可移植性、可擴充性 b. 可執行性、確定性、有窮性
c. 確定性、有窮性、穩定性d. 易讀性、穩定性、安全性
2、下面關於演算法說法正確的是（ d ）
a．演算法最終必須由電腦程式實現
b. 為解決某問題的演算法同為該問題編寫的程式含義是相同的
c. 演算法的可行性是指指令不能有二義性d. 以上幾個都是錯誤的
3、從邏輯上可以把資料結構分為（ c ）兩大類。
a．動態結構、靜態結構 b．順序結構、鏈式結構
c．線性結構、非線性結構 d．初等結構、構造型結構
4、在下面的程式段中，對x的賦值語句的頻度為（ c ）
for i:=1 to n do
for j:=1 to n do
x:=x+1;
a． o(2n) b．o(n) c．o(n2d．o(log2n)
5、程式段 for i:=n-1 downto 1 do
for j:=1 to i do
if a[j]>a[j+1]
then a[j]與a[j+1]對換；
其中 n為正整數，則最後一行的語句頻度在最壞情況下是（ d ）
a. o（n） b. o(nlogn) c. o(n3) d. o(n2)
二、判斷
1. 資料元素是資料的最小單位。( × )
2．資料的物理結構是指資料在計算機內的實際儲存形式。( √ )
三、計算及簡答
1、下面程式段的時間複雜度為__ o(n)__。(n>1)
sum=1；
for (i=0;sum2、若將資料結構定義為乙個二元組（d，r）,說明符號d，r 應分別表示什麼？
答：d是資料元素的有限集合，s是d上資料元素之間關係的有限集合。
第二章複習題
本章重點掌握：線性結構特點，順序儲存結構和鏈式儲存結構特點。
1. 在順序表中插入或刪除乙個元素，需要平均移動( 一半 )元素，具體移動的元素個數與( 插入或刪除的位置 )有關。插入時平均次數（ n/2 ）,刪除時平均次數（ (n-1)/2 ）。
2. 有乙個含頭結點的迴圈鍊錶，頭指標為head, 則其為空的條件是：( c )
a)head==nullb)head->next==null c)head->next==head
3. 在長度為n的順序表的第i個位置上插入乙個元素（1≤i≤n+1），元素的移動次數為：( a )
a) n – i + 1 b) n – ic) id) i – 1
4. 對於只在表的首、尾兩端進行插入操作的線性表，宜採用的儲存結構為( c )
a) 順序表b) 用頭指標表示的迴圈單鏈表
c) 用尾指標表示的迴圈單鏈表 d) 單鏈表
5. 設單鏈表中結點的結構為（data, link）。已知指標q所指結點是指標p所指結點的直接前驅，若在*q與*p之間插入結點*s，則應執行下列哪乙個操作？（ b ）
(a) s->link = p->link; p->link = s; (b) q->link = s; s->link = p;
(c) p->link = s->link; s->link = p; (d) p->link = s; s->link = q;
6. 設單鏈表中結點的結構為（data, link）。已知指標p所指結點不是尾結點，若在*p之後插入結點*s，則應執行下列哪乙個操作？（b）
(a) s->link = p; p->link = s; (b) s->link = p->link; p->link = s;
(c) s->link = p->link; p = s; (d) p->link = s; s->link = p;
7. 設單鏈表中結點的結構為（data, link）。若想摘除結點*p的直接後繼，則應執行下列哪乙個操作？（a）
(a) p->link = p->link->link; (b) p = p->link; p->link = p->link->link;
(c) p->link = p->linkd) p = p->link->link;
8. 設單迴圈鍊錶中結點的結構為（data, link），且rear是指向非空的帶表頭結點的單迴圈鍊錶的尾結點的指標。若想刪除鍊錶第乙個結點，則應執行下列哪乙個操作？（d）
(a) s = rear; rear = rear->link; delete s;
(b) rear = rear->link; delete rear;
(c) rear = rear->link->link; delete rear;
(d) s = rear->link->link; rear->link->link = s->link; delete s;
（rear指向尾結點，rear->link->link指向第乙個結點，第乙個結點變為原來的第二個結點）
9. 設雙向迴圈鍊錶中結點的結構為（data, llink, rlink），且不帶表頭結點。若想在指標p所指結點之後插入指標s所指結點，則應執行下列哪乙個操作？( d )
(a) p->rlink = s; s->llink = p; p->rlink->llink = s; s->rlink = p->rlink;
(b) p->rlink = s; p->rlink->llink = s; s->llink = p; s->rlink = p->rlink;
(c) s->llink = p; s->rlink = p->rlink; p->rlink = s; p->rlink->llink = s;
(d) s->llink = p; s->rlink = p->rlink; p->rlink->llink = s; p->rlink = s;
10. 已知l是無表頭結點的單鏈表，且p結點既不是首元結點，也不是尾元結點，試從下列提供的答案中選擇合適的語句序列。
(a) 在p結點後插入s結點的語句序列是 4，1
(b) *在p結點前插入s結點的語句序列是 7，11，8，4，1 。
(c) 在表首插入s結點的語句序列是 5，12
(d) 在表尾插入s結點的語句序列是 9，1，6
1. p->next = s；
2. p->next = p->next ->next；
3. p->next =s->next；
4. s->next =p->next；
5. s->next = l；
6. s->next = null；
7. q = p；
8. while(p->next ! = q) p = p->next；
9. while(p->next ! = null) p = p->next；
10. p = q；
11. p = l；
12. l = s；
13. l = p；
11. 已知l是帶表頭結點的非空單鏈表，且p結點既不是首元結點，也不是尾元結點，試從下列提供的答案中選擇合適的語句序列。
(a) 刪除p結點的直接後繼結點的語句序列是 11，3，14
(b) 刪除p結點的直接前驅結點的語句序列是 10，12，8，11，3，14
(c) 刪除p結點的語句序列是 10，12，7，3，14
(d) 刪除首元結點的語句序列是 12，11，3，14
(e) 刪除尾元結點的語句序列是 9，11，3，14 / 10，6，3，14
1. p = p->next；
2. p ->next = p；
3. p->next = p->next ->next；
4. p = p->next ->next；
5. while(p ! = null) p = p->next；
6. while(q->next ! = null)
7. while(p->next ! = q) p = p->next；
8. while(p->next ->next ! = q) p = p->next；
9. while(p->next ->next ! = null) p = p->next；
10. q = p；
11. q = p->next；
12. p = l；
13. l = l->next；
14. free(q)；
12. 已知p結點是某雙向鍊錶的中間結點，試從下列提供的答案中選擇合適的語句序列。
(a) 在p結點後插入s結點的語句序列是 7，12，3，6 。
(b) 在p結點前插入s結點的語句序列是 8，13，5，4
(c) 刪除p結點的直接後繼結點的語句序列是 15，1，11，18 。
(d) 刪除p結點的直接前驅結點的語句序列是 16，2，10，18 。
(e) 刪除p結點的語句序列是 9，14，17
1. p->next = p->next ->next；
2. p->prior = p-> prior -> prior；
3. p->next = s；
4. p-> prior = s；
5. s->next = p；
6. s-> prior = p；
7. s->next =p->next；
8. s-> prior =p-> prior；
9. p-> prior ->next =p-> next；
10. p-> prior ->next =p；
11. p->next -> prior =p；
12. p->next -> prior = s；
13. p-> prior ->next = s；
14. p->next -> prior =p-> prior；
資料結構與拓撲資料結構
資料結構在gis中對於資料的採集 儲存 查詢 檢索和應用分析等操作方式有著重要的影響，一種高效率的資料結構應該具備以下幾個要求 1 組織的資料能夠表示要素之間的層次關係，便於不同資料聯絡於覆蓋 2 正確反映地理實體之間的空間排列方式和各實體之間的相互關係 3 便於訪問與檢索 4 節省儲存空間，減少資...
資料結構複習總結
第二章線性表 1.線性表的邏輯結構 資料元素之間存在一對一的線性關係 線性表的儲存結構 順序和鏈式 順序表和煉表。順序錶用一維陣列實現，鍊錶有單鏈表和雙鏈表及迴圈鍊錶。每種鍊錶含有指標的個數 2.掌握順序表和煉表的查詢，插入 刪除和排序操作的演算法時間複雜度。第三章棧和佇列 1.棧和佇列邏輯結構 資...
資料結構內容總結
第0章緒論 2 一 基礎知識 2 第1章線性表 3 一 基礎知識和演算法 3 1.線性表及其特點 3 2.順序表 線性表的順序儲存結構 3 3.單鏈表 線性表的鏈式儲存結構之一 6 4.迴圈鍊錶 10 5.雙向迴圈鍊錶 11 6.順序表與單鏈表的比較 12 第2章棧和佇列 13 一 基礎知識和演算法...