嚴(yán)飛_軟件技術(shù)基礎(chǔ)沈被娜習(xí)題解答(已修改)
2025-04-07 23:06 本頁面
【正文】 第二章 什么是數(shù)據(jù)結(jié)構(gòu)？它對算法有什么影響？ 數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)對象中各數(shù)據(jù)元素間存在的關(guān)系。 數(shù)據(jù)結(jié)構(gòu)對算法的影響：算法的實現(xiàn)必須借助程序設(shè)計語言中提供的數(shù)據(jù)類型及其運算。一個算法的效率往往與數(shù)據(jù)的表達(dá)形式有關(guān)，因此數(shù)據(jù)結(jié)構(gòu)的選擇對數(shù)據(jù)處理的效率起著至關(guān)重要的作用。它是算法和程序設(shè)計的基本部分，它對程序的質(zhì)量影響很大。 何謂算法？它與程序有何區(qū)別？廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算法”。計算機(jī)算法是通過計算機(jī)能執(zhí)行的算法語言來表達(dá)的。和程序的區(qū)別：一個程序包括兩個方面的內(nèi)容：（1）對數(shù)據(jù)的描述，即數(shù)據(jù)結(jié)構(gòu)。（2）對操作的描述，即算法。所以算法是程序的一個要素。 何謂頻度，時間復(fù)雜度，空間復(fù)雜度？說明其含義。頻度：在某個算法中某個語句被重復(fù)執(zhí)行的次數(shù)就是此語句的頻度。時間復(fù)雜度：是用來估算一個算法的執(zhí)行時間的量，以算法中頻度最大的語句來度量?？臻g復(fù)雜度：指在算法中所需的輔助空間的單元，而不包括問題的原始數(shù)據(jù)占用的空間。 =anxn +an1 xn1+a1x+a0的值Pn(x 0)的算法，要求用乘法次數(shù)最少，并說明算法中主要語句的執(zhí)行次數(shù)及整個算法的時間復(fù)雜度。A=(a0, a1 ……an)mul ＝ 1 // sum=a0for i=1 to nmul ＝ mul * x // xsum = A[i]*mul + sum //求和end(i)進(jìn)行了n次時間復(fù)雜度為：2n←X+1執(zhí)行次數(shù)(1)for i=1 to n for j=1 to ifor k=1 to j x←x+1end(k) end(j)end(i)執(zhí)行次數(shù)：n*n*n (2)i←1while in dox←x+1i←i+1end(while)執(zhí)行次數(shù)：n1(3)for i=1 to nj←1for k=j+1 to nx← x+1end(k)end(i)執(zhí)行次數(shù)：n*（n1） 數(shù)據(jù)的存儲結(jié)構(gòu)主要有哪兩種?它們之間的本質(zhì)區(qū)別是什么？數(shù)據(jù)的存儲結(jié)構(gòu)：向量和鏈表。本質(zhì)區(qū)別：向量是連續(xù)存放的，其存儲空間是靜態(tài)分配的，以存放順序來表達(dá)元素的前后件的關(guān)系。鏈?zhǔn)酱鎯Y(jié)果不需要一組連續(xù)的存儲單元，其數(shù)據(jù)元素可以分散存放在存儲空間中，其元素關(guān)系由指針來指向。(a1, a2, … , an ) 元素按遞增有序排列。用向量作為存儲結(jié)構(gòu)，試編寫算法：刪除表中值在c與d之間(c=d)的元素大于等于c序號4大于d序號11a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15找到第1個大于等于c的元素，序號為s找到第一個大于d的元素，序號為tL[s] ← L[t]L[s+1] ← L[t+1]…L[s+m] ← L[t+m] // s+m = t 1 m = t – s 1 L[s + i ] ← L[t + i ] // i = 0 to ts1 i=1。 // i 從1 循環(huán)到ns = 1。 // 第1個大于等于c的元素序號t = 1。 // 第1個大于d的元素序號for i = 1 to n step 1if s ==1 and L[i]=c // 找到第1個大于等于c的元素 s = i if t == 1 and L[i] d // 找到第1個大于d的元素 t = i 。 end (i)if s != 1 and t !=1 i = s while i t and i + t – s =n L[i] = L [i + t – s ] i++end(while)else return(錯誤 沒有找到 元素在c和d之間)end(if) for j=c to nd+cL[j]L[j+dc]//把j+dc項給jEnd(j)Nnd+c//所有項數(shù)減少Return 線性表A，B中的元素為字符串類型，用向量結(jié)構(gòu)存儲，試編寫算法，判斷B是否為A的子序列（例如A=ENGLISH ，B=LIS ，則B為A的子序列）A[m] B[n]a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15A：b1b2b3b4b5b6B：i=1 檢查A中第1個元素開始的字符串是否與B匹配i=2 檢查A中第2個元素開始的字符串是否與B匹配… …i= m – n + 1 檢查 A中 第(mn+1)個元素開始的字符串是否與B匹配A[m]B[n]if ( mn ) then return errorfor ( i =1。 i= mn+1。 i++) for (j = 1。 j= n 。 j++) if (A[i+j1 ] != B[j ]) break。 end(j) if jn then return( A字符串中第i個字符開始的子串與B匹配 ) end(i)renturn (找不到匹配的子串)設(shè)A，B兩個線性表的元素個數(shù)為m，nIf (m=n)then{return}For i=0 to n1a=A[i]for j=0 to m1if(a=B[j])then{b++}end(j)end(i)if(b=m)then{B 為A的子集}return（a1 ，a2， an）倒置的算法。a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15對L(a1，a2, ... ..., an )如果是奇數(shù)個元素，則1, 15 交換 1, n 交換2，14 交換 2, n1 交換3，13 交換 3，n2 交換 4，12 交換 4，n3 交換5，11 交換 5，n4 交換6，10 交換 6，n5 交換7，9 交換 7，n6 交換8，8 交換 8，n7 交換9，7 交換 9，n8 交換？ 停止?。?！a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15如果是偶數(shù)個元素，則1，14 交換 1, n 交換2，13 交換 2, n1 交換3，12 交換 3，n2 交換4，11 交換 4，n3 交換5，10 交換 5，n4 交換6，9 交換 6，n5 交換7，8 交換 7，n6 交換8，7 交換？ 8，n7 交換？ 停止?。。?！小結(jié)：n個元素倒置的算法是，i = 1while ( ini+1)a[i] 與 a[ni+1] 交換i++end(while) ，并考慮表空的情況。^p = headi = 0While(p!=nil) //表不為空P next(p)//移動到下一個元素i++End(while)Return i //返回數(shù)據(jù)的個數(shù)。標(biāo)簽GETNODE(q)GETNODE(p)qheadFor i=1 to k1qnext(q)End(i)Pnext(q)。next(q)next(p)Ret(p)Return 已知一循環(huán)鏈表中數(shù)值已按遞增有序排列現(xiàn)要插入一個新結(jié)點，并使插入一個新節(jié)點，并使插入后鏈表仍為有序序列GETNODE(p)Data(p)=aWhile(data(p)data(n))nnext(n)End(while) q nnext(p) next(q)preturn 設(shè)在長度大于1 的循環(huán)鏈表中，即無頭結(jié)點，也無頭指正，p為指向鏈表中每個節(jié)點的指針，試編寫算法刪除該節(jié)點的前趨結(jié)點。qNext(p)//找到該節(jié)點的前趨結(jié)點pnext(q)。next(q)next(p)RET(p)Return 試用單鏈表表示兩個多項式：A=4X12 +5X8+6X3+4 ,B=3X12+6X7+2X4+5(1)設(shè)計此兩個多項式的數(shù)據(jù)結(jié)構(gòu)1A0436851241B054
研究報告相關(guān)推薦
鄂ICP備17016276號-1