10. 若長度為n的線性表採用順序儲存結構，在其第i個位置插入乙個新元素的演算法的時間複雜度為（ ）(1<=i<=n+1)。
a. o(0) b. o(1c. o(nd. o(n2)
11. 對於順序儲存的線性表，訪問結點和增加、刪除結點的時間複雜度為（ c ）。
a．o(n) o(n) b. o(n) o(1) c. o(1) o(n) d. o(1) o(1)
12．線性表（ a1,a2,…,an）以鏈結方式儲存時，訪問第i位置元素的時間複雜性為（ ）
a．o（i） b．o（1） c．o（n） d．o（i-1）
13．在雙向鍊錶指標p的結點前插入乙個指標q的結點操作是（ ）。
a. p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=q；
b. p->llink=q;p->llink->rlink=q;q->rlink=p;q->llink=p->llink;
c. q->rlink=p;q->llink=p->llink;p->llink->rlink=q;p->llink=q;
d. q->llink=p->llink;q->rlink=q;p->llink=q;p->llink=q;
14．在單鏈表指標為p的結點之後插入指標為s的結點，正確的操作是：（ b ）。
a．p->next=s;s->next=p->next; b． s->next=p->next;p->next=s;
c．p->next=s;p->next=s->next; d． p->next=s->next;p->next=s;
15．對於乙個頭指標為head的帶頭結點的單鏈表，判定該錶為空表的條件是（ b ）
a．head==null b．head→next==null
c．head→next==head d．head!=null
二、填空
1．當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度訪問線性表中的元素時，應採用_______儲存結構。
2．線性表l=（a1,a2,…,an）用陣列表示，假定刪除表中任一元素的概率相同，則刪除乙個元素平均需要移動元素的個數是________。
3．設單鏈表的結點結構為(data,next)，next為指標域，已知指標px指向單鏈表中data為x的結點，指標py指向data為y的新結點 , 若將結點y插入結點x之後，則需要執行以下語句
4．在乙個長度為n的順序表中第i個元素（1<=i<=n）之前插入乙個元素時，需向後移動________個元素。
5．在單鏈表中設定頭結點的作用是________。
6．鏈結儲存的特點是利用________來表示資料元素之間的邏輯關係。
7. 順序儲存結構是通過________表示元素之間的關係的。
8. 對於雙向鍊錶,在兩個結點之間插入乙個新結點需修改的指標共 ______個，單鏈表為_______個。
9. 迴圈單鏈表的最大優點是
10. 已知指標p指向單鏈表l中的某結點，則刪除其後繼結點的語句是：________
11. 帶頭結點的雙迴圈鍊錶l中只有乙個元素結點的條件是：________
12. 在單鏈表l中，指標p所指結點有後繼結點的條件是：__
13.帶頭結點的雙迴圈鍊錶l為空表的條件是
17． 在雙向迴圈鍊錶中,向p所指的結點之後插入指標f所指的結點，其操作是
三、應用題
1．線性表有兩種儲存結構：一是順序表，二是鍊錶。試問：
（1）如果有 n個線性表同時並存，並且在處理過程中各表的長度會動態變化，線性表的總數也會自動地改變。在此情況下，應選用哪種儲存結構？ 為什麼？
（2）若線性表的總數基本穩定，且很少進行插入和刪除，但要求以最快的速度訪問線性表中的元素，那麼應採用哪種儲存結構？為什麼？
2．線性表的順序儲存結構具有三個弱點：其一，在作插入或刪除操作時，需移動大量元素；其二，由於難以估計，必須預先分配較大的空間，往往使儲存空間不能得到充分利用；其三，表的容量難以擴充。線性表的鏈式儲存結構是否一定都能夠克服上述三個弱點，試討論之。
3．線性表（a1，a2，…，an）用順序儲存表示時，ai和ai+1（1<=i4. 說明**性表的鏈式儲存結構中，頭指標與頭結點之間的根本區別；頭結點與首元結點的關係。
5. 在單鏈表和雙向鍊錶中，能否從當前結點出發訪問到任何乙個結點?
6. 如何通過改鏈的方法，把乙個單向鍊錶變成乙個與原來鏈結方向相反的單向鍊錶？
7. 設單鏈表結點指標域為next，試寫出刪除鍊錶中指標p所指結點的直接後繼的c語言語句。
8．設雙向迴圈鍊錶中結點的資料域、前驅和後繼指標域分別為data,pre和next,試寫出在指標p 所指結點之前插入一s結點的c語言描述語句。
10. 帶頭結點且頭指標為ha和hb的兩線性表a和b 分別表示兩個集合。兩表中的元素皆為遞增有序。
請寫一演算法求a和b的並集aub。要求該並集中的元素仍保持遞增有序。且要利用a和b的原有結點空間。
18. 請寫乙個演算法將順序儲存結構的線性表（a1...an）逆置為(an...a1)。
參***
一、選擇題
1．a 2．b 3．c 4．a 5．d 6．d 7．b 8．b c 9．b 10．c 11．c 12．c 13. c 14. b
15. b
二、填空題
1．順序2．（n-1）/23．py->next=px->next; px->next=py
4 ．n-i+1
5．主要是使插入和刪除等操作統一，在第乙個元素之前插入元素和刪除第乙個結點不必另作判斷。另外，不論鍊錶是否為空，鍊錶指標不變。
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==l
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取下一元素
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是下個待插入結點的指標。
三、應用題
1．（1）選鏈式儲存結構。它可動態申請記憶體空間，不受表長度（即表中元素個數）的
影響，插入、刪除時間複雜度為o（1）。
（2）選順序儲存結構。順序表可以隨機訪問，時間複雜度為o（1）。
2．鏈式儲存結構一般說克服了順序儲存結構的三個弱點。首先，插入、刪除不需移動元素，只修改指標，時間複雜度為o(1)；其次，不需要預先分配空間，可根據需要動態申請空間；其三，表容量只受可用記憶體空間的限制。其缺點是因為指標增加了空間開銷，當空間不允許時，就不能克服順序儲存的缺點。
5.順序對映時，ai與ai+1的物理位置相鄰；鍊錶表示時ai與ai+1的物理位置不要求相鄰。
6．**性表的鏈式儲存結構中，頭指標指鍊錶的指標，若煉表有頭結點則是鍊錶的頭結點的指標，頭指標具有標識作用，故常用頭指標冠以鍊錶的名字。頭結點是為了操作的統
一、方便而設立的，放在第一元素結點之前，其資料域一般無意義（當然有些情況下也可存放鍊錶的長度、用做監視哨等等），有頭結點後，對在第一元素結點前插入結點和刪除第一結點，其操作與對其它結點的操作統一了。而且無論鍊錶是否為空，頭指標均不為空。首元結點也就是第一元素結點，它是頭結點後邊的第乙個結點。
9. 在單鏈表中不能從當前結點（若當前結點不是第一結點）出發訪問到任何乙個結點，鍊錶只能從頭指標開始，訪問到鍊錶中每個結點。在雙鏈表中求前驅和後繼都容易，從當前結點向前到第一結點，向後到最後結點，可以訪問到任何乙個結點。
10．本題是鍊錶的逆置問題。設該鍊錶帶頭結點，將頭結點摘下，並將其指標域置空。然後從第一元素結點開始，直到最後乙個結點為止，依次前插入頭結點的後面，則實現了鍊錶的逆置。
資料結構與演算法習題庫重點
第一章緒論 一 選擇題 1 資料結構被形式地定義為 k，r 其中k是 b 的有限集合，r是k上的 d 的有限集合。a 演算法 b 資料元素 c 資料操作 d 邏輯結構 a 操作 b 映象 c 儲存 d 關係 2 演算法分析的目的是 c，演算法分析的兩個主要方面是 a。a 找出資料結構的合理性 b 研...
資料結構與演算法分析練習題
1 表示式x y z u的逆波蘭式表示是 b 南方名校經典試題 a xyzuub xyz u c xyz u d xyzu 2 一棵左右子樹都不為空的二叉樹在先序線索化後，其空鏈域數為 b a 0b 1c 3d 不確定 3 設某二叉樹前序為abdcef，中序為dbaecf，則此二叉樹的後序為 a 南...
資料結構與演算法1 5單元練習題及答案
單元練習1 一 判斷題 下列各題，正確的請在前面的括號內打 錯誤的打 1 資料的邏輯結構與資料元素本身的內容和形式無關。2 乙個資料結構是由乙個邏輯結構和這個邏輯結構上的乙個基本運算集構成的整體。3 資料元素是資料的最小單位。4 資料的邏輯結構和資料的儲存結構是相同的。5 程式和演算法原則上沒有區別...