计算机国二office公共基础知识

第1章 数据结构与算法（10-12分）考点：算法(****)数据结构(***)线性表及其顺序存储结构(**)栈和队列(*****)线性链表(**)树与二叉树(*****)查找技术(****)排序技术(

第1章 数据结构与算法（10-12分） 考点： 1. 算法() **** 2. 数据结构() *** 3. 线性表及其顺序存储结构() ** 4. 栈和队列() ***** 5. 线性链表() ** 6. 树与二叉树() ***** 7. 查找技术() **** 8. 排序技术() *** 一、数据结构与算法 1、概念 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作 2、数据的逻辑结构 ● 线性结构(例：一维数组、链表、栈、队列、串、线性表) ● 非线性结构(例：多维数组、广义表、树、图) 3、数据的存储结构(线性表) ● 顺序存储方法：线性表中所有元素所占的存储空间是连续的;线性表中各数据元素在存储空间中 是按逻辑顺序依次存放的 ● 链接存储方法：逻辑上相邻的结点，物理上也相邻，存储单元可以是连续的，也可以是不连续的 ● 计算机中有数据进行处理时，数据的存储结构对程序的执行效率有很大的关系 ● 一种数据的逻辑结构根据需要可以表示成多种存储结构。数组是数据的逻辑结构，可以用多种存 储结构来表示 ● 线性链表：就是指线性表的链式存储结构，简称链表 4、算法的基本特征 ● 可行性：针对实际问题而设计的算法，执行后能够得到满意的结果 ● 确定性：算法中的每一个步骤都必须有明确的定义，不允许出现歧义性 ● 有穷性：算法必须在有限时间内做完，即必须在执行有限个步骤之后终止，算法程序的运行时间 是有限的 ● 拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才 最有效的；而当提供的情报不够时，算法可能无效 5、算法的复杂度 ● 时间复杂度：该算法执行的时间耗费，是指执行算法所需要的计算工作量，即算法执行过程中所 需要的基本运算次数 ● 空间复杂度：该算法执行时所耗费的存储空间 6、顺序表和链表的比较： 基于空间的考虑：(1)顺序表的存储空间是静态分配的，而链表的存储空间是动态分配的。(2)顺序表 占的存储空间必须是连续的，而链表占的存储空间可以是连续的，也可是不连续的 二、栈 出栈 入栈 ● 栈实际也是线性表，只不过是一种特殊的线性表。栈称为“” 先进后出 表或“”表，顺序存储、链式存储 后进先出 top 栈顶 D ● 栈的计算：求栈中元素的个数： 栈底元素—栈顶元素 ● 栈是限定在一端进行插入与删除的线性表，允许插入元素的一端为栈顶， C 允许删除元素的一端为栈底，栈顶元素总是最后被插入的元素，也是最 B A bottom 栈底