二级考试笔记(公共基础)B

本文由用户“hwgxy”分享发布 更新时间:2022-01-18 07:31:37 举报文档

以下为《二级考试笔记(公共基础)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》的无排版文字预览,完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。

图片预览