第2章線性表
一．選擇題
二．判斷題
部分答案解釋如下。
1、 頭結點並不「僅起」標識作用，並且使操作統一。另外，頭結點資料域可寫入鍊錶長度，或作監視哨。
4．兩種儲存結構各有優缺點，應根據實際情況選用，不能籠統說哪乙個好。
7．集合中元素無邏輯關係。
9．非空線性表第乙個元素無前驅，最後乙個元素無後繼。
13．線性表是邏輯結構，可以順序儲存，也可鏈式儲存。
三．填空題
1．順序2．（n-1）/23．py->next=px->next; px->next=py
4 ．n-i+1
5．主要是使插入和刪除等操作統一，在第乙個元素之前插入元素和刪除第乙個結點不必另作判斷。另外，不論鍊錶是否為空，鍊錶指標不變。
6．o(1)，o(n) 7．單鏈表，多重鍊錶，（動態）鍊錶，靜態鍊錶
8．f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;
9．p^.prior s^.prior^.next
10． 指標 11．物理上相鄰指標 12．4 2
13．從任一結點出發都可訪問到鍊錶中每乙個元素。
14．u=p->next; p->next=u->next; free(u); 15．l->next->next==l 16．p->next!=null
17．l->next==l && l->prior==l18．s->next=p->next;p->next=s;
19．(1) if pa=nil then return(true);
(2) pb<>nil and pa^.data>=pb^.data
(3) return(inclusion(pa,pb));
(4) pb:=pb^.next;
(5) return(false);
非遞迴演算法：
(1)pre:=pb; (2) pa<>nil and pb<>nil and pb^.data>=pa^.
data (3)pa:=pa^.next; pb:
=pb->next;
(4)pb:=pre^.next;pre:
=pb;pa:=pa^.next;(5)if pa=nil then return(true) else return(false);
[注]：本題是在鍊錶上求模式匹配問題。非遞迴演算法中用指標pre指向主串中開始結點（初始時為第一元素結點）。
若主串與子串對應資料相等，兩串工作指標pa和pb後移；否則，主串工作指標從pre的下一結點開始（這時pre又指向新的開始結點），子串工作指標從子串第一元素開始，比較一直繼續到迴圈條件失敗。若pa為空，則匹配成功，返回true，否則，返回false。
20．a．var head:ptr b. new(p) c.
p^.data:=k d.
q^.next:=p e.
q:=p(帶頭結點)
21．（1）new(h);∥生成頭結點，以便於操作。
（2）r^.next:=p; (3) r^.next:=q; (4) if (q=nil) then r^.next:=p;
22．a: r^.link^.data<>max and q^.link^.data<>max
b: r:=r^.
link c: q^.link d:
q^.link e: r^.
link f: r^.link
g: r:=s（或r:= r^.link） h: r:=r^.link i: q^.link:=s^.link
23．(1)la (2)03)j 24.(1)head^.left:=s ∥head的前驅指標指向插入結點
(2)j:=1;
(3)p:=p^.right ∥工作指標後移
(4)s^.left:=p
(5)p^.right^.left:=s; ∥p後繼的前驅是s
(6)s^.left:=p;
25.(1)i<= ∥ 為元素個數
(2)j:=j+1 ∥有值不相等的元素
(3) ∥元素前移
(4) ∥元素個數
26.(a)p^.link:=q;∥拉上鏈，前驅指向後繼
(b)p:=q;∥新的前驅
(c)p^.link:=head;∥形成迴圈鍊錶
(d)j:=0; ∥計數器，記被刪結點
(e)q:=p^.link∥記下被刪結點
(f)p^.link=q^.link ∥刪除結點
27. (1)p:=r;∥r指向工作指標s的前驅，p指向最小值的前驅。
(2)q:=s;∥q指向最小值結點，s是工作指標
(3)s:=s^.link∥工作指標後移
(4)head:=head^.next;∥第乙個結點值最小；
(5)p^link:=q^.link;∥跨過被刪結點（即刪除一結點）
28．(1) l^.key:=x;∥頭結點l這時起監視哨作用
(2) l^.freq:=p^.freq ∥頭結點起監視哨作用
(3) q->pre->next=q->next; q->next->pre=q->pre; ∥先將q結點從鍊錶上摘下
q^.next:=p; q^.pre:=p^.pre; p^.pre->next:=q; p^.pre:=q; ∥結點q插入結點p前
(4) q^.freq=0 ∥鍊錶中無值為x的結點，將新建結點插入到鍊錶最後（頭結點前）。
29．(1)a^.key:=』@』∥a的頭結點用作監視哨，取不同於a鍊錶中其它資料域的值
(2)b^.key:=p^.key∥b的頭結點起監視哨作用
(3)p:=p^.next∥找到a,b表中共同字母，a表指標後移
(4)0(m*n)
30. c 部分：(1)p!=null ∥鍊錶未到尾就一直作
(2)q將當前結點作為頭結點後的第一元素結點插入
31. (1)l=l->next; ∥暫存後繼
(2)q=l待逆置結點
(3)l=p頭指標仍為l
32. (1) p^.next<>p0 (2)r:= p^.next (3) p^.next:= q0;
(4) q0:= p5) p:=r
33. (1)r2)nil3)x (5)p:=p^.next (6)p^.data>=x; (7)r8)p
(9)r10)nil (11)nil
34．(1)pa!=ha或pa->exp!=-1
(2)pa->exp==0 ∥若指數為0，即本項為常數項
(3)q->next=pa->next ∥刪常數項
(4)q->next取下一元素
(5)=pa->coef*pa->exp
(6指數項減1
(7)pa前驅後移,或q->next
(8)pa->next取下一元素
35．(1)q:=pq是工作指標p的前驅
(2)p^.data>m ∥p是工作指標
(3)r:=qr 記最大值的前驅，
(4)q:=p或q:=q^.next;
(5)r^.next:=q^.next; ∥或r^.next:=r^.next^.next 刪最大值結點
36．(1)l->next=null ∥置空鍊錶,然後將原鍊錶結點逐個插入到有序表中
(2)p!=null ∥當鍊表尚未到尾，p為工作指標
(3)q!=null ∥查p結點在鍊錶中的插入位置，這時q是工作指標。
(4)p->next=r->next ∥將p結點鏈入鍊錶中
(5)r->next=p ∥r是q的前驅，u是下個待插入結點的指標。
37．程式（a） pascal部分(編者略）
程式（b） c部分
(1)(a!=null && b!=null) ∥兩均未空時迴圈
(2)a->element==b->element ∥兩表中相等元素不作結果元素
(3)b=b->link向後移動b表指標
(4)a!=null將a 表剩餘部分放入結果表中
(5)last->link=null置鍊錶尾
四、 應用題
1．（1）選鏈式儲存結構。它可動態申請記憶體空間，不受表長度（即表中元素個數）的影響，插入、刪
除時間複雜度為o（1）。
（2）選順序儲存結構。順序表可以隨機訪問，時間複雜度為o（1）。
2．鏈式儲存結構一般說克服了順序儲存結構的三個弱點。首先，插入、刪除不需移動元素，只修改指標，時間複雜度為o(1)；其次，不需要預先分配空間，可根據需要動態申請空間；其三，表容量只受可用記憶體空間的限制。其缺點是因為指標增加了空間開銷，當空間不允許時，就不能克服順序儲存的缺點。
資料結構與演算法模擬試題
一 選擇題 1.在邏輯上可以把資料結構分成 a.線性結構和非線性結構 b.動態結構和靜態結構 c.緊湊結構和非緊湊結構 d.內部結構和外部結構 2.單鏈表中各結點之間的位址 a.必須連續 b.部分必須連續 c.不一定連續 d.以上均不對 3.在乙個長度為n的順序表中向第i個元素 0a n ib n ...
演算法與資料結構
演算法 是按部就班地解決某個問題的方法，是對特定問題求解步驟的一種描述。偽碼語言是一種包括高階程式語言的3種基本控制結構 順序 選擇和迴圈 和自然語言成分的 物件導向 的語言。演算法的特徵 1 可行性 一是演算法中的每個步驟必須是能實現的 二是演算法執行的結果要能達到預期的目的。2 確定性 演算法的...
資料結構與演算法
課程設計報告 目錄一 問題描述1 二 資料結構1 三 演算法設計思想及流程圖1 四 源程式2 五 測試情況6 參考文獻6 一 問題描述 計算表示式的值 問題描述 對於給定的乙個表示式，表示式中可以包括常數 算術執行符和括號，編寫程式計算表示式的值。基本要求 從鍵盤輸入乙個正確的中綴表示式，將中綴表示...