文档介绍：全国计算机等级考试二级公共基础知识
中国海洋大学青岛学院
学习方法
逻辑推理运算必须理解
概念性、理论性知识点要加强记忆
适当记忆一些名词
与所学的VF程序设计知识结合起来,以增加对知识的理解能力
做大量习题
中国海洋大学青岛学院
一、数据结构与算法
考点提示:
1. 算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。
2. 数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。
3. 线性表的定义;线性表的顺序存储结构及其插入与删除运算。
4. 栈和队列的定义;栈和队列的顺序存储结构及其基本运算。
5. 线性单链表、双向链表与循环链表的结构及其基本运算。
6. 树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。
7. 顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序)。
中国海洋大学青岛学院
算法
算法:
是指解题方案的准确而完整的描述。
算法不等于程序,也不等于计算方法;算法是解题思路,而程序是解题思路的在其编译环境中的具体描述。
算法的特征:
(1)可行性:在具体环境中可执行和正确与否
(2)确定性:每一步必须有明确的定义
(3)有穷性:在有限步骤(时间)内执行完毕
(4)拥有足够的情报:初始数据或初始状态必须要充足且正确。
中国海洋大学青岛学院
算法的基本要素:
一是对数据对象的运算和操作(四类)
二是算法的控制结构(各操作之间的执行顺序)。
基本运算和操作包括:
算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构:
顺序、选择、循环。
算法设计的基本方法:
列举法、归纳法、递推、递归、减半递推技术、回溯法。
中国海洋大学青岛学院
算法复杂度:
算法时间复杂和算法空间复杂度。
算法时间复杂度:
是指执行算法所需要的计算工作量(运算的执行次数)。
衡量算法时间复杂度的主要因素:
 一方面依赖于问题的规模,(如N×N矩阵乘法运算,f(n)=O(n3))
另一方面,某些情况下还和问题的输入数据集有关(如冒泡排序),此时用两种方法分析:
(1)平均性态:用基本运算次数的加权平均值来衡量----A(n)=
(2)最坏情况复杂性:最大执行次数
----W(n)=
中国海洋大学青岛学院
算法空间复杂度:
是指执行算法所占用的空间,包括算法程序所占用的空间、输入的初始数据所占用的空间、算法执行过程中所需要的额外空间。
算法设计的要求:
(1)正确性 (2)可读性 (3)健壮性
(4)效率与低存储量需求
中国海洋大学青岛学院
例题
算法的时间复杂度是指______。A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数
算法的空间复杂度是指______。A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 执行算法所需要的空间
下面叙述正确的是______。A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令(或语句)的条数C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对
(C)
(D)
(C)
中国海洋大学青岛学院
算法一般都可以用哪几种控制结构组合而成______。A. 循环、分支、递归B. 顺序、循环、嵌套C. 循环、递归、选择D. 顺序、选择、循环
在下列选项中,哪个不是一个算法一般应该具有的基本特征______。A. 确定性 B. 可行性 C. 无穷性 D. 拥有足够的情报
算法的时间复杂度取决于_____。A. 问题的规模 B. 待处理数据的初态
C. 问题的难度 D. A和B
在计算机中,算法是指______。A. 查询方法B. 加工方法C. 解题方案的准确而完整的描述D. 排序方法
(D)
(C)
(D)
(C)
中国海洋大学青岛学院
数据结构的基本概念
数据结构:
反映数据元素之间关系的表示。
数据结构研究的三个方面:
(1)各数据元素之间所固有的逻辑关系,即数据的逻辑结构;
(2)各数据元素在计算机中的存储关系,即数据的存储结构;
(3)对各种数据结构进行的运算。
数据的逻辑结构:
(1)表示数据元素的信息;
(2)表示各数据元素之间的前后件关系。
数据的逻辑结构是个数据元素之间固有的,是与计算机硬件没有关系结构