數(shù)據(jù)結(jié)構(gòu)-線性表-習題

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

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

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

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

5、t;n ext ;q = p_>next ;p_>next = q ;q_>next = p_>n ext ;p , 10,20代表地址，則如下的鏈表存儲結(jié)構(gòu)18.19.20.稱為（）。21.C.元素的邏輯順序與物理順序不一致D.插入、刪除操作效率低以下鏈表結(jié)構(gòu)中，從當前結(jié)點出發(fā)能夠訪問到任一結(jié)點的是（A.單向鏈表和雙向鏈表C.單向鏈表和循環(huán)鏈表 線性表是具有n個（）的有限序列。A.數(shù)據(jù)項 若長度為n 度為（A. 0 （ l ）B.數(shù)據(jù)元素 的線性表采用鏈式存儲結(jié)構(gòu),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不帶頭結(jié)點的單鏈表 L為空的條件是（）A. L! = NULL B. L = NULLC. L-> next = NULL帶頭結(jié)點的單鏈表 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所指元素前驅(qū)的條件是（）。A. P-> next = Q-> nextB. P-> next = QC. Q-> next = PD. P = Q23. 在長度為n的順序表中，若要刪除第i （1 w i < n ）個元素，則需要向前移動元素的次數(shù)為（ ）。A. 1B. n 一 iC. n 一 i+1D. n 一 i 一 I24. 在長度為n的順序表中第i （1 w i w n）個位

8、置上插入一個元素時，為留出插入位置所需移動元素的次數(shù)為（）。A. n-iB. iC. n i+1D. n-i-l25. 假定己建立以下動態(tài)鏈表結(jié)構(gòu)，且指針Pl和P2已指向如圖所示的結(jié)點：則以下可以將P2所指結(jié)點從鏈表中刪除并釋放該結(jié)點的語句組是（）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所指的結(jié)點插入到鏈表尾部,構(gòu)成新的單向鏈表的語句

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. 有如下函數(shù)，其中形參hl和h2分別指向2

10、個不同鏈表的第一個結(jié)點，此函數(shù)的功能是（）。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的最后一個結(jié)點由指針返回D .將鏈表hl拆分成兩個鏈表二、判斷題1. 循環(huán)鏈表不是線性表.（x ）2. 線性表就是順序存儲的表。（X ）3. 線性表只能用順序存儲結(jié)構(gòu)實現(xiàn)。（x ）4. 鏈表中的頭結(jié)

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

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

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

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

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

16、插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用 存儲結(jié)構(gòu)。31. 線性表L = （ a1, a2 ,，an）用數(shù)組存儲。假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動的元素個數(shù)是 。32. 在單鏈表中要在已知結(jié)點 *p之前插入一個新結(jié)點，需找到 ，其時間復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個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需要找到 .其時間復雜度為。鏈表相對于順序表的優(yōu)點有 和操作方便；缺點

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

18、執(zhí)行下列語句：sA .next:=p； sA .prior:= ； pA .prior:=s ； :=s ；36. 設單鏈表的結(jié)點結(jié)構(gòu)為(data,next)， next為指針域，已知指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點,若將結(jié)點y插入結(jié) 點x之后，則需要執(zhí)行以下語句 :；;37. 設有結(jié)點定義如下，且已建立如下圖所示的帶有頭結(jié)點的單向鏈表：struct node int data ;struct node * next ; ;dlU IHEVlt1 生函數(shù)sum的功能是：計算鏈表中各結(jié)點數(shù)據(jù)域之和，作為函數(shù)值返回。請?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指向一個帶有頭結(jié)點的單向鏈表，鏈表中每個結(jié)點包含整型數(shù)據(jù)域 (data )和指針域(next)。以下算法用來查找鏈表所有結(jié)點中數(shù)據(jù)域值最大的結(jié)點的位置，由指針 s傳回調(diào)用程序。請?zhí)羁铡truct 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