第第 1 章章 绪论绪论 教材中练习题及参考答案 1. 简述数据与数据元素的关系与区别 答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合数据元素是数 据的基本单位，是数据的个体数据元素与数据之间的关系是元素与集合之间的关系 2. 采用二元组表示的数据逻辑结构 S=， 其中 D={a， b， „， i}， R={r}， r={，，，，，，，}，问关系 r 是什么类型 的逻辑结构？哪些结点是开始结点，哪些结点是终端结点？ 答：该逻辑结构为树形结构，其中 a 结点没有前驱结点，它是开始结点，b、e、i 和 g、 结点没有后继结点，它们都是终端结点 3. 简述数据逻辑结构与存储结构的关系 答：在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在 计算机中的表示存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还 要在内存中存储各数据元素间的逻辑关系通常情况下，一种逻辑结构可以有多种存储结 构，例如，线性结构可以采用顺序存储结构或链式存储结构表示 4. 简述数据结构中运算描述和运算实现的异同 答： 运算描述是指逻辑结构施加的操作， 而运算实现是指一个完成该运算功能的算法。
它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作不 同点是，运算描述只是描述处理功能，不包括处理步骤和方法，而运算实现的核心则是设 计处理步骤 5. 数据结构和数据类型有什么区别？ 答：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个 方面的内容，即数据的逻辑结构、存储结构和数据的运算而数据类型是一个值的集合和 定义在这个值集上的一组运算的总称，如C语言中的short int数据类型是由-32768～32767 （16位机）的整数和+、-、*、/、%等运算符构成 6. 在 C/C++中提供了引用运算符，简述其在算法描述中的主要作用 答：在算法设计中，一个算法通常用一个或多个 C/C++函数来实现，在 C/C++函数之 间传递参数时有两种情况，一是从实参到形参的单向值传递，二是实参和形参之间的双向 值传递对形参使用引用运算符，即在形参名前加上“ while (n1) { y=y*x; n--; } } 答：本算法的功能是计算 y=xn 8. 用 C/C++语言描述下列算法，并给出算法的时间复杂度 （1）求一个 n 阶整数数组的所有元素之和。
（2）对于输入的任意 3 个整数，将它们按从小到大的顺序输出 （3）对于输入的任意 n 个整数，输出其中的最大和最小元素 答： （1）算法如下： int sum(int A[int sum(int A[N N][][N N],int n)],int n) { int i,j,s=0; for (i=0;ic) printf(“%d,%d,%d\n“,c,b,a); else if (ac) printf(“%d,%d,%d\n“,b,c,a); else printf(“%d,%d,%d\n“,b,a,c); } else { if (bc) { if (ac) printf(“%d,%d,%d\n“,c,a,b); else printf(“%d,%d,%d\n“,a,c,b); } else printf(“%d,%d,%d\n“,a,b,c); } } 本算法的时间复杂度为 O(1) （3）算法如下： void maxmin(int A[],void maxmin(int A[],i int n,int min=min=A[0]; for (i=1;imax) max=A[i]; if (A[i]1 其中，O(n)为 merge()所需的时间，设为 cn（c 为常量） 。
因此： T(n)=2T( 2 n )+cn=2(2T( 22 n )+ 2 cn )+cn=22T( 22 n )+2cn=23T( 23 n )+3cn ┇ =2kT( 2k n )+kcn=2kO(1)+kcn 由于 2k n 趋近于 1，则 k=log2n所以 T(n)=2log2nO(1)+cnlog2n=n+cnlog2n=O(nlog2n) 第 1 章 绪论 5 13. 描述一个集合的抽象数据类型 ASet，其中所有元素为正整数，集合的基本运算包 括： （1）由整数数组 a[0n-1]创建一个集合 （2）输出一个集合的所有元素 （3）判断一个元素是否在一个集合中 （4）求两个集合的并集 （5）求两个集合的差集 （6）求两个集合的交集 在此基础上设计集合的顺序存储结构，并实现各基本运算的算法 答：抽象数据类型 ASet 的描述如下： ADT ASet { 数据对象：D={ di | 0≤i≤n，n为一个正整数} 数据关系：无 基本运算： createset( dispset( s)：输出集合s; inset(s,e)：判断元素e是否在集合s中 void add(s1，s2，s3)：s3=s1∪s2; //求集合的并集 void sub(s1，s2，s3)：s3=s1-s2; //求集合的差集 void intersection(s1，s2，s3)：s3=s1∩s2; //求集合的交集 } 设计集合的顺序存储结构类型如下： typedef struct //集合结构体类型 { int data[MaxSize]; //存放集合中的元素，其中 MaxSize 为常量 int length; //存放集合中实际元素个数 } SetSet; //将集合结构体类型用一个新类型名 Set 表示 采用 Set 类型的变量存储一个集合。
对应的基本运算算法设计如下： void createset(Set for (i=0;in;i++) s.data[i]=a[i]; s.length=n; } void dispset(Set s)void dispset(Set s) ////输出一个集合输出一个集合 { int i; for (i=0;is.length;i++) printf(“%d “,s.data[i]); printf(“\n“); } boolbool inset(Set s,int e)inset(Set s,int e) ////判断判断 e e 是否在集合是否在集合 s s 中中 { int i; for (i=0;is.length;i++) if (s.data[i]==e) return true; 6 数据结构教程学习指导 return false; } void add(Set s1,Set s2,Set for (i=0;is1.length;i++) //将集合 s1 的所有元素复制到 s3 中 s3.data[i]=s1.data[i]; s3.length=s1.length; for (i=0;is2.length;i++) //将 s2 中不在 s1 中出现的元素复制到 s3 中 if (!inset(s1,s2.data[i])) { s3.data[s3.length]=s2.data[i]; s3.length++; } } void sub(Set s1,Set s2,Set s3.length=0; for (i=0;is1.length;i++) //将 s1 中不出现在 s2 中的元素复制到 s3 中 if (!inset(s2,s1.data[i])) { s3.data[s3.length]=s1.data[i]; s3.length++; } } vovoid intersection(Set s1,Set s2,Set s3.length=0; for (i=0;is1.length;i++) //将 s1 中出现在 s2 中的元素复制到 s3 中 if (inset(s2,s1.data[i])) { s3.data[s3.length]=s1.data[i]; s3.length++; } } 。