《資料結構》
一、單項選擇題
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. 線性表採用鏈式儲存時，其位址________。
a．必須是連續的b．一定是不連續的
c．部分位址必須是連續的 d．連續與否均可以
4. 從乙個具有n個結點的單鏈表中查詢其值等於x的結點時，在查詢成功的情況下，需平均比較________個元素結點。
a．n/2b．nc．（n+1）/2 d．（n-1）/2
5. 在雙向迴圈鍊錶中，在p所指的結點之後插入s指標所指的結點，其操作是____。
a． p->next=s; s->prior=p;
p->next->prior=s; s->next=p->next;
b． s->prior=p; s->next=p->next;
p->next=s; p->next->prior=s;
c． p->next=s; p->next->prior=s;
s->prior=p; s->next=p->next;
d． s->prior=p; s->next=p->next;
p->next->prior=s; p->next=s;
6. 設單鏈表中指標p指向結點m，若要刪除m之後的結點（若存在），則需修改指標的操作為________。
a．p->next=p->next->next; b．p=p->next; c．p=p->next->next; d．p->next=p;
7. 在乙個長度為n的順序表中向第i個元素(0< ia．n-ib．n-i+lc．n-i-1d．i
8. 在乙個單鏈表中，已知q結點是p結點的前趨結點，若在q和p之間插入s結點，則須執行
a．s->next=p->next; p->next=sb．q->next=s; s->next=p
c．p->next=s->next; s->next=pd．p->next=s; s->next=q
9. 以下關於線性表的說法不正確的是______。
a．線性表中的資料元素可以是數字、字元、記錄等不同型別。
b．線性表中包含的資料元素個數不是任意的。
c．線性表中的每個結點都有且只有乙個直接前趨和直接後繼。
d．存在這樣的線性表：表中各結點都沒有直接前趨和直接後繼。
10. 線性表的順序儲存結構是一種_______的儲存結構。
a．隨機訪問 b．順序訪問 c．索引訪問 d．雜湊訪問
11. 在順序表中，只要知道_______，就可在相同時間內求出任一結點的儲存位址。
a．基位址 b．結點大小 c．向量大小 d．基位址和結點大小
12. 在等概率情況下，順序表的插入操作要移動______結點。
a．全部 b．一半 c．三分之一 d．四分之一
13. 在______運算中，使用順序錶比鍊錶好。
a．插入 b．刪除 c．根據序號查詢 d．根據元素值查詢
14. 在乙個具有n個結點的有序單鏈表中插入乙個新結點並保持該錶有序的時間複雜度是_______。
a．o(1) b．o(n) c．o(n2) d．o(log2n)
15. 設有乙個棧，元素的進棧次序為a, b, c, d, e,下列是不可能的出棧序列
a．a, b, c, d, e b．b, c, d, e, a c．e, a, b, c, d d．e, d, c, b, a
16. 在乙個具有n個單元的順序棧中，假定以位址低端（即0單元）作為棧底，以top作為棧頂指標，當做出棧處理時，top變化為______。
a．top不變b．top=0c．topd．top++
17. 向乙個棧頂指標為hs的鏈棧中插入乙個s結點時，應執行______。
a．hs->next=sb．s->next=hs; hs=s;
c．s->next=hs->next;hs->next=sd．s->next=hs; hs=hs->next;
18. 在具有n個單元的順序儲存的迴圈佇列中，假定front和rear分別為隊頭指標和隊尾指標，則判斷隊滿的條件為________。
a．rear％n= = frontb．（front+l）％n= = rear
c．rear％n -1= = frontd．(rear+l)％n= = front
19. 在具有n個單元的順序儲存的迴圈佇列中，假定front和rear分別為隊頭指標和隊尾指標，則判斷隊空的條件為________。
a．rear％n= = front b．front+l= rear c．rear= = front d．(rear+l)％n= front
20. 在乙個鏈佇列中，假定front和rear分別為隊首和隊尾指標，則刪除乙個結點的操作為________。
a．front=front->nextb．rear=rear->next
c．rear=front->nextd．front=rear->next
二、填空題
1. 線性表是一種典型的_________結構。
2. 在乙個長度為n的順序表的第i個元素之前插入乙個元素，需要後移____個元素。
3. 順序表中邏輯上相鄰的元素的物理位置________。
4. 要從乙個順序表刪除乙個元素時，被刪除元素之後的所有元素均需_______乙個位置，移動過程是從_______向_______依次移動每乙個元素。
5. **性表的順序儲存中，元素之間的邏輯關係是通過_______決定的；**性表的鏈結儲存中，元素之間的邏輯關係是通過_______決定的。
6. 在雙向鍊錶中，每個結點含有兩個指標域，乙個指向_______結點，另乙個指向_______結點。
7. 當對乙個線性表經常進行訪問操作，而很少進行插入和刪除操作時，則採用_______儲存結構為宜。相反，當經常進行的是插入和刪除操作時，則採用_______儲存結構為宜。
8. 順序表中邏輯上相鄰的元素，物理位置____相鄰，單鏈表中邏輯上相鄰的元素，物理位置____相鄰。
9. 線性表、棧和佇列都是_______結構，可以**性表的______位置插入和刪除元素；對於棧只能在_______位置插入和刪除元素；對於佇列只能在_______位置插入元素和在_______位置刪除元素。
10. 根據線性表的鏈式儲存結構中每個結點所含指標的個數，鍊錶可分為_________和_______；而根據指標的聯接方式，鍊錶又可分為________和
11. 在單鏈表中設定頭結點的作用是________。
12. 對於乙個具有n個結點的單鏈表，在已知的結點p後插入乙個新結點的時間複雜度為______，在給定值為x的結點後插入乙個新結點的時間複雜度為_______。
13. 對於乙個棧作進棧運算時，應先判別棧是否為_______，作退棧運算時，應先判別棧是否為_______，當棧中元素為m時，作進棧運算時發生上溢，則說明棧的可用最大容量為_______。為了增加記憶體空間的利用率和減少發生上溢的可能性，由兩個棧共享一片連續的記憶體空間時，應將兩棧的_______分別設在這片記憶體空間的兩端，這樣只有當_______時才產生上溢。
14. 設有一空棧，現有輸入序列1，2，3，4，5，經過push, push, pop, push, pop, push, push後，輸出序列是
15. 無論對於順序儲存還是鏈式儲存的棧和佇列來說，進行插入或刪除運算的時間複雜度均相同為
三、簡答題
1. 描述以下三個概念的區別：頭指標，頭結點，表頭結點。
2. 線性表的兩種儲存結構各有哪些優缺點？
3. 對於線性表的兩種儲存結構，如果有n個線性表同時並存，而且在處理過程中各表的長度會動態發生變化，線性表的總數也會自動改變，在此情況下，應選用哪一種儲存結構？為什麼？
4. 對於線性表的兩種儲存結構，若線性表的總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度訪問線性表中的元素，應選用何種儲存結構？試說明理由。
5. 在單迴圈鍊錶中設定尾指標比設定頭指標好嗎？為什麼?
6. 假定有四個元素a, b, c, d依次進棧，進棧過程中允許出棧，試寫出所有可能的出棧序列。
7. 什麼是佇列的上溢現象？一般有幾種解決方法，試簡述之。
8. 下述演算法的功能是什麼?
linklist *demo(linklist *l)
return (l);
}四、演算法設計題
1. 設計在無頭結點的單鏈表中刪除第i個結點的演算法。
2. 在單鏈表上實現線性表的求表長listlength(l)運算。
3. 設計將帶表頭的鍊錶逆置演算法。
4. 假設有乙個帶表頭結點的鍊錶，表頭指標為head，每個結點含三個域：data, next和prior。
其中data為整型數域，next和prior均為指標域。現在所有結點已經由next域連線起來，試編乙個演算法，利用prior域（此域初值為null）把所有結點按照其值從小到大的順序鏈結起來。
資料結構習題第二章線性表答案
第2章線性表 一 選擇題 二 判斷題 部分答案解釋如下。1 頭結點並不 僅起 標識作用，並且使操作統一。另外，頭結點資料域可寫入鍊錶長度，或作監視哨。4 兩種儲存結構各有優缺點，應根據實際情況選用，不能籠統說哪乙個好。7 集合中元素無邏輯關係。9 非空線性表第乙個元素無前驅，最後乙個元素無後繼。13...
資料結構考研習題 第二章線性表
第2章線性表 一選擇題 1 下述哪一條是順序儲存結構的優點？北方交通大學 2001 一 4 2分 a 儲存密度大 b 插入運算方便 c 刪除運算方便 d 可方便地用於各種邏輯結構的儲存表示 2 下面關於線性表的敘述中，錯誤的是哪乙個？北方交通大學 2001 一 14 2分 a 線性表採用順序儲存，必...
資料結構及應用演算法教程習題第二章線性表
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 ...