注：概念題
8．線性表（ a1,a2,…,an）以鏈結方式儲存時，訪問第i位置元素的時間複雜性為（c）
a．o（i） b．o（1） c．o（n） d．o（i-1）
注：訪問第i位置元素的期望值為（n-1）\2，所以時間複雜度為o(n)
9．非空的迴圈單鏈表head的尾結點p滿足（a）。
a．p->link=head b．p->link= null c．p=null d．p=head
注：概念題
10．在雙向迴圈鍊錶中,在p指標所指向的結點前插入乙個指標q所指向的新結點,其修改指標的操作是(c)。
注:雙向鍊錶的結點結構為(llink,data,rlink)。 供選擇的答案：
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=p； p->llink=q；p->llink=q；
注：概念題，p->llink=q;必須是最後的語句
11．在雙向鍊錶儲存結構中,刪除p所指的結點時須修改指標 (b)。
a．p->llink=( p->llink) ->llink； ( p->llink) ->rlink=p；
b．( p->llink) ->rlink = p->rlink； ( p->rlink) ->llink= p->llink；
c．( p->llink) ->rlink=p；p->rlink= ( p->rlink) -> llink；
d． p->rlink=( p->rlink) -> llink； p->llink =( p->rlink) -> rlink；
注：概念題
二、判斷題
1. 鍊錶中的頭結點僅起到標識的作用。(×)
注：還能便於對首元素的操作
2. 順序儲存結構的主要缺點是不利於插入或刪除操作。(√)
注：概念題
3．線性表採用鍊錶儲存時，結點和結點內部的儲存空間可以是不連續的。(√)
注：概念題
4．順序儲存方式插入和刪除時效率太低，因此它不如鏈式儲存方式好。(×)
注：這兩種儲存方式各有優缺點
5. 對任何資料結構鏈式儲存結構一定優於順序儲存結構。(×)
注：不一定
6．順序儲存方式只能用於儲存線性結構。(×)
注：還能儲存陣列等等
7. 線性表的特點是每個元素都有乙個前驅和乙個後繼。(×)
注：除了第乙個元素（只有乙個後繼）和最後乙個元素（只有乙個前驅）以外
8. 取線性表的第i個元素的時間同i的大小有關. (×)
注：時間與線性表的儲存方式有關
9. 迴圈鍊錶不是線性表. (×)
注：概念題
10. 線性表只能用順序儲存結構實現。(×)
注：還有鏈式儲存
11. 線性表就是順序儲存的表。(×)
注：概念題，線性表是n個資料元素的有限序列
12. 順序儲存方式的優點是儲存密度大，且插入、刪除運算效率高。(×)
注：順序儲存方式插入、刪除運算效率低
13. 鍊錶是採用鏈式儲存結構的線性表,進行插入、刪除操作時，在鍊錶中比在順序儲存結構中效率高。(√)
注：概念題
三、填空題
1．當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度訪問線性表中的元素時，應採用順序儲存結構。
注：題目要求的儲存方式能隨機訪問，並且很少進行插入和刪除操作，故採用順序儲存
2．線性表l=（a1,a2,…,an）用陣列表示，假定刪除表中任一元素的概率相同，則刪除乙個元素平均需要移動元素的個數是（n-1）/2。
注：期望值為（n-1）/2
3．設單鏈表的結點結構為(data,next)，next為指標域，已知指標px指向單鏈表中data為x的結點，指標py指向data為y的新結點 , 若將結點y插入結點x之後，則需要執行以下語句:py->next=px->next；px->next=py；
注：鍊錶儲存演算法應用題
4．在乙個長度為n的順序表中第i個元素（1<=i<=n）之前插入乙個元素時，需向後移動n-i+1個元素。
注：即i以及i之後的元素都要向後移動一位
5．對於乙個具有n個結點的單鏈表，在已知的結點*p後插入乙個新結點的時間複雜度為
o(1),在給定值為x的結點後插入乙個新結點的時間複雜度為o(n)。
注：鏈式儲存插入和刪除操作的時間複雜度都是o(1)，但是後半句「在給定值為x的結點後插入乙個新結點」即要先在鍊錶中查詢值為x的結點，故時間複雜度為o(n)
6．鏈結儲存的特點是利用指標來表示資料元素之間的邏輯關係。
注：概念題
7. 對於雙向鍊錶,在兩個結點之間插入乙個新結點需修改的指標共 4個，單鏈表為2個。
注：概念題
8.帶頭結點的雙迴圈鍊錶l中只有乙個元素結點的條件是：l->next->next=l
注：即l的後乙個結點的後繼為l
9.在單鏈表l中，指標p所指結點有後繼結點的條件是：p->next≠null
10.帶頭結點的雙迴圈鍊錶l為空表的條件是：l->next=l&&l->prior=l
注：即l的前驅和後繼都是自己
必修二第二章測試題
一 選擇題 本大題共10小題，每小題5分，共50分 在每小題給出的四個選項中，只有一項是符合題目要求的 1 下面四個命題 分別在兩個平面內的兩直線是異面直線 若兩個平面平行，則其中乙個平面內的任何一條直線必平行於另乙個平面 如果乙個平面內的兩條直線平行於另乙個平面，則這兩個平面平行 如果乙個平面內的...
資料結構第二章練習題答案
getelem l,3,e printf 6 順序表l的第3個元素 c n e printf 7 元素a的位置 d n locateelem l,a printf 8 在第4個元素位置上插入f元素 n listinsert l,4,f printf 9 輸出順序表l displist l print...
《資料結構》第二章線性表習題
資料結構 一 單項選擇題 1.線性表是 a 乙個有限序列，可以為空 b 乙個有限序列，不可以為空 c 乙個無限序列，可以為空 d 乙個無限序列，不可以為空 2.在乙個長度為n的順序表中刪除第i個元素 0 i n 時，需向前移動個元素。a n i b n i l c n i 1 d i 3.線性表採用...