计算机软件复习要点

《计算机软件复习要点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章1、算法的基本特征：能行性、确定性、有穷性。2、所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。3、算法的基本要素：一是对数据对象的运算和操作，二是算法的控制结构（顺序、选择、循环）。4、算法的复杂度主要包括时间复杂度和空间复杂度。第二章1、进行数据处理的关键问题是什么？为什么？答：关键问题是大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间。实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中。2、提高数据处理的两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程

2、中所占用的计算机存储空间。3、数据结构是指相互有关联的数据元素的集合。4、前后件关系式数据元素间的一个基本关系，数据元素之间的任何关系都可以用前后件关系来描述。5、所谓数据的逻辑结构，是指反映数据元素之间的逻辑关系的数据结构，且独立于计算机。6、数据的逻辑结构在将计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。7、线性表是由n(n≥0)数据元素,…,组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件，即线性表或是一个空表，或表示为（,,…,,…,）其中（i=1，2，…，n）是属于数据对象的元素，通常也称为线性表的一个

3、结点。8、非空线性表有如下一些结构特征：（1）有且只有一个根结点,它无前件。（2）有且只有一个终端结点，它无后件。（3）除根结点和终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。9、线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素所占的存储空间是连续的。（2）线性表中个数据元素在存储空间中是按逻辑顺序依次存放的。10、栈的特点：其插入与删除运算都只在线性表的一端进行，即在这种线性表的结构中，一端是封闭的，不允许插入与删除元素，另一端是开口的，允许数据的插入与删除元素。在顺序存储结构下，对这种类型线性表的

4、插入与删除运算是不需要移动表中其他数据元素的。11、队列是指，需要的加入的元素总是插入到线性表的末尾，而且又总是从线性表的头部取出元素。12、树的结构特点：每一个结点只有一个前件，称为父节点。在树中，没有前件的结点只有一个，就是根结点。简称为树的根。13、二叉树的两个特点：一非空二叉树只有一个根结点，二每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。14、满二叉树：除最后一层外，每一层上的所有结点都有两个子节点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。（简答）15、二叉树的遍历：前序遍历：是指在访问根节点，遍历左子树与遍历右子树先

5、访问根结点，然后遍历左子树，遍历右子树；并且在遍历左右子树中，仍遵循这一规则。中序遍历：先遍历左子树，然后访问根结点，再遍历右子树；并且在遍历左右子树中，仍遵循这一规则。后序遍历：先遍历左子树，然后遍历右子树，最后访问根结点；并且在遍历左右子树中，仍遵循这一规则。第四章16、操作系统的分类：多道批处理操作系统，分时操作系统，实时操作系统，通用操作系统，多窗口系统。17、顺序程序的特点：程序的顺序性，顺序程序的封闭性，顺序程序的可再现性。并发程序的特点：没有封闭性，程序跟其执行过程不是一一对应的关系，程序并发执行可以相互制约。18、进程的状态及其转化：运行状态，就绪状态，等待状态。19、多道程

6、序系统中，存储管理一般包括以下功能：（1）地址转换。（2）内存分配。（3）存储共享与保护。(4)存储器扩充。第六章20、软件生命周期：软件定义期：问题定义、可行性研究、需求分析软件开发期：系统设计、详细设计、编码和测试软件维护期：运行维护阶段。21、分时系统的特点：（1）同时性。（2）独立性。（3）及时性。(4)交互性。实时系统中，要求对随机发生的外部事件作出及时的响应并对其进行处理。实时系统的特点是严格的时间限制，它要求计算机对输入的信息作出快速响应，并在规定的时间内完成规定的操作。22、多窗口系统的特点（1）灵活、方便的窗口操作。（2）采用“弹出式菜单”方式，即每个应用程序的命令按其性质

7、分成若干组，在窗口上只列出菜单的名字，需要时选择适当的菜单名将其菜单“弹出”。（3）各种对话一般通过对话框来实现。多窗口系统能提供将多个作业同时展现在用户面前的操作环境，每个作业占据一个窗口，用户可以交替地与各个窗口进行对话，各个窗口之间也可以互相通信、交换信息。23、数据流程图：是SA方法最主要的一种图形工具，它从数据加工的角度，以图形方式描述信息处理系统的逻辑结构，能比较直观地描述信息处理中的业务情况。