计算机二级考(笔试)复习资料 公共基础知识

《计算机二级考(笔试)复习资料 公共基础知识》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一、算法1.算法基本概念：算法是在有限的步骤内求解某一问题所使用的一组定义明确的法则。通俗的说就是计算机解决问题的过程（计算方法），这个过程中无论是形成解题思路（推理实现的算法）还是编写程序（操作实现的算法），都是实施某种算法。算法是一组逻辑步骤程序是用计算机语言描述的算法2.算法特征：输入（初始条件）、确定性（每一计算步骤都有确切的定义）、有穷性（算法必须保证执行有限步结束）、可行性（算法原则上能精确计算，而且人用纸笔做有限次运算后即可完成）、输出（没输出的结果无意义）。3.算法的表示：传统算法----

2、-图形法（如流程图）目前常用方法------伪代码表示4.算法的基本要素：①对数据对象的运算和操作（算数运算、关系运算、逻辑运算、数据传输）②算法的控制结构（顺序、选择、循环）5.算法的基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法6.算法的评价：时间复杂度（执行这个算法所需的计算工作量）空间复杂度（执行这个算法所需的内存空间）算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。二、数据结构程序=算法+数据结构数据结构是指相互有关联的数据元素的集合。包括三个方面：数据结构中

3、各数据元素之间所固有的逻辑关系，即数据的逻辑结构；在对数据进行处理时，各数据元素在计算机中的储存关系，即数据的储存结构；对各种数据结构进行计算。1.逻辑结构数据的逻辑结构是指反映数据元素之间关系的数据结构。数据的逻辑结构包含：1）表示数据元素的信息2）表示各数据元素之间的前后关系。常见的逻辑结构有：线性结构（结构中每个元素存在一个对一个的关系）、树形结构（存在一个对多个的关系）、图形结构（存在多个对多个的关系）。其中树形结构和图形结构统称为非线性结构。2.存储结构（物理结构）储存结构是指数据结构在存储空间

4、中的具体实现。只抽象的反应数据元素之间的关系的结构，而不管其储存方式的数据结构称为逻辑结构。各数据元素在计算机中的储存位置与他们的逻辑关系不一定是相同的。而且一般是不同的。一种数据结构可以根据需要而选择一种或多种存储结构常见的存储结构有：顺序存储结构、链式存储结构、索引存储结构。3.数据的运算检索、插入、删除、更新、排序常见的数据结构1.线性表线性表是由n(n>=0)个数据元素组成的一个有限的序列（如：春→夏→秋→冬）线性表的存储结构有两种：顺序存储结构、链式存储结构线性表的链式存储结构称为线性链表。链式

5、存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且个数据元素的存储位置也是任意的。各数据元素的先后关系是由各节点的指针域指示。链式存储结构每一个存储结点不仅是存储节点的值，而且存储结点之间的关系6采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量的域元素移动。循环链表是链式存储结构的一种，特点是表中最后一个节点的指针域指向头结点。双向链表的结点中有两个指针域，其中一个直接指向直接后继，另一个直接指向直接前趋。线性表的存储结构有两种：顺序存储结构、链式存储结构。数据元素在计算机存储空

6、间中的位置关系域与他们的逻辑关系不一定是相同的。一个逻辑数据结构可以有多种存储结构而且不同的存储结构影响数据处理的效率。1.栈和队列A）栈是一种特殊的线性表其特点是插入和删除运算都只能在线性表的一端进行。栈是按照“先进后出”或“后进先出”的原则组织数据的线性表。栈的物理存储结构可以用顺序结构，也可以用链表结构。栈的基本运算只有三种：入栈、退栈、和读栈项元素。B）队列是一种特殊的线性表其特点是：所有的插入在线性表的一端进行，所有的删除运算都在表的另一端进行。即在表的前端进行插入操作，在表的后端进行删除操作。

7、（队列进行插入运算的是队首，进行删除运算的队尾）队列是按照“先进先出”或“后进后出”的原则组织数据的线性表。即最先插入的元素是最先删除的元素，最后插入的是最后删除的。队列有三种运算：入队、出队、读队首元素。循环队列：把队列的存储空间在逻辑上看成一个环，当R指向存储空间的末端时，就把它重新置于始端。线性表（线性结构）、栈（特殊的线性表）、队列（是一种操作受限制的线性表）、树（是一种重要的非线性数据结构）非线性结构：一个数据结构不是线性结构就是非线性结构。线性结构的特点：①有且仅有一个根节点②除第一个结点外，

8、每一个结点最多有一个直接前驱节点③除最后一个接点外，每一个结点最多有一个直接后缀结点。3.树与二叉树树的概念树的定义，n个结点的有限集。根只有一个。如果n=0则称之为空树，否则当n>1时，其余结点被分成m(m>0)个互不相交的子集，每个子集又是有一棵树。树型结构的常用术语：结点的度（一个结点子树的个数）；树的度（树中所有结点度的最大值）；终端结点（度为零的结点）；非终端结点（度不为零的结点）；节点的层次（树中根节点的层次为1，