文档介绍：第四章 软件基础
第2页
计算机二级考试公共基础知识
基本数据结构与算法()
程序设计基础
软件工程基础
数据库设计基础(教材第8章自学)
二级考试科目分成二级语言程序设计(C、C++、Java、Visual Basic)和二级数据库程序设计(Visual FoxPro、Access)两类。
公共基础知识在各科笔试中的比重为30%
()
第3页
算法
⒈算法的基本概念
⒉算法的表示
⒊常用算法
⒋算法的评价
一、基本数据结构与算法
数据结构
⒈数据结构的概念
⒉线性表
⒊栈和队列
⒋树与二叉树
⒌查找技术
⒍排序技术
第4页
对解题方案准确而完整的描述称为算法。
程序——用计算机语言描述的算法
流程图——图形化的算法(机械图)
算法是程序设计的核心
⒈算法的基本概念
INPUT r
S=r*r*
PTINT S
开始
输入R
S=R*R*
输出S
结束
问题:
输入园的半径,计算园的面积
起止框
输入输出框
处理
框
第5页
算法分为两类:
数值计算算法
求数值解
特点:少量的输入、输出,复杂的运算
非数值计算算法
数据处理
特点:大量的输入、输出,简单的运算
第6页
算法的两个要素:
操作
算术运算
关系运算
逻辑运算
数据传输
控制结构
顺序
选择
循环
第7页
算法的基本特征
是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。
有穷性
确定性
可行性
输入
输出
算法在执行有穷步骤后结束,且每一步都能在有限时间内完成。
算法中的每一步操作的内容和顺序必须含义确切,不能有二义性。
算法中的每一步操作都必须是可执行的,也称之为有效性。
算法中有零个或多个输入。这些输入数据应在算法操作前提供。
算法的目的是用来解决一个给定的问题,因此,它应向人们提供产生的结果。
拥有足够的情报
第8页
⒉算法的表示
描述算法的方法有多种:
自然语言
传统流程图
N-S流程图
伪代码
计算机语言
第9页
A
C
B
变量C是一个临时工作单元,用来保存中间结果。
⒊算法举例
⑴两个变量的值交换
有红、蓝两个墨水瓶,要求将其互换。
C=B
B=A
A=C
高级语言语句实现
第一步
第二步
第三步
第10页
⑵计数器和累加器
计数器(统计60分以下0分以上的人数)
i=i+1
累加器sum=sum+x
输入X
X<60
i=i+1
输出i
0→i
X<0
y
y
输入X
SUM=SUM+X
输出SUM
0→SUM
X<0
y
问题:求阶乘用什么算法?
n
n