嚴飛軟件技術基礎沈被娜習題解答

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

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

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

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

5、1xa0的值的值Pn(x0)的算法，要的算法，要求用乘法次數(shù)最少，并說明算法中主要語句的執(zhí)行次數(shù)及整個算法的時間復雜求用乘法次數(shù)最少，并說明算法中主要語句的執(zhí)行次數(shù)及整個算法的時間復雜度。度。A=(a0a1……an)mul＝1sum=a0fi=1tonmul＝mulxxsum=A[i]mulsum求和求和end(i)進行了進行了n次時間復雜度為：時間復雜度為：2n2.5計算下列各片段程序中計算下列各片段程序中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)元素按遞增有序排列。用向量作為存儲結構，元素按遞增有序排列。用向量作為存儲結構，試編寫算法：刪除表中值在試編寫算法：刪除表中值在c與d之間之間(c=c找到第找到第1個大于等于個大于等于c的元素的元素s=iift==1L[i]d找到第找到第1個大于個大于d的元素的元素t=iend(