计算机公共基础知识要点

《计算机公共基础知识要点》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第1章数据结构与算法　　（1）算法的基本特征　　算法一般具有4个基本特征：可行性、确定性、有穷性、拥有足够的情报。　　（2）算法的基本运算和操作　　算法的基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。　　（3）算法的3种基本控制结构　　算法的3种基本控制结构是：顺序结构、选择结构、循环结构。　　（5）指令系统　　所谓指令系统指的是一个计算机系统能执行的所有指令的集合。　　2.算法复杂度　　算法复杂度包括时间复杂度和空间复杂度。注意两者的区别，无混淆，见表1-1。表1-1算法复杂性名称描述时间复杂度执行算法所需要的计

2、算工作量空间复杂度执行这个算法所需要的内存空间1.2数据结构　　（2）数据结构研究的3个方面　　①数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；　　②在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；　　③对各种数据结构进行的运算。　　3.存储结构　　一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接等存储结构。　　顺序存储方式主要用于线性的数据结构　　链式存储结构就是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系。　　1.2.2线性结构和非线性结

3、构　　根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。　　（1）如果一个非空的数据结构满足下列两个条件：　　①有且只有一个根结点；　　②每一个结点最多有一个前件，也最多有一个后件。　　则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都为线性结构。　　如果一个数据结构不是线性结构，则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。　　（2）线性表的顺序存储结构具有以下两个基本特点：　　①线性表中所

4、有元素所占的存储空间是连续的；　　②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。　　（3）顺序表的运算有查找、插入、删除3种。　1．4　队列的顺序存储结构一般采用队列循环的形式1.5链表　　在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。　　链式存储方式既可用于表示线性结构，也可用于表示非线性结构。　　（1）线性链表　　线性表的链式存储结构称为线性链表。1.6二叉树　　1.6.1二叉树概念及其

5、基本性质　　1.二叉树及其基本概念　　二叉树是一种很有用的非线性结构，具有以下两个特点：　　①非空二叉树只有一个根结点；　　②每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。　　在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树。另外，二叉树中的每个结点的子树被明显地分为左子树和右子树。　　在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即为叶子结点。　　例如，一个家族中的族谱关系如图1-1所示：　　A有后代B，C；B

6、有后代D，E；C有后代F。　　典型的二叉树如图1-1所示：　　详细讲解二叉树的基本概念，见表1-2。图1-1二叉树图父结点（根）在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。例如，在图1-1中，结点A是树的根结点。子结点和叶子结点在树结构中，每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。例如，在图1-1中，结点D，E，F均为叶子结点。度在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。例如，在图1-1中，根结点A和

7、结点B的度为2，结点C的度为1，叶子结点D，E，F的度为0。所以，该树的度为2。深度定义一棵树的根结点所在的层次为1，其他结点所在的层次等于它的父结点所在的层次加1。树的最大层次称为树的深度。例如，在图1-1中，根结点A在第1层，结点B，C在第2层，结点D，E，F在第3层。该树的深度为3。子树在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。表1-2二叉树的基本概念　　1.6.2二叉树的遍历　　在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历分为三类：中序前

8、序遍历、遍历和后序遍历。　　（1）前序遍历　　先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左、右子树时，仍需先访问根结点，然后遍历左子树，最后遍历右子树。例如，对图1-1中的二叉树进行前序遍历的结果（或称为该二叉树的前序序列）为：A，B，D，E，C，