计算机公共基础知识

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

1、第一章数据结构与算法1.1算法的复杂度1.算法的基本概念（1）.算法的基本特征一般具有四个基本特征：可行性。确定性，有穷性，拥有足够的情报（2）算法的基本运算和操作包括:算术运算，逻辑运算，关系运算，数据运算。（3）控制结构顺序结构，循环结构，选择结构。（4）设计方法列举法，归纳法，递推，递归，减半递推技术，回溯法。（5）指令系统是指一个计算机系统能执行的所有指令的集合。2算法复杂度空间复杂度执行算法所需要的计算工作量时间复杂度执行这个算法所需要的内存空间1.2数据结构1.2.1数据结构和存储结构1）逻辑结构中就是二元组的表示；2)存储结构数据的逻辑结构在计算机存储空间的存放形式顺序存储方式

2、主要用于线性数据逻辑的数据存放在物理相同的存储单元里。节点间的关系由存储单元的邻接关系体现链式存储方式每个节点至少包括一个指针域，用指针来体现数据元之间逻辑上的关系1.2.2线性结构和非线性结构按数据结构中各数据元素之间前后件关系的复杂程度：线性结构和非线性结构线性结构的特征（非空数据结构）：1.有且只有一个根节点2.每一个结点最多有一个前件，也最多有一个后件线性结构栈，队列，串非线性结构数组，广义表，树，图线性表的顺序存储结构基本特点：1.所有元素所占的存储空间是连续的2.各数据元素在存储空间中按逻辑顺序依次存放顺序表的运算：查找、插入、删除。1.3栈（是一种特殊的线性表）基本特征：一端封

3、闭，一端开口（允许插入和删除元素）开口端是栈顶，封闭端是栈底。空栈（表中无元素）栈的数据组织原则：先进后出，后进先出。基本运算、；入栈，退栈，读栈顶元素。1.4队列只允许在一端（队头）进行删除，另一端（队尾）进行插入元素。空队列（表中无元素）。队列数据组织原则：先进先出。后进后出。队列运算：入队运算在队尾插入元素退队运算在队尾删除元素队列的顺序存储结构：队列循环（循环队列s=0（队列空）；s=1且front=tear（队列满）计算队列元素个数：尾指针减头指针，若为负数，加上其容量。1.5链表链式存储方式中：每个结点由两个部分表示：一部分存放数据元素值，另一部分存放指针。指针指向结点的前件或后

4、件。链式存储结构既可以表示线性结构，又可表示非线性结构。（1）、线性链表（线性表的链式存储结构0）双向链表：每个结点设置两个指针。一个指向前件结点（Llink），一个指向后件结点（Rlink）。单向链表，HEAD是头指针，HEAD=NULL(或0)是空表。线性链表的特征：1、各数据元素结点的存储空间可以不连续2、各数据元素的存储顺序与逻辑顺序可以不一致线性链表的运算：查找，插入和删除（无需移动链表的元素）。带链的栈:可以收集计算机存储空间所有空闲的存储结点，称为可利用栈。1.3二叉树基本特点：1.非空二叉树只有一个根节点2．每一个结点最多两个子树，左子树和右子树。根结点没有前件的结点子结点和

5、叶子结点每个结点的后件称为子结点，没后件的结点称为叶子结点度一个结点拥有的后件个数称为该结点的度。所有结点中最大的度称为树的度深度多少层次的子结点加上父结点层次子树每个子结点为根的树构成子树二叉树的性质：1）、k层上。最多有2∟k-1【k≥1】个结点。2）、深度为m的二叉树最多(2∟m)-1个结点。　　　　　　3）、任意一棵二叉树，度为0的结点总比度为2的结点多一个。4）、具有n个结点的二叉树。深度至少为㏒2∟m）+1，其中（㏒2∟m）表示其整数部分。满二叉树和完全二叉树满二叉树：除最后一层外，每层的所有结点都有两个子结点。每层结点数达到最大值，满二叉树的第K层上有2∟（k-1）个结点。深度

6、为M的满二叉树有(2∟m)-1个结点。完全二叉树：除最后一层外，每层的结点数达到最大值，最后一层上只缺少右边的若干结点。1.6.2二叉树的遍历分为三类：前序遍历，中序遍历，后序遍历。前序遍历：先根节点→左子树→右子树。中序遍历：先左子树→跟结点→右子树。后序遍历：先左子树→右子树→根结点。1.7查找1）、顺序查找两种特殊情况只能用顺序查找：（1）、线性表为无序表，不管是顺序或链式存储结构，都只能用顺序查找；（2）、有序表中，采用了链式存储结构，只能使用顺序查找。2）、二分法查找使用的两个条件：1、使用顺序存储结构；2、线性表是有序表。（有序指元素按从小到大排列）长度为n的有序线性表，在最坏的

7、情况下，需比较㏒2∧n。1.6排序1、交换类排序法（1）、冒泡排序法从表头往后扫描线性表，逐次比较相邻两个元素大小，并互换位置。反之。直至剩下的线性表为空为止。最坏的情况下。需比较n（n-1）/2。（2）、快速排序法选取某个元素为基准，然后比较大小分为两个子序列，然后让子序列进行顺序排列，直至整个序列有序。2、插入类排序法①、简单插入排序法，最坏情况需要n（n-1）/2次比较。②、希尔排序法，最坏情况需要O（