数据结构答案李春葆第1章绪论.pdf

《数据结构答案李春葆第1章绪论.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论教材中练习题及参考答案1.简述数据与数据元素的关系与区别。答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。数据元素是数据的基本单位，是数据的个体。数据元素与数据之间的关系是元素与集合之间的关系。2.采用二元组表示的数据逻辑结构S=，其中D={a，b，„，i}，R={r}，r={，，，，，，，}，问关系r是什么类型的逻辑结构？哪些结点是开始结点，哪些结点是终端结点？答：该逻辑结构为树形结构，其中a结点没有前驱结点，它是开始结点，b、e、i和g、结点没有后继结点，它们

2、都是终端结点。3.简述数据逻辑结构与存储结构的关系。答：在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在计算机中的表示。存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还要在内存中存储各数据元素间的逻辑关系。通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采用顺序存储结构或链式存储结构表示。4.简述数据结构中运算描述和运算实现的异同。答：运算描述是指逻辑结构施加的操作，而运算实现是指一个完成该运算功能的算法。它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作。不同点是，运算描述只是描述处理功能，不包括处理

3、步骤和方法，而运算实现的核心则是设计处理步骤。5.数据结构和数据类型有什么区别？答：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。而数据类型是一个值的集合和定义在这个值集上的一组运算的总称，如C语言中的shortint数据类型是由-32768～32767（16位机）的整数和+、-、*、/、%等运算符构成。6.在C/C++中提供了引用运算符，简述其在算法描述中的主要作用。答：在算法设计中，一个算法通常用一个或多个C/C++函数来实现，在C/C++函数之间传递参数时有两种情况，一是从实参到形参的单向值传递

4、，二是实参和形参之间的双向值传递。对形参使用引用运算符，即在形参名前加上“&”，不仅可以实现实参和形参之间的双向值传递，而且使算法设计简单明晰。2数据结构教程学习指导7.有以下用C/C++语言描述的算法，说明其功能：voidfun(double&y,doublex,intn){y=x;while(n>1){y=y*x;n--;}}n答：本算法的功能是计算y=x。8.用C/C++语言描述下列算法，并给出算法的时间复杂度。（1）求一个n阶整数数组的所有元素之和。（2）对于输入的任意3个整数，将它们按从小到大的顺序输出。（3）对于输入的任意n个整数，输出其中的最大和最小元素。答：（

5、1）算法如下：intsum(intA[N][N],intn){inti,j,s=0;for(i=0;ib){if(b>c)printf("%d,%d,%d",c,b,a);elseif(a>c)printf("%d,%d,%d",b,c,a);elseprintf("%d,%d,%d",b,a,c);}else{if(b>c){if(a>c)printf("%d,%

6、d,%d",c,a,b);elseprintf("%d,%d,%d",a,c,b);}elseprintf("%d,%d,%d",a,b,c);}}本算法的时间复杂度为O(1)。（3）算法如下：voidmaxmin(intA[],intn,int&max,int&min)第1章绪论3{inti;min=min=A[0];for(i=1;imax)max=A[i];if(A[i]

7、25n＋5000nl.5h(n)=n＋5000nlog2n求它们对应的时间复杂度。323323答：f(n)=100n＋n+1000=O(n)，g(n)=25n＋5000n=O(n)l.51.5当n→∞时，n＞log2n，所以h(n)=n＋5000nlog2n=O(n)。10.分析下面程序段中循环语句的执行次数。intj=0,s=0,n=100;do{j=j+1;s=s+10*j;}while(j