小编所收集到的相关计算机二级公共基础知识数据结构与算法重点讲解的资料 大家要认真阅读哦!
◆算法的基本概念
1.算法:是对问题处理方案的正确而完整的描述,是求解问题的方法,是指令的有效序列。
2. 具有5个特性:
(1) 有穷性(在有穷步后完成)算法程序的运行时间是有限的
(2) 确定性(每一步都有确定的含义)
(3) 可行性
(4) 输入(一个算法有零个或多个输入)
(5) 输出(一个算法有一个或多个输出)
3. 算法的复杂度
包括:时间复杂度和空间复杂度。 二者没有必然的联系。
时间复杂度:执行算法所需要的计算工作量或基本运算次数。
空间复杂度:算法所需要的空间的度量。
◆数据结构的定义
1. 数据结构包括数据的逻辑结构、数据的存储结构、数据的操作
数据的逻辑结构:数据的外部结构,指各数据元素之间的逻辑关系,反映人们对数据含义的解释。 包括:线性结构(线性表、栈、队列)和非线性结构(树和图)
数据的存储结构:数据的物理结构,指数据的逻辑结构在计算机中的表示。
一个逻辑结构可以有多种存储结构。
◆ 线性表:线性表中元素的个数n(n>=0)定义为线性表的长度。
顺序存储是线性表的一种最常用的存储方式。
线性表的顺序存储结构和线性表的链式存储结构分别是随机存取的存储结构和顺序存取的存储结构。
1.栈:是限定在表尾进行插入和删除操作的线性表。 具有记忆功能 只能顺序存储(错)
允许插入和删除的一端叫栈顶。另一端叫栈底。
后进先出的线性表
2队列:是限定在一端插入而在另一端删除,插入端叫队尾,删除端叫对头。
先进先出的线性表
3栈和队列的顺序存储结构
循环队列属于线性表存储结构中顺序存储结构和链式存储结构的前者。
◆ 树
1.定义:树的结点、度(结点的度)、叶子(终端结点)、数的度、深度、有序树和无序数
2.二叉树:结点至多有两棵子树,并且二叉树的子树有之分,次序不能颠倒。
性质:★在二叉树的第i层上至多有2i-1个结点
★ 深度为k的二叉树至多有2k-1个结点。
★ 对任一个二叉树T,如果其叶子(终端结点数)为n,度为二的结点数为m,则n=m
+1.
★ 具有n个结点的完全二叉树的深度为k+1,其中k是㏒2n的整数部分。
2. 二叉树的遍历
▼先序遍历(根—左—右)
▼中序遍历(左—根—右)
▼后序遍历(左—右—根)
◆查找算法
(1)顺序查找
顺序查找的平均查找长度为(n+1)/2,最坏的情况下比较的次数为n
(2) 二分查找
限定于顺序存储的有序线性表
◆排序算法
(1)插入类排序
▲直接插入排序
▲折半插入排序
▲希尔排序
(2)交换类排序
▲冒泡排序 最坏情况下的比较次数n(n-1)/2
▲快速排序 最坏情况下的比较次数n(n-1)/2
(3)选择类排序
文字很枯燥,但内容却很丰富,小编在此祝大家都能考出让自己满意的成绩哦!
继续了解公共基础知识?点击下方链接,进入考无忧官方网站,更多精彩等你来!
小编特别推荐二级ms office可以了解一下噢! 毕竟这项科目着实相比其他科目比较容易啦!
文章推荐:
温馨提示:
想要了解更多试题请点击查看>>>计算机二级考试题库
考试想拿高分吗?更多二级ms office试题请点击查看>>>二级ms office
想知道更多关于计算机等级考试的最新资讯吗?点击进入>>>计算机等级考试