数据结构(c++版)doc

《数据结构(c++版)doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、135数据结构(C++版)数据结构(C++版)135数据结构(C++版)第1章绪论1.1数据结构的重要性图1-11.2面向对象程序设计1.2.1面向对象程序设计方法1.面向对象2.面向对象程序设计方法的特征1.2.2C++的特征及基本概念1.3基本术语135数据结构(C++版)图1-2数据元素和数据项1.4抽象数据类型1.5数据结构的概念135数据结构(C++版)1.6数据的逻辑结构图1-3一周七天数据结构图示1.7数据的存储结构1.顺序存储方法2.链式存储方法135数据结构(C++版)图1-5线性结构的链接存储135数据结构(C++版)3.索引存储方法4.

2、散列存储方法1.8数据的运算1.9数据的逻辑结构、存储结构及数据的运算的关系1.10算法的描述小结习题1.填空题(1)数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K是，R是。(2)存储结构可根据数据元素在机器中的位置是否连续分为，。(3)是数据的基本单位，有时一个由若干个组成，在这种情况下，称为记录，是数据的最小单位，而由记录生成的线性表称为。(4)算法的基本要求有，，，，。(5)度量算法效率可通过，两方面进行。(6)在C++中建立参数类型和参数个数不同的同名函数是可能的，这称为函数。2.综合题(1)简述下列术语:数据数据元素数据对象数据结构

3、存储结构数据类型抽象数据类型(2)常用的存储表示方法有哪几种？(3)举例说明一下数据结构和算法的关系。(4)设有数据逻辑结构为B=(K，R)，K={k1，k2，…135数据结构(C++版)，k9},R={，，，，，，，，，，}画出逻辑结构图，并确定相对于R哪些结点是开始结点，哪些结点是终端结点？(5)试举一个数据结构的例子，并叙述其逻辑结构、存储结构、运算三方面的内容。(6)什么是算法？详述算法设计的目的和

4、算法必须满足的条件。第2章算法分析2.1算法分析的概念图2-1小规模输入时的运行时间图2-2中等规模输入时的运行时间135数据结构(C++版)2.2算法运行时间举例2.3最大连续子序列之和问题2.3.1简单易懂的O(n3)算法2.3.2一个改进的O(n2)算法2.3.3一个线性算法135数据结构(C++版)2.4静态搜索问题2.4.1顺序搜索2.4.2二分搜索2.4.3插值搜索2.5检验一个算法分析135数据结构(C++版)2.6Big

5、Oh分析法的限制小结习题1.简答题(1)如定理2-1所描述的,从盒子中往外取球,在A)~D)所给的答案中，哪一个是定理中

6、变量i，j，k对应的值？A)red，5，6B)blue，5，6C)blue，3，redD)6，5，red(2)基于定理2-2的描述，为什么不能充分获得一个最大连续子序列之和的次平方运行时间？(3)假设T1(n)=O(F(n))，T2(n)=O(F(n))，下列哪一个正确？A)T1(n)+T2(n)=O(F(n))B)T1(n)-T2(n)=O(F(n))C)T1(n)/T2(n)=O(1)D)T1(n)=O(T2(n))(4)将下列各式组合成与Big

7、Oh相等的函数。x2，x2+x，x2-x，x3/(x-1)(5)程序A和程序B经分析，有不超过150nlo

8、gn和n2的最坏情况下的运行时间，如可能，分别回答下列各问题:A)当n值很大时(n>10000),哪个程序对运行时间有保证？B)n值较小(n<1000)时，哪一个程序对运行时间有更好的保证？C)在n=1000的平均情况下，哪个程序运行更好？D)在所有可能的输入中，程序B总比程序A运行的快吗？(6)对于算法2-4的二分搜索，写出用以下代码片段替换的结果。A)第13行(测试):low

9、型算法用手工来计算下述问题，确定其运行时间。A)两个n位整数相加B)两个n位整数相乘C)两个n位整数相除(2)对于n个项来说，以下计算xn的算法运行时间是多少？doublepower(doublex，intn){doubleresult=1.0;for(inti=0;i

10、它将花费多少时间？(低次项不考虑)A)线性算法B)O