2019年10月自考计算机软件基础(二)复习必看资料

《2019年10月自考计算机软件基础(二)复习必看资料》由会员分享，可在线阅读，更多相关《2019年10月自考计算机软件基础(二)复习必看资料（22页珍藏版）》请在金锄头文库上搜索。

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

2、它 的源程序也需经编译程序编译成目标程序后才能运行。它是面向过程的语言，运行速度比较 慢，但是易懂，易理解，易编写。 5操作系统及其概念操作系统及其概念：负责控制和管理及调度计算机系统资源，合理组织计算机工作流 程，方便用户使用计算机的系统软件称为操作系统，它的发展经历了五个阶段：手工操作， 批处理系统，执行程序系统，多道程序系统，分时系统阶段。 6手工操作阶段特点手工操作阶段特点：没有操作系统，纯人工操作计算机，所有资源由一个用户程序独 占，处理器所牌等待状态。机器利用率不高。 7批处理阶段特点批处理阶段特点：用监控程序对计算机资源进行管理，减少了人工干预，提高了计算 机的效率， ，但很多时

3、间化在输入输出上，处理机大部份时间仍处于等待状态。 8执行系统阶段特点执行系统阶段特点：此阶段使用了通道和中断技术，实现了输入输出操作与处理器并 行工作，减少了处理器的等待时间，但没有完全消除处理器对外设的等待现象。 9多道程序系统阶段特点多道程序系统阶段特点：此系统可在内存同时放入多个程序，它们可以交替占用 CPU 和外设，即多个程序可以同时运行，便某一刻仅一道程序运行。它显著提高了计算机资 源利用率，并用调度程序，存储管理程序，设备管理程序，文件调度程序来管理计算机系统 相关资源。 10分时系统阶段特点分时系统阶段特点：此系统用时间片算法调度 CPU，当用户在各自终端用交互方式 操作各自程

4、序时，使得每个用户感觉到自己在使用一立的高速计算机。 11软件分类：软件分类： 系统软件：系统软件：为应用软件服务的软件，如操作系统等。应用软件：应用软件：解决实 际问题所使用的软件。它又分事务处理软件，工程与科学计算软件，实时应用软件，嵌入式 应用软件，微机应用软件，人工智能软件等。 第二章第二章 数据结构数据结构 12数据：数据：描述客观事物的数，字符，及所有能输入到计算机中并被计算机程序处理的 符号的集合。 13数据元素：数据元素：数据运算的基本单位，又称结点，记录，它的形式可以是一个数，字符 第 2 页 串，或由多个数据项组成的记录。构成数据元素的项目称为数据项。 14程序：程序：由算

5、法加数据结构组成。 15数据结构：数据结构：相互间存在一种或多种特定关系的数据元素的集合。 16数据的逻辑结构：数据的逻辑结构：从逻辑上反映数据元素间的结构（邻接）关系的组织形式。种类 有，线性结构，非线性结构的树形，网状，集合结构，共四种 l 17数据的存储结构：数据的存储结构：数据逻辑结构在存储器上的具体体现（组织形式） ，它有顺序结构， 链式结构，索引结构，散列结构四种。 18顺序存储结构：顺序存储结构：逻辑上相邻的元素存储在物理上也相邻（地址连续）的存储单元上 的存储形式。其特点是：存储密度大，空间利用率高，可以随机和顺序访问，插入，删除一 个元素耗费资源高。因为要移动元素。 19链式

6、存储结构：链式存储结构：逻辑上相邻的元素可以存储在物理上不相邻的存储单元上的存储形 式。其特点是：存储密度低，空间利用率低，只能顺序访问，插入，删除一个元素耗费资源 低。因为不要移动元素。 20线性表及其特点：线性表及其特点：元素间存在线性逻辑关系的逻辑结构，其特点是：首结点只有一 个直接后继，尾结点只有一个直接前趋，其它结点只有一个直接前趋，一个直接后继。 21顺序表及其特点：顺序表及其特点：采用顺序存储结构的线性表为顺序表。其任一元素 i 的地址计算 公式为：i 元素地址=首元素地址+（i-1）* 数据类型的字节数。其中 i 为元素个数。 22顺序表的基本运算：顺序表的基本运算：见 P13

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

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

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

10、量级。其特点是：结构简单，估计所需空 间易不准确。估大浪费，估小不够。 34顺序队列特点：直形队列不足：顺序队列特点：直形队列不足：易形成假满，为此用循环队列，循环队列，队空判 据：rear=front, 队满判据：（rear+1）%m=front.。循环队列的指针移动规定。 Front=（front+1）%m。rear=（rear+1）%m。 35链队及其特点：链队及其特点：采用链式存储结构的队列为链队，另外有单链表的特点。 36链队的基本运算：链队的基本运算：其基本运算见 P28。其特点是：平均时间复杂度为：O（n）量级。 37数组：数组：二维数组中：先行序存储：每行存储满了，再存储下一行

11、。先列序：每列存 储满了，再存储下一列。任一元素地下计算公式。LOC（ai,j）=LOC(a1,1)+(i-1)*n+(j-1) *m。m 为数据类型字节数。 38关于树和二叉树：关于树和二叉树：树的定义请看 P33，没有空树，最少有一个结点，只有根结点无 前趋，其它结点只有一个前趋，可有多个后继。树的基本术语看 P34。 39树的存储结构：树的存储结构：链式存储结构，有结点异构型，即每个结点的指针域数目（度）不 同。结点同构型，即每个结点指针域（度）相同。 40二叉树：二叉树： 结点的度最大为 2 的树，可以有空及非空二叉树。二叉树的五种形态请见 P35。 41二叉树的性质：二叉树的性质：二

12、叉树第 i 层最多结点数为：2i-1个。最多结点数为：2k-1。叶结点 数 n0=n2+1。对完全二叉树，其树的深度=log2n+1。 42完全二叉树父子结点间编号关系是：完全二叉树父子结点间编号关系是：父结点号=子结点号/2，左孩号=父号*2， 右孩 号=父号*2+1，若父号*2n，无左孩。父号*2+1n 无右孩。 43二叉树的存储结构：二叉树的存储结构：有顺序二叉树，结点编号为下标，依次存入数据元素内。按父 结点号=子结点号/2，左孩号=父号*2， 右孩号=父号*2+1 关系，访问各结点。对于非完全二 叉树采用加虚结点变为完全二叉树的方式存储。见 P37 44完全二叉树：完全二叉树：树结点

13、按从上到下，从左到右顺序排放的二叉树为完全二叉树。满二 叉树：有 2k-1 个结点的二叉树为满二叉树。 45二叉树链式存储结构：二叉链表存储结构二叉树链式存储结构：二叉链表存储结构见 P37。 46树转换成二叉树方式：树转换成二叉树方式：横连仅留左子树再顺时针转 45 度。二叉树转换成树则反之。 47二叉树遍历：二叉树遍历：前根序：根左右。中根序：左根右。后根序：左右根。 有关代码见 P41。 48二叉排序树特点：二叉排序树特点：对于升序：根结点值=左孩值，根结点值执行态完成态。见 P108 158作业调度算法：作业调度任务作业调度算法：作业调度任务：完成作业从后备态到执行态到完成态的转换。

14、159调度的三个目标调度的三个目标：尽量提高作业呑吐量、系统资源利用率、公平性。 160作业调度算法：作业调度算法：先来先服务法，最短作业优先法，最高响应比优先法：响应比=响 应时间/计算时间，此法公平性强。最高优先数法，均衡调度法。 161分时方式下作业管理分时方式下作业管理：有交互控制方式：有命令驱动方式，菜单驱动方式，命令文 件方式等方式，见 P111 162终端作业调度终端作业调度：采用时间片轮转法。即每个作业使用完自己的时间片就必须让出 CPU，给下一个作业占用 CPU。另外，将终端作业作为前台作业，批处理作业作为后台作业。 优先权总是给终端作业。见 P111112 163DOS 作

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

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