第 1章 基础知识
1.1 计算机软件概述
1.2 操作系统的基本概念
1.3 算 法
1.1 计算机软件概述
1.1.1 计算机软件及其分类
计算机系统由计算机硬件系统和计算
机软件系统组成。
计算机硬件系统是指实际的物理设备，
包括计算机的主机和外围设备。
计算机软件系统，是指能指挥
计算机工作的程序、程序运行时所
需要的数据以及与这些程序和数据
有关的文字说明和图表资料。
其中文字说明和图表资料又称
为文档。
1．系统软件
系统软件是指管理、监控和维护计算
机资源 (包括硬件和软件 )，并提供用户与
计算机之间界面等工具的软件。
（ 1）操作系统
（ 2）程序设计语言与语言处理程序
（ 3）工具软件
2．应用软件
常见的应用软件有以下几种,
① 各种信息管理软件。
② 办公自动化系统。
③ 各种文字处理软件。
④ 各种辅助设计软件以及辅助教学软件。
⑤ 各种软件包，如数值计算程序库、图形
软件包等。
1.1.2程序设计语言及其语言处理程序
程序设计语言一般分为机器语言、汇
编语言和高级语言三类。
1．机器语言
机器语言是最底层的计算机语言。用
机器语言编写的程序，计算机硬件可以直
接识别。
2．汇编语言
汇编语言与机器语言一般是一一对应
的，用汇编语言编写的程序也比机器语言
程序易读、易检查、易修改。
将汇编语言源程序翻译成机器语言程
序的程序称为汇编程序。
3．高级语言
机器语言和汇编语言都是面向机
器的语言，一般称为低级语言。
面向问题的程序设计语言，称为
高级语言。
高级语言与具体的计算机硬件无
关，其表达方式接近于被描述的问题，
易为人们接受和掌握。
1.2 操作系统的基本概念
1.2.1 操作系统的功能与任务
操作系统是最基本的和核心的系统软
件 。
操作系统实际上是由一些程序模块组
成的，它们是系统软件中最基本的部分，
其主要作用有以下几个方面：
① 管理系统资源。
② 为用户提供资源共享的条件和环境，
并对资源的使用进行合理调度。
③ 提供输入 /输出的方便环境，简化
用户的输入 /输出工作，提供良好的用户界
面。
④ 规定用户的接口，发现、处理或报
告计算机操作过程中所发生的各种错误。
操作系统的功能和任务主要有以下
五个方面。
1．处理机管理
处理机管理的主要任务是：充分发
挥处理机的作用，提高它的使用效率。
2．存储器管理
存储器管理的主要任务是：对有限
的内存储器进行合理的分配，以满足多
个用户程序运行的需要。
3．设备管理
设备管理的主要任务是：有效地管理
各种外部设备，使这些设备充分发挥效率；
并且还要给用户提供简单而易于使用的接
口，以便在用户不了解设备性能的情况下，
也能很方便地使用它们。
4．文件管理
文件管理的主要任务是：实现惟一地
标识计算机系统中的每一组信息，以便能
够对它们进行合理地访问和控制；以及有
条理地组织这些信息，使用户能够方便且
安全地使用它们。
5．作业管理
它的主要任务是：对所有的用户作业
进行分类，并且根据某种原则，源源不断
地选取一些作业交给计算机去处理。
1.2.2 操作系统的发展过程
1．手工操作阶段
2．成批处理系统
3．执行程序系统
4．多道程序系统的引入
1.2.3 操作系统的分类
1．多道批处理操作系统
多道批处理操作系统包含“多道”和
“批处理”两层意思。
“多道”是指在计算机内存中存入多
个用户作业。
―批处理”是指这样一种操作方式，
在外存中存入大量的后备作业，作业
的运行完全由系统控制，用户与其作
业之间没有交互作用，用户不能直接
控制其作业的运行，通常称这种方式
为批操作或脱机操作。
2．分时操作系统
在分时操作系统中，多个用户分
享使用同一台计算机，即在一台计算
机上联接若干台终端，每个用户可以
独占一台终端。
分时操作系统具有以下几方
面的特点：
① 同时性。
② 独立性。
③ 及时性。
④ 交互性。
3．实时操作系统
所谓实时，是指对随机发生的外部
事件作出及时的响应并对其进行处理。
具有实时要求的系统称之为实时系
统。
4．通用操作系统
5．优良的操作环境
——多窗口系统
所谓多窗口，就是把计算机的显示
屏幕划分出多个区域，每个区域称为一
个窗口，每个窗口负责处理和显示某一
类信息。
向用户提供友好界面是多窗口系统主
要体现在以下几方面：
（ 1）灵活、方便的窗口操作
（ 2）弹出式菜单
（ 3）命令对话框
1.3 算 法
1.3.1 算法的基本概念
算法是指解题方案的准确而完整的
描述。
通常，算法又分为数值型算法与非
数值型算法。
非数值型算法又称为符号处理。
1．算法的基本特征
（ 1）可行性
① 算法中的每一个步骤必须能够
实现。
② 算法执行的结果要能够达到预
期的目的。
（ 2）确定性
算法的确定性（ Definiteness），是
指算法中的每一个步骤都必须是有明确
定义的 。
（ 3）有穷性
算法的有穷性（ Finiteness），是指
算法必须能在有限的时间内做完，即算
法必须能在执行有限个步骤之后终止。
（ 4）拥有足够的情报
2．算法的基本要素
一个算法通常由两种基本要素组成：
一是对数据对象的运算和操作，二是算法
的控制结构。
（ 1）算法中对数据的运算和操作
（ 2）算法的控制结构
1.3.2 算法描述语言
1．符号与表达式
符号是以字母开头的字母和数字的有
限串，主要用以表示变量名、数组名等，
必要时也用来表示语句标号。
在语句标号后应跟随一个冒号，然后
是语句。例如：
loop,i = i + 1
在算法中，算术运算符沿用数学中的
表示法。
关系运算符用 =,≠、＜、＞,≤,≥等
表示。
逻辑运算符用 and（与）,or（或）、
not（非）来表示。
2．赋值语句
赋值语句的形式为：
a = e
3．控制转移语句
无条件转移语句的形式为：
GOTO 标号
4．循环语句
循环语句有两种形式：一是 WHILE语
句，二是 FOR语句。
WHILE语句的形式为：
WHILE C DO S
FOR语句的形式为：
FOR i = init TO limit BY step DO S
5．其他语句
1.3.3 算法设计基本方法
1．列举法
列举法的基本思想是，根据提出的
问题，列举所有可能的情况，并用问题
中给定的条件检验哪些是需要的，哪些
是不需要的。
2．枚举归纳法
枚举归纳法的基本思想是，通过列举
足够多（但不是全部）的特殊情况，发现
其中的一些规律，经过分析，最后找出一
般的关系。
3．递推
递推是指从已知的初始条件出发，逐
次推出所要求的各中间结果和最后结果。
4．递归
这种将问题逐层分解的过程，实
际上并没有对问题进行求解，而只是
当解决了最后那些最简单的问题后，
再沿着原来分解的逆过程逐步进行综
合，这就是递归的基本思想。
由此可以看出，递归的基础也是
归纳。
递归分为直接递归与间接递归两种。
如果一个算法 P直接调用自己则称为直接
递归。
如果算法 P调用另一个算法 Q，而算法
Q又调用算法 P，则称为间接递归调用。
5．减半递推技术
“减半”是指将问题的规模减半，而
问题的性质不变。
“递推”是指重复“减半”的过程。
6．回溯法
1.3.4 算法的复杂度分析
算法的复杂度主要包括时间复杂度和
空间复杂度。
1．算法的时间复杂度
算法的时间复杂度，是指执行算法所
需要的计算工作量。
（ 1）平均性态分析
平均性态分析 (Average Behavior)，是
指用各种特定输入下的基本运算次数的带
权平均值来度量算法的工作量。
（ 2）最坏情况复杂性分析
最坏情况分析 (Worst–Case
Complexity)，是指在规模为 n时，算法所
执行的基本运算的最大次数。
2．算法的空间复杂度
一个算法的空间复杂度，一般是指执
行这个算法所需要的内存空间。
