数据结构课后习题答案.doc

附录习题参考答案习题1参考答案1.1.选择题(1).A.(2).A.(3).A.(4).B.,C.(5).A.(6).A.(7).C.(8).A.(9).B.(10.)A.1.2.填空题(1).数据关系(2).逻辑结构物理结构(3).线性数据结构树型结构图结构(4).顺序存储链式存储索引存储散列表（Hash）存储(5).变量的取值围操作的类别(6).数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7).关系网状结构树结构(8).空间复杂度和时间复杂度(9).空间时间(10).Ο(n)1.3名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变量的取值围和所能够进行的操作的总和。算法：是对特定问题求解步骤的一种描述，是指令的有限序列。1.4语句的时间复杂度为：(1)Ο(n2)(2)Ο(n2)(3)Ο(n2)(4)Ο(n-1)(5)Ο(n3)1.5参考程序：main(){intX,Y,Z;scanf("%d,%d,%d",&X,&Y,&Z);if(X>=Y)if(X>=Z)if(Y>=Z){printf("%d,%d,%d",X,Y,Z);}else{printf("%d,%d,%d",X,Z,Y);}else{printf("%d,%d,%d",Z,X,Y);}elseif(Z>=X)if(Y>=Z){printf("%d,%d,%d",Y,Z,X);}else{printf("%d,%d,%d",Z,Y,X);}else{printf("%d,%d,%d",Y,X,Z);}}1.6参考程序：main(){inti,n;floatx,a[],p;printf("\nn=");scanf("%f",&n);printf("\nx=");scanf("%f",&x);for(i=0;i<=n;i++)scanf("%f",&a[i]);p=a[0];for(i=1;i<=n;i++){p=p+a[i]*x;x=x*x;}printf("%f",p);}习题2参考答案2.1选择题(1).C.(2).B.(3).B.(4).B.5.D.6.B.7.B.8.A.9.A.10.D.2.2.填空题(1).有限序列(2).顺序存储和链式存储(3).Ｏ(n)O(n)(4).n-i+1n-i(5).链式(6).数据指针(7).前驱后继(8).Ο(1)Ο(n)(9).s->next=p->next;p->next=s;(10).s->next2.3.解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0，1,2,…,（n-1）/2的元素依次与下标为n,n-1,…,（n-1）/2的元素交换，输出数组a的元素。参考程序如下：main(){inti,n;floatt,a[];printf("\nn=");scanf("%f",&n);for(i=0;i<=n-1;i++)scanf("%f",&a[i]);for(i=0;i<=(n-1)/2;i++){t=a[i];a[i]=a[n-1-i];a[n-1-i]=t;}for(i=0;i<=n-1;i++)printf("%f",a[i]);}2.4算法与程序：main(){inti,n;floatt,a[];printf("\nn=");scanf("%f",&n);for(i=0;i<n;i++)scanf("%f",&a[i]);for(i=1;i<n;i++)if(a[i]>a[0]{t=a[i];a[i]=a[0];a[0]=t;}printf("%f",a[0]);for(i=2;i<n;i++)if(a[i]>a[1]{t=a[i];a[i]=a[1];a[1]=t;}printf("%f",a[0]);}2.5算法与程序：main(){inti,j,k,n;floatx,t,a[];printf("\nx=");scanf("%f",&x);printf("\nn=");scanf("%f",&n);for(i=0;i<n;i++)scanf("%f",&a[i]);/*输入线性表中的元素*/for(i=0;i<n;i++){/*对线性表中的元素递增排序*/k=i;for(j=i+1;j<n;j++)if(a[j]<a[k])k=j;if(k!=j){t=a[i];a[i]=a[k];a[k