计算机二级公共基础知识总结

数据结构和算法

1算法

算法:是指对解的准确完整的描述。
算法不等于程序，也不等于计算机方法。程序的编程不可能比算法的设计更好。
算法的基本特征:它是一组严格定义运算顺序的规则。每一条规则都是有效且明确的，这个序列将在有限的次数内终止。特点:
(1)可行性；
(2)确定性，算法中的每一步都必须定义清楚，不允许有模棱两可的解释或歧义；
(3)是有限的，算法必须在有限的时间内完成，即在有限步数后可以终止，包括合理执行时间的含义；
(4)掌握足够的信息。
算法的基本要素:一、数据对象的运算和操作；二是算法的控制结构。
指令系统:计算机系统可以执行的所有指令的集合。
基本运算和操作包括:算术运算、逻辑运算、关系运算和数据传输。
算法的控制结构:顺序结构、选择结构、循环结构。
算法的基本设计方法:枚举法、归纳法、递归、递归、桶归约递归技术、回溯法。
算法复杂度:算法时间复杂度和算法空复杂度。
算法的时间复杂度是指执行算法所需的计算量。
算法间的复杂度空是指执行这个算法所需的内存空。

2数据结构的基本概念

数据结构研究的三个方面:
(1)一个数据集中数据元素之间的内在逻辑关系，即数据的逻辑结构；
(2)处理数据时，计算机中各数据元素的存储关系，即数据的存储结构；
(3)对各种数据结构的操作。
数据结构是指相互关联的数据元素的集合。
数据的逻辑结构包括:
(1)表示数据元素的信息；
(2)表示数据元素之间的上下文关系。
数据的存储结构包括顺序、链接、索引等。
线性结构条件:
(1)只有一个根节点；
(2)每个节点最多有一个前部，最多有一个后部。
非线性结构:不满足线性结构条件的数据结构。

3线性表及其顺序存储结构

线性表是由一组数据元素组成的，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
在复杂的线性表中，由几个数据元素组成的数据元素称为一条记录，而由多条记录组成的线性表也称为一个文件。
非空线性表的结构特征是:
(1)只有一个根节点a1，没有前件；
(2)终端节点an只有一个，没有后继；
(3)除了根节点和终端节点，其他所有节点都只有一个前件，也只有一个前件。节点数n称为线性表的长度，当n=0时称为空表。
线性表的顺序存储结构有以下两个基本特征:
(1)线性表中所有元素的存储空是连续的；
(2)线性表中的数据元素按逻辑顺序存储在存储室空。
AI的存储地址是:adr(ai)=adr(a1)+(i-1)k，其中adr(a1)是第一个元素的地址，k代表每个元素的字节数。
序列表的操作:插入和删除。(详见第14-16页)

4个堆栈和队列

堆栈是一个线性表，仅限于一端插入和删除。允许插入和删除的一端称为栈顶，不允许插入和删除的另一端称为栈底。
Stack按照“filo”或者“lifo”来组织数据。堆栈具有记忆功能。Top表示堆栈的顶部位置，bottom表示底部位置。
栈的基本操作:(1)插入元素称为push操作；(2)删除元素称为弃栈操作；(3)读取栈顶元素是将栈顶元素赋给指定的变量。此时，指针不变。
Queue指的是一个线性表，允许在一端(队列的末端)插入，在另一端(队列的头部)删除。后面的指针指向队列的末尾，前面的指针指向队列的开头。
Queue是fifo或lilo的线性表。
队列操作包括(1)入队操作:从队列末尾插入一个元素；(2)退出操作:从队列的头部删除一个元素。
循环队列:s=0表示队列空，s=1，front=rear表示队列已满。

5线性链表

数据结构中的每个节点对应一个存储单元，简称存储节点。
节点由两部分组成:(1)用于存储数据元素的值，称为数据字段；(2)用于存储指针，称为指针字段，用于指向上一个或下一个节点。
在链式存储结构中，存储数据结构的存储空可以是不连续的，每个数据节点的存储顺序可以与数据元素之间的逻辑关系不一致，这是由指针字段决定的。
链存储可用于表示线性和非线性结构。
线性链表，head称为头指针，head=null(或0)称为空表。如果是两个指针，左指针(llink)指向前节点，右指针(rlink)指向后节点。
线性链表的基本操作:查找、插入、删除。

6树和二叉树

树是一种简单的非线性结构，所有元素都具有明显的层次特征。
在树形结构中，每个节点只有一个前件，称为父节点，只有一个没有前件的节点，称为树的根节点。每个节点可以有多个后继节点，这些后继节点称为该节点的子节点。没有后继节点的节点称为叶节点。
在树形结构中，一个节点拥有的后继数称为该节点的度，所有节点的度称为树的度。树的层次称为树的深度。
二叉树的特点:(1)非空二叉树只有一个根节点；(2)每个节点最多有两个子树，称为该节点的左子树和右子树。
二叉树的基本性质:
(1)在二叉树的第k层上，最多有2k-1(k≥1)个节点；
(2)深度为m的二叉树最多有2m-1个节点；
(3)度为0的节点(即叶节点)总比度为2的节点多一个；
(4)具有n个节点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分；
(5)n节点完全二叉树的深度为[log2n]+1；
(6)设一棵完全二叉树有n个节点。如果从根节点开始并用自然数1、2，...n按顺序排列(每层从左到右)(k=1，2...n)，得出以下结论:
①如果k = 1，则该节点是根节点，它没有父节点；如果k>1，则该节点的父节点号为int(k/2)；
②如果2k≤n，编号为k的节点的左子节点号为2k；否则，该节点没有左子节点(或右子节点)；
③若2k+1≤n，编号为k的节点的右子节点号为2k+1；否则，该节点没有正确的子节点。
满二叉树是指除最后一层外，每层上的所有节点都有两个子节点，所以k层上有2k-1个节点，深度为m的满二叉树有2m-1个节点。
完全二叉树是指除了最后一层，每一层的节点数都达到值，最后一层只缺少右边的几个节点。
二叉树存储结构采用链式存储结构，全二叉树和完全二叉树可以顺序存储。
二叉树的遍历:
(1)先序遍历(dlr)，先访问根节点，然后遍历左子树，最后遍历右子树；
(2)在顺序遍历(ldr)中，先遍历左边的子树，然后访问根节点，最后遍历右边的子树；
(3)后序遍历(lrd)首先遍历左子树，然后访问右子树，最后访问根节点。

7搜索技术

搜索序列的用法:
(1)线性表是无序的；
(2)表格采用链式存储结构。
二分搜索法仅适用于顺序存储的有序表。对于长度为n的有序线性表，最坏情况下只需要log2n次。

8分类技术

排序是指将一个无序的序列按照值的非降序排序成有序的序列。
交换排序法:(1)冒泡排序法，要比较的次数是n(n-1)/2；(2)快速排序法。
插入排序法:(1)简单插入排序法，最坏情况下需要n(n-1)/2次比较；(2)希尔排序法，最坏情况需要o(n1.5)次比较。
选择排序法:(1)简单选择排序法，
最坏的情况需要n(n-1)/2次比较；(2)堆排序法，最坏的情况需要o(nlog2n)次比较。