计算机等级考试二级公共基础知识讲义.docx

PAGE 15 PAGE  计算机等级考试二级公共基础知识讲义 数据结构与算法 算法 算法定义：解题方案的准确而完善的描述。 算法的基本特征：①可行性 ②确定性 ③有穷性 ④拥有足够的情报 算法的基本要素：①算法中对数据的运算和操作：包括算术运算、逻辑运算、关系运算、数据传输。②算法的控制结构：包括顺序结构、选择结构、循环结构 算法设计的基本方法：①列举法 ②归纳法 ③递推 ④递归 ⑤减半递推技术 ⑥回溯法 算法的复杂度：包括时间复杂度和空间复杂度 算法的时间复杂度：执行算法所需要的计算工作量。 算法的空间复杂度：执行这个算法所需要的内存空间大小。 数据结构 数据结构学科主要研究内容：①数据的逻辑结构，数据集合中各数据元素之间所固有的逻辑关系。②数据的存储结构，在对数据进行处理时，各数据元素在计算机中的存储关系。③对各种数据结构进行的运算。 数据结构学科的研究目的：提高数据处理的效率。包括：①数据处理速度。②尽量节省在数据处理过程中所占用的计算机存储空间。 数据处理：对数据集合中的各元素以各种方式进行运算。 数据元素：每一个需要处理的对象都可以抽象为数据元素。 数据结构：相互关联的数据元素的集合。 一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构。常用的存储结构有顺序、链接、索引等存储结构。 线性结构和非线性结构 线性结构满足如下条件：①有且仅有一个根结点。②每一个结点最多有一个前件，也最多有一个后件。③在一个线性结构中插入或删除任何一个结点后还是线性结构。 如果一个数据结构不是线性结构，则称之为非线性结构。 线性表及其顺序存储结构 线性表定义：线性表是由n(n=0)个数据元素a1,a2……, an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。 非空线性表结构特征：①有且只有一个根结点a1，它无前件。②有且只有一个终端结点an,它无后件。③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 线性表的长度：线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。 线性表的顺序存储结构的基本特点：①线性表中所有元素所占的存储空间是连续的。②线性表中个数据元素在存储空间中是按逻辑顺序一次存放的。 线性表的主要操作：①线性表的插入 ②线性表的删除 ③线性表的查找 ④线性表的排序 ⑤线性表的分解 ⑥线性表的合并 ⑦线性表的复制 ⑧线性表的逆转 栈和队列 栈及其基本运算 栈的定义：栈是限定在一端进行插入和删除的线性表。它按照“后进先出”的原则组织数据。 栈的顺序存储及其运算：在程序设计语言中，一般是用一维数组S(1:m)作为栈的顺序存储空间，其中m为栈的最大容量。 栈的基本运算： ①入栈运算：首先将栈顶指针加1，然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能在进行入栈操作。此时发生栈“上溢”错误。 ②退栈运算：首先将栈顶元素赋给一个指定的变量，然后将栈顶指针减1。当栈顶指针为0时，说明栈空，不可能进行退栈操作。此时，发生栈“下溢”错误。 ③读栈顶元素：将栈顶元素赋给一个指定的变量，栈指针不变。当栈顶指针为0时，说明栈空，读栈顶元素操作失败。 队列及其基本运算 队列的定义：是指允许在一端进入插入、而在另一端进入删除的线性表。它按照“先进先出”的原则组织数据。 循环队列空的状态：s=0,且 front=rear=m 循环队列满的状态：s=1,且 front=rear 循环队列的基本运算： ①入队运算：首先将队尾指针加1(rear=rear+1)，并当rear=m+1时置rear=1;然后将新元素插入到指针指向的位置。当循环队列满时（s=1,且front=rear）入队操作将引起“上溢”错误。 ②退队运算：首先将排头指针加1(front=front+1)，并当front=m+1时置front=1;然后将排头指针指向的元素赋给指定的变量。当循环队列为空时（s=0,front=rear），退队操作将引起“下溢”错误。 线性链表 线性链表的基本概念：线性表的链式存储结构称为线性链表。 线性链表 ①线性链表的链式存储结构：线性链表的每个结点中数据域存放数据元素的值，指针域存放后后件结点的存储地址。 ②双向链表的链式存储结构：双向链表的链式存储结构比线性链表的链式存储结构多出一个指针域，它用来存放前件结点的存储地址。 带链的栈 栈的链式结构：栈的链式结构基本上和线性链表的链式存储结构相同。只是线性链表的链式存储结构的头指针变成了栈的链式结构的栈顶指针。 带链的队列 队列的链式结构：保持两个指针，一个指向队列头的指针和一个指向队列尾的尾指针。 线性链表的主