|
简述下列概念数据数据元素数据类型数据结构逻辑结构存储结构线性结构非线性结构 ● 数据指能够被计算机识别存储和加工处理的信息载体 ● 数据元素就是数据的基本单位在某些情况下数据元素也称为元素结点顶点记录数据元素有时可以由若干数据项组成 ● 数据类型是一个值的集合以及在这些值上定义的一组操作的总称通常数据类型可以看作是程序设计语言中已实现的数据结构 ● 数据结构指的是数据之间的相互关系即数据的组织形式一般包括三个方面的内容:数据的逻辑结构存储结构和数据的运算 ● 逻辑结构指数据元素之间的逻辑关系 ● 存储结构数据元素及其关系在计算机存储器内的表示称为数据的存储结构 ● 线性结构数据逻辑结构中的一类它的特征是若结构为非空集则该结构有且只有一个开始结点和一个终端结点并且所有结点都有且只有一个直接前趋和一个直接后继线性表就是一个典型的线性结构栈队列串等都是线性结构 ● 非线性结构数据逻辑结构中的另一大类它的逻辑特征是一个结点可能有多个直接前趋和直接后继数组广义表树和图等数据结构都是非线性结构 试举一个数据结构的例子叙述其逻辑结构存储结构运算三个方面的内容 答 例如有一张学生体检情况登记表记录了一个班的学生的身高体重等各项体检信息这张登记表中每个学生的各项体检信息排在一行上这个表就是一个数据结构每个记录(有姓名学号身高和体重等字段)就是一个结点对于整个表来说只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)这几个关系就确定了这个表的逻辑结构是线性结构 这个表中的数据如何存储到计算机里并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题 在这个表的某种存储结构基础上可实现对这张表中的记录进行查询修改删除等操作对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了 常用的存储表示方法有哪几种? 答 常用的存储表示方法有四种: ● 顺序存储方法它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里结点间的逻辑关系由存储单元的邻接关系来体现由此得到的存储表示称为顺序存储结构通常借助程序语言的数组描述 ● 链接存储方法它不要求逻辑上相邻的结点在物理位置上亦相邻结点间的逻辑关系是由附加的指针字段表示由此得到的存储表示称为链式存储结构通常借助于程序语言的指针类型描述 ● 索引存储方法除建立存储结点信息外还建立附加的索引表来标识结点的地址组成索引表的索引项由结点的关键字和地址组成若每个结点在索引表中都有一个索引项则该索引表称之为稠密索引（Dense Index）若一组结点在索引表中只对应一个索引项则该索引表称为稀疏索引 ● 散列存储方法就是根据结点的关键字直接计算出该结点的存储地址 设三个函数fgh分别为 f(n)=n+n+ g(n)=n+n h(n)=n+nlgn 请判断下列关系是否成立 () f(n)=O(g(n)) () g(n)=O(f(n)) () h(n)=O(n) () h(n)=O(nlgn) 分析 数学符号O的严格的数学定义 若T（n）和f（n）是定义在正整数集合上的两个函数则T（n）=O（f（n））表示存在正的常数C和n使得当n≥n时都满足≤T（n）≤C·f（n） 通俗地说就是当n→∞时f(n)的函数值增长速度与T（n)的增长速度同阶一般一个函数的增长速度与该函数的最高次阶同阶 即 O(f(n))=n O(g(n))=n O(h(n))=n 所以答案为 答 ●（）成立 ●（）成立 ●（）成立 ●（）不成立 设有两个算法在同一机器上运行其执行时间分别为n和n要使前者快于后者n至少要多大? 分析 要使前者快于后者即前者的时间消耗低于后者即 n<n 求解上式可得 答 n= 设n为正整数利用大O记号将下列程序段的执行时间表示为n的函数 () i=; k=; while(i<n) { k=k+*i;i++; } 分析 i=; // k=; // while(i<n) //n { k=k+*i; //n i++; //n } 由以上列出的各语句的频度可得该程序段的时间消耗 T(n)=++n+(n)+(n)=n 可表示为T(n)=O(n) () i=; k=; do{ k=k+*i; i++; } while(i<n); 分析 i=; // k=; // do{ //n k=k+*i; //n i++; //n } while(i<n);//n 由以上列出的各语句的频度可得该程序段的时间消耗 T(n)=++n+n+n+n=n+ 可表示为T(n)=O(n) () i=; j=; while(i+j<=n) { if (i>j) j++; else i++; } 分析 通过分析以上程序段可将i+j看成一个控制循环次数的变量且每执行一次循环i+j的值加该程序段的主要时间消耗是while循环而while循环共做了n次所以该程序段的执行时间为 T(n)=O(n) ()x=n; // n> while (x>=(y+)*(y+)) y++; 分析 由x=n且x的值在程序中不变又while的循环条件(x>=(y+)*(y+))可知当(y+)*(y+)刚超过n的值时退出循环 由(y+)*(y+)<n得y<n^ 所以该程序段的执行时间为 向下取整(n^) () x=; y=; while(y>) if(x>) {x=x;y;} else x++; 分析 x=; // y=; // while(y>) // if(x>) // {x=x; // y; // } else x++; // 以上程序段右侧列出了执行次数该程序段的执行时间为 T(n)=O() 算法的时间复杂度仅与问题的规模相关吗? 答 算法的时间复杂度不仅与问题的规模相关还与输入实例中的初始状态有关但在最坏的情况下其时间复杂度就是只与求解问题的规模相关的我们在讨论时间复杂度时一般就是以最坏情况下的时间复杂度为准的 按增长率由小至大的顺序排列下列各函数 (/)n(/)n nn n n! n lgn nlgn n(/) 答 常见的时间复杂度按数量级递增排列依次为:常数阶()对数阶(logn)线性阶(n)线性对数阶(nlogn)平方阶(n)立方阶(n)k次方阶(nk)指数阶(n) 先将题中的函数分成如下几类 常数阶 对数阶lgn K次方阶nn(/) 指数阶 (按指数由小到大排)nlgn(/)nn n! nn 注意(/)^n由于底数小于所以是一个递减函数其数量级应小于常数阶 根据以上分析按增长率由小至大的顺序可排列如下 (/)n < < lgn < n < n(/) < nlgn < (/)n < n < n! < nn 有时为了比较两个同数量级算法的优劣须突出主项的常数因子而将低次项用大O记号表示例如设T(n)=nlgn+n+=nlgn+O(n) T(n)=nlgnn=lgn+O(n) 这两个式子表示当n足够大时T(n)优于T(n)因为前者的常数因子小于后者请用此方法表示下列函数并指出当n足够大时哪一个较优哪一个较劣? 上一篇：第一章绪论习题练习
下一篇：第2章线性表习题练习
|
