全国计算机等级考试二级辅导讲义

看了 记会了 笔试肯定过 1.1 算法1、算法是指解题方案的准确而完整的描述。换句话说，算法是对特定问题求解步骤的一种描述。 *：算法不等于程序，也不等于 1.3 线性表及其顺序存储结构1、线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。线性表是由n(n≥0)个数据元素组成的一 等等 ### 全国计算机等级考试二级辅导讲义知识点详解 #### 一、算法基础 **算法定义** 根据《全国计算机等级考试二级辅导讲义》第一章的内容介绍，算法是指解题方案的准确而完整的描述，是对特定问题求解步骤的一种描述。需要注意的是，算法并不等同于程序或计算方法。一个优秀的程序往往依赖于良好的算法设计。 **算法的基本特征** 算法的基本特征包括可行性、确定性、有穷性和足够的输入情报： 1. **可行性**：执行算法后能得到预期的结果。 2. **确定性**：每一步操作都有明确的含义，对于同样的输入只有一种输出。 3. **有穷性**：算法必须在有限的时间内完成。 4. **足够的情报**：算法的执行结果依赖于充分的初始数据，不充分或错误的数据会导致算法失效。 **算法复杂度** 算法复杂度包括时间和空间两个方面： 1. **时间复杂度**：衡量执行算法所需的基本运算次数。 2. **空间复杂度**：执行算法所需的内存空间大小。 #### 二、数据结构概述 **数据结构定义** 数据结构是相互关联的数据元素集合。数据结构主要涉及数据的逻辑结构、存储结构以及对数据的操作。 **逻辑结构与存储结构** 1. **逻辑结构**：描述数据元素间的逻辑关系，包括数据元素本身的信息以及它们之间的前后件关系。 2. **存储结构**：描述数据在计算机中的存储方式，主要包括顺序存储、链接存储和索引存储。 - **顺序存储**：逻辑上相邻的结点存储在物理位置相邻的存储单元中。 - **链接存储**：结点间通过附加的指针字段表示逻辑关系。 - **索引存储**：通过额外的索引表来标识结点的地址。 **图形表示** 数据结构也可以通过图形直观表示，其中数据元素通常表示为带有元素值的方框，通过有向线段连接表示前后件关系。 **数据结构分类** 数据结构分为线性结构和非线性结构： 1. **线性结构**：满足特定条件的数据结构，例如线性表、栈、队列等。 2. **非线性结构**：不满足线性结构条件的数据结构，如树、二叉树、图等。 #### 三、线性表及其顺序存储结构 **线性表定义** 线性表是由一系列数据元素组成，数据元素的位置仅取决于自身的序号，元素间的相对位置是线性的。线性表的长度指的是表中数据元素的数量，线性表可以为空。 **顺序存储特点** 线性表的顺序存储结构具有以下特点： 1. **存储空间连续**：所有元素占据连续的存储空间。 2. **逻辑顺序一致**：数据元素在存储空间中的顺序与其逻辑顺序一致。 **插入与删除操作** 1. **插入操作**：在顺序表中插入新元素需要移动元素。例如，在第i个元素前插入新元素时，需要从第n个元素至第i个元素依次向后移动。 2. **删除操作**：删除指定位置的元素也需要移动元素。例如，删除第i个元素时，需要将第i+1至第n个元素向前移动一位。 **总结** 本讲义主要介绍了算法的基础知识、数据结构的概念及其分类，特别强调了线性表的顺序存储结构及其操作。这些知识点对于理解计算机科学中的数据组织和处理方式至关重要。通过学习这些内容，考生可以更好地准备全国计算机等级考试二级的相关部分。