下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、第二章 線性表一、選擇題1. 線性表是( )A一個有限序列,可以為空B一個有限序列,不可以為空C一個無限序列,可以為空D一個無限序列,不可以為空2. 一維數(shù)組與線性表的特征是( )。 A前者長度固定,后者長度可變 B兩者長度均固定 C后者長度固定,前者長度可變 D兩者長度均可變 3. 用單鏈表方式存儲的線性表,存儲每個結(jié)點需要兩個域,一個數(shù)據(jù)域,另一個是( ). A當(dāng)前結(jié)點所在地址域B指針域 C空指針域D空閑域 4. 用鏈表表示線性表的優(yōu)點是( )。 A便于隨機存取B便于進(jìn)行插入和刪除操作 C占用的存儲空間較順序表少D元素的物理順序與邏輯順序相同 5. 在具有 n 個結(jié)點的單鏈表中,實現(xiàn)_的操
2、作,其算法的時間復(fù)雜度都是O(n)。 A遍歷鏈表和求鏈表的第i個結(jié)點D刪除地址為P的結(jié)點的后繼結(jié)點B在地址為P的結(jié)點之后插入一個結(jié)點 C刪除開始結(jié)點6. 下面關(guān)于線性表的敘述中,錯誤的是( )。 A線性表采用順序存儲必須占用一片連續(xù)的存儲單元 B線性表采用順序存儲便于進(jìn)行插入和刪除操作 C線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲單元 D線性表采用鏈?zhǔn)酱鎯Ρ阌谶M(jìn)行插入和刪除操作7. 已知單鏈表的每個結(jié)點包括一個指針域next,它指向該結(jié)點的后繼結(jié)點?,F(xiàn)要將指針 q 指向的新結(jié)點插入到指針 p 指向的結(jié)點之后,下面的操作序列中正確的是( )。A . q = p->next; p->ne
3、xt = q->next ;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. 設(shè) al,a2, a3為三個結(jié)點; p , 10 , 20 代表地址,則如下的鏈表存儲結(jié)構(gòu)稱為( )。A鏈表B單鏈表C雙向循環(huán)鏈表D雙向鏈表 9. 單鏈表的存儲密度( )。 A大于 1 B等于1C小于1D不能確定 10. 己知一個順序存儲的線性表,設(shè)每個結(jié)點需占 m 個存儲單元,若第一
4、個結(jié)點的地址al ,則第i個結(jié)點的地址為( )。A. al+(i-1)*mB. al+i*mC. al-i*mD. al+(i+1)*m 11. 在 n 個結(jié)點的順序表中,算法的時間復(fù)雜度是 O(l)的操作是( )。 A訪問第i個結(jié)點(1in)和求第 i 個結(jié)點的直接前驅(qū)(2in) B在第 i 個結(jié)點之后插入一個新結(jié)點(1in-1) C刪除第 i 個結(jié)點( 1in ) D將 n 個結(jié)點從小到大排序 12. 在線性表中( )只有一個直接前驅(qū)和一個直接后繼。 A首元素B中間元素C尾元素D所有元素 13. 對具有 n 個結(jié)點的線性表進(jìn)行查找運算,所需的算法時間復(fù)雜度為( )。 A. 0 (n2)B.
5、 0 (nlog2n)C. O (log2n)D. O (n) 14. 線性表采用順序存儲的缺點是( )。 A存儲密度降低B只能順序訪問 C元素的邏輯順序與物理順序不一致D插入、刪除操作效率低 15. 以下鏈表結(jié)構(gòu)中,從當(dāng)前結(jié)點出發(fā)能夠訪問到任一結(jié)點的是( )。A單向鏈表和雙向鏈表B雙向鏈表和循環(huán)鏈表 C單向鏈表和循環(huán)鏈表D單向鏈表、雙向鏈表和循環(huán)鏈表 16. 線性表是具有 n 個( )的有限序列。 A數(shù)據(jù)項B數(shù)據(jù)元素C表元素D字符 17. 若長度為 n 的線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu),訪問其第 i 個元素的算法時間復(fù)雜度為( )。A. 0 ( l )B. 0 ( n )C. 0 ( n2 )D.
6、0 ( log2n )18. 指針 P 指向循環(huán)鏈表 L 的首元素的條件是( )。 A. PLB. L->nextPC.P->next= =NULLD. P->nextL 19. 指針 P 所指的元素是雙循環(huán)鏈表 L 的尾元素的條件是( )。 A. PLB. P->priorLC. PNULLD. P->nextL 20. 不帶頭結(jié)點的單鏈表L為空的條件是( )A. L!NULLB. LNULLC. L->nextNULLD. L->nextL21. 帶頭結(jié)點的單鏈表L為空的條件是( )A. L!NULLB. LNULLC. L->nextNUL
7、LD. L->nextL22. 兩個指針 P 和 Q ,分別指向單鏈表的兩個元素, P 所指元素是 Q 所指元素前驅(qū)的條件是( )。 A. P->nextQ->nextB. 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. 假定己建立
8、以下動態(tài)鏈表結(jié)構(gòu),且指針 Pl 和 P2 已指向如圖所示的結(jié)點:則以下可以將 P2 所指結(jié)點從鏈表中刪除并釋放該結(jié)點的語句組是( )A. pl->next=p2->next; 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)成新的單向鏈表的語句組是( )。A . s->next = a->next->next ; a->next-&g
9、t;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 = s->next ;27. 有如下函數(shù),其中形參 hl 和 h2 分別指向 2 個不同鏈表的第一個結(jié)點,此函數(shù)的功能是( )。Void fun( struct node * hl , struct node * h2 ) stru
10、ct node * t ; t = hl ;while ( t->next ! '0' ) t = t->next ; t->next = h2 ; A將鏈表 h2 接到鏈表 h1 后B將鏈表 h1 接到鏈表 h2 后 C找到鏈表 hl 的最后一個結(jié)點由指針返回D將鏈表 hl 拆分成兩個鏈表 二、判斷題1. 循環(huán)鏈表不是線性表. ( × )2. 線性表就是順序存儲的表。( × ) 3. 線性表只能用順序存儲結(jié)構(gòu)實現(xiàn)。( × ) 4. 鏈表中的頭結(jié)點僅起到標(biāo)識的作用。( )5. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲。( × )
11、 6. 順序存儲的線性表可以實現(xiàn)隨機存取。( ) 7. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。( )8. 鏈表的每個結(jié)點都恰好包含一個指針域。( × )9. 所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。( × )鏈表中的結(jié)點可含多個指針域,分別存放多個指針。 10. 集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。( × ) 11. 取線性表的第i個元素的時間同i的大小有關(guān). ( × ) 12. 順序存儲結(jié)構(gòu)的主要缺點是不利于插入或刪除操作。( )13. 線性表的特點是每個元素都有一個前驅(qū)和一個后繼。( × ) 14. 對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲
12、結(jié)構(gòu)。( × ) 15. 順序存儲方式的優(yōu)點是存儲密度大,插入、刪除效率高。( × ) 16. 為了很方便的插入和刪除數(shù)據(jù),可以使用雙向鏈表存放數(shù)據(jù)。( × ) 17. 順序存儲方式的優(yōu)點是存儲密度大,且插入、刪除運算效率高。( × ) 18. 順序存儲方式插入和刪除時效率太低,因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩? × ) 19. 線性表采用鏈表存儲時,結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。( ) 20. 線性表鏈?zhǔn)酱鎯Φ奶攸c是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。( ) 21. 在線性表的順序存儲結(jié)構(gòu)中,邏輯上相鄰的兩個元素在物理位置上并不一
13、定相鄰。( × ) 22. 在線性表的順序結(jié)構(gòu)中,插入和刪除元素時,移動元素的個數(shù)與該元素的位置有關(guān)。( × ) 23. 在單鏈表中,要取得某個元素,只要知道該元素的指針即可,因此單鏈表是隨機存取的存儲結(jié)構(gòu)。( × ) 24. 鏈表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時,在鏈表中比在順序存儲結(jié)構(gòu)中效率高。 ( ) 25. 在單鏈表中,任何兩個元素的存儲位置之間都有固定的聯(lián)系,所以可以從頭結(jié)點開始查找任何一個元素。( )26. 線性表中的元素可以是各種各樣的,但同一線性表中的數(shù)據(jù)元素具有相同的特性,因此屬于同一數(shù)據(jù)對象。( )三、填空題1. 順序表中邏輯上
14、相鄰的元素在物理位置上相鄰。2. 在鏈表中邏輯上相鄰的元素的物理位置相鄰。3. 帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是:。4. 在單鏈表p結(jié)點之后插入s結(jié)點的操作是:。5.6. 順序表相對于鏈表的優(yōu)點有和。7. 在雙鏈表中要刪除已知結(jié)點*p ,其時間復(fù)雜度為。8. 在順序表中訪問任意一個結(jié)點的時間復(fù)雜度均為。9. 鏈接存儲的特點是利用來表示數(shù)據(jù)元素之間的邏輯關(guān)系。10. 帶頭結(jié)點的雙循環(huán)鏈表L中只有一個元素結(jié)點的條件是:11. 在單鏈表L中,指針p所指結(jié)點有后繼結(jié)點的條件是:12.13. 在單鏈表中除首結(jié)點外,任意結(jié)點的存儲位置都由結(jié)點中的指針指示。14. 已知指針p指向單鏈表L中的某結(jié)點,則刪
15、除其后繼結(jié)點的語句是:15.16. 在 n 個結(jié)點的單鏈表中要刪除已知結(jié)點*p ,需要找到.其時間復(fù)雜度為。17. 鏈表相對于順序表的優(yōu)點有和操作方便;缺點是存儲密度。18. 建立單鏈表的算法時間復(fù)雜度 ;建立有序單鏈表的算法時間復(fù)雜度 。19. 在單鏈表中設(shè)置頭結(jié)點的作用是。20. 對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共個,單鏈表為個。21. 在一個長度為n的順序表中第i個元素(1<=i<=n)之前插入一個元素時,需向后移動個元素。22. 在循環(huán)鏈表中,可根據(jù)一個結(jié)點的地址訪問整個鏈表,而單鏈表中需知道才能訪問整個鏈表。23. 順序存儲結(jié)構(gòu)是通過表示元素之間的關(guān)
16、系的;鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過表示元素之間的關(guān)系的。24. 有一單鏈表結(jié)構(gòu)如下,若要刪除值為 c 的結(jié)點,應(yīng)做的操作是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. 當(dāng)
17、線性表的元素總數(shù)基本穩(wěn)定,且很少進(jìn)行插入和刪除操作,但要求以最快的速度存取線性表中的元素時,應(yīng)采用存儲結(jié)構(gòu)。31. 線性表 L = ( a1, a2 , ,an)用數(shù)組存儲。假定刪除表中任一元素的概率相同,則刪除一個元素平均需要移動的元素個數(shù)是 。32. 在單鏈表中要在已知結(jié)點*p 之前插入一個新結(jié)點,需找到,其時間復(fù)雜度為;而在雙鏈表中,完成同樣操作時其時間復(fù)雜度為。33. 對于一個具有n個結(jié)點的單鏈表,在已知的結(jié)點*p后插入一個新結(jié)點的時間復(fù)雜度為,在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為。34. 根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù),將線性鏈表分成和;而又根據(jù)指針的
18、連接方式,鏈表又可分成和。35. 在雙向鏈表結(jié)構(gòu)中,若要求在p 指針?biāo)傅慕Y(jié)點之前插入指針為s 所指的結(jié)點,則需執(zhí)行下列語句:s .next:=p; s .prior:= ;p .prior:=s;:=s;36. 設(shè)單鏈表的結(jié)點結(jié)構(gòu)為(data,next),next為指針域,已知指針px指向單鏈表中data為x的結(jié)點,指針py指向data為y的新結(jié)點 , 若將結(jié)點y插入結(jié)點x之后,則需要執(zhí)行以下語句: ; ;37. 設(shè)有結(jié)點定義如下,且已建立如下圖所示的帶有頭結(jié)點的單向鏈表: struct node int data ; struct node * next ; ;函數(shù) sum 的功能是:計算
19、鏈表中各結(jié)點數(shù)據(jù)域之和,作為函數(shù)值返回。請?zhí)羁铡?int sum (struct node * head ) int s = 0 ; struct node * p ; p = head->next ; 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 指向一個帶有頭結(jié)點的單向鏈表,鏈表中每個結(jié)點包含整型數(shù)據(jù)域( data ) 和指針域( next )。以下算法用來查找鏈表所有結(jié)點中數(shù)據(jù)域值最大的結(jié)點的位置,由指針 s 傳回調(diào)用程序。請?zhí)羁?。struct link char data ; struct link *next;main ( )struct link * head , * q ; findmax ( head , & q ) ;printf ( " max = % d n " , q->data ) ; findmax ( st
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二手車交易協(xié)議個人
- 勞動合同解除協(xié)議書大全七篇
- 頸動脈斑塊病因介紹
- 公司借款的協(xié)議書范本10篇
- 單位股東合作的協(xié)議書
- 藥物中毒性周圍神經(jīng)病病因介紹
- 2023-2024學(xué)年天津市五區(qū)縣重點校聯(lián)考高三(上)期末語文試卷
- 2023年天津市部分區(qū)高考語文二模試卷
- 江蘇省鹽城市建湖縣漢開書院學(xué)校2023-2024學(xué)年七年級上學(xué)期第二次月考道德與法治試題(解析版)-A4
- 食品工廠機械與設(shè)備模擬習(xí)題與參考答案
- 初一《皇帝的新裝》課本劇劇本
- 知識創(chuàng)業(yè)思維與方法智慧樹知到答案2024年湖南師范大學(xué)
- 焊錫作業(yè)標(biāo)準(zhǔn)
- 深圳包裝木箱生產(chǎn)工藝的流程
- 生活中的數(shù)學(xué)(課堂PPT)
- 醫(yī)療環(huán)境表面清潔與消毒PPT課件
- 年產(chǎn)20萬噸過磷酸鈣生產(chǎn)工藝設(shè)計
- 專業(yè)合作社盈余及盈余分配表
- 日處理300噸鮮乳的全脂乳粉的車間工藝設(shè)計
- 新概念英語第一冊Lesson11-12-
- 良好農(nóng)業(yè)規(guī)范認(rèn)證實施規(guī)則(試行)
評論
0/150
提交評論