?? 考研論壇 - 軟件碩士（mse） - [推薦]數據結構（c＋＋）習題解答(頁 1) 簡化版本.htm
字號:
}<BR>}<BR><BR>1-9 (1)
在下面所給函數的適當地方插入計算count的語句：<BR>
void d (ArrayElement x[ ], int n )
{<BR>
int i = 1;<BR>
do {<BR>
x[ i ] += 2; i +=2;<BR>
} while (i <= n );<BR>
i = 1;<BR>
while (
i <= (n/2) ) {<BR>
x[ i ]
+= x[ i+1]; i++;<BR>
}<BR>
}<BR>
(2)
將由(1)所得到的程序化簡。使得化簡后的程序與化簡前的程序具有相同的count值。<BR>
(3) 程序執行結束時的count值是多少？<BR>
(4) 使用執行頻度的方法計算這個程序的程序步數，畫出程序步數統計表。 <BR>【解答】<BR>(1)
在適當的地方插入計算count語句<BR>void d ( ArrayElement x [
], int n ) {<BR>int i = 1;<BR>
count ++;<BR>
do {<BR>
x[ i ] += 2; count ++;<BR>
i += 2; count
++; <BR>
count ++;
//針對while語句<BR>
} while ( i <= n
);<BR>
i = 1;<BR>
count ++;<BR>
while (
i <= ( n / 2 ) ) {<BR>
count ++;
//針對while語句<BR>
x[ i ] += x[ i+1];<BR>count ++;<BR>i ++;<BR>count
++;<BR>
}<BR>
count ++;
//針對最后一次while語句<BR>
}<BR> (2)
將由(1)所得到的程序化簡。化簡后的程序與原來的程序有相同的count值：<BR>
void d ( ArrayElement x [ ], int n )
{<BR>
int i = 1;<BR>do {<BR>
count += 3; i += 2;<BR>
} while ( i
<= n );<BR>
i = 1;<BR>while ( i <= ( n / 2 ) )
{<BR>
count +=
3; i ++; <BR>
}<BR>
count += 3;
<BR> }<BR>
(3) 程序執行結束后的count值為 3n + 3。<BR>
當n為偶數時，count = 3 * ( n / 2
) + 3 * ( n / 2 ) + 3 = 3 * n + 3<BR>當n為奇數時，count = 3 * ( ( n
+ 1 ) / 2 ) + 3 * ( ( n – 1 ) / 2 ) + 3 = 3 * n + 3<BR>(4)
使用執行頻度的方法計算程序的執行步數，畫出程序步數統計表：<BR><BR>行 號
程 序 語 句
一次執行步數 執行頻度
程序步數<BR> 1<BR>
2<BR> 3<BR> 4<BR>
5<BR> 6<BR> 7<BR>
8<BR>
9<BR> 10<BR> 11<BR> 12
void d ( ArrayElement x [
], int n ) {<BR> int i =
1;<BR> do {<BR> x[ i ]
+= 2;<BR> i += 2;<BR> }
while ( i <= n );<BR> i =
1;<BR> while ( i <= ( n / 2 ) ) {<BR>
x[ i ] += x[ i+1];<BR>
i ++;<BR> }<BR>}
0<BR>
1<BR> 0<BR>
1<BR> 1<BR>
1<BR> 1<BR>
1<BR> 1<BR>
1<BR> 0<BR>
0
1<BR>1<BR>(n+1)/2
<BR>(n+1)/2<BR>(n+1)/2<BR>(n+1)/2<BR>1<BR> n/2+1<BR>
n/2<BR> n/2<BR>
n/2<BR> 1
0<BR>1<BR>
0<BR>(n+1)/2<BR>(n+1)/2<BR>(n+1)/2<BR>1<BR> n/2+1<BR>
n/2<BR> n/2<BR> 0<BR>
0<BR>
( n  0 )
3n + 3<BR><BR>1-10
設有3個值大小不同的整數a、b和c，試求<BR>(1) 其中值最大的整數；<BR>(2) 其中值最小的整數；<BR>(3)
其中位于中間值的整數。<BR>【解答】<BR>(1) 求3個整數中的最大整數的函數<BR>
【方案1】<BR>int max ( int a, int b, int c )
{<BR> int m = a;<BR> if ( b > m ) m =
b;<BR> if ( c > m ) m = c;<BR> return
m;<BR>}<BR> 【方案2】(此程序可修改循環終止變量擴大到n個整數)<BR>int max
( int a, int b, int c ) {<BR> int data[3] = { a, b,
c };<BR> int m = 0;
//開始時假定data[0]最大<BR> for ( int i = 1; i < 3; i++
)
//與其他整數逐個比較<BR>
if ( data[ i ] > data[m] ) m = i;
//m記錄新的最大者<BR> return data[m];<BR>}<BR>(2)
求3個整數中的最小整數的函數<BR>可將上面求最大整數的函數稍做修改，“>”改為“<”，可得求最小整數函數。<BR>
【方案1】<BR>int min ( int a, int b, int c )
{<BR> int m = a;<BR> if ( b < m ) m =
b;<BR> if ( c < m ) m = c;<BR> return
m;<BR>}<BR> 【方案2】(此程序可修改循環終止變量擴大到n個整數)<BR>int max
( int a, int b, int c ) {<BR> int data[3] = { a, b,
c };<BR> int m = 0;
//開始時假定data[0]最小<BR> for ( int i = 1; i < 3; i++
)
//與其他整數逐個比較<BR>
if ( data[ i ] < data[m] ) m = i;
//m記錄新的最小者<BR> return data[m];<BR>}<BR>(3)
求3個整數中具有中間值的整數<BR>可將上面求最大整數的函數稍做修改，“>”改為“<”，可得求最小整數函數。<BR>
【方案1】<BR>int mid ( int a, int b, int c )
{<BR> int m1 = a, m2; <BR> if
( b < m1 ) { m2 = m1; m1 = b;
}<BR> else m2 = b;<BR> if ( c < m1 )
{ m2 = m1; m1 = c; }<BR> else if ( c
< m2 ) { m2 = c; }<BR> return m2;<BR>}<BR>
【方案2】(此程序可修改循環終止變量擴大到n個整數尋求次小元素)<BR>int mid ( int a, int
b, int c ) {<BR> int data[3] = { a, b, c
};<BR> int m1 = 0, m2 = -1;
//m1指示最小整數, m2指示次小整數<BR> for (
int i = 1; i < 3; i++ )
//與其他整數逐個比較<BR> if ( data[ i
] < data[m1] ) { m2 = m1; m1 = i; }
//原來最小變為次小, m1指示新的最小<BR>
else if ( m2 == -1 || data[ i ] < data[m2] ) m2 =
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -