MS二级考试必备笔记栈二叉树等.docx

MS二级考试必备笔记(栈-二叉树等)————————————————————————————————作者:————————————————————————————————日期: 第一课数据结构和算法数据结构——由数据和结构构成数据由一堆元素构成。结构就是关系,集合中各个数据元素之间存在的关系(联系)。数据元素之间的关系用前件后件/直接前驱和直接后继数据元素之间的关系:逻辑关系表示前后件关系:存储关系跟逻辑关系不一定一致。数据的存储结构1顺序存储结构:逻辑相邻的数据元素存储在物理相邻存储单位里2链式存储结构:第二课:栈及其基本运算子弹匣就是一个形象的栈。栈的特点:1先进后出,2栈有记忆作用,3顺序结构下,栈的插入与删除不需要一栋表中其他数据元素;4栈顶指针top动态反应了栈中元素的变化情况。栈也称先进后出表(FILO)或者后进先出表(LIFO)栈的基本运算栈的存储第三课二叉树及其基本性质定义:与一般树结构比较,二叉树在结构上具有规范性和确定性的特点。二叉树的基本性质:性质5和6是完全二叉树和满二叉树特有的性质:例子:二叉树遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。在遍历二叉树的过程中,一般先遍历左子树,再遍历右子树。在先左后右的原则下,根据访问根节点的次序不同。前序遍历(DLR)中序遍历(LDR)后序遍历(LRD)程序设计结构面向对象方法的基本概念:关于面向对象方法,对其概念有许多不同的看法和定义,但是都涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。1对象是面向对象方法中最基本的概念。对象可以用来表示客观世界中的任何实体,它既可以是具体的物理实体的抽象,也可以是人为的概念,或者是任何有明确边界和意义的东西。面向对象的程序设计方法中设计的对象是系统中用来描述客观事物的一个实体,是构成系统的一个基本单位,它由一组静态特征和它可执行的一组操作组成。客观世界中的实体通常都既具有静态的属性,又具有动态的行为,因此面向对象方法中的对象是由该对象属性的数据以及可以对这些数据施加的所有操作封装在一起构成的统一体。属性是对象所包含的信息,它在设计对象时确定,一般只能通过执行对象的操作来改变。不同对象的同意属性可以具有不同的属性值。一个对象能够接受不同形式、不同内容的多个消息,相同形式的消息可以送往不同的对象,不同的对象对于形式相同的消息可以有不同的解释,能够做出不同的反应。一个对象可以同时往多个对象传递消息,两个对象也可以同时向某一个对象传递消息。软件工程基本概念软件的定义软件特点: