文档介绍：二级C语言公共基础知识
数据结构与算法
主讲人:丁吉安
联系电话:********** QQ:32334692
全国计算机等级考试
二级C语言
笔试
公共基础知识(30分)
C语言知识(70分)
第一章数据结构与算法
1、算法是指解题方案的准确而完整的描述。换句话说,算法是对特定问题求解步骤的一种描述。(规则、有限步骤、具体步骤)
例如:判断 7 是不是素数
*算法不等于程序,也不等于计算方法。
2、算法的基本特征
算法
可行性
确定性
有穷性
拥有足够的情报
08年4月选择题第5题
算法的有穷性是指
A)算法程序的运行时间是有限的
B)算法程序所处理的数据量是有限的
C)算法程序的长度是有限的
D)算法只能被有限的用户使用
3、算法的基本要素。
(1)数据对象的运算和操作
算数运算:
逻辑运算
关系运算:
数据传输:包括赋值、输入、输出等
(2)算法的控制结构
算法中各种操作之间执行顺序称为控制结构,主要有顺序、选
择、循环三种基本控制结构。
4、算法复杂度主要包括时间复杂度和空间复杂度。
(1)算法时间复杂度是指执行算法所需要的计算工作量,和具体的计算机、程序设计语言和具体的程序是无关的。可以用执行算法的过程中所需基本运算的执行次数来度量。(基本语句的执行次数)
T(n)=O(F(n)) n是指问题的规模
(2)算法空间复杂度是指执行这个算法所需要的内存空间。
存储空间:算法程序+初始数据+额外空间
S(n)= O(F(n)) n是指问题的规模
06年9月选择题第7题
下列叙述中正确的是
A)一个算法的空间复杂度大,则其时间复杂度也必定大
B)一个算法的空间复杂度大,则其时间复杂度必定小
C)一个算法的时间复杂度大,则其空间复杂度必定小
D)上述三种说法都不对
例题2:设n为问题的规模,当描述该问题的基本语句执行次数为____时,其时间复杂度为O(log2 n)
A)n+ log2 n B)2log2 n C)nlog2 n D)n/log2 n
1、数据结构概念的引入
存储在计算中的大量数据如何组织,提高存储空间的利用率和数据的处
理效率,这是计算处理考虑的关键问题。基于对这个问题的考虑,出现
了数据结构的基本概念,主要研究以下三个问题:
(1)各个数据集合中的数据元素之间的逻辑关系(一般指前后关系)---逻辑结构
(2)在计算机上存储时的,各个元素之间的存储关系—物理结构
(3)在各个数据结构上进行的各种运算
数据结构引入目的:提高数据处理的效率,包括数据处理的速度和提高
存储空间的利用率
数据结构的基本概念
2、定义:数据结构是指相互有关联的数据元素的集合。
(1)逻辑结构:反映数据元素之间逻辑关系的数据结构。
表示为:B=(D,R)或者图形方式
主要有:线性结构、树形结构、图形结构、集合结构
(2)存储结构:数据的存储结构(也称数据的物理结构)是数据的逻辑结构在计算机存储空间中的存放形式。
同一种逻辑结构的数据可以采用不同的存储结构,但影响数据处理效率
主要有:顺序、链接、索引等结构
它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。
它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。
除建立存储结点信息外,还建立附加的索引表来标识结点的地址,称为索引结构。
07年4月选择题第1题
下列叙述中正确的是
A)算法的效率只与问题的规模有关,而与数据的存储结构无关
B)算法的时间复杂度是指执行算法所需要的计算工作量
C)数据的逻辑结构与存储结构是一一对应的
D)算法的时间复杂度与空间复杂度一定相关