第1章 緒論習(xí)題參考答案

1、習(xí)題一參考答案一、概念題1. 試述下列各組概念： 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng) 數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)類(lèi)型、數(shù)據(jù)操作 算法、算法的時(shí)間復(fù)雜度、算法的空間復(fù)雜度參考答案: 略2試述數(shù)據(jù)結(jié)構(gòu)研究的3個(gè)方面的內(nèi)容。參考答案: 數(shù)據(jù)結(jié)構(gòu)研究的3個(gè)方面分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算（操作）。3試述集合、線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)和圖型結(jié)構(gòu)四種常用數(shù)據(jù)結(jié)構(gòu)的特性。參考答案: 集合結(jié)構(gòu)：集合中數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的特性外，數(shù)據(jù)元素之間無(wú)其它關(guān)系，它們之間的關(guān)系是松散性的。 線性結(jié)構(gòu)：線性結(jié)構(gòu)中數(shù)據(jù)元素之間存在“一對(duì)一”的關(guān)系。即若結(jié)構(gòu)非空，則它有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和

2、終端結(jié)點(diǎn)，開(kāi)始結(jié)點(diǎn)沒(méi)有前趨但有一個(gè)后繼，終端結(jié)點(diǎn)沒(méi)有后繼但有一個(gè)前趨，其余結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)和一個(gè)后繼。 樹(shù)形結(jié)構(gòu)：樹(shù)形結(jié)構(gòu)中數(shù)據(jù)元素之間存在“一對(duì)多”的關(guān)系。即若結(jié)構(gòu)非空，則它有一個(gè)稱(chēng)為根的結(jié)點(diǎn)，此結(jié)點(diǎn)無(wú)前驅(qū)結(jié)點(diǎn)，其余結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)，所有結(jié)點(diǎn)都可以有多個(gè)后繼。 圖形結(jié)構(gòu)：圖形結(jié)構(gòu)中數(shù)據(jù)元素之間存在“多對(duì)多”的關(guān)系。即若結(jié)構(gòu)非空，則在這種數(shù)據(jù)結(jié)構(gòu)中任何結(jié)點(diǎn)都可能有多個(gè)前驅(qū)和后繼。4設(shè)有數(shù)據(jù)的邏輯結(jié)構(gòu)的二元組定義形式為B=(D,R)，其中D=a1,a2,an，R=<ai,ai+1>| i=1,2,，n-1，請(qǐng)畫(huà)出此邏輯結(jié)構(gòu)對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的示意圖。參考答案:

3、順序存儲(chǔ)結(jié)構(gòu)示意圖如下： 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖如下：5設(shè)一個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)如圖1.9所示，請(qǐng)寫(xiě)出它的二元組定義形式。圖1.9 第5題的邏輯結(jié)構(gòu)圖參考答案: 它的二元組定義形式為B=（D，R），其中D=k1,k2,k3,k4,k5,k6,k7,k8,k9，R=<k1,k3>,<k1,k8>,<k2,k3><k2,k4>,<k2,k5>,<k3,k9>,<k4,k6>,<k4,k7>,<k5,k6>,<k8,k9>,<k9,k7> 。6設(shè)有函數(shù)f (n)=3n2-n

4、+4，請(qǐng)證明f (n)=O(n2)。證明：因?yàn)榇嬖赾=6，N=1，對(duì)所有的nN ，0 3n2-n+46×n2都是恒成立的，所以由書(shū)P16的定義可得f (n)=O(n2)。7請(qǐng)比較下列函數(shù)的增長(zhǎng)率，并按增長(zhǎng)率遞增的順序排列下列函數(shù)：(1) 2100 (2) (3/2)n (3) (4/3)n (4) nn (5) n2/3 (6) n3/2 (7) n! (8)(9) n (10) log2n (11) 1/log2n (12)log2(log2n) (13)nlog2n (14) nlog2n參考答案: 按增長(zhǎng)率遞增的排列順序是:1/log2n< 2100  

5、;<log2(log2n)<log2n<n1/2 <n2/3 <n <nlog2n <n3/2 <nlog2n<(4/3)n  < (3/2)n  < n! <nn8試確定下列程序段中有標(biāo)記符號(hào)“*”的語(yǔ)句行的語(yǔ)句頻度（其中n為正整數(shù))。 i=1; k=0; while ( i<=n-1) k += 10 * i; /* i+; i=1; k=0;do k +=10 * i; /* i+; while(i<=n-

6、1); i = 1; k = 0;while (i<=n-1) i+ ; k+= 10 * i; /* k=0;for( i=1; i<=n; i+) for (j=1 ; j<=i; j+) k+; /* i=1; j=0;while (i+j<=n) if (i>j ) j+ ; /* else i+ ; x=n; y=0; / n 是不小于1的常數(shù)while (x>=(y+1)*(y+1) y+; /* x=91; y=100;while (y>0 ) if (x>100 ) x -= 10; y- -; /* else x+; a=1;

7、m=1; while(a<n) m+=a; a*=3; /* 參考答案: 指定語(yǔ)句行的語(yǔ)句頻度分別為：（1）n-1 (2) 當(dāng)n1時(shí)語(yǔ)句頻yac 為1，當(dāng)n>1時(shí)語(yǔ)句頻度為n-1(3) n-1(4) n(n+1)/2(5) n(6) 取整(7) 1100(8) log3n二、算法設(shè)計(jì)題1有一個(gè)包括100 個(gè)數(shù)據(jù)元素的數(shù)組，每個(gè)數(shù)據(jù)元素的值都是實(shí)數(shù)，試編寫(xiě)一個(gè)求最大數(shù)據(jù)元素的值及其下標(biāo)的算法，并分析算法的時(shí)間復(fù)雜度。參考答案:void max(double a) double max = a0;/ 初始化最大值為數(shù)組中的第一個(gè)元素 int index = 0; / for (int

8、i = 0; i < a.length; i+) if (max < ai) max = ai;index = i; System.out.println("最大的實(shí)數(shù)為：" + max + "n其在數(shù)組中的下標(biāo)為：" + index); 此算法的時(shí)間復(fù)雜度為O(n) ，其中n為數(shù)組的長(zhǎng)度。2試編寫(xiě)一個(gè)求一元多項(xiàng)式的值Pn(x0)的算法，并確定算法中每一條語(yǔ)句的執(zhí)行次數(shù)和整個(gè)算法的時(shí)間復(fù)雜度。輸入是ai(i=0,1,2,n-1)和x0，輸出為Pn(x0)。參考答案:0 double getPolynomialResult(double a, double x) /a是多項(xiàng)式中系數(shù)數(shù)組1 double result = 0;2 double powX = 1;/ 臨時(shí)變量，用于減少計(jì)算x冪的計(jì)算次數(shù)3 for (int i = 0; i < a.length; i+) 4result +=