以下为《二级考试笔记(公共基础)B》的无排版文字预览,完整格式请下载
下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。
二级考试笔记(公共基础)B
第一章:数据结构与算法
01算法(是指解题方案的准确而完整的描述)算法不等于程序
·算法的基本特征:可行性、确定性、有穷性、足够的情报
算法的基本要素:1对数据对象的运算和操作:算术运算、逻辑运算、关系运算、数据传输
2算法的控制结构:A算法中各操作之间的执行顺序
B描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言
C一个算法一般可以用顺序、选择、循环三种基本结构组合而成
·时间和空间复杂度(算法的时间复杂度和算法的空间复杂度相互独立)
算法的时间:是指执行算法所需要的计算工作量,可以用算法所执行的基本运算次数度量
算法的空间:是指执行算法所需要的内存空间。包括算法程序、输入的初始数据以及算法执行过程中需要的额外空间。
02数据结构的基本概念
·数据:需要处理的数据元素的集合,一般来说,这些数据元素,具有莫个共同的特征
·数据元素是数据的基本单位,及数据集合中的个体
·有时一个数据元素可由若干数据项(Data Item)组成。数据项是数据的最小单位
·结构:所谓“结构”,是集合中各个数据元素之间存在的莫种关系(或联系)
·数据结构:是指相互有关联的数据元素的集合
·数据结构的逻辑结构:指反映数据元素之间的逻辑关系(即前后件关系)的数据结构
·逻辑结构:线性结构(线性表):1有且只有一个根节点,它无前件
2每一个节点最多有一个前件,也最多有一个后件
非线性结构:不满足以上两个条件的数据结构就称为非线性结构,树形结构和网状结构
·数据结构的分类:逻辑顺序:(线性结构:线性表、栈、队列/非线性结构:树,图)
存储结构(顺序存储/链式存储)
运算(插入,删除,查找,排序)
·数据结构的存储结构:
【又称为数据的物理结构,是数据的逻辑结构在计算机存储空间中的存放方式】
1 顺序存储结构:主要用于线性的数据结构,它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里
2链式存储结构:每一个节点至少包含一个指针域,用指针的指向来体现数据元素之间在逻辑上的联系
(1一种逻辑结构可以有多种存储结构。2不同的存储结构其数据处理的效率不同。)
03线性表:(是n(n"g0)个数据元素构成的有限序列,表中除第一个元素外的每一个元素,有且只有一个前件,除最后一个元素外,有且只有一个后件)
例如:英文字母表、地理学中的四向、表格
·线性表的顺序储存结构(又称顺序表)
特点:1线性表中所有元素所占的存储空间是连续的;
2线性表中数据元素在存储空间中是按逻辑顺序依次存放的
3可以随机访问数据元素
4做插入、删除是移动大量元素,因此线性表不便于插入和删除元素
04栈和队列
· 栈:是限定在一端进行插入和删除的线性表。
(栈底指针bottom、栈顶指针top、入栈、栈满、出栈)
特点:1栈是智能在栈顶进行插入和删除
2栈的修改原则是“先进后出”或“后进先出”
3栈底指针不变,栈中元素随栈顶指针的变化而动态变化
4栈具有记忆功能
5栈支持子程序调用
· 队列:是指允许在一端进行插入,而在另一端进行删除的线性表。原则是:先进先出(或后进后出)【对头指针front、队尾指针rear、入队、出队】
特点:1队列只允许在队尾进行插入,而在队头进行删除。
2队列的修改原则是“先进先出”或“后进后出”
3队列中元素随队头指针和队尾指针的变化而动态变化
·循环队列:是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间
Real>fornt s=R-F 2、real0)个元素的有限集合,它有且仅有一个称为根的元素;其余元素是互不相交的子树。【父结点、子结点、根结点、叶子结点、结点的度、树的度、树的深度、子树】
二叉树:是一个有限的结点集合,该集合或者为空,或者由一个根结点及其两棵互不相交的左右二叉子树所组成(五种基本形态)
特点:1非空二叉子树只有一个跟结点;
2每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树
①在二叉树的第k层上,最多有2k-1个结点
②深度为m的二叉树最多有2m-1个结点
③度为0的结点(叶子结点)总比度为2的结点多一个
④有n个结点的二叉树深度至少为[3? n]+1
二叉树的遍历:前序遍历:根左右 中序遍历:左某某 后序遍历:左右根
特殊二叉树:满二叉树:除最后一层外,每一层的结点数均达到最大值
完全二叉树:除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点
07顺序查找:对于长度为n的线性表,平均要进行n/2次比较,在最坏情况下进行n次比较(顺序查找适应于无序表或链式线性表,不管有序、无序)
二分查找:适用于顺序存储的有序表,对长度为n的线性表,在最坏情况下进行3? n次比较(不能采用链式储存结构)
08排序技术
排 序
平均时间
最坏情况
交换类
冒泡排序
n(n-1)/ 2
n(n-1)/ 2
快速排序
n(n-1)/ 2
n(n-1)/ 2
插入类
插入排序
n(n-1)/ 2
n(n-1)/ 2
希尔排序
n3? n
N1.5
选择类
选择排序
n(n-1)/ 2
n(n-1)/ 2
堆排序
n3? n
n3? n
09快速排序
基本思想:1在要排序的序列中找一个作为基准数(通常为第一个数)
2通过交换将这个序列中所有比基数大的数放在右边,比基数小的放在左边
3以基准数为分割线分为两个子表,对两个子表重复上述步骤
第二章程序设计基础
01程序设计方法与风格
良好的程序设计风格:清晰第一,效率第二
HOW:1源程序内部文档化(a选择标识符的名字b注释{【序言性(位于模块的首部,说明模块的信息);功能性:位于源程序模块内部】c程序的视觉组织)
2数据说明 3语句的结构 4输入与输出
02结构化程序设计:
原则:自项向下、逐步求精、模块化、限用goto
基本结构:顺序、选择(分支)、循环
基本成分:数据成分、运算成分、控制成分、传输成分
03面向对象的程序设计
对 内容过长,仅展示头部和尾部部分文字预览,全文请查看图片预览。 两种方法:面向数据的方法:以信息需求为主,兼顾处理需求
面向过程的方法:以处理需求为主,兼顾信息需求
数据库设计步骤:生命周期法(需求分析阶段:建立数据字典、概念设计阶段:设计E-R图、逻辑设计阶段:把E-R图转换为关系模式。实体与联系表示成关系,E-R图中属性转换成关系的属性、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段)
(在数据设计中采用前四个阶段,并且重点以数据结构与模型的设计为主线)
数据库管理:数据库的建立、数据库的调整、数据库的重组、数据库安全性控制与完整性控制、数据库的故障修复、数据库监控
[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]
以上为《二级考试笔记(公共基础)B》的无排版文字预览,完整格式请下载
下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。