数据结构习题集答C语言版严蔚敏).pdf

第1章 绪 论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型解：数据是对客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理数据对象是性质相同的数据元素的集合，是数据的一个子集数据结构是相互之间存在一种或多种特定关系的数据元素的集合存储结构是数据结构在计算机中的表示数据类型是一个值的集合和定义在这个值集上的一组操作的总称抽象数据类型是指一个数学模型以及定义在该模型上的一组操作是对般数据类型的扩展1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3 设有数据结构(D,R),其中O=dl,d2,13,14,R=r,r=(dl,d2),(d2,d3),(d3,d4)试按图论中图的画法惯例画出其逻辑结构图解：(1)*(3?)-(d3)-1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)解：A D T C o m p l e x 数据对象：D=r,i|r,i 为实数数据关系：R=r,i 基本操作：I n i t C o m p l e x(&C,r e,i m)操作结果：构造一个复数C,其实部和虚部分别为r e 和 i mD e s t r o y C m o p l e x(&C)操作结果：销毁复数CG e t (C,k,&e)操作结果：用 e 返回复数C的第k 元的值P u t (&C,k,e)操作结果：改变复数C的第k元的值为eI s A s c e n d i n g(C)操作结果：如果复数C的两个元素按升序排列，则返回1,否则返回0I s D e s c e n d i n g(C)操作结果：如果复数C的两个元素按降序排列，则返回1,否则返回0M a x(C,&e)操作结果：用 e 返回复数C的两个元素中值较大的个M i n(C,&e)操作结果：用 e 返回复数C的两个元素中值较小的个(A D T C o m p l e xA D T R a t i o n a l N u m b e r 数据对象：D=s,m|s,m为自然数，且用不为0 数据关系：R=基本操作：I n i t R a t i o n a 1 N u m b e r (&R,s,m)操作结果：构造个有理数R,其分子和分母分别为s 和mD e s t r o y R a t i o n a l N u m b e r(&R)操作结果：销毁有理数RG e t (R,k,&e)操作结果：用 e 返回有理数R的第k 元的值P u t (&R,k,e)操作结果：改变有理数R的第k 元的值为eI s A s c e n d i n g(R)操作结果：若有理数R的两个元素按升序排列，则返回1,否则返回0I s D e s c e n d i n g(R)操作结果：若有理数R的两个元素按降序排列，则返回1,否则返回0M a x (R,&e)操作结果：用 e 返回有理数R的两个元素中值较大的一个M i n(R,&e)操作结果：用 e 返回有理数R的两个元素中值较小的一个 A D T R a t i o n a l N u m b e r1.5 试画出与下列程序段等价的框图。

1)p r o d u c t=l;i=l;w hi l e(i =n)p r o d u c t *=i;i+；(2)i=0;d o i+；w hi l e(i!=n)&(a i !=x);(3)s w i t c h c a s e x y:z=y-x;b r e a k;c a s e x=y:z=a b s(x*y);b r e a k;d e f a u l t:z=(x-y)/a b s(x)*a b s(y);1.6 在程序设计中，常用下列三种不同的出错处理方式：(1)用 e x i t 语句终止执行并报告错误；(2)以函数的返回值区别正确返回或错误返回；(3)设置一个整型变量的函数参数以区别正确返回或某种错误返回试讨论这三种方法各自的优缺点解：(l)e x i t常用于异常错误处理，它可以强行中断程序的执行，返回操作系统2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误1.7在程序设计中，可采用下列三种方法实现输出和输入：(1)通过s c a n f 和 p r i n t f 语句；(2)通过函数的参数显式传递；(3)通过全局变量隐式传递。

试讨论这三种方法的优缺点解：(1)用s ca n f和p r i n t f直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难1.8设 n 为正整数试确定下列各程序段中前置以记号 的语句的频度：(1)i=l;k=0;w h i l e(i =n-l)k +=10*i;i+；)(2)i=l;k=0;d o k +=10*i;i+；)w h i l e(i =n-l);(3)i=l;k=0;w h i l e (i =n-l)i+；k +=10*i;)(4)k=0;f o r(i=l;i =n;i+)f o r(j=i;j =n;j+)k+;)(5)f o r(i=l;i =n;i+)f o r(j=l;j =i;j+)f o r(k=l;k =j;k+)x +=d e l t a;)(6)i=l;j=0;w h i l e(i+j j)j+；e l s e i+;(7)x=n;y=0;/n 是不小于1的常数w h i l e(x =(y+1)*(y+1)y+;(8)x=91：y=100;w h i l e(y 0)e i f(x 100)x -=10;y;e l s e x+;)解：n-1n-1n-1n(n+1)(4)n+(n-l)+(n-2)+.+1=-2进+1)2l +(l+2)+(1+2+3)+.+(1+2+3+.+n)=):r=l=万1?+1)=汽(/+，)=万1?2+万1?乙/=1 乙/=!乙/=1 乙/=1二一n(n+1)(2 +1)+n(n+1)=n(n+1)(2 +3)12 4 12(6)n(7)|_ V n J向下取整(8)11001.9假设n为 2 的乘嘉，并且n 2,试求下列算法的时间复杂度及变量c o u n t 的值(以n的函数形式表示)。

i n t T i m e(i n t n)c o u n t =0;x=2;w h i l e(x 4 38 时，n2 5 0n log2 n1.14 判断下列各对函数/(n)和 g()，当-0 0 时，哪个函数增长更快？(1)/(n)=10n2+ln(n!+10,3).g()=2/+7(2)f(n)=(ln(!)+5)2,g()=13n2 5(3)f(n)=n2+Vtt4+1 g(n)=(ln(n!)2+n(4)/(”)=)+(2 ,g()解:g(n)快(2)g(n)快(3)f(n)快(4)f(n)快1.15 试用数学归纳法证明：(1)Z J =(+“2 +1)/6 (n 0)1)/=1(4)之 2 i-l)=M (1)i=l1.1 6 试写一算法，自大至小依次输出顺序读入的三个整数X,Y和 Z 的值解：i nt ma x 3(i nt x,i nt y,i nt z)(i f(x y)i f(x z)re turn x;e lse re turn z;e lsei f(y z)re turn y;e lse re turn z;1.1 7 已知k 阶斐波那契序列的定义为/o=/j =0,.fk_2=0,fk一 i=i ；fn=fn-+fn-2 +f n-k =k,+L 试编写求k 阶斐波那契序列的第m项值的函数算法，k 和 m均以值调用的形式在函数参数表中出现。

解：k 0为阶数，n为数列的第n项i nt Fi b ona c c i (i nt k,i nt n)i f(k l)e x i t(OVE RFL OW);i nt*p,x;p=ne w i nt k+1;i f(!p)e x i t(OVE RFL OW);i nt i,j;f or(i=0;i k+l;i+)i f(i k-l)p i=0;e lse p i=l;)f or(i=k+l;i n+l;1+)x=p 0;f or(j=0;j k;j+)p j=p j+l;p k=2*p k-l-x;)re turn p k;L 18假设有A,B,C,D,E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为I 项 目 名 称 I 性别 I 校名 成绩 I 得分 I编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出解：ty pe d e f e num A,B,C,D,E S c h ool N a me;ty pe d e f e num Fe ma le,M a le S e x T y pe;ty pe d e f struc tc h a r e v e nt 3;项目S e x T y pe se x;S c h ooI N a me sc h ool;i nt sc ore;Compone nt;ty pe d e f struc t(i nt M a l e S um;男团总分i nt Fe ma le S um;女团总分i nt T ota lS um;团体总分 S um;S um S umS c ore(S c h oolN a me sn,Compone nt a ,i nt n)(S um te mp;te mp.M a le S um=0;te mp.Fe ma le S um=O;te mp.T ota lS um=0;i nt i;f or(i=0;i m a x i n t 时，应按出错处理。

注意选择你认为较好的出错处理方法解：#i nc lud e#i nc lud e d e f i ne M AX I N T 6 5 5 35 d e f i ne ArrS i z e 100i nt f un(i nt i);i nt ma i n()i nt i,k;i nt a ArrS i z e;c out E nte r k:;c i nk;i f(k ArrS i z e-l)e x i t(0);f or(i=0;i M AX I N T)e x i t(0);e lse a i=2*i*a i-l;)f or(i=O;i M AX I N T)e x i t(O);e lse)re turn 0;)1.2 0试编写算法求一元多项式的值P(x)=Z%的值P(x0),并确定算法中每一语句的执行次数i=0和整个算法的时间复杂度注意选择你认为较好的输入和输出方法本 题 的 输 入 为=0,1,)，x0和，输出为乙(X o)解：nc 1ud e#i nc lud e d e f i ne N 10d oub le poly noma i l(i nt a ,i nt i,d oub l。