公共基础1 - 图文

全国计算机等级考试

公共基础知识

1

第1章 数据结构与算法

1.1算法

1.1.1算法的基本概念

1、算法：是指解题方案的准确而完整的描述。

2、算法的基本特征：可行性、确定性、有穷性、拥有足够的情报 。

3、算法的基本要素：

一是对数据对象的运算和操作；

二是算法的控制结构。一个算法一般都可以用顺序、选择、循环三种基本控制结 构组合而成。

4、算法设计基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。

1.1.2算法复杂度

1、算法的复杂度主要包括时间复杂度和空间复杂度 。

（1）时间复杂度：执行算法所需要的计算工作量。用算法在执行过程中所需基本运算 的执行次数来度量算法的工作量。

（2）空间复杂度：一般是指执行这个算法做需要的内存空间。

1.2数据结构的基本概念

数据结构作为计算机的一门学科，主要研究和讨论一下三个方面的问题： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构

（2）在对数据进行处理时，各数据元素在计算机中的储存关系，即数据的存储结构 （3）对数据结构进行的运算

1.2.1什么是数据结构

1、数据结构是指反应数据元素之间关系的数据元素集合的表示。更通俗的说，数据结 构是指带有结构的数据元素的集合。在此，所谓的结构实际上是指数据元素之间的前后件 关系。

所以，一个数据结构应包含以下两方面的信息：

（1）表示数据元素的信息； （2）表示 各数据元素之间的前后件关系 。 2、所谓数据的逻辑结构，是指反应数据元素之间逻辑关系的数据结构。

数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了D中数据元素之间的前后件关系，通常记为R。即一个数据节后可以表示成B=（D，R），其中B表示数据结构。

3、数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。

2

1.2.2数据结构的图形表示

1、一个数据的结构除了用二元关系表示外，还可以直观的用图形表示。在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。

2、在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称 为叶子结点）。

1.2.3线性结构与非线性结构

1、根据数据结构中各数据元素之间前后件关系的复杂程度一般将数据结构分为两大类型： 线性结构与非线性结构。

2、如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点；

（2）每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构， 又称线性表。

3、特别说明：在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构满足上述两个条件，但当在此数据结构中插入或删除任何一个节点后就不满足这两个条件了，则该数据结构不能称为线性结构。

1.3线性表及其顺序存储结构 1.3.1线性表的基本概念

1、线性表是最简单、最常用的一种数据结构。 2、非空线性表有以下结构特征：

（1）有且只有一个根结点a，它无前件；

1 （2）有且只有一个终结点an，它无后件；

（3）除根结点与终结端外，其他所有结点有且只有一个前件，也有且只有一个后件， 线性表中结点的个数n称为为线性表长度，当n=0时，称为空表。

3

1.3.2线性表的顺序存储结构

1、在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。 2、线性表的顺序存储结构具有两个基本特点： （1）线性表中所有元素所占的存储空间是连续的；

（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

3、顺序表的插入、删除运算

1.4栈和队列 1.4.1栈及其基本运算

1、栈：是限定在一端进行插入与删除的线性表.

2、 在栈中，允许插入与删除的一端称为栈顶，而不允许插入 删除的一端称为栈底。栈顶元素总是最后被插入的元素，从而也是 最先被删除的元素；栈底元素总是最想被插入的元素，从而也是最 后才能被删除的元素。即栈是按照“先进后出”或“后进先出”的 原则组织数据的。因此，栈也被称为“先进后出” 表或“后进先出” 表。

3、栈中元素的个数=bottom-top+1 (用值大的减值小的再加一) 。 Top=0表示栈空 top=m表示栈满。

4、栈的基本运算有三种：入栈、退栈、与读栈顶元素。

1.4.2队列及其基本运算

1、队列：是指允许在一端进行插入、而在另一端进行删除的线性表。

2、在队列中，允许插入的一端称为队尾，通常用一个称为尾指针（Rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也称为对头），通常也用一个排头指针（Front）指向排头元素的前一个位置。显然，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之最后插入的元素将最后才能被删除。因此，队列称为“先进先出”或“后进后出”的线性表。

3、对列空与对列满的条件：队列空的条件为s=0，队列满的条件为s=1且ftont=rear 。

4

4、入队运算：是指在循环队列的队尾加入一个新元素

退队运算：是指在循环队列的排头位置退出一个元素并赋给指定的变量

1.5线性链表

1、线性表的链式存储式结构称为线性链表。 2、线性链表的基本运算： （1）在线性链表中查找指定元素；

（2）线性链表的插入：是指在链式存储结构下的线性表中插入一个新元素；

（3）线性链表的删除：是指在链式存储结构下的线性表中删除包含指定元素的结点。

1.6树与二叉树 1.6.1树的基本概念

1、树是一种简单的非线性结构。

2、树这种数据结构的基本特征：

（1）在树结构中每一个结点只有一个前件，称为父结点；没有前件的结点只有一个，称为树的根结点，简称为树的根。

（2）在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。

（3）在树结构中，一个结点所拥有的后件个数称为该结点的度。叶子结点的度为0；在树中，所有结点中的最大的度称为树的度。 3、树的最大层次称为树的深度。

4、在树中，以某结点的一个子结点为根构成的树称为该结点的一颗子树，叶子结点没有子树。

5

1.6.2二叉树及其基本性质

1、二叉树，是一种很有用的非线性结构。二叉树有以下两个特点： （1）非空二叉树只有一个根结点 ；

（2）每一个结点最多有两颗子树，每一个结点的度最大为2。 2、二叉树的基本性质：

（1）在二叉树的第k层上，最多有2的k-1次方（k>=1)个点； （2）深度为m的二叉树最多有2指二叉树共有m层）；

（3）在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个；

（4）具有n个结点的二叉树，其深度至少为【log2N】+1，其中【log2N】表示取其整数部分。

3、满二叉树与完全二叉树

（1）满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。

（2）完全二叉树：除最后一层外，每一层上的结点树均达到最大值，在最后一层上只缺少 右边的若干结点。

m?1个结点（深度为m的二叉树是

6

4、完全二叉树的性质：

（1）具有n个结点的完全二叉树的深度为【log2n】+1；

（2）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自 然数1，2，...，n给结点进行编号，则对于编号为k（k=1，2，...，n）的结点有以下结论： ①若k=1，则该结点为根结点，它没有父结点：若k>1，则该结点的父结点编号为INT（k/2）。

②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。

③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。

1.6.3二叉树的存储结构

1、计算机中二叉树通常采用链式存储结构。

1.6.4二叉树的遍历

1、二叉树的遍历：是指不重复地访问二叉树中的所有结点。

（1）前序遍历（DLR） 先访问根结点，然后遍历左子树，最后遍历右子树；在遍历左右子树时，仍先访问根结点，然后遍历左子树，最后遍历右子树。 （F C A D B E G H P）

（2）中序遍历（LDR）首先遍历左子树，然后访问根结点，最后遍历右子树；在遍历左右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 （A C B D F E H G P）

（3）后序遍历 （LRD）首先遍历左子树，然后遍历右子树，最后访问根结点；在遍历左右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。 （A B D C H P G E F）

1.7查找技术

1、顺序查找的基本方法：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等，则表示找到（即查找成功）；若线性表中的所有元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。

2、二分法查找只适用于顺序存储的有序表。设有序线性表的长度为n，被查元素为x，则对分查找的方法为：将x与线性表的中间项进行比较，若中间项的值等于x，则说明找到，查找结束；若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。

3、对于长度为n的有序线性表，在最坏情况下，二分法查找只需要比较log2N次，而顺序查找需要比较n次 。

7

1.8排序技术

1、交换类排序法：冒泡排序法、快速排序法。 2、插入类排序法：简单插入排序法、希尔排序法。 3、选择类排序法：简单选择排序法、堆排序法 。

8

本文来源：https://www.bwwdw.com/article/3ve5.html