第一章参考答案 、名词解释(略) 填空题 、数据表示数据处理 2、机内表示 3、逻辑结构逻辑结构上的基本运算存储结构和运算评价和选择 4、逻辑性基本运算 5、存储 6、机外表示逻辑结构存储结构 7、处理要求基本运算和运算算法 8、数据数据元素数据项 9、元素结点顶点记录 0、字段域 l1、数据元素数据项 12、集合线性结构树形结构图状结构 加工引用 14、定义在S上的运算S上运算 15、归纳 16、机内表示 17、存储结点数据元素之间关联方式的表示附加设施 18、顺序存储方式链式存储方式索引存储方式散列存储方式 19、给定逻辑结构S的存储实现 存储映象 20、程序算法设计 21、运行终止的程序可执行部分 伪语言算法非形式算法 22、时空性能算法分析 23、正确性能易读性健壮性高效性 24、时间性能(或时间效率)空间性能(或空间效率)计算量存储量 25、标准操作标准操作计算量 26、最坏情况时间复杂性最坏情况时间复杂度平均时间复杂性平均时间复杂度 27、时间复杂性时间复杂度 8、算法输入规模 9、作为该算法输入的数据所含数据元素的数目,或与此数目有关的其他参数 30、1 logan n n22n实际不可计算高效 31、设计实现 32、数据结构的定义数据结构的实现数据结构的评价选择 33、数据的逻辑结构 线性结构非线性结构 34、O(n2) 、o(logn) 三、单项选择题 2①3 4③5①6②7④8③9.③ 10.③11.②12.②13.④14.④15.② 四、简答及应用 1.凡能被计算机存储、加工的对象通称为数据。 数据元素是数据的基本单位,在程序中作为一个整体而加以考虑和处理。换句话说, 数据元素被当作运算的基本单位,并且通常具有完整确定的实际意义。根据需要,数据 元素又被称为元素、结点、顶点或记录 在很多情况下,数据元素又是由数据项组成的,但数据项通常不肯有完整确定的实 际意义,或不被当作一个整体对待。在有些场合下,数据项又称为字段或域。它是数据 的不可分割的最小标识单位。 从某种意义上说,数据,数据元素和数据实际反映了数据组织的三个层次,数据 可由若干个数据元素构成,而数据元素又可由若干个数据项构成
1 第一章 参考答案 一、名词解释 （略） 二、填空题 1、数据表示 数据处理 2、机内表示 3、逻辑结构 逻辑结构上的基本运算 存储结构和运算 评价和选择 4、逻辑性 基本运算 5、存储 6、机外表示 逻辑结构 存储结构 7、处理要求 基本运算和运算 算法 8、数据 数据元素 数据项 9、元素 结点 顶点 记录 10、字段 域 11、数据元素 数据项 12、集合 线性结构 树形结构 图状结构 13、加工 引用 14、定义在 S 上的运算 S 上运算 15、归纳 16、机内表示 17、存储结点 数据元素之间关联方式的表示 附加设施 18、顺序存储方式 链式存储方式 索引存储方式 散列存储方式 19、给定逻辑结构 S 的存储实现 存储映象 20、程序 算法设计 21、运行终止的程序可执行部分 伪语言算法 非形式算法 22、时空性能 算法分析 23、正确性能 易读性 健壮性 高效性 24、时间性能（或时间效率） 空间性能（或空间效率） 计算量 存储量 25、标准操作 标准操作 计算量 26、最坏情况时间复杂性 最坏情况时间复杂度 平均时间复杂性 平均时间复杂度 27、时间复杂性 时间复杂度 28、算法输入规模 29、作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数 30、1 log2n n n2 2 n 实际不可计算 高效 31、设计 实现 32、数据结构的定义 数据结构的实现 数据结构的评价 选择 33、数据的逻辑结构 34、线性结构 非线性结构 34、O（n 2） 36、o(log2n)。 三、单项选择题 1.② 2.① 3.② 4.③ 5.① 6.② 7.④ 8.③ 9.③ 10.③ 11.② 12.② 13.④ 14.④ 15.② 四、简答及应用 1． 凡能被计算机存储、加工的对象通称为数据。 数据元素是数据的基本单位，在程序中作为一个整体而加以考虑和处理。换句话说， 数据元素被当作运算的基本单位，并且通常具有完整确定的实际意义。根据需要，数据 元素又被称为元素、结点、顶点或记录。 在很多情况下，数据元素又是由数据项组成的，但数据项通常不肯有完整确定的实 际意义，或不被当作一个整体对待。在有些场合下，数据项又称为字段或域。它是数据 的不可分割的最小标识单位。 从某种意义上说，数据，数据元素和数据实际反映了数据组织的三个层次，数据 可由若干个数据元素构成，而数据元素又可由若干个数据项构成
2、所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。数据元素之间 逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。关于逻辑结 构的以下几点需特别注意: 1)、逻辑结构与数据元素本身的形成、内容无关。 (2)、逻辑结构与数据元素的相对位置无关。 (3)、逻辑结构与所含结点个数无关 由此可见,一些表面上很不相同的数据可以有相同的逻辑结构,因此,逻辑结 构是数据组织的某种“本质性”的东西,是数据内部组织的主要方面。 3、逻辑结构反映数据元素之间的逻辑关系,而存储结构是数据结构在计算机中的 表示,它包括数据元素的表示及其关系的表示。 4、一般地,运算是指在任何逻辑结构上施加的操作,即对逻辑结构的加工。一个 运算的实现是指一个完成该运算功能的程序。 相同点:运算与运算的实现都能完成对数据的“处理”或某种特定的操作。 不同点:运算只描述处理功能,不包括处理步骤和方法,而运算实现的核心是 处理步骤。 5、类C语言基本上是标准C语言的简化。类C语言与标准C语言的主要区别如下 (1)局部量的说明可以省略(但形参表中及函数类型的说明需保留),重要的 变量需在注解中用文字说明基类型和作用。 (2)分情形语句可以采用下述形式: swItc case条件1:语句序列1: break case条件2:语句序列2; break case条件n:语句序列n: break; default:语句序列n+1; 其中“ default:语句序列n+1;”可以省略。 (3)不含goto语句,增加了一个出错处理语句 error(字符串),其功能是 终止它所在算法的执行并回送表示出错信息的字符串 (4)输入输出语句有: 输入语句 scanf([格式串],变量度 变量n) 输出语句 printf([格式串],变量度,……,变量n); (5)类C语言的形参书写比标准C语言简单,如 int abc(inta,intb,int c)可以简写为 int abc(inta,b,c) 五.算法设计 (1)int locate(dataytpe A[l. n), dateytpe k while((l<=n)&&(A[il=k))1++, mn(1) return(o) 当查找不成功时,总是比较n+1次,所以,最坏时间复杂性为n+1。其量
2 ２、所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。数据元素之间 逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。关于逻辑结 构的以下几点需特别注意： （１）、逻辑结构与数据元素本身的形成、内容无关。 （２）、逻辑结构与数据元素的相对位置无关。 （３）、逻辑结构与所含结点个数无关。 由此可见，一些表面上很不相同的数据可以有相同的逻辑结构，因此，逻辑结 构是数据组织的某种“本质性”的东西，是数据内部组织的主要方面。 ３、逻辑结构反映数据元素之间的逻辑关系，而存储结构是数据结构在计算机中的 表示，它包括数据元素的表示及其关系的表示。 ４、一般地，运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。一个 运算的实现是指一个完成该运算功能的程序。 相同点：运算与运算的实现都能完成对数据的“处理”或某种特定的操作。 不同点：运算只描述处理功能，不包括处理步骤和方法，而运算实现的核心是 处理步骤。 ５、类Ｃ语言基本上是标准Ｃ语言的简化。类Ｃ语言与标准Ｃ语言的主要区别如下： （１） 局部量的说明可以省略（但形参表中及函数类型的说明需保留），重要的 变量需在注解中用文字说明基类型和作用。 （２） 分情形语句可以采用下述形式： switch { case 条件１：语句序列１；break; case 条件 2：语句序列 2；break; …… case 条件 n：语句序列 n；break; default: 语句序列 n+1; } 其中“default: 语句序列 n+1;”可以省略。 （３） 不含 goto 语句，增加了一个出错处理语句 error（字符串），其功能是 终止它所在算法的执行并回送表示出错信息的字符串。 （４） 输入输出语句有： 输入语句 scanf([格式串]，变量度，……，变量 n); 输出语句 printf([格式串]，变量度，……，变量 n); (５) 类Ｃ语言的形参书写比标准Ｃ语言简单，如 int abc (int a,int b,int c)可以简写为 int abc(int a,b,c)。 五．算法设计 １．（１）int locate(dataytpe A[1..n],dateytpe k) { i=n; while ((I<=n)&&(A[i]!=k)) I++; if (I<=n) return(i); else return(o); } 当查找不成功时，总是比较 n+1 次，所以，最坏时间复杂性为 n+1。其量 T（n）=O(n)
(2)Void CZ max( datatype A[n], x, y) iXAI y=Alll for(l=21<=n;1+) if(x<A[i]y=x; x=A0]) /*替换最大值* [y=A[ *替换次最大值* 若经条件判断语句为标准操作,则最坏情况时间复杂性为n-1。其量级为 T(n=O(n)
3 （２）Void CZ_max(datatype A[n],x,y) { x=A[1]; y=A[1]; for(I=2;I<=n;I++) if(x<A[i]{y=x;x=A[i];} /*替换最大值*/ else if(y<A[i] y=A[i]; /*替换次最大值*/ } 若经条件判断语句为标准操作，则最坏情况时间复杂性为 n-1。其量级为 T(n)=O(n)