数据结构课后习题答案清华大学出版社殷人昆(2)

(1) 用cerr<<及exit (1)语句来终止执行并报告错误；

(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；

(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。

试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。

【解答】

#include "iostream.h"

#define arraySize 100

#define MaxInt 0x7fffffff

int calc ( int T[ ], int n ) {

int i, value = 1;

if ( n != 0 ) {

int edge = MaxInt / n / 2;

for ( i = 1; i < n; i++ ) {

value *= i*2;

if ( value > edge ) return 0;

}

value *= n * 2;

}

T[n] = value;

cout << "A[" << n << "]=" << T[n] << endl;

return 1;

}

void main ( ) {

int A[arraySize];

int i;

for ( i = 0; i < arraySize; i++ )

if ( !calc ( A, i ) ) {

cout << "failed at " << i << " ." << endl;

break;

}

}

1-9 (1) 在下面所给函数的适当地方插入计算count的语句：

void d (ArrayElement x[ ], int n ) {

int i = 1;

do {

x[i] += 2; i +=2;

.

} while (i <= n );

i = 1;

while ( i <= (n/2) ) {

x[i] += x[i+1];i++;

}

}

(2) 将由(1)所得到的程序化简。使得化简后的程序与化简前的程序具有相同的count值。

(3) 程序执行结束时的count值是多少？

(4) 使用执行频度的方法计算这个程序的程序步数，画出程序步数统计表。

【解答】

(1) 在适当的地方插入计算count语句

void d ( ArrayElement x [ ], int n ) {

int i = 1;

count ++;

do {

x[i] += 2; count ++;

i += 2;count ++;

count ++;//针对while语句

} while ( i <= n );

i = 1;

count ++;

while ( i <= ( n / 2 ) ) {

count ++;//针对while语句

x[i] += x[i+1];

count ++;

i ++;

count ++;

}

count ++; //针对最后一次while语句

}

(2) 将由(1)所得到的程序化简。化简后的程序与原来的程序有相同的count值：

void d ( ArrayElement x [ ], int n ) {

int i = 1;

do {

count += 3;i += 2;

} while ( i <= n );

i = 1;

while ( i <= ( n / 2 ) ) {

count += 3;i ++;

}

count += 3;

}

(3) 程序执行结束后的count值为3n + 3。

当n为偶数时，count = 3 * ( n / 2 ) + 3 * ( n / 2 ) + 3 = 3 * n + 3

.

当n为奇数时，count = 3 * ( ( n + 1 ) / 2 ) + 3 * ( ( n – 1 ) / 2 ) + 3 = 3 * n + 3

(4) 使用执行频度的方法计算程序的执行步数，画出程序步数统计表：

1-10 设有3个值大小不同的整数a、b和c，试求

(1)其中值最大的整数；

(2)其中值最小的整数；

(3)其中位于中间值的整数。

【解答】

(1) 求3个整数中的最大整数的函数

【方案1】

int max ( int a, int b, int c ) {

int m = a;

if ( b > m ) m = b;

if ( c > m ) m = c;

return m;

}

【方案2】(此程序可修改循环终止变量扩大到n个整数)

int max ( int a, int b, int c ) {

int data[3] = { a, b, c };

int m = 0;//开始时假定data[0]最大

for ( int i = 1; i < 3; i++ ) //与其他整数逐个比较

if ( data[i] > data[m] ) m = i;//m记录新的最大者

return data[m];

}

(2)求3个整数中的最小整数的函数

可将上面求最大整数的函数稍做修改，“>”改为“<”，可得求最小整数函数。

【方案1】

int min ( int a, int b, int c ) {

int m = a;

if ( b < m ) m = b;

.

if ( c < m ) m = c;

return m;

}

【方案2】(此程序可修改循环终止变量扩大到n个整数)

int max ( int a, int b, int c ) {

int data[3] = { a, b, c };

int m = 0;//开始时假定data[0]最小

for ( int i = 1; i < 3; i++ ) //与其他整数逐个比较

if ( data[i] < data[m] ) m = i;//m记录新的最小者

return data[m];

}

(3)求3个整数中具有中间值的整数

可将上面求最大整数的函数稍做修改，“>”改为“<”，可得求最小整数函数。

【方案1】

int mid ( int a, int b, int c ) {

int m1 = a, m2;

if ( b < m1 ) { m2 = m1;m1 = b; }

else m2 = b;

if ( c < m1 ) { m2 = m1;m1 = c; }

else if ( c < m2 ) { m2 = c; }

return m2;

}

【方案2】(此程序可修改循环终止变量扩大到n个整数寻求次小元素)

int mid ( int a, int b, int c ) {

int data[3] = { a, b, c };

int m1 = 0, m2 = -1; //m1指示最小整数, m2指示次小整数

for ( int i = 1; i < 3; i++ ) //与其他整数逐个比较

if ( data[i] < data[m1] ) { m2 = m1; m1 = i; }//原来最小变为次小, m1指示新的最小

else if ( m2 == -1 || data[i] < data[m2] ) m2 = i;//m2记录新的次小者

return data[m2];

}

第10章索引与散列

10-1 什么是静态索引结构？什么是动态索引结构？它们各有哪些优缺点？

【解答】

静态索引结构指这种索引结构在初始创建，数据装入时就已经定型，而且在整个系统运行期间，树的结构不发生变化，只是数据在更新。动态索引结构是指在整个系统运行期间，树的结构随数据的增删及时调整，以保持最佳的搜索效率。静态索引结构的优点是结构定型，建立方法简单，存取方便；缺点是不利于更新，插入或删除时效率低。动态索引结构的优点是在插入或删除时能够自动调整索引树结构，以保持最佳的搜索效率；缺点是实现算法复杂。

10-2 设有10000个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高搜索效率, 每一个子表的大小应设计为多大?

.

【解答】

每个子表的大小 s = ?n ? = ?10000? = 100 个记录对象。

10-3如果一个磁盘页块大小为1024 (=1K) 字节，存储的每个记录对象需要占用16字节，其中关键码占4字节，其它数据占12字节。所有记录均已按关键码有序地存储在磁盘文件中，每个页块的第1个记录用于存放线性索引。另外在内存中开辟了256K 字节的空间可用于存放线性索引。试问：

(1) 若将线性索引常驻内存，文件中最多可以存放多少个记录？(每个索引项8字节，其中关键码4字节，地址4字节)

(2) 如果使用二级索引，第二级索引占用1024字节（有128个索引项），这时文件中最多可以存放多少个记录？

【解答】

(1) 因为一个磁盘页块大小为1024字节，每个记录对象需要占用16字节，则每个页块可存放1024 / 16 = 64个记录，除第 …… 此处隐藏：2959字，全部文档内容请下载后查看。喜欢就下载吧 ……