数据结构课后答案清华大学出版社殷人昆.docx

《数据结构课后答案清华大学出版社殷人昆.docx》由会员分享，可在线阅读，更多相关《数据结构课后答案清华大学出版社殷人昆.docx（159页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1-1什么是数据？它与信息是什么关系？【解答】什么是信息？广义地讲，信息就是消息。宇宙三要素(物质、能量、信息)之一。它是 现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。 信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可 共享。什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理， 例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表 等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data) 是信息的载体，是描述客观事物的数、字符、以及所有能输入到计

2、算机中并被计算机程序识 别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。1-2什么是数据结构？有关数据结构的讨论涉及哪三个方面？【解答】数据结构是指数据以及相互之间的关系。记为：数据结构=41。其中，D是某一 数据对象，R是该对象中所有数据成员之间的关系的有限集合。有关数据结构的讨论一般涉及以下三方面的内容：数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构;数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为 存储结构：施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存 储无关的。因此，

3、数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的 应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现(亦称为映像)，它是 依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每 种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等；非线性结构包括树、图等、这两类结构各自的特点是什么？【解答】线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员 和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后

4、继。例如，一维数 组、线性表等就是典型的线性结构非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例 如，树、图或网络等都是典型的非线性结构。14.什么是抽象数据类型？试用C+的类声明定义“复数”的抽象数据类型。要求(1)在复数内部用浮点数定义它的实部和虚部。(2)实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋 给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚 部。(3)定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。(4)定义重载的流函数来输出一个复数。【解答】抽象数据类型通常是指由用户定义

5、，用以表示应用问题的数据模型。抽象数据类型山基 本的数据类型构成，并包括一组相关的服务。在头文件complex.h中定义的复数类#ifndef _complex_h_#define _complex_h_#include class comlex 不带参数的构造函数只置实部的构造函数分别置实部、虚部的构造函数取复数实部取复数虚部修改复数实部修改复数虚部public:complex () Re = Im = 0; complex ( double r ) Re = r; Im = 0; complex ( double r. double i) Re = r; Im = i; double ge

6、tReal () return Re; double getlmag () return Im; void setReal ( double r) Re = r; void setlmag ( double i) ( Im = i;complex& operator = ( complex& ob) Re = ob.Re; Im = ob.Im; 复数赋值重载函数：复数四则运算complex& operator + ( complex& ob );complex& operator - ( complex& ob );complex& operator * ( complex& ob );co

7、mplex& operator / ( complex& ob );friend ostream& operator ( ostreani& os, complex& c ); 友元函数：重载vv private:double Re, Im;复数的实部与虚部)；#endif复数类complex的相关服务的实现放在C+源文件complex.cpp中#include #include #include complex.hcomplex& complex : operator + (complex & ob ) /重载函数：复数加法运算。complex * result = new complex

8、( Re + ob.Re, Im + ob.Im );return result;)complex& complex : operator - ( complex & ob ) 重载函数：复数减法运算complex * result = new complex (Re - ob.Re. Im - ob.Im ); return result;complex& complex : operator * (complex& ob ) 重载函数：复数乘法运算complex * result =new complex (Re * ob.Re - Im * ob.Im, Im * ob.Re + Re

9、* ob.Im ); return *result;complex& complex : operator / ( complex& ) 重载函数：更数除法运算double d = ob.Re * ob.Re + ob.Im * ob.Im;complex * result = new complex ( Re * ob.Re + Im * ob.Im ) / d, (Im * ob. Re - Re * ob.Im )/d );return * result;friend ostream& operator ( ostream& os, complex & ob ) 友元函数：重载vv,将复

10、数ob输出到输出流对象os中。return os ob.Re ( ob.Im = 0.0 ) ?: 一 fabs ( ob.Im ) i”;1-5用归纳法证明:V， n(n + l) i=, nl i=l/iln(n + D(2n + D, n)(3)x.l, n.o【证明】略1-6什么是算法？算法的5个特性是什么？试根据这些特性解释算法与程序的区别。【解答】通常，定义算法为“为解决某一特定任务而规定的一个指令序列一个算法应当具有 以下特性：有输入。一个算法必须有0个或多个输入。它们是算法开始运算前给予算法的量。 这些输入取自于特定的对象的集合。它们可以使用输入语句由外部提供，也可以使用赋值语

11、 句在算法内给定。有输出。一个算法应有一个或多个输出，输出的量是算法计算的结果。确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况，需要执行的 动作都应严格地、清晰地规定。有穷性。一个算法无论在什么情况下都应在执行有穷步后结束。有效性。算法中每一条运算都必须是足够基本的。就是说，它们原则上都能精确地 执行，甚至人们仅用笔和纸做有限次运算就能完成。算法和程序不同，程序可以不满足上述的特性(4)。例如，个操作系统在用户未使用 前一直处于“等待”的循环中，直到出现新的用户事件为止。这样的系统可以无休止地运行, 直到系统停工。此外，算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对

12、象方式搭建 它的框架。1-7设为正整数，分析下列各程序段中加下划线的语句的程序步数。(1) for (int i = 1; i = n; i+)for (intj = 1; j = n; j+) c(ij = 0.0;for (int k = 1; k = n; k+)cfim = cilfil + ailkl*bkfil;)(3) inti=l, j = l;while (i=n & j=n) 土 j=j + i；(2) x = 0; y = 0;for (int i = 1; i = n; i+)for (intj = l；j=i；j+)for (int k = 1; k = j; k+)

13、 x = x + y;(4) int i =1;do for (intj = l;j=n;j+)1 = i + i； while (i i = 2时，i = 3,j=j + i = (2+ 1 ) + 3 = 3 + l2,i = 3时，i= 4,i = i + i = (3 + l+ 2) + 4 = 4+1+2 + 3,i = 4时，i = 5,i = i + i = (4+l+2 + 3) + 5 = 5+l+ 2 + 3 + 4,i = k 时，i = k + 1, j=j + i = (k+l) + (l+2 + 3 + 4+ , +k),0 j = (k + l)+ini=l,(k

14、 + i)+ 业=k2+3k + 3/v 722 i = l 盹 i = l + j = l +她12j=i2i = 2时，i = (i+12)+Zj = (i+12) + U = i + 2(12)+ j = l + 3(.j=l vi = 3 时，i = 1 + 2n(n + l)一般地，i = k时 i = l + kp)100 + n求出满足此不等式的k值，即为语句1 = 1+)的程序步数。解出满足上述不等式的k值，即为语句i = i + 1的程序步数。1-8试编写一个函数计算n!*2n的值，结果存放于数组AarraySize的第n个数组元素中，0 4 n arraySize或者对于某

15、 一个k(04k4n),使得k!*2kmaxlnt时，应按出错处理。可有如下三种不同的出错处理方 式：(1)用cerrv及exit (1)语句来终止执行并报告错误；(2)用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。 试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】#include iostream.h#define arraySize 10()#define Maxlnt Ox7fffffffint calc (int T , int n ) int i, value = 1

16、;if(n!=0)int edge = Maxlnt / n / 2;for (i = 1; i edge ) return 0;1value *= n * 2;)Tn = value;cout MA| n M=M Tn endl;return 1;)void main () int AfarraySize;int i;for (i = 0; i arraySize; i+ )if ( !calc (A, i) cout failed atM i M .M endl;break;1-9(1)在下面所给函数的适当地方插入计算count的语句:void d (ArrayElement x , in

17、t n ) int i = 1;doxi += 2; i +=2;)while (i = n );i = 1；while (i = (n/2) xi+= xi+l; i+;)(2)将由(1)所得到的程序化简。使得化简后的程序与化简前的程序具有相同的count值。(3)程序执行结束时的count值是多少？(4)使用执行频度的方法计算这个程序的程序步数，画出程序步数统计表。【解答】(1)在适当的地方插入计算count语句void d ( ArrayElement x , int n ) int i = 1;count +;do xi += 2; count -H-;i += 2; count +;

18、count +;针对 while 语句 while (i = n );i-1；count +;while (i = ( n / 2 ) count +;针对 while 语句xi +=xi+l;count +;i+；count +;)count +;针对最后一次while语句)(2)将由(1)所得到的程序化简。化简后的程序与原来的程序有相同的count值：void d ( ArrayElement x J, int n ) int i = 1;do count += 3; i += 2; w hile (i = n );i= 1；while (i = ( n / 2 ) count += 3;

19、 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-l )/2) + 3 = 3*n + 3 (4)使用执行频度的方法计算程序的执行步数，画出程序步数统计表：行号程序语句一次执行步数执行频度程序步数1void d (ArrayElement x , int n ) 0I02int i = 1;1113do(0l(n+l)/2j04xi += 2;IL(n+l)/2jl(n+l)/2j5i+

20、= 2;1L(n+l)/2jL(n+l)/2j6 while (i = n );1L(n+l)/2jL(n+l)/2j7i=l；1118while (i m)m = b;if ( c m ) m = c;return tn;【方案2】(此程序可修改循环终止变量扩大到n个整数)int max (int % int b, int c ) int data3 = a, b, c );/开始时假定data最大与其他整数逐个比较/m记录新的最大者int m = 0;for (int i = 1; i datam ) m = i;return datam;(2)求3个整数中的最小整数的函数可将上面求最大整

21、数的函数稍做修改，“”改为“”，可得求最小整数函数。【方案1int min (int % int b, int c ) int m = a;if(bm)m = b;if (c m ) m = c;return m;【方案2(此程序可修改循环终止变量扩大到n个整数)int max (int a, int b, int c ) int data3J = a, b, c );int m = 0;for (int i = 1; i 3; i+ )if ( datai ”改为“V”，可得求最小整数函数。【方案1】int mid (int a, int b, int c ) int ml = a, m2;

22、if ( b ml ) m2 = ml; ml = b;else m2 = b;if ( c m 1 ) m2 = m 1; ml = c;else if ( c m2 ) m2 = c; return m2;【方案2(此程序可修改循环终止变量扩大到n个整数寻求次小元素)int mid (int a, int b, int c ) int data3 = a, b, c );int ml = 0, m2 = T;/ml指示最小整数,m2指示次小整数for(inti= l;i3;i+)与其他整数逐个比较if(data(idata|ml) m2 = ml; ml =i; 原来最小变为次小,ml指示新的最小else if ( m2 = -1 datai |2,解得 a42。又有 a= 2 =空4 2,则 m2 225。2v -a)3m m 310-15若设散列表的大小为m,利用散列函数计算出的散列地址为h = hash(x)。(1)试证明：如果二次探