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

计算机二级公共基础知识总结
数据结构与算法
算法
算法:是对特定问题求解步骤的一种描述,是指令的有限序列,其中每一条指令表示一个或多个操作。
算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。
算法的基本特征:
(1)可行性;
(2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性;
(3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义;
(4)一个或多个输入;零个或多个输出
(5)拥有足够的情报。
算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。
指令系统:一个计算机系统能执行的所有指令的集合。
基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构:顺序结构、选择结构、循环结构。
算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。
算法复杂度:算法时间复杂度和算法空间复杂度。
名称
描述
时间复杂度
执行算法所需要的计算工作量
空间复杂度
执行算法所需要的内存空间
数据结构的基本基本概念
数据结构:
是只相互有关联的数据元素的集合。
数据结构研究的三个方面:
(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构
(2)在对数据进行处理时,各数据元素在计算机中存储的形式,即数据的存储结构
(3)对各种数据结构进行的运算
数据的逻辑结构(即数据元素之间所固有的逻辑关系)包含:
(1)表示数据元素的信息; D
(2)表示各数据元素之间的前后间关系。 R
B=(D,R)
数据的存储结构(即在对数据进行处理时,各数据元素在计算机中存储的形式),主要有顺序存储和链式存储。
顺序存储:是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。
链式存储:是在每个结点中必须包含一个指针域,用指针来体现数据元素之间逻辑上的关系
数据结构分为两类:线性结构和非线性结构
满足线性结构条件:
(1)有且只有一个根结点;
(2)每一个结点最多有一个前件,也最多有一个后件。
注:在一个线性结构中插入或删除任何一个结点,还是线性结构。栈、队列、串、线性链等都是线性结构。
满足非线性结构的条件:不满足线性结构条件的数据结构。
注:数组、广义表、二叉树、树和图等都是非线性结构。
线性表及其顺序存储结构
线性表:线性表由若干数据元素构成的有限序列,表中除第一个元素外,有且只有一个前件,除最后一个元素外,有且只有一个后件。
在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。
非空线性表的结构特征:
(1)且只有一个根结点a1,它无前件;
(2)有且只有一个终端结点an,它无后件;
(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。
线性表的顺序存储结构具有以下两个基本特点:
(1)线性表中所有元素的所占的存储空间是连续的;
(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
ai的存储地址为:ADR(ai)=ADR(a1)+(i-1)k,,ADR(a1)为第一个元素的地址,k代表每个元素占的字节数。
顺序表的运算:插入、删除。
顺序表的插入运算:在一般情况下,要在第i(1≤i≤n)个元素之前插入一个新元素时,首先要从最后一个(即第n个)元素开始,知道第i 个元素之间共有n-i+1个元素一次向后移动一个位置,移动结束后,第i 个位置就被空出,然后将新元素插到第i 项。插入后,线性表的长度就增加的1.
顺序表的删除运算:在一般情况下,要删除第i(1≤i≤n)个元素时,则要从第i+1个元素开始,直到第n 个元素之间共有n-i个元素一次向前移动一个位置。删除后,线性表的长度就减少了1.
栈和队列
栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。
栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom表示栈底。
栈的基本运算:
入栈运算:在栈顶插入一个新元素
退栈运算:取出栈顶元素并赋给一个指定变量
读栈顶元素:将栈顶元素赋给一个指定的变量,此时指针无变化。
队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。允许进行删除运算的一端叫队头,允许进行插入运算的一端叫队尾。Rear为尾指针,front为头指针。
队列是“先进先出”(FIFO)