嚴(yán)飛軟件技術(shù)基礎(chǔ)沈被娜習(xí)題解答

1、第二章第二章2.1什么是數(shù)據(jù)結(jié)構(gòu)？它對算法有什么影響？什么是數(shù)據(jù)結(jié)構(gòu)？它對算法有什么影響？數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)對象中各數(shù)據(jù)元素間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)對象中各數(shù)據(jù)元素間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)對算法的影響：算法的實(shí)現(xiàn)必須借助程序設(shè)計(jì)語言中提供的數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)對算法的影響：算法的實(shí)現(xiàn)必須借助程序設(shè)計(jì)語言中提供的數(shù)據(jù)類型及其運(yùn)算。一個算法的效率往往與數(shù)據(jù)的表達(dá)形式有關(guān)，因此數(shù)據(jù)結(jié)類型及其運(yùn)算。一個算法的效率往往與數(shù)據(jù)的表達(dá)形式有關(guān)，因此

2、數(shù)據(jù)結(jié)構(gòu)的選擇對數(shù)據(jù)處理的效率起著至關(guān)重要的作用。它是算法和程序設(shè)計(jì)的構(gòu)的選擇對數(shù)據(jù)處理的效率起著至關(guān)重要的作用。它是算法和程序設(shè)計(jì)的基本部分，它對程序的質(zhì)量影響很大。基本部分，它對程序的質(zhì)量影響很大。2.2何謂算法？它與程序有何區(qū)別？何謂算法？它與程序有何區(qū)別？廣義地說，為解決一個問題而采取的方法和步驟，就稱為廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算法算法”。計(jì)算機(jī)。計(jì)算機(jī)算法是通過計(jì)算機(jī)能執(zhí)行的算法語言來表達(dá)的。算法是

3、通過計(jì)算機(jī)能執(zhí)行的算法語言來表達(dá)的。和程序的區(qū)別：一個程序包括兩個方面的內(nèi)容：和程序的區(qū)別：一個程序包括兩個方面的內(nèi)容：（1）對數(shù)據(jù)的描述，即數(shù)據(jù)結(jié)構(gòu)。）對數(shù)據(jù)的描述，即數(shù)據(jù)結(jié)構(gòu)。（2）對操作的描述，即算法。）對操作的描述，即算法。所以算法是程序的一個要素。所以算法是程序的一個要素。2.3何謂頻度，時間復(fù)雜度，空間復(fù)雜度？說明其含義。何謂頻度，時間復(fù)雜度，空間復(fù)雜度？說明其含義。頻度：在某個算法中某個語句被重復(fù)執(zhí)行的次數(shù)就是此語句的頻度

4、。頻度：在某個算法中某個語句被重復(fù)執(zhí)行的次數(shù)就是此語句的頻度。時間復(fù)雜度：是用來估算一個算法的執(zhí)行時間的量，以算法中頻度最大的時間復(fù)雜度：是用來估算一個算法的執(zhí)行時間的量，以算法中頻度最大的語句來度量。語句來度量?？臻g復(fù)雜度：指在算法中所需的輔助空間的單元，而不包括問題的原始數(shù)空間復(fù)雜度：指在算法中所需的輔助空間的單元，而不包括問題的原始數(shù)據(jù)占用的空間。據(jù)占用的空間。2.4試編寫一個求多項(xiàng)式試編寫一個求多項(xiàng)式Pn=anxnan1xn1a

5、1xa0的值的值Pn(x0)的算法，要的算法，要求用乘法次數(shù)最少，并說明算法中主要語句的執(zhí)行次數(shù)及整個算法的時間復(fù)雜求用乘法次數(shù)最少，并說明算法中主要語句的執(zhí)行次數(shù)及整個算法的時間復(fù)雜度。度。A=(a0a1……an)mul＝1sum=a0fi=1tonmul＝mulxxsum=A[i]mulsum求和求和end(i)進(jìn)行了進(jìn)行了n次時間復(fù)雜度為：時間復(fù)雜度為：2n2.5計(jì)算下列各片段程序中計(jì)算下列各片段程序中X←X1執(zhí)行次數(shù)執(zhí)行次數(shù)(1

6、)fi=1tonfj=1toifk=1tojx←x1end(k)end(j)end(i)執(zhí)行次數(shù)：執(zhí)行次數(shù)：nnn2.8已知線性表已知線性表L(a1a2…an)元素按遞增有序排列。用向量作為存儲結(jié)構(gòu)，元素按遞增有序排列。用向量作為存儲結(jié)構(gòu)，試編寫算法：刪除表中值在試編寫算法：刪除表中值在c與d之間之間(c=c找到第找到第1個大于等于個大于等于c的元素的元素s=iift==1L[i]d找到第找到第1個大于個大于d的元素的元素t=iend(