自考计算机软件基础(二)概念.doc

《自考计算机软件基础(二)概念.doc》由会员分享，可在线阅读，更多相关《自考计算机软件基础(二)概念.doc（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机软件基础（二）复习资料第一章 概论1 裸机，虚拟机; 由处理器，存储器，输入输出设备组成的没有软件的硬件系统称为裸机，加上软件系统称为虚拟机。2 软件：程序加相关文档加所需数据，构成软件。3 汇编语言及其特点：用指令助记符组成的语言为汇编语言，其特点是：其源程序需由汇编程序编译成由机器指令组成的目标程序后，才能运行。它是面向机器的语言执行速度比较快，但难记，难理解，难编写。4 高级语言及其特点：按一定的语法规则，用词和数学公式组成的语言为高级语言。它的源程序也需经编译程序编译成目标程序后才能运行。它是面向过程的语言，运行速度比较慢，但是易懂，易理解，易编写。5 操作系统及其概念：负责控制

2、和管理及调度计算机系统资源，合理组织计算机工作流程，方便用户使用计算机的系统软件称为操作系统，它的发展经历了五个阶段：手工操作，批处理系统，执行程序系统，多道程序系统，分时系统阶段。6 手工操作阶段特点：没有操作系统，纯人工操作计算机，所有资源由一个用户程序独占，处理器所牌等待状态。机器利用率不高。7 批处理阶段特点：用监控程序对计算机资源进行管理，减少了人工干预，提高了计算机的效率，但很多时间化在输入输出上，处理机大部份时间仍处于等待状态。8 执行系统阶段特点：此阶段使用了通道和中断技术，实现了输入输出操作与处理器并行工作，减少了处理器的等待时间，但没有完全消除处理器对外设的等待现象。9 多

3、道程序系统阶段特点：此系统可在内存同时放入多个程序，它们可以交替占用CPU和外设，即多个程序可以同时运行，便某一刻仅一道程序运行。它显著提高了计算机资源利用率，并用调度程序，存储管理程序，设备管理程序，文件调度程序来管理计算机系统相关资源。10 分时系统阶段特点：此系统用时间片算法调度CPU，当用户在各自终端用交互方式操作各自程序时，使得每个用户感觉到自己在使用一台独立的高速计算机。11 软件分类： 系统软件：为应用软件服务的软件，如操作系统等。应用软件：解决实际问题所使用的软件。它又分事务处理软件，工程与科学计算软件，实时应用软件，嵌入式应用软件，微机应用软件，人工智能软件等。 第二章 数据

4、结构 12 数据：描述客观事物的数，字符，及所有能输入到计算机中并被计算机程序处理的符号的集合。13 数据元素：数据运算的基本单位，又称结点，记录，它的形式可以是一个数，字符串，或由多个数据项组成的记录。构成数据元素的项目称为数据项。14 程序：由算法加数据结构组成。15 数据结构：相互间存在一种或多种特定关系的数据元素的集合。16 数据的逻辑结构：从逻辑上反映数据元素间的结构（邻接）关系的组织形式。种类有，线性结构，非线性结构的树形，网状，集合结构，共四种l17 数据的存储结构：数据逻辑结构在存储器上的具体体现（组织形式），它有顺序结构，链式结构，索引结构，散列结构四种。18 顺序存储结构：

5、逻辑上相邻的元素存储在物理上也相邻（地址连续）的存储单元上的存储形式。其特点是：存储密度大，空间利用率高，可以随机和顺序访问，插入，删除一个元素耗费资源高。因为要移动元素。19 链式存储结构：逻辑上相邻的元素可以存储在物理上不相邻的存储单元上的存储形式。其特点是：存储密度低，空间利用率低，只能顺序访问，插入，删除一个元素耗费资源低。因为不要移动元素。20 线性表及其特点：元素间存在线性逻辑关系的逻辑结构，其特点是：首结点只有一个直接后继，尾结点只有一个直接前趋，其它结点只有一个直接前趋，一个直接后继。21 顺序表及其特点：采用顺序存储结构的线性表为顺序表。其任一元素i的地址计算公式为：i元素地

6、址=首元素地址+（i-1）* 数据类型的字节数。其中i为元素个数。22 顺序表的基本运算：见P1314，其插入，删除运算的平均移动次数是：n/2,（n-1）/2,平均时间复杂度为：O（n）量级。其特点是：结构简单，可随机访问数据元素，插，删要平均移动一半元素，估计所需空间易不准确。估大浪费，估小不够。23 链表及其特点：采用链式存储结构的线性表为链表，不能计算元素的地址。24 链表的基本运算：见P1721。其特点是：平均时间复杂度为：O（n）量级。只能顺序访问数据元素，插，删不要移动元素，不须估计所需空间。25 带头结点的单链表：有一个不放数据的结点作头结点的单链表，此为空表，其优点是，空表，

7、非空表，以及任一一个结点的操作方式都一样。26 循环链表：尾结点地址域放头结点地址的单链表称循环链表，其优点是：从任一结点出发都能访问完所有的结点。27 双向链表：每个结点有前后二个指针域的链表。其优点是：可方便访问前趋结点。其链结特点是：前一结点的右指针域=后一结点的左指针域。28 栈及其特点：只能从一端进行插，删操作的线性表称为栈。有栈顶（只能从这儿插，删操作），栈底之分。其访问特点是：先进后出，或后进先出。其基本运算见P23。29 顺序栈及其基本运算：见P2325，采用顺序存储结构的栈称为顺序栈，其插入，删除只能从栈顶进行，平均时间复杂度为：O（n）量级。其特点是：结构简单，估计所需空间

8、易不准确。估大浪费，估小不够。30 链栈及其特点：采用链式存储结构的栈为链栈，另外有单链表的特点31 链表的基本运算：其基本运算见P24-25。其特点是：平均时间复杂度为：O（n）量级。不须估计所需空间。32 队列及其特点：只能尾插，头删的线性表称为队列。有队尾（只能从这儿插，删操作），队头之分。其访问特点是：先进先出，或后进后出。其基本运算见P25。33 顺序队列及其基本运算：见P27，采用顺序存储结构的队列称为顺序队列，只能从队尾插入，队头删除，平均时间复杂度为：O（n）量级。其特点是：结构简单，估计所需空间易不准确。估大浪费，估小不够。34 顺序队列特点：直形队列不足：易形成假满，为此用

9、循环队列，循环队列，队空判据：rear=front, 队满判据：（rear+1）%m=front.。循环队列的指针移动规定。Front=（front+1）%m。rear=（rear+1）%m。35 链队及其特点：采用链式存储结构的队列为链队，另外有单链表的特点。36 链队的基本运算：其基本运算见P28。其特点是：平均时间复杂度为：O（n）量级。37 数组：二维数组中：先行序存储：每行存储满了，再存储下一行。先列序：每列存储满了，再存储下一列。任一元素地下计算公式。LOC（ai,j）=LOC(a1,1)+(i-1)*n+(j-1)*m。m为数据类型字节数。38 关于树和二叉树：树的定义请看P33

10、，没有空树，最少有一个结点，只有根结点无前趋，其它结点只有一个前趋，可有多个后继。树的基本术语看P34。39 树的存储结构：链式存储结构，有结点异构型，即每个结点的指针域数目（度）不同。结点同构型，即每个结点指针域（度）相同。40 二叉树： 结点的度最大为2的树，可以有空及非空二叉树。二叉树的五种形态请见P35。41 二叉树的性质：二叉树第i层最多结点数为：2i-1个。最多结点数为：2k-1。叶结点数n0=n2+1。对完全二叉树，其树的深度=log2n+1。42 完全二叉树父子结点间编号关系是：父结点号=子结点号/2，左孩号=父号*2， 右孩号=父号*2+1，若父号*2n，无左孩。父号*2+1

11、n无右孩。43 二叉树的存储结构：有顺序二叉树，结点编号为下标，依次存入数据元素内。按父结点号=子结点号/2，左孩号=父号*2， 右孩号=父号*2+1关系，访问各结点。对于非完全二叉树采用加虚结点变为完全二叉树的方式存储。见P3744 完全二叉树：树结点按从上到下，从左到右顺序排放的二叉树为完全二叉树。满二叉树：有2k-1个结点的二叉树为满二叉树。45 二叉树链式存储结构：二叉链表存储结构见P37。46 树转换成二叉树方式：横连仅留左子树再顺时针转45度。二叉树转换成树则反之。47 二叉树遍历：前根序：根左右。中根序：左根右。后根序：左右根。有关代码见P41。48 二叉排序树特点：对于升序：根

12、结点值=左孩值，根结点值执行态完成态。见P108158 作业调度算法：作业调度任务：完成作业从后备态到执行态到完成态的转换。159 调度的三个目标：尽量提高作业呑吐量、系统资源利用率、公平性。160 作业调度算法：先来先服务法，最短作业优先法，最高响应比优先法：响应比=响应时间/等待时间，此法公平性强。最高优先数法，均衡调度法。161 分时方式下作业管理：有交互控制方式：有命令驱动方式，菜单驱动方式，命令文件方式等方式，见P111162 终端作业调度：采用时间片轮转法。即每个作业使用完自己的时间片就必须让出CPU，给下一个作业占用CPU。另外，将终端作业作为前台作业，批处理作业作为后台作业。优

13、先权总是给终端作业。见P111112163 DOS作业管理的特点：向用户提供程序级（软中断和系统功能调用）和作业控制级（一组操作命令）二种接口。只有作业控制功能无作业调度功能。因为它是一个单用户操作系统。 第四章 数据库基础 164 数据管理发展三阶段：人工管理，文件管理，数据库管理三阶段。165 人工管理阶段：没有数据管理软件，不保存数据，既使要共用数据也不能互相利用。166 文件管理阶段：有了文件系统，有存放在外存中的数据文件，程序和数据文件只有一对一的关系，独立性低，数据间相互联系很弱。共享性低，数据冗余度大。167 数据库阶段：数据面向系统，可适应多个应用程序的要求，数据冗余度小，独立

14、性高，数据间联系性强，可保证数据的完整性。见P120168 数据库：相关数据的集合，它可为各种用户共享，有最小的数据冗余，数据间联系密切而且有较高的数据及程序独立性，有管理数据库的软件DBMS，169 数据库又一种定义：为一个特点组织多种应用服务的数据的集合。具有尽可能小的数据冗余度和较高的数据独立性。170 数据库的组成与结构：DB（数据库），DBA（数据库管理员），DBMS（数据库管理系统）。DBS（数据库系统）：它由计算机系统，DB，DBMS，DBA，和应用程序集合构成。见P121171 DBMS主要功能：维持DBS的正常活动，接受并响应用户对数据库的一切要求，如建立删除表，检索，统计修

15、改数据库中数据。为用户提供对数据库的维护手段等。172 数据库三级结构：用户逻辑结构（面向用户或应用程序员的用户级，外模式，子模式，用户视图，对应用户级数据库）；数据整体逻辑结构（面向建立和维护数据库人员的概念级，概念模式，全局视图，对应概念级数据统库）；物理存储结构（面向存储数据的系统程序员的物理级，内模式，存储视图，内视图，对应物理级数据库）。参见P122173 二级映象：外模式与概念模式间映象，定义了外用户视图和全局视图间的对应关系；内模式和概念模式间映象，它定义了全局视图与内视图间的对应关系。174 数据的物理独立性和逻辑独立性：175 数据的物理独立性：内模式和概念模式间映象，使得数

16、据的存储结构改变时即内模式改变时，数据的概念模式即全局逻辑结构可以不变，这样应用程序可以不变。176 数据的逻辑独立性：是指外模式与概念模式间映象使得，当数据的逻辑结构即全局模式改变时，数据的局部逻辑结构，不用改变，即应用程序可不改变。参见P122177 数据模型：数据的描述：178 现实世界：客观世界，客观事物包括有生命和无生命的事物。179 信息世界：是客观世界的抽象。180 机器世界：信息世界在计算机中的表现形式。181 现实世界的客观事物集合在信息世界称为实体集，在机器世界称为数据文件，客观事物性质在信息世界称为属性，在机器世界称为字段。现实世界的一个事物，在信息世界称为实体，在机器世

17、界称为一条记录。记录是实体集中各字段某一组值的集合。关键字：能唯一标识记录的字段或字段组合。182 实体间联系：主要有1:1，1:N，M:N，三种类型，掌握如何用实例判断它们。要会画E-R图即实体模型，又称概念模型，参见P124183 数据模型：它是实体模型的数据化模型，主要有三种类型，层次模型，网状模型，关系模型。184 层次模型：又称树型模型，它的二个基本条件是：有且只有一个没有双亲结点的根结点，其它结点只有一个双亲结点，可有多个子结点。查询记录必须从根结点开始，比较麻烦。IMS系统是其典型代表。这种模型比较适于1：1和1：n联系类型，参见P125185 网状模型：它的二个基本条件是：有一

18、个以上的没有双亲的结点，其它结点可以有多个双亲结点。引入了系概念，系就是一棵二叉树，根为首记录，叶为属记录，查询比较麻烦，DBTG系统是其典型代表。见P126。以上二者称为格式化数据模型。186 关系模型：一个二维表是一个关系，若干个表组成关系模型，表中列称为属性，数据项，表中一行称为记录，关系用：关系名（属性名列表）描述。其特点是：实体，实体间联系是有关系，操作对象是关系，操作结果也是关系。其最大优点是：简单，用户易掌握，易操作，适用于1:1，1:N，M:N，三种联系类型。用查表的方式就可以查找数据，参见P126-127187 109关系代数：分为二类，一类是传统集合运算，如并，交，差，笛卡

19、尔积; 一类是关系特有的运算,如：投影，选择，等值连接，自然连接。188 传统集合运算：并，交，差，笛卡尔积，参见P128。189 特有关系运算：190 投影：从一个关系中选出所需要的列的得新关系的运算，纵向选，为单目运算。191 选择：从一个关系中选出所需要的元组得新关系的的运算，横向选，为单目运算。192 连接：从二个关系的笛卡尔积中选出属性间满足一定条件的元组得新关系的的运算，为双目运算。193 自然连接：对二个有部分相同属性的关系进行这些属性的等值连接，并除去重复属性得新关系的的运算，为双目运算。以上四种运算，参见P129132。194 数据库结构设计：数据库是表的集合， 一个数据库文

20、件（.DBF）就是一张二维表，表的一列称为一个字段，一行称为一条记录，它由框架和数据二部分组成。195 数据库结构的一些规定：字段名命名规则：由110字符组成，只能以字母为首，只有用字母、数字、下划线字符。196 字段的数据类型：有字符型C，可以是任何字符，最多254个字符。数值型N：缺省为8个字节，最多20个字节。对于实数还要定义小数位数。浮点型F：缺省为8个字节，最多20个字节。对于实数还要定义小数位数。其精密度超过数值型。日期型D：缺省为8个字节。逻辑型L：宽度只能为1个字节，只有T，F二个值。备注型M：宽度只能为10个字节，其内只放，备注文件的地址，不是放备注的内容。没有备注文件时是小写的m.以上参见P134135。197 111数据库建立及记录操作命令：参见P136142（各命令的具体参数项请看书有关页）198 CREATE 文件名 回车。按图示法操作。建库结构（建表）命令见P136；199 Ctrl+PgDn:打开备注窗口写备注文件。200 USE 文件名 回车：打开后面文件，关闭当前文件。201 USE 回车：只关闭文件。202 LIST STRUCTURE 打开查看数据库结构窗口203 MODIFY STRUCTURE 打开修改数据库结构窗口204