文档介绍：1 公共基础全国计算机等级考试大纲要求,各种笔试除了要考 70 分的程序设计相关知识外,还要考 30 分的公共基础知识,包括基本数据结构与算法、程序设计基础、软件工程基础和数据设计基础。本章将介绍这些基础知识。 数据结构与算法 算法本节重点掌握算法的基本概念和典型算法的时间复杂度。 1 、基本考点 1 )算法基本概念算法:是指解题方案的准确而完整的描述。算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。算法的基本特征: 是一组严谨地定义运算顺序的规则, 每一个规则都是有效的, 是明确的,此顺序将在有限的次数下终止。特征包括: (1) 可行性: 通过已实现的基本运算执行有限次而完成;(2) 确定性: 算法中每一步骤都必须有明确定义,不允许有模棱两可的解释,不允许有多义性;( 3) 有穷性:算法必须能在有限的时间内做完, 即能在执行有限个步骤后终止, 包括合理的执行时间的含义;(4) 拥有足够的情报。算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。算法的控制结构:顺序结构、选择结构、循环结构。算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。算法复杂度:算法时间复杂度和算法空间复杂度。算法时间复杂度: 指执行算法所需要的计算工作量。一般来说, 算法的工作量用其执行的基本运算次数来度量, 而算法执行的基本运算次数是问题规模的函数,用O( f(n) ) 表示。在同一个问题规模下,用平均性态和最坏情况复杂性来分析。一般情况下,用最坏情况复杂性来分析算法的时间复杂度。算法空间复杂度是指执行这个算法所需要的内存空间。 2 )查找算法顺序查找的使用情况: (1 )线性表为无序表(不管是顺序存储结构还是链式存储结构); (2 )表采用链式存储结构(即使是有序线性表)。二分法查找只适用于顺序存储的有序表。对于长度为 n 的有序线性表, 二分查找最坏情况只需比较 log2 n次, 顺序查找需要比较 n 次。 3 )排序算法 2 排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。(1 )交换类排序法: 假设线性表的长度为 n 冒泡排序法:在最坏情况下,需要比较的次数为 n(n-1)/2 ; 快速排序法:在最坏情况下,需要比较的次数为 n(n-1)/2 (2 )插入类排序法: 简单插入排序法,最坏情况需要 n(n-1)/2 次比较; 希尔排序法,最坏情况需要 O(n ) 次比较。(3 )选择类排序法: 简单选择排序法, 最坏情况需要 n(n-1)/2 次比较; 堆排序法,最坏情况需要 O(nlog 2 n) 次比较。 2 、重要考点详解(1) 对于长度为 n 的线性表,在最坏情况下,下列各排序法所对应的比较次数中正确的是______ 。 A) 冒泡排序为 n/2 B) 冒泡排序为 n C) 快速排序为 nD) 快速排序为 n(n-1)/2 解析: 国二级考试中涉及的排序算法( 冒泡排序法、快速排序法、简单插入排序法、希尔排序法、简单选择排序、堆排序法), 只有“堆”排序和“希尔”排序不是 n(n-1)/2 , 其它都是 n(n-1)/2 。堆排序是 O(nlog2 n) ,希尔排序是 O(n )。(2) 对于长度为 n 的线性表进行顺序查找,在最坏情况下所需要的比较次数为_______ 。 A) log 2nB) n/2 C)nD) n+1 解析: 最坏的情况是要找的元素在最后一个或不在序列中, 所以要把 n 个元都比较一下。(3) 下列叙述中正确的是______ 。 A )对长度为 n 的有链序表进行查找,最坏的情况需要比较次数为 n。 B )对长度为 n 的有链序表进行对分查找,最坏的情况需要比较次数为( n/2 )。 C )对长度为 n 的有链序表进行对分查找,最坏的情况需要比较次数为( log 2 n)。 D )对长度为 n 的有链序表进行对分查找,最坏的情况需要比较次数为( n log 2 n)。解析: 二分查找(对分查找)只能用于顺序存储的有序表,所以只有 A 是对的。(4) 对长度为 10 的线性表进行冒泡排序,最坏情况下需要比较的次数为 45。解析: n(n-1)/2=10*9/2=45 数据结构 1 、基本考点本节主要内容是数据结构的三要素: 数据的逻辑关系、在计算机中的存储关系、与存储关系对应的运算。栈、队列的数据结构(逻辑关系、存储关系、运算)。 1)数据结构数据结构研究的三个方面: (1) 数据集合中各数据元素之间所固有的逻辑关系, 即数据的逻辑结构;(2) 在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;( 3 )对各种数据结构进行的运算。数据结