數據結構-線性表-習題

1、第二章一、選擇題1. 線性表是（）A. 個有限序列，可以為空C. 一個無限序列，可以為空2. 一維數組與線性表的特征是（）。A.前者長度固定，后者長度可變C.后者長度固定，前者長度可變線性表B. 個有限序列，不可以為空D. 個無限序列，不可以為空B.兩者長度均固定D.兩者長度均可變用單鏈表方式存儲的線性表,3.是（）A.當前結點所在地址域C.空指針域4. 用鏈表表示線性表的優(yōu)點是（）。A.便于隨機存取C.占用的存儲空間較順序表少5. 在具有n個結點的單鏈表中，實現A. 遍歷鏈表和求鏈表的第i個結點B. 在地址為P的結點之后插入一個結點6.存儲每個結點需要兩個域，一個數據域，另一個B.指針域D.

2、空閑域B.便于進行插入和刪除操作D.元素的物理順序與邏輯順序相同 的操作，其算法的時間復雜度都是 （n）。D.刪除地址為P的結點的后繼結點C .刪除開始結點A.鏈表B.單鏈表C.雙向循環(huán)鏈表D.雙向鏈表9. 單鏈表的存儲密度（）。A.大于1B.等于1C.小于1D.不能確定10. 己知一個順序存儲的線性表，設每個結點需占m個存儲單元，若第一個結點的地址al ,則第i個結點的地址為（ ）。A. al+（i-1）*mB. al+i*mC. al-i*mD. al+（i+1）*m11. 在n個結點的順序表中，算法的時間復雜度是0（1 ）的操作是（）。A. 訪問第i個結點（K i < n）和求第i

3、個結點的直接前驅（2< i < n）B. 在第i個結點之后插入一個新結點（ K i < n-1 ）C. 刪除第i個結點（1 w i w n ）D. 將n個結點從小到大排序12. 在線性表中（）只有一個直接前驅和一個直接后繼。A.首元素B.中間元素C.尾元素D.所有元素13. 對具有n個結點的線性表進行查找運算，所需的算法時間復雜度為（）。2A. 0 （n ）B. 0 （n log2n）C. O （log 2n） D. O （n）14. 線性表采用順序存儲的缺點是（）。A.存儲密度降低B.只能順序訪問F面關于線性表的敘述中，錯誤的是（）。15.A. 線性表采用順序存儲必須占用一

4、片連續(xù)的存儲單元B. 線性表采用順序存儲便于進行插入和刪除操作C. 線性表采用鏈式存儲不必占用一片連續(xù)的存儲單元D. 線性表采用鏈式存儲便于進行插入和刪除操作7.已知單鏈表的每個結點包括一個指針域next，它指向該結點的后繼結點?，F16.17.要將指針q指向的新結點插入到指針 p指向的結點之后，下面的操作序列中正確的是()。A . q = p_>n ext;B . p->n ext = q->n ext;C . q_>next = p_>n ext;D . p_>next = q;8. 設a l, a2, a 3為三個結點;p_>next = q_&g

5、t;n ext ;q = p_>next ;p_>next = q ;q_>next = p_>n ext ;p , 10,20代表地址，則如下的鏈表存儲結構18.19.20.稱為（）。21.C.元素的邏輯順序與物理順序不一致D.插入、刪除操作效率低以下鏈表結構中，從當前結點出發(fā)能夠訪問到任一結點的是（A.單向鏈表和雙向鏈表C.單向鏈表和循環(huán)鏈表 線性表是具有n個（）的有限序列。A.數據項 若長度為n 度為（A. 0 （ l ）B.數據元素 的線性表采用鏈式存儲結構,B. 0 ( n )B.D.雙向鏈表和循環(huán)鏈表單向鏈表、雙向鏈表和循環(huán)鏈表表元素 訪問其第iC.C. 0

6、 ( n 2 )D.字符個元素的算法時間復雜D. 0 ( log2n )指針P指向循環(huán)鏈表L的首元素的條件是（）。A. P = L B. L-> next = P C.P-> next= =NULL指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是（A. P = LB. P->prior = L C. P = NULL不帶頭結點的單鏈表 L為空的條件是（）A. L! = NULL B. L = NULLC. L-> next = NULL帶頭結點的單鏈表 L為空的條件是（）D. P->next)。D. P->nextD. L-> next=L=L=LA.

7、L! = NULL B. L = NULL C. L->next = NULL D. L->next = L22. 兩個指針P和Q ,分別指向單鏈表的兩個元素，P所指元素是Q所指元素前驅的條件是（）。A. P-> next = Q-> nextB. P-> next = QC. Q-> next = PD. P = Q23. 在長度為n的順序表中，若要刪除第i （1 w i < n ）個元素，則需要向前移動元素的次數為（ ）。A. 1B. n 一 iC. n 一 i+1D. n 一 i 一 I24. 在長度為n的順序表中第i （1 w i w n）個位

8、置上插入一個元素時，為留出插入位置所需移動元素的次數為（）。A. n-iB. iC. n i+1D. n-i-l25. 假定己建立以下動態(tài)鏈表結構，且指針Pl和P2已指向如圖所示的結點：則以下可以將P2所指結點從鏈表中刪除并釋放該結點的語句組是（）A. pl->n ext=p2->n ext; free （pl）;B. pl=p2; free （p2）;C. pl->next=p2->next; free （p2）;D. pl=p2->next; free （p2）;26. 若已建立如圖所示的單向鏈表，則以下不能將s所指的結點插入到鏈表尾部,構成新的單向鏈表的語句

9、組是（）。iii> iLskA . s->next = a->n ext- >next ; a->n ext->n ext = s ;B . a = a->n ext; a->n ext =s ; s->n ext = NULL ;C . s->n ext = NULL ; a = a->n ext; a->next = s ;D . a = a->next ; s->n ext = a->next ; a->n ext = s->n ext ;27. 有如下函數，其中形參hl和h2分別指向2

10、個不同鏈表的第一個結點，此函數的功能是（）。Void fun（ struct n ode * hl , struct n ode * h2 ）struct node * t ;t = hl ;while （ t->n ext != '0'）t = t->next ; t->next = h2 ;A.將鏈表h2接到鏈表h1后B.將鏈表h1接到鏈表h2后C.找到鏈表hl的最后一個結點由指針返回D .將鏈表hl拆分成兩個鏈表二、判斷題1. 循環(huán)鏈表不是線性表.（x ）2. 線性表就是順序存儲的表。（X ）3. 線性表只能用順序存儲結構實現。（x ）4. 鏈表中的頭結

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

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

13、中的結點可含多個指針域，分別存放多個指針。在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此單鏈表是隨機存取的存儲結構。（X ）鏈表是采用鏈式存儲結構的線性表，進行插入、刪除操作時，在鏈表中比在順序存儲結構中效率高。（V ）在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯系，所以可以從頭結點開始查找任何一個元素。（V ）線性表中的元素可以是各種各樣的，但同一線性表中的數據元素具有相同的特性，因此屬于同一數據對象。（V ）填空題順序表中邏輯上相鄰的元素在物理位置上 相鄰。在鏈表中邏輯上相鄰的元素的物理位置 相鄰。帶頭結點的雙循環(huán)鏈表 L為空表的條件是： 。在單鏈表p結點之后插入s結點的

14、操作是： 。順序表相對于鏈表的優(yōu)點有 和。在雙鏈表中要刪除已知結點 *p，其時間復雜度為。在順序表中訪問任意一個結點的時間復雜度均為 。鏈接存儲的特點是利用 來表示數據元素之間的邏輯關系。帶頭結點的雙循環(huán)鏈表 L中只有一個元素結點的條件是： 在單鏈表L中，指針p所指結點有后繼結點的條件是： 在單鏈表中除首結點外，任意結點的存儲位置都由 結點中的指針指示。已知指針p指向單鏈表L中的某結點，則刪除其后繼結點的語句是：向后移動個元素。22. 在循環(huán)鏈表中，可根據一個結點的地址訪問整個鏈表，而單鏈表中需知道_才能訪問整個鏈表。23. 順序存儲結構是通過表示元素之間的關系的；鏈式存儲結構是通過表示元素之

15、間的關系的。24. 有一單鏈表結構如下，若要刪除值為c的結點，應做的操作是 25. 在n個結點的順序表中插入一個結點，平均需要移動 個結點，具體的移動次數取決于。26. 在n個結點的順序表中刪除一個結點，平均需要移動 個結點，具體的移動次數取決于。27. 在雙向循環(huán)鏈表中，向p所指的結點之后插入指針f所指的結點，其操作是 _28. 線性表L= （a1,a2,an ）用數組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數是 。29. 循環(huán)單鏈表與非循環(huán)單鏈表的主要不同是，循環(huán)單鏈表尾結點的指針，而非循環(huán)單鏈表的尾結點指針 。30. 當線性表的元素總數基本穩(wěn)定，且很少進行

16、插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用 存儲結構。31. 線性表L = （ a1, a2 ,，an）用數組存儲。假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動的元素個數是 。32. 在單鏈表中要在已知結點 *p之前插入一個新結點，需找到 ，其時間復23.24.25.26.三、1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.雜度為;而在雙鏈表中，完成同樣操作時其時間復雜度為 。33.linlc在n個結點的單鏈表中要刪除已知結點*p，需要找到 .其時間復雜度為。鏈表相對于順序表的優(yōu)點有 和操作方便；缺點

17、是存儲密度。建立單鏈表的算法時間復雜度 ;建立有序單鏈表的算法時間復雜度。在單鏈表中設置頭結點的作用是 對于雙向鏈表，在兩個結點之間插入一個新結點需修改的指針共 個，單鏈表為個。34.在一個長度為n的順序表中第i個元素（1<=i<=n ）之前插入一個元素時，需對于一個具有n個結點的單鏈表，在已知的結點 *p后插入一個新結點的時間復雜度為,在給定值為x的結點后插入一個新結點的時間復雜度為。根據線性表的鏈式存儲結構中每一個結點包含的指針個數，將線性鏈表分成禾口; 而又根據指針的連接方式，鏈表又可分成 和。35. 在雙向鏈表結構中，若要求在p指針所指的結點之前插入指針為s所指的結點，則需

18、執(zhí)行下列語句：sA .next:=p； sA .prior:= ； pA .prior:=s ； :=s ；36. 設單鏈表的結點結構為(data,next)， next為指針域，已知指針px指向單鏈表中data為x的結點，指針py指向data為y的新結點,若將結點y插入結 點x之后，則需要執(zhí)行以下語句 :；;37. 設有結點定義如下，且已建立如下圖所示的帶有頭結點的單向鏈表：struct node int data ;struct node * next ; ;dlU IHEVlt1 生函數sum的功能是：計算鏈表中各結點數據域之和，作為函數值返回。請?zhí)羁?。int sum (struct n

19、ode * head ) int s = 0 ;struct node * p ;p = head->next ;do s= s +；p = p_>next ; while ( p !=);return s; 19. 己知head指向一個帶有頭結點的單向鏈表，鏈表中每個結點包含整型數據域 (data )和指針域(next)。以下算法用來查找鏈表所有結點中數據域值最大的結點的位置，由指針 s傳回調用程序。請?zhí)羁?。struct li nk char data ;struct link *n ext;mai n ( )struct link * head , * q ;fin dmax ( head , & q );printf ( " max = % d n ”，q->data ) ; fin dmax ( s