《數(shù)據(jù)結(jié)構(gòu)》呂云翔編著第1章緒論習(xí)題解答

1、數(shù)據(jù)結(jié)構(gòu)第一章緒論習(xí)題一、【單選題】1. （A）是數(shù)據(jù)的基本單位。A、數(shù)據(jù)元素B、數(shù)據(jù)對(duì)象C、數(shù)據(jù)項(xiàng)D、數(shù)據(jù)結(jié)構(gòu)2. （C）是數(shù)據(jù)的不可分割的最小單位。A、數(shù)據(jù)元素B、數(shù)據(jù)對(duì)象C、數(shù)據(jù)項(xiàng)D、數(shù)據(jù)結(jié)構(gòu)3. 若采用非順序映象，則數(shù)據(jù)元素在內(nèi)存中占用的存儲(chǔ)空間（C）。A、一定連續(xù)B、一定不連續(xù)C、可連續(xù)可不連續(xù)4. 若采用順序映象，則數(shù)據(jù)元素在內(nèi)存中占用的存儲(chǔ)空間（A）。A、一定連續(xù)B、一定不連續(xù)C、可連續(xù)可不連續(xù)5. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C）A、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)6. 在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素間存在（B）的關(guān)

2、系。A、一對(duì)一B、一對(duì)多C、多對(duì)多D、除同屬一個(gè)集合外別無(wú)關(guān)系7. 下列說(shuō)法中錯(cuò)誤的是（B）。A、數(shù)據(jù)對(duì)象是數(shù)據(jù)的子集B、數(shù)據(jù)元素間關(guān)系在計(jì)算機(jī)中的映象即為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C、非順序映象的特點(diǎn)是借助指示元素存儲(chǔ)地址的指針來(lái)表示數(shù)據(jù)元素間邏輯關(guān)系D、抽象數(shù)據(jù)類(lèi)型指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作8. 計(jì)算機(jī)算法指的是（C）。A、計(jì)算方法B、排序方法C、解決問(wèn)題的有限運(yùn)算序列D、調(diào)度方法9. 下列不屬算法特性的是（D）。A、有窮性B、確定性C、零或多個(gè)輸入D、健壯性10. 算法分析的目的是（C）。A、找出數(shù)據(jù)結(jié)構(gòu)的合理性B、研究算法中的輸入和輸出的關(guān)系C、分析算法的效率以求改進(jìn)D、分析算法的易

3、讀性和文檔性11算法分析的兩個(gè)主要方面是（A）。A、空間復(fù)雜性和時(shí)間復(fù)雜性B、正確性和簡(jiǎn)明性C、可讀性和文檔性D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性12. 算法的計(jì)算量的大小稱(chēng)為算法的（A）。A、效率B、復(fù)雜性C、現(xiàn)實(shí)性D、難度13. 在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（C）。for（i=1;i<=n;+i）for（j=1;j<=n;+j）x=x+1;A、2nB>nC、n2D、log2n14設(shè)n為正整數(shù)，則如下程序段中最后一行的語(yǔ)句頻度在最壞情況下是（D）。for（i=n-1;i>=1;-i）for（j=1;j<=i;+j）if（Aj>Aj+1）Aj-Aj+1;A

4、、nB、n（n-1）/2C、n（n+1）/2D、n2、填空題1. 數(shù)據(jù)邏輯結(jié)構(gòu)包括（集合）、（線(xiàn)性結(jié)構(gòu)）、（樹(shù)形結(jié)構(gòu)）、（圖型結(jié)構(gòu)）四種類(lèi)型，樹(shù)型和圖型結(jié)構(gòu)合稱(chēng)（非線(xiàn)性結(jié)構(gòu)）。2. 對(duì)于給定的n個(gè)元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有（集合）、（線(xiàn)性結(jié)構(gòu)）、（樹(shù)形結(jié)構(gòu)）和（圖型結(jié)構(gòu)）四種。3.算法的五個(gè)重要特性是（有窮性）、（確定性）、（可行性）、（輸入）、（輸出）。4. 評(píng)價(jià)算法的性能從利用計(jì)算機(jī)資源角度看主要從（時(shí)間復(fù)雜度和空間復(fù)雜度）方面進(jìn)行分析。5. 線(xiàn)性結(jié)構(gòu)中元素之間存在（一對(duì)一）關(guān)系，樹(shù)型結(jié)構(gòu)中元素之間存在（一對(duì)多）關(guān)系，圖型結(jié)構(gòu)中元素之間存在（多對(duì)多）關(guān)系。6. 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)

5、據(jù)元素之間的（邏輯關(guān)系）。7. 在線(xiàn)性結(jié)構(gòu)中，開(kāi)始結(jié)點(diǎn)（沒(méi)有）直接前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有（一）個(gè)直接前驅(qū)結(jié)點(diǎn)。8. 在樹(shù)形結(jié)構(gòu)中，根結(jié)點(diǎn)只有（一個(gè)），根結(jié)點(diǎn)無(wú)前驅(qū)，其余每個(gè)結(jié)點(diǎn)有且只有（一個(gè)）直接前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有（后繼）結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以（任意個(gè)）。9. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)可以有（任意個(gè)）。10. 存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的（物理）實(shí)現(xiàn)。11. 一個(gè)算法的時(shí)空性能是指該算法的（時(shí)間復(fù)雜度）和（空間復(fù)雜度）。12. 在一般情況下，一個(gè)算法的時(shí)間復(fù)雜性是（問(wèn)題規(guī)模）的函數(shù)。三、算法設(shè)計(jì)題1.判斷n是否為一個(gè)素?cái)?shù)，若是則返回邏輯值true,否則返回邏輯值

6、false,并計(jì)算算法的時(shí)間復(fù)雜度。Publicbooleanprime（intm）booleanflag=true;if（m=1）flag=false;for（inti=2;i<=m-1;i+）if（m%i=0）flag=false;break;returnflag;該算法的時(shí)間復(fù)雜度為O2）。2.計(jì)算£i!的值，并計(jì)算算法的時(shí)間復(fù)雜度。i=1方法1：時(shí)間復(fù)雜度為O(nlogn)。publicclassTest3publicstaticvoidmain(Stringargs)intsum=0,fact,n,i，j;for(j=1;j<=n;j+)fact=1;for(i

7、=1;i<=j;i+)fact*=i;sum+=fact;System.out.println("sum="+sum);方法2：時(shí)間復(fù)雜度為O(n)。publicclassTest3publicstaticvoidmain(Stringargs)intsum=0,fact=1,n;for(n=1;n<=10;n+)fact*=n;sum+=fact;System.out.println("sum="+sum);4. 求出滿(mǎn)足不等式l+2+3+.+i三n的最小i值，并計(jì)算算法的時(shí)間復(fù)雜度。publicstaticvoidmax()inti=1;intsum=0;intn=5050;for(i=1;sum<=n;i+)sum+=i;i-;System.out.println(i+"");時(shí)間復(fù)雜度為0(*匸)。5. 打印出一個(gè)具有n行的乘法表，第i行(lWiWn)中有n-i+1個(gè)乘法項(xiàng)，每個(gè)乘法項(xiàng)為i與j(iWjWn)的乘積，并計(jì)算算法的時(shí)間復(fù)雜度。publicstaticvoidmain(Stringargs)/TODOAuto-generatedmethodstubintn=9;for(inti=1;i<=n;i