数据结构题集答案-0001.pdf

《数据结构题集答案-0001.pdf》由会员分享，可在线阅读，更多相关《数据结构题集答案-0001.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构存储结构是数据结构在电脑中的表示。数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。1.21.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解：解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直

2、接提供应编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。1.31.3 设有数据结构设有数据结构(D,R)(D,R)，其中，其中D d1,d2,d3,d4，R r，r d1,d2,d2,d3,d3,d4试按图论中图的画法惯例画出其逻辑结构图。试按图论中图的画法惯例画出其逻辑结构图。解：解：1.41.4 试仿照三元组的抽象数据类型分别写出抽象数据类型

3、复数和有理数的定义有理数是其分子、分母均试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义有理数是其分子、分母均为自然数且分母不为零的分数为自然数且分母不为零的分数 。解：解：ADT ComplexADT RationalNumber数据对象：D=r,i|r,i 为实数数据关系：R=基本操作：InitComplex(&C,re,im)操作结果：构造一个复数 C，其实部和虚部分别为 re 和 imDestroyCmoplex(&C)操作结果：销毁复数 CGet(C,k,&e)操作结果：用 e 返回复数 C 的第 k 元的值操作结果：改变复数 C 的第 k 元的值为 e操作结果：如果

4、复数 C 的两个元素按升序排列，则返回 1，否则返回 0操作结果：如果复数 C 的两个元素按降序排列，则返回 1，否则返回 0操作结果：用 e 返回复数 C 的两个元素中值较大的一个操作结果：用 e 返回复数 C 的两个元素中值较小的一个Put(&C,k,e)IsAscending(C)IsDescending(C)Max(C,&e)Min(C,&e)ADT Complex数据对象：D=s,m|s,m 为自然数，且 m 不为 0数据关系：R=基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数 R，其分子和分母分别为 s 和 mDestroyRationalN

5、umber(&R)操作结果：销毁有理数 RGet(R,k,&e)操作结果：用 e 返回有理数 R 的第 k 元的值操作结果：改变有理数 R 的第 k 元的值为 e操作结果：假设有理数 R 的两个元素按升序排列，则返回 1，否则返回 0操作结果：假设有理数 R 的两个元素按降序排列，则返回 1，否则返回 0操作结果：用 e 返回有理数 R 的两个元素中值较大的一个操作结果：用 e 返回有理数 R 的两个元素中值较小的一个Put(&R,k,e)IsAscending(R)IsDescending(R)Max(R,&e)Min(R,&e)ADT RationalNumber(1) product=1

6、; i=1;(1) product=1; i=1; while(i=n) while(i=n) product *= i; product *= i; i+; i+; (2) i=0;(2) i=0; do do i+; i+; while(i!=n) & (ai!=x); while(i!=n) & (ai!=x);(3) switch (3) switch case xy: z=y-x; break; case xy: z=y-x; break; case x=y: z=abs(x*y); break; case x=y: z=abs(x*y); break; default: z=(x-

7、y)/abs(x)*abs(y); default: z=(x-y)/abs(x)*abs(y); 1.51.5 试画出与以下程序段等价的框图。试画出与以下程序段等价的框图。1.61.6 在程序设计中，常用以下三种不同的出错处理方式：在程序设计中，常用以下三种不同的出错处理方式：(1)(1) 用用 exitexit 语句终止执行并报告错误；语句终止执行并报告错误；(2)(2) 以函数的返回值区别正确返回或错误返回；以函数的返回值区别正确返回或错误返回；(3)(3) 设置一个整型变量的函数参数以区别正确返回或某种错误返回。设置一个整型变量的函数参数以区别正确返回或某种错误返回。试讨论这三种方法各

8、自的优缺点。试讨论这三种方法各自的优缺点。解：解：(1)exit 常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。 (2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。 (3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。1.71.7 在程序设计中，可采用以下三种方法实现输出和输入：在程序设计中，可采用以下三种方法实现输出和输入：(1)(1) 通过通过 scanfscanf 和和 printfprintf 语句；语句；(2)(2) 通过函数的参数显式传递；通过函数的参数显式传递；(3)(3) 通过全局变量隐式传递。通过全局变量隐式传递。试

9、讨论这三种方法的优缺点。试讨论这三种方法的优缺点。解：解：(1)用 scanf 和 printf 直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。 (2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。 (3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。1.81.8 设设 n n 为正整数。试确定以下各程序段中前置以记号为正整数。试确定以下各程序段中前置以记号 的语句的频度：的语句的频度：(1) i=1; k=0;(1) i=1; k=0; whil

10、e(i=n-1) while(i=n-1) k += 10*i; k += 10*i; i+; i+; (2) i=1; k=0;(2) i=1; k=0; do do k += 10*i; k += 10*i; i+; i+; while(i=n-1); while(i=n-1);(3) i=1; k=0;(3) i=1; k=0; while (i=n-1) while (i=n-1) i+; i+; k += 10*i; k += 10*i; (4) k=0;(4) k=0; for(i=1; i=n; i+) for(i=1; i=n; i+) for(j=i; j=n; j+) fo

11、r(j=i; j=n; j+) k+; k+; (5) for(i=1; i=n; i+) (5) for(i=1; i=n; i+) for(j=1; j=i; j+) for(j=1; j=i; j+) for(k=1; k=j; k+) for(k=1; k=j; k+) x += delta; x += delta; (6) i=1; j=0;(6) i=1; j=0; while(i+j=n) while(i+jj) j+; if(ij) j+; else i+; else i+; (7) x=n; y=0; / n(7) x=n; y=0; / n 是不小于是不小于 1 1 的常数

12、的常数 while(x=(y+1)*(y+1) while(x=(y+1)*(y+1) y+; y+; (8) x=91; y=100;(8) x=91; y=100; while(y0) while(y0) if(x100) x -= 10; y-; if(x100) x -= 10; y-; else x+; else x+; 解：解：(1) n-1 (2) n-1 (3) n-1 (4) n+(n-1)+(n-2)+.+1=n(n 1)2 (5) 1+(1+2)+(1+2+3)+.+(1+2+3+.+n)=i(i 1)2i1n1n1n21n21n =i(i 1) (i i) i i2i1

13、2i12i12i1 =111n(n 1)(2n 1) n(n 1) n(n 1)(2n 3)12412 (6) n (7)n向下取整 (8) 11001.91.9 假设假设 n n 为为 2 2 的乘幂，的乘幂， 并且并且 n2n2， 试求以下算法的时间复杂度及变量试求以下算法的时间复杂度及变量 countcount 的值的值 以以 n n 的函数形式表示的函数形式表示 。int Time(int n) int Time(int n) 解：解：o(log2count=log2count = 0;count = 0; x=2;x=2;while(xn/2) while(x438 时，n2 50nlog2n1.141.14 判断以下各对函数判断以下各对函数fn和和gn，当，当n 时，哪个函数增长更快？时，哪个函数增长更快？(1)(1)(2)(2)fn10n2ln n!10nfnlnn!523，gn 2n4 n7，gn13n2.52(3)(3)(4)(4)fn n2.1n41，gnlnn! n2fn 2n2n，gn nnn532解：解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快1.151.15 试用数学归纳法证明：试用数学归纳法证明：(1)(1)ii1nn2 nn 12n 1/6n 0 x 1,n 0(2)(2)x xii0n11 /x 1