《数据结构与算法 C语言版》—— 1.9习题

本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第1章，第1.9节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.9习题

1.解释下列术语：数据、数据元素、数据对象、数据结构。

2.数据类型和抽象数据类型是如何定义的？两者有何异同？抽象数据类型的主要特点是什么？使用抽象数据类型的主要优点是什么？

3.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？

4.简述数据结构的三个层次、五个要素。

5.举一个数据结构的例子，说明其逻辑结构、存储结构及其运算三个方面的内容，并说明数据的逻辑结构、存储结构及其运算之间的关系。

6.设n为整数，试给出下列各程序段中标号为@的语句的频度。

（1）

i=1;
while(i<n)
@ i=i+2;

（2）

i=1;k=0;
while(i<=n-1){
@ k+=10*i;
i++;
}

（3）

i=1;k=0;
while(i<=n-1){
i++;
@ k+=10*i;
}

（4）

i=1;j=0;
while(i+j<=n){
@if(i>j)j++;
else i++;
}

（5）

x=n;y=0;//n是不小于1的常数
while(x>=(y+1)*(y+1)){
@ y++;
}

（6）

x=91;y=100;
while(y>0){
@if(x>100){x-=10;y--;}
else x++;
}

7.调用下列C函数f(n)，回答问题：

（1）试指出f(n)值的大小，并写出f(n)值的推导过程。

（2）假定n=5，试指出f(5)值的大小和执行f(5)时的输出结果。

int f(int n){
int i,j,k,sum=0;
for(i=1;i<n+1;i++){
for(j=n;j>i-1;j--)
for(k=1;k<j+1;k++)sum++;
printf("sum=%d\\n",sum);
}
return (sum);
}

8.试编写一个算法，从小到大依次输出顺序读入的3个整数x、y和z的值。

9.将下列各函数按它们在n→∞时的无穷阶数从小到大排序：n，n－n3+7n5，nlogn1
此处的logn表示log2n，全书后同。
，2n/2，n3，logn，n1/2+logn，(3/2)n，n!，n2+logn。

10.已知k阶裴波那契序列的定义为：

f0=0，f1=0，…，fk－2=0，fk－1=1
fn=fn－1+fn－2+…+fn－k，n=k，k+1，…

试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。