《一 简述下列概念：数据、数据元素、数据类型、数据结构、17611》由会员分享，可在线阅读，更多相关《一 简述下列概念：数据、数据元素、数据类型、数据结构、17611（5页珍藏版）》请在金锄头文库上搜索。
1、一一 简述下列概念：数据、数据元素、数据类型、数据结构、简述下列概念：数据、数据元素、数据类型、数据结构、1761117611我所要做的只是以我微薄之力来为真理和正义服务，即使不为人所喜欢也在所不惜。一. 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构解答： 数据：指能够被计算机识别、存储和加工处理的信息载体 数据元素：就是数据的基本单位在某些情况下数据元素也称为元素、结点、顶点、记录数据元素有时可以由若干数据项组成 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称通常数据类型可以看作是程序设计语言中已实现的数据结构 数据结构：指的是数据之
2、间的相互关系即数据的组织形式一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算 逻辑结构：指数据元素之间的逻辑关系 存储结构：数据元素及其关系在计算机存储器内的表示称为数据的存储结构 线性结构：数据逻辑结构中的一类它的特征是若结构为非空集则该结构有且只有一个开始结点和一个终端结点并且所有结点都有且只有一个直接前趋和一个直接后继线性表就是一个典型的线性结构栈、队列、串等都是线性结构 非线性结构：数据逻辑结构中的另一大类它的逻辑特征是一个结点可能有多个直接前趋和直接后继数组、广义表、树和图等数据结构都是非线性结构二. 设 n 为正整数利用大“O“记号将下列程序段的执行时间表示为 n 的函
3、数(1) i=1; k=0; while(ij) j+;else i+;解析：通过分析以上程序段可将 i+j 看成一个控制循环次数的变量且每执行一次循环i+j 的值加 1该程序段的主要时间消耗是 while 循环而 while 循环共做了 n 次所以该程序段的执行时间为：T(n)=O(n)(4)x=n; / n1 while (x=(y+1)*(y+1) y+;解析：由 x=n 且 x 的值在程序中不变又 while 的循环条件(x=(y+1)*(y+1)可知：当(y+1)*(y+1)刚超过n 的值时退出循环由(y+1)*(y+1)0) if(x100) x=x-10;y-;else x+;解
4、析：x=91; /1y=100; /1while(y0) /1101if(x100) /1100 x=x-10; /100y-; /100else x+; /1000以上程序段右侧列出了执行次数该程序段的执行时间为：T(n)=O(1) 三. 按增长率由小至大的顺序排列下列各函数：2100(3/2)n(2/3)nnn n0.5 n! 2n lgn nlgnn(3/2) 解答：常见的时间复杂度按数量级递增排列依次为:常数阶 0(1)、对数阶 0(log2n)、线性阶 0(n)、线性对数阶0(nlog2n)、平方阶 0(n2)、立方阶 0(n3)、k 次方阶 0(nk)、指数阶0(2n)先将题中的函数分成如下几类：常数阶：2100对数阶：lgnK 次方阶：n0.5、n(3/2) 指数阶 (按指数由小到大排)：nlgn、(3/2)n、2n、 n!、 nn注意：(2/3)n 由于底数小于 1所以是一个递减函数其数量级应小于常数阶根据以上分析按增长率由小至大的顺序可排列如下：(2/3)n 2100 lgn n0.5 n(3/2) nlgn (3/2)n 2n n! nn
