數(shù)據(jù)結(jié)構(gòu)第1、2章練習(xí)題講解

1、練習(xí)題1.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的( )以及它們之間的相互關(guān)系。A. 物理結(jié)構(gòu)，邏輯結(jié)構(gòu) B. 理想結(jié)構(gòu)，抽象結(jié)構(gòu)C. 理想結(jié)構(gòu)，物理結(jié)構(gòu) D. 抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)2.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu) D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)3.以下不屬于算法要素的是（ ）。A. 有窮性 B. 可行性 C. 可讀性D. 輸入4. 算法的時(shí)間復(fù)雜度與（ ）有關(guān)。A.問題規(guī)模 B.計(jì)算機(jī)硬件性能 C.編譯程序質(zhì)量 D.程序設(shè)計(jì)語言ACCA5.某算法的時(shí)間復(fù)雜度為O（n2），表明該算法的（ ）A.問題規(guī)模是n2 B.執(zhí)行時(shí)間等于n2 C.執(zhí)行

2、時(shí)間與n2成正比 D.問題規(guī)模與n2成正比1輸入非法數(shù)據(jù)時(shí)，也要能作出相應(yīng)的處理，這種算法要求稱為 （ ） A正確性 B可行性C健壯性 D輸入性6.假設(shè)某算法語句總的執(zhí)行次數(shù)為T(n)=2n+n,那么該算法的時(shí)間復(fù)雜性量級(jí)為（ ）。 A. O(2) B. O(n) C. O(n) D. O(1)7.設(shè)n為正整數(shù)，下面程序段中標(biāo)號(hào)為的語句頻度為 （ n-1 ）。 i = 1;k = 0;while ( i = n-1 )k += 10*i; i+;CCB8. 數(shù)據(jù)結(jié)構(gòu)是指 （ ）。A. 一種數(shù)據(jù)類型B. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C. 一組性質(zhì)相同的數(shù)據(jù)元素的集合D. 相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元

3、素的集合9. 以下算法的時(shí)間復(fù)雜度為 ( ) 。void func(int n)int i=0,s=0;while (s=n)i+;s=s+i;A. O(n)B. O( )C. O(nlog2n)D. O(log2n)DB10. 以下算法的時(shí)間復(fù)雜度為 ( ) 。void fun(int n)int i=1;while (i=n)i=i*3;A. O(n)B. O(n2)C. O(log2n)D. O(log3n)11. 某算法的空間復(fù)雜度為O(1)，則 ( ) 。A.該算法執(zhí)行不需要任何輔助空間B.該算法執(zhí)行所需輔助空間大小與問題規(guī)模n無關(guān)C.該算法執(zhí)行不需要任何空間D.該算法執(zhí)行所需全部空

4、間大小與問題規(guī)模n無關(guān)12. 在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)( )。A. 數(shù)據(jù)的處理方法 B. 數(shù)據(jù)元素的類型C. 數(shù)據(jù)元素之間的關(guān)系 D. 數(shù)據(jù)的存儲(chǔ)方法DBC10. 以下算法的時(shí)間復(fù)雜度為 ( ) 。void fun(int n)int i=1;while (i=n)i=i*3;A. O(n)B. O(n2)C. O(log2n)D. O(log3n)11. 某算法的空間復(fù)雜度為O(1)，則 ( ) 。A.該算法執(zhí)行不需要任何輔助空間B.該算法執(zhí)行所需輔助空間大小與問題規(guī)模n無關(guān)C.該算法執(zhí)行不需要任何空間D.該算法執(zhí)行所需全部空間大小與問題規(guī)模n無關(guān)12. 在存

5、儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)( )。A. 數(shù)據(jù)的處理方法 B. 數(shù)據(jù)元素的類型C. 數(shù)據(jù)元素之間的關(guān)系 D. 數(shù)據(jù)的存儲(chǔ)方法DBC13.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的哪種結(jié)構(gòu) （ ）A.存儲(chǔ) B.物理 C. 邏輯 D. 物理和存儲(chǔ)14.數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu) 、 和 三種類型。（樹形結(jié)構(gòu) 圖狀結(jié)構(gòu)）15.評(píng)估一個(gè)算法的優(yōu)劣，通常從 和空間復(fù)雜度兩個(gè)方面考察。 （時(shí)間復(fù)雜度） C16. 程序段for( i=0; in; i+ ) for( j=0; ji; j+ ) k+;中，語句k+的執(zhí)行次數(shù)為_n*(n-1)/2_。17.在下面的程序段中，對(duì)x的賦值語句

6、的漸進(jìn)時(shí)間復(fù)雜度為O(n2) 。for(k=1;k=n;k+) for(j=1;j=n;j+) x=x+1;18.下面程序段的時(shí)間復(fù)雜度為 O(log2n) 。void fun(int n) int y=1;while (y next=h C. h-next=NULL D.h!=NULL第2章練習(xí)題DADC5.在表頭指針為head且表長(zhǎng)大于1的單向循環(huán)鏈表中，指針p指向表中的某個(gè)結(jié)點(diǎn)，若p-next-next= =head,則( ) A. p指向頭結(jié)點(diǎn) B. *p的直接后繼是尾結(jié)點(diǎn) C. p指向尾結(jié)點(diǎn) D. *p的直接后繼是頭結(jié)點(diǎn)6.如果線性表長(zhǎng)度變化較大，且經(jīng)常進(jìn)行插入刪除操作，則采用（ ）

7、更合適。A. 單鏈表 B. 有序表 C. 無序表 D.順序表7.在順序線性表（a1,a2,a29,a30）中，在a20之前插入一個(gè)新的結(jié)點(diǎn)，需要將( )個(gè)結(jié)點(diǎn)后移。A. 11 B. 20 C. 19 D. 10BAA8.在不帶頭結(jié)點(diǎn)的單鏈表L中的第一個(gè)結(jié)點(diǎn)前插入結(jié)點(diǎn)S，以下正確的是( )。A. S-next=L;L =S; B. L-next=S;S-next=L-next; C. S-next=L-next;L-next=S; D. S-next=L-next;9.在一個(gè)單鏈表中，若結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入結(jié)點(diǎn)s。則執(zhí)行( )。A.s-next=p;p-next=s; B.s-next

8、=p-next;p-next=s;C.s-next=p-next;p=s; D.p-next=s;s-next=p;10.在單鏈表中，刪除*p結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)的操作是( ) A.p-next=p B.p-next-next=p-next C.p-next-next=p D.p-next=p-next-nextABD11順序存儲(chǔ)結(jié)構(gòu)的優(yōu)勢(shì)是 （ ）A利于插入操作 B利于刪除操作C利于順序訪問 D利于隨機(jī)訪問12 在帶有頭結(jié)點(diǎn)的單鏈表L中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行操作（ ）Ap-next=L-next; L-next=p; Bp-next=L; L=p；Cp-next=L; p=

9、L DL=p; p-next=L；13對(duì)線性表，應(yīng)當(dāng)采用鏈表表示的是 （ ）A經(jīng)常需要隨機(jī)地存取元素B經(jīng)常需要進(jìn)行插入和刪除操作C表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D表中元素的個(gè)數(shù)不變DAB14. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址 （ ）A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以15. 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 （ ）A. head=nullB. head-next=null C. head-next=headD. head!=null16. 在一個(gè)單鏈表中，若p結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s結(jié)點(diǎn)，則

10、執(zhí)行（ ）A. s-next=p；p-next=sB. s-next=p-next；p-next=s C. s-next=p-next；p=sD. p-next=s；s-next=pDAB17.鏈表不具備的特點(diǎn)是（ ）A可隨機(jī)訪問任一結(jié)點(diǎn) B插入刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間 D所需空間與其長(zhǎng)度成正比18.在一個(gè)單鏈表中，若p結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s結(jié)點(diǎn)，則執(zhí)行（ ）A. s-next=p；p-next=sB. s-next=p-next；p-next=s C. s-next=p-next；p=sD. p-next=s；s-next=p19. 在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表L中，

11、刪除元素值為x的結(jié)點(diǎn)，算法的時(shí)間復(fù)雜度為 ( ) 。A. O(n)B. O( ) C. O(nlog2n)D. O(n2)AAB20. 在長(zhǎng)度為n的順序表中插入一個(gè)元素，對(duì)應(yīng)算法的時(shí)間復(fù)雜度為 ( )。A.O(1)B.O(log2n) C.O(n) D.O(n2)21. 設(shè)線性表中有n個(gè)元素，以下運(yùn)算中,在單鏈表上實(shí)現(xiàn)要比在順序表上實(shí)現(xiàn)效率更高的是( )。A.刪除指定位置元素的后一個(gè)元素B.在最后一個(gè)元素的后面插入一個(gè)新元素C.順序輸出前k個(gè)元素D.交換第i個(gè)元素和第n-i+1個(gè)元素的值（i=1，2，n）22、順序表和鏈表相比存儲(chǔ)密度較大，這是因?yàn)椋?）。A.順序表的存儲(chǔ)空間是預(yù)先分配的B.順

12、序表不需要增加指針來表示元素之間的邏輯關(guān)系C.鏈表中所有節(jié)點(diǎn)的地址是連續(xù)的D.順序表中所有元素的存儲(chǔ)地址是不連續(xù)的CAB1評(píng)估一個(gè)算法的優(yōu)劣，通常從 和空間復(fù)雜度兩個(gè)方面考察。2在單鏈表中（假設(shè)結(jié)點(diǎn)指針域名稱為next），刪除指針P所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語句是 。3.設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，next為指針域，已知指針p指向單鏈表中data為x的結(jié)點(diǎn)，指針q指向data為y的新結(jié)點(diǎn)，若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語句： q-next=p-next ； p-next=q ；4.p是指向單鏈表L的中間結(jié)點(diǎn)的指針，補(bǔ)充下列刪除p的后繼結(jié)點(diǎn)的程序段。s = p-next;_p

13、-next=s-next;_free( s );5.在一個(gè)長(zhǎng)度為n的順序表的最后插入一個(gè)數(shù)據(jù)元素，其時(shí)間復(fù)雜度為（O（1），在第i個(gè)元素（1in+1）之前插入一個(gè)元素時(shí)，需向后移動(dòng)( ni+1 )個(gè)元素。6.循環(huán)單鏈表LA中，指針P所指結(jié)點(diǎn)為表尾結(jié)點(diǎn)的條件是 P-next=LA 7.以下是雙向鏈表中結(jié)點(diǎn)s（data，prior，next）插入到結(jié)點(diǎn)p之前的插入過程，請(qǐng)補(bǔ)充完整。s-next =（ p ）; （ p-prior-next ） = s;（ s-proir ）= p-proir; ( p-proir ) = s;8. 在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向 ，另一個(gè)指向 。（前驅(qū)結(jié)點(diǎn) 后繼結(jié)點(diǎn)）（ ）1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。（ ）2在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是：P-next= S ; S- next = P-next。（ ）3. 線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。 1. 什么是算法? 它具有哪些特性?算法概念：通俗地講，一個(gè)算法就是一種解