计算机二级知识点

公共基础知识公共基础知识 数据结构和算法数据结构和算法 算法算法 算法是指解决方案准确而完备的描述 算法的基本特征：可行性、确定性、有穷性（算法程序的运行时间是有限的） 、拥有足够的 情报 算法的基本要素：算法对数据的基本运算和操作、算法的控制结构（顺序结构、选择结构、 循环结构） 算法的复杂度（较易考）算法的复杂度（较易考） 时间复杂度时间复杂度 是指执行执行算法所需的计算工作量计算工作量（而不是时间） 换言之，算法的时间复杂度是指执行该算法所需要的基本运算次数 空间复杂度空间复杂度 是指执行执行这个算法所需的内存空间 算法的时间复杂度与空间复杂度没有直接关系 数据结构的基本概念数据结构的基本概念 什么是数据结构什么是数据结构 事物的存在有两种形式：实体、关系 数据结构研究和讨论问题： 数据集合中各数据之间所固有的逻辑关系，即数据的逻辑结构 在对数据处理时，各数据在计算机中的存储结构，即数据的存储结构 对各种数据结构进行的运算 数据结构是指相互有关联数据元素集合的表示。数据结构是指相互有关联数据元素集合的表示。 更通俗地讲， 数据结构是带有结构地数据元 素的集合。 一个数据结构应该包含以下两方面内容： 表示数据元素信息即数据元素的集合，通常记为D 表示各数据元素之间的前后件关系， 通常记为R。 即一个数据结构可以表示为B= （D,R） 。 例如：B=（D,R）D={ 春、夏、秋、冬} R={ （ 春，夏 ） ， （ 夏，秋 ） ， （ 秋，冬 ）} 数据结构的图形表示数据结构的图形表示 一个数据结构除了用二元关系表示外， 还可以直观地用图形表示， 在数据结构的图形表示中， 对于数据集合 D 中的每一个元素用中间标有元素值的方框表示，一般称之为数据节点，并 简称为节点； 为了进一步表示各数据之间的前后件关系， 对于关系 R 中的每一个二元组， 用 一天有向线段从前件节点指向后件节点。 父亲 数据结构的图形表示 秋冬 夏 春 女儿 儿子 线性结构和非线性结构（重点）线性结构和非线性结构（重点） 如果一个非空的数据结构满足下列两个条件： 1)有且只有一个根节点 2)每一个节点最多有一个前件，也最多有一个后件。 则，称该数据结构为线性结构。 线性结构又称线性表。一个数据结构不是线性结构，则称为 非线性结构。 线性表的基本概念线性表的基本概念 线性表由一组数据元素组成。比如一年中的（春、夏、秋、冬） 。其中矩阵也是线性表。 非空线性表有如下结构特征： 1)有且只有一个根节点，它无前件； 2)有且只有一个终端节点（叶子节点） ，它无后件； 3)除根节点与终端节点外， 其他所有节点有且只有一个前件， 也有且只有一个后件。线性 表中节点个数 n 称为线性表的长度。当 n=0 时，称为空表。 线性表的顺序存储结构线性表的顺序存储结构 线性表的顺序存储结构具有以下两个基本特点： 1.线性表中所有元素所占的存储空间是连续连续的； 2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放按逻辑顺序依次存放的。 练习：练习： 1.下列叙述中正确的是（A） A.具有两个根节点的数据结构一定是非线性结构 B.存储空间连续的数据结构一定是线性结构二叉树 C.没有根节点的非空数据结构一定是线性结构 D.存储空间不连续的数据结构一定是非线性结构链表不连续， 是线性结构 2.在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数 相同，元素的存储 顺序与逻辑顺序一致。 栈和队列栈和队列 栈及其基本运算栈及其基本运算 栈顶 栈底 栈是限定在一端插入与删除的线性表。 允许插入与删除的一端称为栈顶（Top） ，而不允许插入与删除的另一端称为栈底 （Bottom） 。 栈是按照“先出后进”或“先进后出”的原则组织数据。 在栈的顺序存储空间 S（1：m）中，S（bottom）通常为栈底元素（在非空情况下） ，S （top）为栈顶元素。top=0 表示栈空；top=m 表示栈满。 入栈运算是栈顶插入一个元素， top=top+1.如果栈空间已满，不能再入栈。这种情况称 为“上溢”错误。 退栈运算是栈顶取出一个元素， top=top-1.如果栈空， 不能再退栈， 这种情况称为“下溢” 错误。 一般来说， top=0， 栈的开口向上， 元素的个数是 top； top=bottom+1， 栈的开口向下， 元素的个数是 bottom-top+1 队列及其基本运算队列及其基本运算 队列：队头删除元素、队尾插入元素的线性表 允许插入元素的一端称为队尾（Rear） ，允许删除元素的另一端称为队头（Front） 。 队列又称为“先进先出”或“后进后出”的线性表， 它体现了‘先来先服务”的原则。 在计算机 方面应用广泛。 队列的顺序存储结构一般采用循环队列的形式。循环队列是线性的。 在循环队列顺序存储空间Q（1：m） ，元素的个数为：Rear-Front,如果此值为负数，则 为： （Rear-Front）+m。如果 Rear-Front=0，则元素个数为 0 或 m。 入队运算是队尾加入元素即 Rear=Rear+1，并当 Rear=m+1，Rear 置于 1.如果队列已 满，不能进行入队运算，这种情况称为“上溢”错误。 退队运算时队头删除元素即 Front=Front+1，不能进行退队运算，这种情况称为“下溢” 错误。 1 2 3 练习练习 正确观点如下： 栈与队列都是线性结构 在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 在循环队列中，元素的个数是由队头指针和队尾指针共同决定的 循环队列中，队头指针可以大于队尾指针，也可以小于队尾指针 错在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况 误在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况 循环队列的存储空间为Q（1：60） ，初始状态为空。经过一系列正常的入队与退队操作 后，front=24，rear=25.循环队列中的元素个数为1 某循环队列的存储空间为Q（1：m） ，初始状态为 front=rear=m。现经过一系列的入队 操作和退队操作后，front=m，rear=m-1，则该循环队列中的元素个数为m-1 设循环队列存储空间为Q（1：50） ，初始状态为front=rear=50.经过一系列入队和退队 操作后，front=rear=25，则该循环队列中元素个数为0 或 50 设循环队列的存储空间为 Q（1：50） ，初始状态为 front=rear=50，现经过一系列入队 与退队操作后，front=rear=1，此后又正常地插入了两个元素，最后该队列中的元素个 数为 2 循环队列的存储空间为 Q（1：50） ，初始状态为人、front=rear=50.经过一系列正常的 入队与退队操作后， front=rear=25， 此后又插入了一个元素， 则循环队列中的元素个数 为 1 或 50 且产生上溢错误 设栈的顺序存储空间为 S （1： 50） ， 初始状态为 top=0.现经过一系列入栈与退栈运算后， top=20.则当前栈中元素个数为 20 设栈的顺序存储空间为 S（0:49）,栈底指针 bottom=4