1.下面關於線性表的敘述中,錯誤的是哪乙個?( )
a.線性表採用順序儲存,必須占用一片連續的儲存單元。
b.線性表採用順序儲存,便於進行插入和刪除操作。
c.線性表採用鏈結儲存,不必占用一片連續的儲存單元。
d.線性表採用鏈結儲存,便於插入和刪除操作。
2.線性表是具有n個( )的有限序列(n>0)。
a.表元素 b.字元 c.資料元素
d.資料項 e.資訊項
3. 線性表( a1,a2,…,an)以鏈結方式儲存時,訪問第i位置元素的時間複雜性為( )
a.o(i) b.o(1) c.o(n) d.o(i-1)
4. 若長度為n的線性表採用順序儲存結構,在其第i個位置插入乙個新元素的演算法的時間複雜度為( )(1<=i<=n+1)。
a. o(0) b. o(1c. o(nd. o(n2)
5. 對於順序儲存的線性表,訪問結點和增加、刪除結點的時間複雜度為( )。
a.o(n) o(n) b. o(n) o(1) c. o(1) o(n) d. o(1) o(1)
6.對於乙個頭指標為head的帶頭結點的單鏈表,判定該錶為空表的條件是( )
a.head==null b.head→next==null c.head→next==head d.head!=null
7. 鍊錶不具有的特點是( )
a.可隨機訪問任一元素 b.插入、刪除不需要移動元素
c.不必事先估計儲存空間 d.所需空間與線性長度成正比
8. 在雙向鍊錶指標p的結點前插入乙個指標q的結點操作是( )。
>llink=q;q->rlink=p;p->llink->rlink=q;q->llink=q;
>llink=q;p->llink->rlink=q;q->rlink=p;q->llink=p->llink;
c. q->llink=p->llink;q->rlink=q;p->llink=q;p->llink=q;
>rlink=p;q->llink=p->llink;p->llink->rlink=q;p->llink=q;
9. 在單鏈表指標為p的結點之後插入指標為s的結點,正確的操作是:( )。
a. s->next=p->next;p->next=s;
b. p->next=s;s->next=p->next;
c.p->next=s;p->next=s->next;
d. p->next=s->next;p->next=s;
10 .對於乙個頭指標為head的帶頭結點的單鏈表,判定該錶為空表的條件是( )
a.head==null b.head→next==null c.head→next==head d.head!=null
答案:1. b 3. c 5. c
6. b 10. b
作業一1.線性表有兩種儲存結構:一是順序表,二是鍊錶。試問:
(1)如果有 n個線性表同時並存,並且在處理過程中各表的長度會動態變化,線性表的總數也會自動地改變。在此情況下,應選用哪種儲存結構? 為什麼?
(2)若線性表的總數基本穩定,且很少進行插入和刪除,但要求以最快的速度訪問線性表中的元素,那麼應採用哪種儲存結構?為什麼?
2.設雙向迴圈鍊錶中結點的資料域、前驅和後繼指標域分別為data,pre和next,試寫出在指標p 所指結點之前插入一s結點的c語言描述語句。
3.一線性表儲存在帶頭結點的雙向迴圈鍊錶中,l為頭指標。如下演算法:
(1)說明該演算法的功能。(2)在空缺處填寫相應的語句。
void unknown (bnodetp *l)
} 4.已知線性表(a1 a2 a3 …an)按順序存於記憶體,每個元素都是整數,試設計用最少時間把所有值為負數的元素移到全部正數值元素前邊的演算法:例:(x,-x,-x,x,x,-x …x)變為(-x,-x,-x…x,x,x)。
答案:1.(1)選鏈式儲存結構。它可動態申請記憶體空間,不受表長度(即表中元素個數)的影響,插入、刪除時間複雜度為o(1)。
(2)選順序儲存結構。順序表可以隨機訪問,時間複雜度為o(1)。
2.在指標p所指結點前插入結點s的語句如下:
s->pre=p->pre; s->next=p; p->pre->next=s; p->pre=s;
3. 1)本演算法功能是將雙向迴圈鍊錶結點的資料域按值自小到大排序,成為非遞減(可能包括資料域值相等的結點)有序雙向迴圈鍊錶。
2)(1)r->prior=q->prior;∥將q結點摘下,以便插入到適當位置。
(2)p->next->prior=q;∥(2)(3)將q結點插入
(3)p->next=q;
(4)r=r->next;或r=q->next;∥後移指標,再將新結點插入到適當位置。
4[題目分析]題目要求重排n個元素且以順序儲存結構儲存的線性表,使得所有值為負數的元素移到正數元素的前面。這可採用快速排序的思想來實現,只是提出暫存的第乙個元素(樞軸)並不作為以後的比較標準,比較的標準是元素是否為負數。
int rearrange(seqlist a; int n)
∥a是具有n個元素的線性表,以順序儲存結構儲存,線性表的元素是整數。本演算法重排線性表a,
∥使所有值為負數的元素移到所有值為正數的數的前面。
[演算法討論] 本演算法時間複雜度為o(n)。演算法只是按題目要求把正負數分開,如要求統計負數和大於等於零的個數,則最後以t來定。如t為負數,則0至i共i+1個負數,n-1-i個正數(包括零)。
另外,題目並未提及零的問題,筆者將零放到正數一邊。對此問題的擴充是若元素包含正數、負數和零,並要求按負數、零、正數的順序重排線性表
,統計負數、零、正數的個數。
資料結構 第2章線性表
第2章線性表 一選擇題 1 下述哪一條是順序儲存結構的優點?北方交通大學 2001 一 4 2分 a 儲存密度大 b 插入運算方便 c 刪除運算方便 d 可方便地用於各種邏輯結構的儲存表示 2 下面關於線性表的敘述中,錯誤的是哪乙個?北方交通大學 2001 一 14 2分 a 線性表採用順序儲存,必...
資料結構第2章線性表
第2章線性表自測卷 一 填空 1.在順序表中插入或刪除乙個元素,需要平均移動元素,具體移動的元素個數 與有關。2.線性表中結點的集合是的,結點間的關係是的。3.向乙個長度為n的向量的第i個元素 1 i n 1 之前插入乙個元素時,需向後移動個元素。4.向乙個長度為n的向量中刪除第i個元素 1 i n...
資料結構第2章線性表
第2章線性表練習題 一 填空 1.在順序表中插入或刪除乙個元素,需要平均移動元素,具體移動的元素個數 與有關。2.線性表中結點的集合是的,結點間的關係是的。3.向乙個長度為n的向量的第i個元素 1 i n 1 之前插入乙個元素時,需向後移動個元素。4.向乙個長度為n的向量中刪除第i個元素 1 i n...