数据结构复习资料,java数据结构期末考试.doc

数据结构复习资料,java数据结构期末考试.doc

ID:48367025

大小:196.44 KB

页数:14页

时间:2019-11-28

数据结构复习资料,java数据结构期末考试.doc_第1页
数据结构复习资料,java数据结构期末考试.doc_第2页
数据结构复习资料,java数据结构期末考试.doc_第3页
数据结构复习资料,java数据结构期末考试.doc_第4页
数据结构复习资料,java数据结构期末考试.doc_第5页
资源描述:

《数据结构复习资料,java数据结构期末考试.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、第二章算法分析1.算法分析是计算机科学的基础2.增长函数表示问题(n)大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用3.渐进复杂度:随着n的增加时增长函数的一般性质,这一特性基于该表达式的主项,即n增加时表达式中增长最快的那一项。4.渐进复杂度称为算法的阶次,算法的阶次是忽略该算法的增长函数中的常量和其他次要项,只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。5.渐进复杂度:增长函数的界限,由增长函数的主项确定的

2、。渐进复杂度类似的函数,归为相同类型的函数。6.只有可运行的语句才会增加时间复杂度。7.O()或者大O记法:与问题大小无关、执行时间恒定的增长函数称为具有O(1)的复杂度。增长函数阶次t(n)=17O(1)t(n)=3lognO(logn)t(n)=20n-4O(n)t(n)=12nlogn+100nO(nlogn)t(n)=3+5n-2O()t(n)=8+3O()t(n)=+18+3nO()8.所有具有相同阶次的算法,从运行效率的角度来说都是等价的。9.如果算法的运行效率低,从长远来说,使用更快的处理

3、器也无济于事。10.要分析循环运行,首先要确定该循环体的阶次n,然后用该循环要运行的次数乘以它。(n表示的是问题的大小)11.分析嵌套循环的复杂度时,必须将内层和外层循环都考虑进来。12.方法调用的复杂度分析:如:publicvoidprintsum(intcount){intsum=0;for(intI=1;I

4、杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复杂度为O()。13指数函数增长>幂函数增长>对数函数增长第三章集合概述——栈1.集合是一种聚集、组织了其他对象的对象。它定义了一种特定的方式,可以访问、管理所包含的对象(称为该集合的元素)。集合的使用者——通常是软件系统中的另一个类或对象——只能通过这些预定的方式与该集合进行交互。2.集合可分为线性集合和非线性集合。线性集合是一种元素按直线方式组织的集合。非线性集合是一种元素按某种非直线方式组织的集合,例如按层次组织或按网状组织。从

5、这种意义上来说,非线性集合也许根本就没有任何组织形式。3.集合中的元素通常是按照它们添加到集合的顺序,或者是按元素之间的某种内在关系来组织的。4.抽象能隐藏某些细节。5.集合是一种隐藏了实现细节的抽象。6.对象是用于创建集合一种完美机制,因为只要设计正确,对象的内部工作对系统其他部分而言是被封装的。几乎在所有情况下,在类中定义的实例变量的可见性都应声明为私有的(private)。因此,只有该类的方法才可以访问和修改这些变量。用户与对象的唯一交互只能通过其公用方法。公用方法表示了对象所能提供的服务。7.数

6、据类型是一组值及作用于这些数值上的各种操作。8.抽象数据类型(ADT)是一种在程序设计语言中尚未定义其值和操作的数据类型。ADT的抽象性体现在,ADT必须对其实现细节进行定义,且对这些用户是不可见的。因此,集合是一种抽象数据类型。9.数据结构是一种用于实现集合的基本编程结构。10.Java集合API(应用程序编程接口)是一个类集,表示了一些特定类型的集合,这些类的实现方式各不相同。11.栈的元素是按照后进先出(LIFO)的方式进行处理的,最后进入栈中的元素最先被移出。栈是一种线性集合,元素的添加和删除都

7、在同一端进行。在科学计算中,栈的基本使用就是用于颠倒顺序(如一个取消操作)。12.通常垂直的绘制栈,栈的末端称为栈的顶部,元素的添加和删除在顶部进行。13.如果pop或者peek可作用于空栈,那么栈的任何实现都要抛出一个异常。集合的作用不是去确定如何处理这个异常,而是把它报告给使用该栈的应用程序。在栈中没有满栈的概念,应由栈来管理它自己的存储空间。14.栈的toString()操作可以在不修改栈的情况下遍历和现实栈的内容,对调试非常有用。15.类型兼容性是指把一个对象赋给引用的特定赋值是否合法。16.继

8、承就是通过某个现有类派生出一个新类的过程。多态:使得一个引用可以多次指向相关但不同的对象类型,且其中调用的方法是在运行时与代码。多态引用是一个引用变量,它可以在不同地点引用不同类型的对象。继承可用于创建一个类层次,其中,一个引用变量可用于只想与之相关的任意对象。类层次:通过继承创建的类之间的关系,某个类的子类可以成为其他类的父类17.一个Object引用可用于引用任意对象,因为所有类最终都是从Object类派生而来的。18.泛型,用泛型定义

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。