程序设计语言、算法分析、算法分类、解题技巧、真题讲解
NULL
大纲
程序设计语言
程序设计语言的基本成分
数据成分:指的是一种程序设计语言的数据和数据类型。数据可分为常量(在程序运行时不可改变)、变量(在程序运行时可以改变)、全局变量(其存储空间在静态数据区分配)、局部变量(其存储空间在堆栈区分配)。数据类型包括整型、字符型、双精度、单精度浮点型、布尔型等。
运算成分:指明了允许使用的运算符号及运算规则。这包括算术运算、逻辑运算、关系运算、位运算等。
控制成分:指明了语言允许表达的控制结构。这包括顺序结构、选择结构和循环结构(包括初始化、循环体和循环条件)。
传输成分:指明语言允许的数据传输方式。如赋值处理、数据的输入输出等。
函数
函数:C程序由一个或多个函数组成,每个函数都一个名字,其中有且仅有一个名字为main的函数作为程序运行时的起点。函数是程序模块的主要成分,是一段具有独立功能的程序。函数使用涉及三个概念:函数定义、函数声明(先声明后使用)、函数调用。
传值调用:将实参的值传递给形参,形参的改变不会导致调用点所传的实参的值改变。实 ...
用例图、类图、序列图、通信图、活动图、状态图、解题技巧、真题讲解
NULL
大纲
图
用例图
用例图:静态图,展现了一组用例、参与者以及它们之间的关系
用例图中的参与者是人、硬件或其他系统可以扮演的角色:用例是参与者完成的一系列操作。
主要考察参与者和用例的识别、用例之间的关系(包含include、扩展extend、泛化)
如图所示,登记外借信息用例包含用户登录用例,因为每次如果要登记外借信息,必然要先进行用户登录。而查询书籍信息的扩展是修改书籍信息,是因为每次查询书籍信息后,发现有错误才会修改,否则不修改,不是必要的操作。
因此,区分用例间的关系是包含还是扩展,关键在于是不是必须操作。
类图
主要考察填类名、多重度、类之间的联系(泛化、组合、聚合、实现、依赖)
多重度含义如下:
1:表示一个集合中的一个对象对应另一个集合中1个对象。
0..*:表示一个集合中的一个对象对应另一个集合中的0个或多个对象。
1..*:表示一个集合中的一个对象对应另一个集合中的一个或多个对象。
*:表示一个集合中的一个对象对应另一个集合中的多个对象。 ...
E-R图和关系模式、E-R转换为关系模式、解题技巧、真题讲解
NULL
大纲
E-R图和关系模式
E-R图
E-R图:即实体-联系图,使用椭圆表示属性(一般没有)、长方形表示实体、菱形表示联系,联系两端要标注联系类型。
联系类型:一对一1:1、一对多1:N、多对多M:N。
实体和子实体(之间直接用直线连接,是从属关系,无联系类型)
多个实体一个类型(一般是三个实体连接到一个类型上,本质也是两两对应的联系关系,根据题目说明,若有三个实体相关,则是此种情况)
主键和外键(主键是本关系内唯一,外键是其他关系的主键,外键可以有多个)
关系模式
关系模式就是以名称和属性名表示一个联系,如下(空出来的数字是考法,要我们填的):
客户(客户ID、姓名、身份证号、电话、住址、账户余额)
员工(工号、姓名、性别、岗位、身份证号、电话、住址)
家电(家电条码、家电名称、价格、出厂日期、(1))
家电厂商(厂商ID、厂商名称、电话、法人代表信息、厂址、(2))
购买(订购单号、(3)、金额)
主键:不能为空,能唯一标识当前关系的属性。
外键:其他关系模式的主键或 ...
数据流图基本概念、数据流图设计原则、解题技巧、真题讲解
NULL
大纲
数据流图基本概念
数据流图
数据流图描述数据在系统中如何被传送或变换,以及如何对数据流进行变换的功能或子功能,用于对功能建模,数据流图相关概念如图:
数据流图是可以分层的,从顶层(即上下文无关数据流)到0层、1层等,顶层数据流图只含有一个加工处理表示整个管理信息系统,描述了系统的输入和输出,以及和外部实体的数据交互。数据流图示例如下:
顶层数据流图
描写的是**外部实体(长方形)和系统(圆角长方形)**之间的交互,而外部实体我们是不需要分析的
零层数据流图
是对顶层数据流图的进一步分析,其中操作是圆角长方形,数据存储是未封闭的长方形
外部实体
通常是人物、部门、系统等
数据存储
通常是记录、文件、清单等
数据字典
数据字典是用来定义在数据流图中出现的符号或者名称的含义,在数据流图中,每个存储、加工、实体的含义都必须定义在数据字典中,并且交图和子图之间这些名称要相同。示例如下:
数据流图的设计原则
基本设计原则
数据流图是一种重要的系统设计工具,其基本设 ...
面向对象基础、UML、设计模式
NULL
大纲
面向对象基础
面向对象基本概念
术语
定义
对象
基本的运行实体,通常是现实世界中的真实存在实体的抽象。每个对象封装了数据和行为的整体,例如学生、汽车等。对象具有清晰的边界,定义了良好的行为和可扩展性。
消息
消息是对象之间进行通信的方式。通过消息,一个对象可以请求另一个对象执行特定的行为。消息是对象之间交互的基本构建块。
类
类是对象的抽象,它定义了一组大致相似的对象结构,包括它们的数据和行为。有几种类型的类,包括实体类、边界类、控制类等。类模型还包括属性、操作和关联等元素。
继承
继承是一种机制,它允许一个类(子类)共享另一个类(父类)的数据和方法。子类继承了父类的属性和行为,可以根据需要扩展或修改它们。继承是类之间的一种关系。
多态
多态是指不同的对象在接收相同的消息时可以产生完全不同的响应。多态通过继承机制实现,包括参数多态、包含多态、过载多态、强制多态等。多态性提高了代码的灵活性。
覆盖
在子类中,可以通过重新定义与父类具有相同名称和参数的方法来覆盖(或重写)父类中的相应方法。子类可以 ...
系统分析与设计、需求分析、需求工程、结构化分析与设计、测试基础知识、系统运行与维护、软件架构介绍
SA,Structural Analysis,结构化分析
大纲
系统分析与设计
系统分析
系统分析是一种问题求解技术,它将一个系统分解成各个组成部分,自的是研究各个部分如何工作、交互,以实现其系统目标。
目的和任务:系统分析的主要任务是对现行系统进一光步详细调查,将调查中所得到的文档资料集中,对组织内部整体管理状况和信息处理过程进行分析,为系统开发提供所需的资料,并提交系统方案说明书。
主要步骤
认识、理解当前的现实环境,获得当前系统的“物理模型”。
从当前系统的“物理模型”抽象出当前系统的“逻辑模型”
对当前系统的“逻辑模型”进行分析和优化,建立目标系统的“逻辑模型”
对目标系统的逻辑模型具体化(物理化),建立目标系统的物理模型。
系统开发的目的是将现有系统的物理模型转换为目标系统的物理模型
系统设计
系统设计基本原理:
抽象(重点说明本质方面,忽略非本质方面);
模块化(可组合、分解和更换的单元);
信息隐蔽(将每个程序的成分隐蔽或封装在一个单 ...
软件工程概述、软件过程模型、软件开发方法、软件工具与软件开发环境、软件项目管理、软件风险管理、软件度量
CMM,Capability Maturity Model,能力成熟度模型
CMMI,Capability Maturity Model Integration,能力成熟度模型集成
大纲
软件工程概述
软件工程基本原理:用分阶段的生命周期计划严格管理、坚持进行阶段评审、实现严格的产品控制、采用现代程序设计技术、结果应能清楚的审查、开发小组的人员应少而精、承认不断改进软件工程实践的必要性。
软件工程的基本要素:方法、工具、过程。
软件生存周期:可行性分析与项目开发计划、需求分析、概要设计(选择系统解决方案,规划子系统)、详细设计(设计子系统内部具体实现)、编码、测试、维护。
软件过程
能力成熟度模型CMM
能力成熟度模型CMM:CMM是对软件组织成熟度阶段的描述,它随着软件组织定义、实施、测量、控制和改进其软件过程,逐步提高软件组织的能力。
CMM五级
CMM级别
描述
初始级(Initial)
软件过程杂乱无章,缺乏明确定义的步骤,项 ...
常用算法、数据挖掘、智能优化
ANN,Artificial Neural Network,人工神经网络
SA,Simulated Annealing,模拟退火
TS,Tabu Search,禁忌搜索
PSO,Particle Swarm Optimization,粒子群优化算法
常用算法
分治法
递归:指子程序(函数)直接调用自己活通过一系列调用语句间接调用自已,是种描述问题和解决快问题的常用方法。
递归两个基本要素:
边界问题:确定递归何时终止,即递归出口
递归模式:大问题如何分解成小问题,即递归体
示例:阶乘的定义
分治法:对于一个规模为n的问题,若该问题可以容易地解决则直接解决;否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解决这些子问题,然后将各子问题的解合并得到原问题的解
步骤:分解(将原问题分解成一系列子问题)一一求解(递归地求解各子问题,若子问题足够小,则直接求解)一一合并(将子问题的解合并成原问题的解)。
凡是涉及到分组解决的都是分治法(二分查找、归并排序等)。
回溯法
回溯法:有 ...
算法基础知识、算法分析基础、查找、排序、常用算法原理
NULL
考纲
算法基础知识
基本概念
算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。算法的五个重要特性如下:
算法分析基础
复杂度
上述的时间复杂度,经常考到,需要注意的是,时间复杂度是一个大概的规模表示,一般以循环次数表示,O(n)说明执行时间是n的正比,另外,log对数的时间复杂度一般在查找二叉树的算法中出现。渐进符号O表示一个渐进变化程度,实际变化必须小于等于O括号内的渐进变化程度。
查找
顺序查找:将待查找的关键字为key的元素从头到尾与表中元素进行比较,如果中间存在关键字为key的元素,则返回成功;否则,则查找失败
时间复杂度为O(n)
折半(二分)查找:设查找表的元素存储在一维数组r[1..n]中,在表中元素已经按照关键字递增方式排序的情况下,进行折半查找的方法是:
首先将待查元素的关键字(key)值与表r中间位置上(下标为mid)记录的关键字进行比较,若相等,则查找成功。
若key>r[mid].key,则说明待查记录 ...
线性结构,数组、矩阵和广义表,树与二叉树,图
NULL
考纲
线性结构
基本概念
每个元素最多只有一个出度和入度 ,表现为一条线状。线性表按照储存方式可分为顺序表和链表
储存结构
顺序存储:用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的元素物理上也相邻。
链式存储:存储各数据元素的结点的地址并不要求是连续的,数据元素逻辑上相邻,物理上分开。
线性表
顺序存储和链式存储对比
在空间方面,因为链表还需要存储指针,因此有空间浪费存在。
在时间方面,由顺表和链表的存储方式可知,当需要对元素进行破坏性操作(插入、删除)时,链表效率更高,因为其只需要修改指针指向即可,而顺序表因为地址是连续的,当删除或插入一个元素后,后面的其他节点位置都需要变动。
而当需要对元素进行不改变结构操作时(读取、查找),顺序表效率更高,因为其物理地址是连续的,如同数组一般,只需按索引号就可快速定位,而链表需要从头节点开始,一个个的查找下去。
单链表
单链表的插入和删除
在上图中p所指向的节点后插入s所指向的节点,操作为:
12s ...