计算机二级公共基础知识数据结构与算法

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表示队列已满