📄 考研论坛 - 软件硕士（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 + -