計(jì)算機(jī)軟件技術(shù)基礎(chǔ)習(xí)題一解答(已修改)
2025-04-06 07:57 本頁面
【正文】 線性結(jié)構(gòu) 習(xí)題解答習(xí)題解答, 分析下列各程序段中加下劃線的語句的執(zhí)行次數(shù)。(1) for (int i = 1。 i = n。 i++) for (int j = 1。 j = n。 j++) { c[i][j] = 。 for (int k = 1。 k = n。 k++) c[i][j] = c[i][j] + a[i][k] * b[k][j]。} (2) x = 0。 y = 0。 for (int i = 1。 i = n。 i++) for (int j = 1。 j = i。 j++) for (int k = 1。 k = j。 k++) x = x + y。(3) int i = 1, j = 1。 while (i=n amp。amp。 j=n) { i = i + 1。 j = j + i。 } (4)* int i =1。 do{ for (int j = 1。 j = n。 j++) i = i + j。 }while(i100 + n)?！窘獯稹?(1) (2) (3)i = 1時，i = 2，j = j + i = 1 + 2 = 2 + 1，i = 2時，i = 3，j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2，i = 3時，i = 4，j = j + i = ( 3 + 1 + 2 ) + 4 = 4 + 1 + 2 + 3，i = 4時，i = 5，j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4，……i = k時，i = k + 1，j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4 + … + k )，解出滿足上述不等式的k值，即為語句i = i + 1的程序步數(shù)。 (4) for語句每執(zhí)行一次，語句i=i+j將執(zhí)行n次，而i的值會增加因此，當(dāng)for語句執(zhí)行k次后，i的值將變?yōu)楣首罱Kfor語句的執(zhí)行次數(shù)k為滿足的最小整數(shù)k，語句i = i + j的程序步數(shù)為n*k。!*2n的值，結(jié)果存放于數(shù)組A[arraySize]的第n個數(shù)組元素中，0 163。 n 163。 arraySize。若設(shè)計(jì)算機(jī)中允許的整數(shù)的最大值為maxInt，則當(dāng)narraySize或者對于某一個k (0 163。 k 163。 n)，使得k!*2k maxInt時，應(yīng)按出錯處理。可有如下三種不同的出錯處理方式： (1) 用printf顯示錯誤信息及exit(1)語句來終止執(zhí)行并報(bào)告錯誤； (2) 用返回整數(shù)函數(shù)值0, 1來實(shí)現(xiàn)算法，以區(qū)別是正常返回還是錯誤返回； (3) 在函數(shù)的參數(shù)表設(shè)置一個引用型的整型變量來區(qū)別是正常返回還是某種錯誤返回。 試討論這三種方法各自的優(yōu)缺點(diǎn)，并以你認(rèn)為是最好的方式實(shí)現(xiàn)它。【解答】include
const int arraySize = 100。const int MaxInt = 0x7fffffff。
int calc( int T[ ], int n ) {
int i, value = 1。T[0]=1。
if ( n != 0 ) { int edge = MaxInt / n / 2。 for ( i = 1。 i n。 i++ ) { value *= i*2。T[i] = value。 if ( value edge ) return 0。 } value *= n * 2。 } T[n] = value。 printf(A[ %d ]= %d\n”,n,T[n])。 return 1。}void main ( ) {
int A[arraySize]。 int i。 for ( i = 0。 i arraySize。 i++ ) if ( !calc ( A, i ) ) { printf(failed at %d .\n, i )。 break。 }}/*，表元素我們使用整型數(shù)據(jù)數(shù)據(jù)元素從data[0]處開始存儲*/typedef struct /*注意typedef的使用*/{ int data[MAXSIZE]。 /*數(shù)據(jù)域*/ int length。 /*表長*/}listtype。 (a0, a1, …, an2, an1) 存放在一個一維數(shù)組A[arraySize]中的前n個數(shù)組元素位置。請編寫一個函數(shù)將這個線性表原地逆置，即將數(shù)組的前n個原址內(nèi)容置換為 (an1, an2, …, a1, a0)。最后分析此算法的時間復(fù)雜度及空間復(fù)雜度。【解答】 void inverse (listtype * A) { int tmp。 int n= Alength。 for( int i = 0。 i = ( n1 ) / 2。 i++ ){ tmp = Adata[i]。 Adata[i] = Adata[ni1]。 Adata[ni1] = tmp。 } }時間復(fù)雜度：需進(jìn)行n/2次循環(huán)，因此時間復(fù)雜度為O(n)；空間復(fù)雜度：使用一個整形輔助存儲單元tmp，因此空間復(fù)雜度為O(1)。設(shè)在等概率情形下, 對有127個元素的順序表進(jìn)行插入, 平均需要移動多少個元素? 刪除一個元素, 又平均需要移動多少個元素?【解答】 若設(shè)順序表中已有n個元素。又設(shè)插入或刪除表中各個元素的概率相等，則在插入時因有n+1個插入位置(可以在表中最后一個表項(xiàng)后面追加)，每個元素位置插入的概率為1/(n+1)，但在刪除時只能在已有n個表項(xiàng)范圍內(nèi)刪除，所以每個元素位置刪除的概率為1/n。插入時平均移動元素個數(shù)AMN(Averagy Moving Number )為 刪除時平均移動元素個數(shù)AMN為 ，實(shí)現(xiàn)以下的函數(shù)。并分析你所編制的函數(shù)的時間復(fù)雜度，并分析(2)與(3)的時間復(fù)雜度出現(xiàn)差異的原因。 (1) 從順序表中刪除具有給定值x的所有元素。 (2) 從順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。 (3) 從有序順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。 (4) 將兩個有序順序表la,lb合并成一個新的有序順序表lc。 (5) 從順序表中刪除所有其值重復(fù)的元素，使表中所有元素的值均不相同。【解答】 (1) 從順序表中刪除具有給定值x的所有元素。void DelValue(listtype * L, int x ){int i = 0, j。 while ( i Llength ) /*循環(huán), 尋找具有值x的元素并刪除它*/if (Ldata[i] == x ) { /*刪除具有值x的元素, 后續(xù)元素前移*/for (j = i。j Llength1。 j++ ) Ldata[j] = Ldata[j+1]。Llength。 /*表長減1*/} else i++。} (2) 實(shí)現(xiàn)刪除其值在給定值s與t之間（要求s小于t）的所有元素的函數(shù)如下：void DelValue_s_to_t (listtype *L,int s, int t){ int i,j。if ( Llength == 0 || s = t ) { printf(“List is empty or
公司管理相關(guān)推薦
鄂ICP備17016276號-1