《數(shù)據(jù)結構-線性表-習題.doc》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構-線性表-習題.doc（4頁珍藏版）》請在匯文網(wǎng)上搜索。

1、第二章 線性表一、選擇題1. 線性表是（ ）A一個有限序列，可以為空B一個有限序列，不可以為空C一個無限序列，可以為空D一個無限序列，不可以為空2. 一維數(shù)組與線性表的特征是（ ）。 A前者長度固定，后者長度可變 B兩者長度均固定 C后者長度固定，前者長度可變 D兩者長度均可變 3. 用單鏈表方式存儲的線性表，存儲每個結點需要兩個域，一個數(shù)據(jù)域，另一個是( ). A當前結點所在地址域B指針域 C空指針域D空閑域 4. 用鏈表表示線性表的優(yōu)點是（ ）。 A便于隨機存取B便于進行插入和刪除操作 C占用的存儲空間較順序表少D元素的物理順序與邏輯順序相同 5. 在具有 n 個結點的單鏈表中，實現(xiàn)_的操

2、作，其算法的時間復雜度都是O（n）。 A遍歷鏈表和求鏈表的第i個結點D刪除地址為P的結點的后繼結點B在地址為P的結點之后插入一個結點 C刪除開始結點6. 下面關于線性表的敘述中，錯誤的是（ ）。 A線性表采用順序存儲必須占用一片連續(xù)的存儲單元 B線性表采用順序存儲便于進行插入和刪除操作 C線性表采用鏈式存儲不必占用一片連續(xù)的存儲單元 D線性表采用鏈式存儲便于進行插入和刪除操作7. 已知單鏈表的每個結點包括一個指針域next，它指向該結點的后繼結點。現(xiàn)要將指針 q 指向的新結點插入到指針 p 指向的結點之后，下面的操作序列中正確的是（ ）。A . q = p-next; p-next = q-n

3、ext ;B . p-next = q-next;q = p-next ; C . q-next = p-next; p-next = q ; D . p-next = q; q-next = p-next ; 8. 設 al，a2， a3為三個結點； p , 10 , 20 代表地址，則如下的鏈表存儲結構稱為（ ）。A鏈表B單鏈表C雙向循環(huán)鏈表D雙向鏈表 9. 單鏈表的存儲密度（ ）。 A大于 1 B等于1C小于1D不能確定 10. 己知一個順序存儲的線性表，設每個結點需占 m 個存儲單元，若第一個結點的地址al ，則第i個結點的地址為（ ）。A. al+(i-1)*mB. al+i*mC.

4、 al-i*mD. al+(i+1)*m 11. 在 n 個結點的順序表中，算法的時間復雜度是 O(l）的操作是（ ）。 A訪問第i個結點（1in）和求第 i 個結點的直接前驅（2in) B在第 i 個結點之后插入一個新結點（1in-1） C刪除第 i 個結點（ 1in ) D將 n 個結點從小到大排序 12. 在線性表中（ ）只有一個直接前驅和一個直接后繼。 A首元素B中間元素C尾元素D所有元素 13. 對具有 n 個結點的線性表進行查找運算，所需的算法時間復雜度為（ ）。 A. 0 (n2)B. 0 (nlog2n)C. O (log2n)D. O (n) 14. 線性表采用順序存儲的缺點

5、是（ ）。 A存儲密度降低B只能順序訪問 C元素的邏輯順序與物理順序不一致D插入、刪除操作效率低 15. 以下鏈表結構中，從當前結點出發(fā)能夠訪問到任一結點的是（ ）。A單向鏈表和雙向鏈表B雙向鏈表和循環(huán)鏈表 C單向鏈表和循環(huán)鏈表D單向鏈表、雙向鏈表和循環(huán)鏈表 16. 線性表是具有 n 個（ ）的有限序列。 A數(shù)據(jù)項B數(shù)據(jù)元素C表元素D字符 17. 若長度為 n 的線性表采用鏈式存儲結構，訪問其第 i 個元素的算法時間復雜度為（ ）。A. 0 ( l )B. 0 ( n )C. 0 ( n2 )D. 0 ( log2n )18. 指針 P 指向循環(huán)鏈表 L 的首元素的條件是（ ）。 A. PLB

6、. L-nextPC.P-next= =NULLD. P-nextL 19. 指針 P 所指的元素是雙循環(huán)鏈表 L 的尾元素的條件是（ ）。 A. PLB. P-priorLC. PNULLD. P-nextL 20. 不帶頭結點的單鏈表L為空的條件是( )A. L!NULLB. LNULLC. L-nextNULLD. L-nextL21. 帶頭結點的單鏈表L為空的條件是( )A. L!NULLB. LNULLC. L-nextNULLD. L-nextL22. 兩個指針 P 和 Q ，分別指向單鏈表的兩個元素， P 所指元素是 Q 所指元素前驅的條件是（ ）。 A. P-nextQ-nex

7、tB. P-nextQC. Q-nextPD. PQ 23. 在長度為 n 的順序表中，若要刪除第 i (1in ）個元素，則需要向前移動元素的次數(shù)為（ ）。 A. 1B. n一iC. n一i+1D. n一i一l 24. 在長度為 n 的順序表中第 i (1in）個位置上插入一個元素時，為留出插入位置所需移動元素的次數(shù)為（ ）。A. n-iB. iC. ni+1D. n-i-l 25. 假定己建立以下動態(tài)鏈表結構，且指針 Pl 和 P2 已指向如圖所示的結點：則以下可以將 P2 所指結點從鏈表中刪除并釋放該結點的語句組是( )A. pl-next=p2-next; free (pl);B. p

8、l=p2; free (p2);C. pl-next=p2-next；free (p2);D. pl=p2-next; free (p2); 26. 若已建立如圖所示的單向鏈表，則以下不能將 s 所指的結點插入到鏈表尾部，構成新的單向鏈表的語句組是（ ）。A . s-next = a-next-next ; a-next-next = s ;B . a = a-next; a-next =s ; s-next = NULL ;C . s-next = NULL ; a = a-next; a-next = s ;D . a = a-next ; s-next = a-next ; a-next

9、 = s-next ;27. 有如下函數(shù)，其中形參 hl 和 h2 分別指向 2 個不同鏈表的第一個結點，此函數(shù)的功能是（ ）。Void fun( struct node * hl , struct node * h2 ) struct node * t ; t = hl ;while ( t-next ! 0 ) t = t-next ; t-next = h2 ; A將鏈表 h2 接到鏈表 h1 后B將鏈表 h1 接到鏈表 h2 后 C找到鏈表 hl 的最后一個結點由指針返回D將鏈表 hl 拆分成兩個鏈表 二、判斷題1. 循環(huán)鏈表不是線性表. ( )2. 線性表就是順序存儲的表。( ) 3

10、. 線性表只能用順序存儲結構實現(xiàn)。( ) 4. 鏈表中的頭結點僅起到標識的作用。( )5. 線性表的鏈式存儲結構優(yōu)于順序存儲。( ) 6. 順序存儲的線性表可以實現(xiàn)隨機存取。( ) 7. 順序存儲方式只能用于存儲線性結構。( )8. 鏈表的每個結點都恰好包含一個指針域。( )9. 所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。( )鏈表中的結點可含多個指針域,分別存放多個指針。 10. 集合與線性表的區(qū)別在于是否按關鍵字排序。( ) 11. 取線性表的第i個元素的時間同i的大小有關. ( ) 12. 順序存儲結構的主要缺點是不利于插入或刪除操作。( )13. 線性表的特點是每個元素都有一個前驅和一個后

11、繼。( ) 14. 對任何數(shù)據(jù)結構鏈式存儲結構一定優(yōu)于順序存儲結構。( ) 15. 順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。( ) 16. 為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。( ) 17. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。( ) 18. 順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。( ) 19. 線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續(xù)的。( ) 20. 線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。( ) 21. 在線性表的順序存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。

12、( ) 22. 在線性表的順序結構中，插入和刪除元素時，移動元素的個數(shù)與該元素的位置有關。( ) 23. 在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此單鏈表是隨機存取的存儲結構。( ) 24. 鏈表是采用鏈式存儲結構的線性表,進行插入、刪除操作時，在鏈表中比在順序存儲結構中效率高。 ( ) 25. 在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，所以可以從頭結點開始查找任何一個元素。( )26. 線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此屬于同一數(shù)據(jù)對象。( )三、填空題1. 順序表中邏輯上相鄰的元素在物理位置上相鄰。2. 在鏈表中邏輯上相

13、鄰的元素的物理位置相鄰。3. 帶頭結點的雙循環(huán)鏈表L為空表的條件是：。4. 在單鏈表p結點之后插入s結點的操作是：。5.6. 順序表相對于鏈表的優(yōu)點有和。7. 在雙鏈表中要刪除已知結點*p ，其時間復雜度為。8. 在順序表中訪問任意一個結點的時間復雜度均為。9. 鏈接存儲的特點是利用來表示數(shù)據(jù)元素之間的邏輯關系。10. 帶頭結點的雙循環(huán)鏈表L中只有一個元素結點的條件是：11. 在單鏈表L中，指針p所指結點有后繼結點的條件是：12.13. 在單鏈表中除首結點外，任意結點的存儲位置都由結點中的指針指示。14. 已知指針p指向單鏈表L中的某結點，則刪除其后繼結點的語句是：15.16. 在 n 個結點

14、的單鏈表中要刪除已知結點*p ，需要找到.其時間復雜度為。17. 鏈表相對于順序表的優(yōu)點有和操作方便；缺點是存儲密度。18. 建立單鏈表的算法時間復雜度 ；建立有序單鏈表的算法時間復雜度 。19. 在單鏈表中設置頭結點的作用是。20. 對于雙向鏈表,在兩個結點之間插入一個新結點需修改的指針共個，單鏈表為個。21. 在一個長度為n的順序表中第i個元素（1=inext ; do s= s ；p = p-next ; while ( p ! )；return s; 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19. 己知 head 指向一個帶有頭結點的單

15、向鏈表，鏈表中每個結點包含整型數(shù)據(jù)域（ data ) 和指針域（ next ）。以下算法用來查找鏈表所有結點中數(shù)據(jù)域值最大的結點的位置，由指針 s 傳回調用程序。請?zhí)羁?。struct link char data ; struct link *next;main ( )struct link * head , * q ; findmax ( head , & q ) ;printf ( max = % d n , q-data ) ; findmax ( struct link * head , struct link * * s ) struct link * p ; p = h ead-n

16、ext ; * s = p ; while （ ） p ; if ( p-data )* s=p ; 20. 設線性表順序存儲結構定義如下：# define MAXSIZE 20typedef int datatypetype struct datatype data MAXSIZE + l ; int last ; sequenlist ; 函數(shù) int 1ocate2 ( sequenlist * L , int x ) ；利用在表頭設立監(jiān)視哨的算法，實現(xiàn)在順序表 L 中查找值為 x 的元素的位置。請?zhí)羁铡?int locate2 ( sequenlist * L , int x ) int i = ；L-data 0 = x ; while ( L-datai! = x ） ;return i ; 21. 設有兩個由尾指針表示的帶有頭結點的單向環(huán)形鏈表 ra 和 rb ，以下算法實現(xiàn)將rb 所指的鏈表連接到 ra 所指鏈表之后。請?zhí)羁铡?LinkList * Connect (LinkList * ra , LinkList * rb )LinkList * p ;p = ra-next ;ra-next ；free ( rb-next ) ; rb一 next = ；return rb;