计算机软件技术基础知识点总结

《计算机软件技术基础》

第一章 算法

1.1算法的基本概念

算法：指解题方案的准确而完整的描述

算法的基本特征：

能行性（算法中的每一个步骤必须能够实现；算法执行的结果要能够达到预期的目的）

确定性（算法中的每一个步骤都必须是有明确定义的，不能摸棱两可，也不能有多义性）

有穷性（算法必须能在执行有限个步骤之后终止）

拥有足够的情报（算法执行的结果总是与输入的初始数据有关。不同输入对应不同输出）

算法：是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的、明确的，此顺序将在有限的次数下终止。

算法的基本要素：

1.算法中对数据的运算和操作（算术运算、逻辑运算、关系运算、数据传输【赋值、输入、输出】）

2.算法的控制结构（算法中各操作之间的执行顺序）

1.2算法描述语言

C语言描述和简单的算法描述语言

（1）符号与表达式：符号主要用以表述变量名、数组名等

（2）赋值语句

（3）控制转移语句：

无条件转移语句形式：GOTO 标号

条件转移语句形式 IF C THEN S

IF C THEN S1

ELSE S2

（4）循环语句

WHILE语句：WHILE C DO S

FOR语句：FOR i=init TO limit BY step DO S

（5）其他语句

EXIT语句：退出某个循环，使控制转到包含EXIT语句的最内层的WHILE或FOR循环后面的一个语句去执行

RETURN语句：结束算法的执行（允许使用用引号括起来的注释信息）

READ(INPUT)和WRITE(PRINT/OUTPUT)语句：用于输入输出

（6）算法中的注释总是用一对方括号【】括起来；复合语句用一对花括号{}括起来

1.3算法设计基本方法

1.列举法【例1.1】

基本思想：根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的（通常解决“是否存在”“有多少种可能”类型问题）

特点：算法比较简单，但列举情况较多时，工作量将很大

寻找路径、查找、搜索等问题采用列举法有效

2.归纳法

基本思想：通过列举少量的特殊情况，经过分析，最后找出一般的关系

3.递推法（数学例题）

指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果（本质属于归纳法）

4.递归

基本思想：将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些简单的问题后，再沿着原来分解的逆过程逐步进行综合【例1.3】

自己调用自己的过程称为递归调用过程

递归分为

直接递归：一个算法P显式地调用自己

间接递归：算法P调用另一个算法Q，而算法Q又调用算法P

5.减半递推技术（分治法）

减半：将问题的规模减半，而问题的性质不变

递推：重复“减半”的过程【例1.4】

6.回溯法

通过对问题的分析，找出一个解决问题的线索；然后沿着这个线索逐步试探。对于每一步的试探，如果成功，就得到问题的解；若试探失败，就逐步回退，换别的路线再进行试探。（处理复杂数据结构方面有广泛应用）【例1.5】

1.4算法的复杂度分析

算法的复杂度主要包括时间复杂度和空间复杂度

算法的时间复杂度：指执行算法所需要的计算工作量

可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量，同时还需对问题的规模进行度量

综上，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即

算法的工作量=f(n)

其中，n是问题的规模

在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量

（1）平均性态：用各种特定输入下的基本运算次数的带权平均数来度量算法分工作量A(n)）

（2）最坏情况复杂性：在规模为n时，算法所执行的基本运算的最大次数W(n)

【例1.6】

算法的空间复杂度：指执行这个算法所需要的内存空间

一个算法所占用的存储空间包括：算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。

其中额外空间包括：算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间

如果额外空间量相对于问题规模来说是常数，则称该算法是原地（in place）工作的

实际问题中，为减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间

第4章 资源管理技术

1、计算机系统主要包括硬件（即物理设备）和软件（即程序及其文档的总称）两大部分；计算机系统中所有的硬件和软件统称为计算机资源。

2、操作系统是最基本和核心的系统软件，是用以控制和管理系统资源、方便用户使用计算机的程序的集合。操作系统的功能和任务主要有处理机管理、存储器管理、设备管理、文件管理、作业管理。

3、操作系统发展过程：手工操作阶段（手编程序）、成批处理系统（脱机技术）、执行程序系统（主机与通道并行工作）、多道程序系统（并行性、共享性）。

4、为使主机和输入输出设备并行工作，人们使用以通道技术、中断技术和多道程序设计技术为基础的假脱机技术。

5、多道程序技术是指在计算机内存中同时存放多道相互独立的程序，他们在操作系统的控制下，共享系统的硬件和软件资源。

6、操作系统的分类（按使用环境及访问方式）：

（1）多道批处理操作系统

（2）分时操作系统，特点：同时性、独立性、及时性、交互性；分时是指若干个并发程序对CPU的分时，其中每个程序对CPU的时间分享单位称为时间片；第一个分时操作系统是UNIX操作系统。

（3）实时操作系统

（4）通用操作系统

（5）多窗口系统，特点：灵活、方便的窗口操作，弹出式菜单、命令对话框；代表：Microsoft Windows系统。

7、顺序程序的特点：顺序性（按顺序执行）、封闭性（一旦执行其结果不受外界因素影响）、可再现性（结果与运行速度无关）。

8、在单处理机的情况下，所谓并发执行是指多个程序的运行在时间上是重叠的，一个程序的运行尚未结束，另一个程序的运行已经开始，而并不是说这些程序在某一时刻同时占用处理机在运行。

9、并发程序特点：并发程序没有封闭性（结果与各程序执行的相对速度有关，结果的不确定性）；程序与其执行过程不是一一对应的关系（共享）；程序并发执行可以相互制约。

10、所谓进程，是指一个具有一定独立能力的程序关于某个数据集合的一次运行活动，简单地说，进程可以是并发执行的程序的执行过程，是控制程序管理下的基本的多道程序单位。

11、进程与程序的区别：

（1）进程是程序在处理机上的一次执行过程，是动态的概念；而程序只是一组指令的有序集合，是一个静态的概念。

（2）进程是程序的执行过程，是一次运行活动，具有一定的生命期；而程序是可以作为一种软件资源长期保存的。

（3）进程的组成包括程序、数据以及进程控制块（PCB）。

（4）一个程序可能对应多个进程。

（5）一个进程可以包含多个程序。

12、进程三种基本状态：运行状态（进程只能在运行状态下结束）、就绪状态、等待状态（又叫阻塞状态或封锁状态），三种基本状态之间在一定条件下可相互转换。

13、对进程的物理组织方式通常有线性表和链接表两种。

14、由于各进程互相独立地动态获得，不断申请和释放系统中的软硬件资源，这就有可能使系统出现这样一种状态：其中若干个进程均因互相“无知地”等待对方所占有的资源而无限地等待。这种状态称为死锁。

15、发生死锁的四个必要条件：资源的独占使用、资源的非抢占分配、资源的部分分配、对资源的循环等待。当其中某一条件满足时，有可能发生死锁，但也并不是一定会发生死锁。

16、当多个进程共享数据块或其他排他性使用资源时，不能同时进入存取或使用，但进入的次序可以任意，这些进程之间的这种相互制约关系称为互斥（多个操作决不能在同一时刻执行）。进程之间为了合作完成一个任务，而需要互相等待和互相交换信息的相互制约关系称为同步。

17、一次只允许一个进程使用的资源称为临界资源，访问临界资源的程序段称为临界区或临界段。

18、进程通信可分为互斥与同步两类，互斥是一种特殊的同步关系。根据通信情况的不同，可把进程之间的同步分为信号同步（低级通信原语用于信号同步，如P/V操作）与信件同步（高级通信原语用于信件同步，消息缓冲是一种高级通信工具）。

19、处理机调度一般分为两级：作业调度（又称为高级调度或宏调度）与进程调度（又称为低级调度或微调度）

20、在进行地址变换时（又称地址映射，当用户程序进入内存执行时，必须要把用户程序中所有相对地址转换为内存中的实际地址，否则用户程序就无法进行），必须修改程序中所有与地址有关的项，也就是说，要对程序中的指令地址以及指令中的有关地址的部分（称为有效地址）进行调整，这个调整的过程称为地址重定位。

21、存储管理的功能：地址变换、内存分配、存储共享与保护、存储器扩充。

22、基本的存储管理技术：界地址存储管理、分页存储管理、分段存储管理、段页式存储管理。

23、分页存储管理与分段存储管理的优缺点：

（1）分页存储管理的优点：a.用户地址空间不再受内存大小的限制；b.更有利地利用了内存；c.动态分页管理提供了虚拟存储器（受外存容量的限制），更有利于多道程序的运行。

（2）分页存储管理带来的问题：a.不利于程序的动态连接装配；b.不利于程序与数据的共享。

（3）分段存储管理正好解决了这两个问题。

24、文件的物理组织形式主要有连续文件、链接文件和索引文件（建议看看P263多级索引结构）；文件系统对磁盘空闲空间的管理方式有空闲文件项和空闲区表、空闲块链、位示图、空闲块成组链接法。

第6章 编译技术概述

25、编译程序是将用高级语言编写的源程序翻译成机器语言程序的实用程序。

26、编译程序的基本组成：（1）词法分析程序（读词程序）；（2）语法分析程序：编译程序的主要组成成分；（3）加工程序：直接影响翻译质量的关键一步，包括大量的造表和查表的过程；（4）优化修饰部分；（5）装配程序或链接程序：将分块编译得到的半目标程序（包括库程序）进行总装配。

27、状态矩阵法的核心是一张状态表（也称状态矩阵）。所谓状态，是表示过去已经扫描了什么语法成分，以便当遇到新的语法符号时，在不同的状态下对该语法符号作出不同的处理。（关于状态矩阵的具体编译过程建议看书299-307）

28、状态矩阵是稀疏矩阵，为节省存储空间，通常对状态矩阵进行压缩。

29、通过词法分析，可将一个常数用V×10m表示，其中V为正整数，m=ep-n，e为阶码符号（+、-），p为阶码绝对值，n为小数位数。如FROTRAN常数0.032E-1中，e= -，p=1，n=3，经词法分析，其结果为32×10-1-3=32×10-4 （V=32，m=-4）。

30、在多遍扫描的编译系统中，源程序每经过一遍扫描都要产生一种等效的中间语言表示。所谓中间语言，可概略地理解为能用来表达源程序并与之等效的一种编码方式，如波兰表示、三元组表示等。

31、一个表达式的波兰表示就是后缀表示，即表达式中的运算对象写在前面，运算符写在后面。三元组表示的一般形式为k, (θ o1 o2)，其意义为：对o1和o2作θ运算，并将结果存放在一个虚拟的累加器k中。（关于波兰表示和三元组表示的具体编译过程建议看书310-316）

32、语法分析和加工是编译系统的核心部分，其主要任务有：（1）识别出各种类型的语句，并进行语法检查；（2）语法的加工处理；（3）编译程序工作的最后结果是产生目标程序或半目标程序。

33、语法分析的方法主要有优先矩阵法（设置优先对象栈和算符栈）、优先数法（构造栈内优先数表和栈外优先数表）、状态矩阵法（用表格形式描述编译过程）、递归子程序法（处理递归定义）等。

第七章 应用软件设计与开发技术

1.软件生命周期分为几个阶段？每个阶段输出的文档

2.什么是数据流程图？数据流程图与程序流程图的区别

3.数据字典包含内容

4.什么是软件支援环境？举例熟悉的软件支援环境

5.有人说：“软件是不会用坏的，因此，经过测试和调试的软件不需要维护。”你认为这句话有道理吗？为什么？

6.分段函数，画出实现该功能的程序流程图，设计测试用例（白箱法、边值分析法）

知识点（可能考点）总结：判断、选择、填空、简答（1～2题）

一、软件工程概述

计算机硬件的发展经历：电子管、晶体管、集成电路和大规模集成电路、超大规模集成电路四个时代

软件工程：采用工程的概念、原理、技术和方法指导软件的开发和维护

软件生命周期：软件定义期（问题定义、可行性研究、需求分析）、软件开发期（系统设计、详细设计、编码和测试）、软件维护期（运行维护阶段）

软件支援环境：指在宿主硬件和宿主软件的基础上，用于辅助、支援其他软件的研制和维护的一种软件，包括环境数据库、接口软件、工具组三个组成部分

二、软件详细设计的表达

工程上常用的表达工具：图形工具、表格工具、语言工具

常用算法描述工具：程序流程图（程序框图）、NS图（盒图）、问题分析图PAD、判定表、过程设计语言PDL（伪码/结构化语言）

三、结构化分析与设计方法

应用软件开发的基本原则：自顶向下的系统结构开发原则、模块化结构开发原则

应用软件的开发方法：

（1）非自动形式的开发方法：系统流程图法、结构化分析方法（SA方法）、结构化设计方法（SD方法）、数据结构法（Jackson法）、层次输入—处理—输出方法（HIPO方法）

（2）半自动形式的开发方法：SREM方法（软件需求工程法）、PSL（问题说明语言）/PSA（问题说明分析器）方法

（3）自动形式的系统开发方法：HOS方法（可自动进行系统分析、系统设计和自动编程）

结构化分析方法（SA）特点：分解和抽象、文档的规范化、面向用户、系统的逻辑设计和物理设计分开进行

数据流程图：简称DFD，是SA方法最主要的一种图形工具，它从数据加工的角度，以图形方式描述信息处理系统的逻辑结构，能比较直观地描述信息处理中的业务情况

数据流程图组成符号：数据流、数据处理（加工）、数据存储（文件）、外部实体

画数据流程图的方法：自顶向下逐层分解、由外向里逐渐深化

数据字典：是结构化分析方法的另一个重要工具。主要是给数据流程图中的每一个数据流名，文件名以及处理名建立一个条目，在这些条目中给出各名字的定义。在每个条目下又可以建立子条目，直到每一个组成部分不能再分为止

条目类型：基本数据项条目、数据流条目、文件条目、加工条目（数据处理条目）

结构化设计方法追求：高内聚（功能内聚），低耦合（数据耦合）

四、测试与调试基本技术

测试：为了提高软件可靠性，在精心控制的环境下执行程序，以发现程序中的错误，给出程序可靠性的鉴定

测试方法：白箱法、黑箱法

测试的特征：测试的挑剔性、完全测试的不可能性、测试的经济性

调试的目的：发现错误位置，并改正错误

调试策略“试探法、回溯法、对分查找法、归纳法、演绎法

五、软件开发新技术

原型法（迭代，更新，修改）、瀑布模型(自上而下，相互衔接）

软件支援环境：交互式系统、数据库管理系统、通用输入输出软件、超级语言、能重用的代码库

软件生命期模型：指对整个软件生命周期内的系统开发运作和维护所实施的全部过程、活动和任务的结构框架

面向对象技术：面向对象分析（需求分析）OOA、面向对象设计OOD、面向对象实现OOI

相关概念：对象、类、方法、封装、继承

对象基本特征：模块性、继承性和类比性、动态连接性、易维护性

面向对象技术的特点：可重用性、可维护性、表示方法的一致性