计算机二级access考点

计算机二级access考点1.1 算法和数据结构的基本概念1.算法（1）算法的基本概念算法是指解题方案的准确而完整的描述。

A.算法的基本特征：①可行性；②确定性；③有穷性；④拥有足够的情报。

B.算法的基本要素：①算法中对数据的运算和操作：基本的运算和操作包括算术运算、逻辑运算、关系运算和数据传输；②算法的控制结构：基本的控制结构包括顺序结构、选择结构、循环结构。

C.算法设计的基本方法：①列举法；②归纳法；③递推；④递归；⑤减半递推技术；⑥回溯法。

（2）算法的复杂度算法的复杂度主要包括时间复杂度和空间复杂度。

A.算法的时间复杂度：是指执行算法所需要的计算工作量。

算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数。

即：算法的工作量=f(n)其中n是问题的规模。

B.算法的空间复杂度：一般是指执行这个算法所需要的内存空间。

一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占用的存储空间以及算法执行过程中所需要的额外空间。

2.数据结构的基本概念数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：①数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；②在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；③对各种数据结构进行的运算。

（1）数据结构的定义①数据结构是指相互有关联的数据元素的集合。

②数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。

③数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。

④数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。

常用的存储结构有顺序、链接、索引等存储结构。

（2）数据结构的图形表示在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。

（3）线性结构与非线性结构如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。

则称该数据结构为线性结构。

如果一个数据结构不是线性结构，则称为非线性结构。

1.2 线性表和线性链表1.线性表（1）线性表的基本概念线性表（Linear List）是最简单、最常用的一种数据结构。

线性表是由n(n≥0)个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。

（2）线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点：①线性表中所有元素所占的存储空间是连续的；②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

（3）顺序表的插入运算在线性表采用顺序存储结构时，如果插入运算在线性表的末尾进行，即在第n个元素之后（可以认为是在第n+1个元素之前）插入新元素，则只要在表的末尾增加一个元素即可，不需要移动表中的元素；如果要在线性表的第1个元素之前插入一个新元素，则需要移动表中所有的元素。

（4）顺序表的删除运算在线性表采用顺序存储结构时，如果删除运算在线性表的末尾进行，即删除第n个元素，则不需要移动表中的元素；如果要删除线性表中的第1个元素，则需要移动表中所有的元素。

2.线性链表（1）线性链表的基本概念在线性链表中，各数据元素之间的前后件关系是由各结点的指针域来指示的，指向线性表中第一个结点的指针HEAD称为头指针，当HEAD=NULL（或0）时称为空表。

（2）线性链表的基本运算线性链表的运算主要有：线性链表的插入、删除、查找、合并、分解、逆转、复制、排序等。

①在线性链表中查找指定元素在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法如下：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。

当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。

②线性链表的插入为了在线性链表中插入一个新元素，首先要给该元素分配一个新结点，它可以从可利用栈中取得。

然后将存放新元素值的结点链接到线性链表中指定的位置。

③线性链表的删除为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。

（3）循环链表及其基本运算①在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。

循环链表的头指针指向表头结点。

②循环链表中最后一个结点的指针域不是空，而是指向表头结点。

1.3 栈和队列1.栈及其基本运算栈是一种特殊的线性表，在这种线性表的结构中，一端是封闭的，不允许进行插入与删除元素；另一端是开口的，允许插入与删除元素。

在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其他数据元素的。

在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。

栈是按照“先进后出”（FILO—First In Last Out）或“后进先出”（LIFO—Last In First Out）的原则组织数据的。

栈的基本运算有三种：入栈、退栈与读栈顶元素。

2.队列及其基本运算（1）队列（queue）是指允许在一端进行插入、而在另一端进行删除的线性表。

队列又称为“先进先出”（FIFO—First In First Out）或“后进后出”（LILO—Last In Last Out）的线性表。

（2）循环队列及其运算在实际应用中，队列的顺序存储结构一般采用循环队列的形式。

所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

循环队列主要有两种基本运算：入队运算与退队运算。

1.4 树与二叉树1.树的基本概念树（tree）是一种简单的非线性结构。

在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。

2.二叉树的定义及其存储结构（1）二叉树的定义二叉树具有以下两个特点：①非空二叉树只有一个根结点；②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

（2）二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。

在二叉树中，由于每一个元素可以有两个后件（即两个子结点），因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。

3.二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。

二叉树的遍历可以分为：①前序遍历（DLR）首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

②中序遍历（LDR）首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。

③后序遍历（LRD）首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

1.5 查找技术和排序技术1.查找技术查找是数据处理领域中的一个重要内容，查找的效率将直接影响到数据处理的效率。

（1）顺序查找在进行顺序查找过程中，如果线性表中的第一个元素就是被查找元素，则只需做一次比较就查找成功，查找效率最高；但如果被查的元素是线性表中的最后一个元素，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况。

在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。

（2）二分法查找二分法查找只适用于顺序存储的有序表。

在此所说的有序表是指线性表中的元素按值非递减排列。

对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较次，而顺序查找需要比较n次。

2.排序技术（1）交换类排序法交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。

冒泡排序法与快速排序法都属于交换类的排序方法。

假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。

在快速排序过程中，随着对各子表不断地进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行再分割处理，需要将暂时不分割的子表记忆起来，这就要用一个栈来实现。

（2）插入类排序法插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中。

在简单插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。

在最坏情况下，简单插入排序需要n(n-1)/2次比较。

（3）选择类排序法选择排序法的基本思想是扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。

简单选择排序法在最坏情况下需要比较n(n-1)/2次。

第2章程序设计基础2.1 程序设计方法与风格程序设计是一门技术，需要相应的理论、技术、方法和工具来支持。

就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。

程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。

著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。

要形成良好的程序设计风格，应注重和考虑这些因素：①源程序文档化；②数据说明的方法；③语句的结构；④输入和输出。

2.2 结构化程序设计1.结构化程序设计的原则结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句。

2.结构化程序设计的基本结构与方法的应用结构化程序设计的三种基本结构分别是：顺序结构、选择结构和循环结构。

在结构化程序设计的具体实施中，要注意把握如下要素：①使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；②选用的控制结构只准许有一个入口和一个出口；③程序语句组成容易识别的块，每块只有一个入口和一个出口；④复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；⑤语言中所没有的控制结构，应该采用前后一致的方法来模拟；⑥严格控制goto语句的使用。

2.3 面向对象的程序设计1.关于面向对象方法面向对象方法的优点：①与人类习惯的思维方法一致；②稳定性好；③可重用性好；④易于开发大型软件产品；⑤可维护性好。

2.面向对象方法的基本概念①面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。