数据结构(C++版).doc

《数据结构(C++版).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构(C++版)第1章绪论1.1数据结构的重要性图1-11.2面向对象程序设计1.2.1面向对象程序设计方法1.面向对象2.面向对象程序设计方法的特征1.2.2C++的特征及基本概念1.3基本术语图1-2数据元素和数据项1.4抽象数据类型1.5数据结构的概念1.6数据的逻辑结构图1-3一周七天数据结构图示1.7数据的存储结构1.顺序存储方法2.链式存储方法图1-5线性结构的链接存储3.索引存储方法4.散列存储方法1.8数据的运算1.9数据的逻辑结构、存储结构及数据的运算的关系1.10算法的描述小结习题1.填空题(1)数据的逻辑结构可形式地用一个二元组B＝(K，R)来

2、表示，其中K是，R是。(2)存储结构可根据数据元素在机器中的位置是否连续分为，。(3)是数据的基本单位，有时一个由若干个组成，在这种情况下，称为记录，是数据的最小单位，而由记录生成的线性表称为。(4)算法的基本要求有，，，，。(5)度量算法效率可通过，两方面进行。(6)在C++中建立参数类型和参数个数不同的同名函数是可能的，这称为函数。2.综合题(1)简述下列术语:数据数据元素数据对象数据结构存储结构数据类型抽象数据类型(2)常用的存储表示方法有哪几种？(3)举例说明一下数据结构和算法的关系。(4)设有数据逻辑结构为B=(K，R)，K={k1，k2，…，k9},R={<

3、k1，k3>，，，，，，，，，，}画出逻辑结构图，并确定相对于R哪些结点是开始结点，哪些结点是终端结点？(5)试举一个数据结构的例子，并叙述其逻辑结构、存储结构、运算三方面的内容。(6)什么是算法？详述算法设计的目的和算法必须满足的条件。第2章算法分析2.1算法分析的概念图2-1小规模输入时的运行时间图2-2中等规模输入时的运行时间2.2算法运行时间举例2.3最大连续子序列之和问题2.3.1简单易懂的O(n3)算法2.3.2一个改进

4、的O(n2)算法2.3.3一个线性算法2.4静态搜索问题2.4.1顺序搜索2.4.2二分搜索2.4.3插值搜索2.5检验一个算法分析2.6Big

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

6、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经分析，有不超过150nlogn和n2的最坏情况下的运行时间，如可能，分别回答下列各问题:A)当n值很大时(n>10000),哪个程序对运行时间有保证？B)n值较小(n<1000)时，哪一个程序对运行时间有更好的保证？C)在n=1000的平均情况下，哪个程序运行更好？D)在所有可能的输入中，程序B总比程序A运行的快吗？(6)对于算法2-4的二分搜

8、索，写出用以下代码片段替换的结果。A)第13行(测试):low

9、的三重和，证实这个结果是一样的。(4)对于求最大子序列之和问题的平方算法而言，精确确定语句最内部循环被执行多少次？(5)一个算法在输入规模为100时，花费0.5ms的时间，在下列情况下，输入规模为500时，它将花费多少时间？(低次项不考虑)A)线性算法B)O(nlogn)C)平方算法D)立方算法(6)一个算法在输入规模为100时，花费0.5ms的时间，在下列情况下，1min可以解决一个多大的问题？(低次项不考虑)A)线性算法B)O(nlogn)C)平方算法D)立方算法第3章线性表3.1线性表及其抽象数据类型说明3.1.1线性表及其逻辑结构