一 简述下列概念：数据、数据元素、数据类型、数据结构、.pdf

一 简述下列概念 数据 数据元素 数据类型 数据结构 逻辑结构 存储结构 线性 结构 非线性结构 解答 数据 指能够被计算机识别 存储和加工处理的信息载体 数据元素 就是数据的基本单位 在某些情况下 数据元素也称为元素 结点 顶 点 记录 数据元素有时可以由若干数据项组成 数据类型 是一个值的集合以及在这些值上定义的一组操作的总称 通常数据类型可 以看作是程序设计语言中已实现的数据结构 数据结构 指的是数据之间的相互关系 即数据的组织形式 一般包括三个方面的内 容 数据的逻辑结构 存储结构和数据的运算 逻辑结构 指数据元素之间的逻辑关系 存储结构 数据元素及其关系在计算机存储器内的表示 称为数据的存储结构 线性结构 数据逻辑结构中的一类 它的特征是若结构为非空集 则该结构有且只有 一个开始结点和一个终端结点 并且所有结点都有且只有一个直接前趋和一个直接后继 线性表就是一个典型的线性结构 栈 队列 串等都是线性结构 非线性结构 数据逻辑结构中的另一大类 它的逻辑特征是一个结点可能有多个直接 前趋和直接后继 数组 广义表 树和图等数据结构都是非线性结构 二 设n为正整数 利用大 O 记号 将下列程序段的执行时间表示为n的函数 1 i 1 k 0 while i n k k 10 i i 解析 i 1 1 k 0 1 while i n n k k 10 i n 1 i n 1 由以上列出的各语句的频度 可得该程序段的时间消耗 T n 1 1 n n 1 n 1 3n 可表示为T n O n 2 i 0 k 0 do k k 10 i i while i n 解析 i 0 1 k 0 1 do n k k 10 i n i n while i n n 由以上列出的各语句的频度 可得该程序段的时间消耗 T n 1 1 n n n n 4n 2 可表示为T n O n 3 i 1 j 0 while i jj j else i 解析 通过分析以上程序段 可将i j看成一个控制循环次数的变量 且每执行一次循环 i j的值加1 该程序段的主要时间消耗是while循环 而while循环共做了n次 所以该程 序段的执行时间为 T n O n 4 x n n 1 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 n得 y0 if x 100 x x 10 y else x 解析 x 91 1 y 100 1 while y 0 1101 if x 100 1100 x x 10 100 y 100 else x 1000 以上程序段右侧列出了执行次数 该程序段的执行时间为 T n O 1 三 按增长率由小至大的顺序排列下列各函数 2100 3 2 n 2 3 n nn n0 5 n 2n lgn nlgn n 3 2 解答 常见的时间复杂度按数量级递增排列 依次为 常数阶0 1 对数阶0 log2n 线性阶 0 n 线性对数阶0 nlog2n 平方阶0 n2 立方阶0 n3 k次方阶0 nk 指数阶0 2n 先将题中的函数分成如下几类 常数阶 2100 对数阶 lgn K次方阶 n0 5 n 3 2 指数阶 按指数由小到大排 nlgn 3 2 n 2n n nn 注意 2 3 n由于底数小于1 所以是一个递减函数 其数量