计算机软件基础 计算机软件基础二复习资料.docx

计算机软件基础 计算机软件基础二复习资料.docx

《计算机软件基础 计算机软件基础二复习资料.docx》由会员分享，可在线阅读，更多相关《计算机软件基础 计算机软件基础二复习资料.docx（28页珍藏版）》请在冰点文库上搜索。

计算机软件基础计算机软件基础二复习资料

计算机软件基础（计算机软件基础

（二）复习资料

第一章概论1，裸机，虚拟机;裸机，虚拟机由处理器，存储器，输入输出设备组成的没有软件的硬件系统称为裸机，加上软件系统称为虚拟机。

2，软件：

程序加相关文档加所需数据，构成软件。

软件3，汇编语言及其特点：

用指令助记符组成的语言为汇编语言，其特点是：

其源程序汇编语言及其特点需由汇编程序编译成由机器指令组成的目标程序后，才能运行。

它是面向机器的语言执行速度比较快，但难记，难理解，难编写。

4，高级语言及其特点：

按一定的语法规则，用词和数学公式组成的语言为高级语言。

高级语言及其特点它的源程序也需经编译程序编译成目标程序后才能运行。

它是面向过程的语言，运行速度比较慢，但是易懂，易理解，易编写。

5，操作系统及其概念：

负责控制和管理及调度计算机系统资源，合理组织计算机工操作系统及其概念作流程，方便用户使用计算机的系统软件称为操作系统，它的发展经历了五个阶段：

手工操作，批处理系统，执行程序系统，多道程序系统，分时系统阶段。

6，手工操作阶段特点：

没有操作系统，纯人工操作计算机，所有资源由一个用户程手工操作阶段特点序独占，处理器所牌等待状态。

机器利用率不高。

7，批处理阶段特点：

用监控程序对计算机资源进行管理，减少了人工干预，提高了批处理阶段特点计算机的效率，，但很多时间化在输入输出上，处理机大部份时间仍处于等待状态。

执行系统阶段特点特点：

实现了输入输出操作与处理器执行系统阶段特点此阶段使用了通道和中断技术，并行工作，减少了处理器的等待时间，但没有完全消除处理器对外设的等待现象。

8，多道程序系统阶段特点：

此系统可在内存同时放入多个程序，它们可以交替占用多道程序系统阶段特点CPU和外设，即多个程序可以同时运行，便某一刻仅一道程序运行。

它显著提高了计算机资源利用率，并用调度程序，存储管理程序，设备管理程序，文件调度程序来管理计算机系统相关资源。

9，分时系统阶段特点：

此系统用时间片算法调度CPU，当用户在各自终端用交互方分时系统阶段特点式操作各自程序时，使得每个用户感觉到自己在使用一台独立的高速计算机。

10，软件分类：

系统软件：

应用软件：

软件分类：

系统软件：

为应用软件服务的软件，如操作系统等。

应用软件：

解决应用软件实际问题所使用的软件。

它又分事务处理软件，工程与科学计算软件，实时应用软件，嵌入式应用软件，微机应用软件，人工智能软件等。

第二章数据结构11，数据：

数据：

描述客观事物的数，字符，及所有能输入到计算机中并被计算机程序处理的符号的集合。

12，数据元素：

数据元素：

数据运算的基本单位，又称结点，记录，它的形式可以是一个数，字符串，或由多个数据项组成的记录。

构成数据元素的项目称为数据项。

13，程序：

程序：

由算法加数据结构组成。

14，数据结构：

数据结构：

相互间存在一种或多种特定关系的数据元素的集合。

15，数据的逻辑结构：

数据的逻辑结构：

从逻辑上反映数据元素间的结构（邻接）关系的组织形式。

种类有，线性结构，非线性结构的树形，网状，集合结构，共四种l16，数据的存储结构：

，它有顺序结数据的存储结构：

数据逻辑结构在存储器上的具体体现（组织形式）构，链式结构，索引结构，散列结构四种。

17，顺序存储结构：

顺序存储结构：

逻辑上相邻的元素存储在物理上也相邻（地址连续）的存储单元上的存储形式。

其特点是：

存储密度大，空间利用率高，可以随机和顺序访问，插入，删除一个元素耗费资源高。

因为要移动元素。

18，链式存储结构：

逻辑上相邻的元素可以存储在物理上不相邻的存储单元上的存储形链式存储结构：

第1页

式。

其特点是：

存储密度低，空间利用率低，只能顺序访问，插入，删除一个元素耗费资源低。

因为不要移动元素。

19，线性表及其特点：

线性表及其特点：

元素间存在线性逻辑关系的逻辑结构，其特点是：

首结点只有一个直接后继，尾结点只有一个直接前趋，其它结点只有一个直接前趋，一个直接后继。

20，顺序表及其特点：

顺序表及其特点：

采用顺序存储结构的线性表为顺序表。

其任一元素i的地址计算公式为：

i元素地址=首元素地址+（i-1）*数据类型的字节数。

其中i为元素个数。

21，顺序表的基本运算：

顺序表的基本运算：

见P13—14，其插入，删除运算的平均移动次数是：

n/2,（n-1）/2,平均时间复杂度为：

O（n）量级。

其特点是：

结构简单，可随机访问数据元素，插，删要平均移动一半元素，估计所需空间易不准确。

估大浪费，估小不够。

22，链表及其特点：

链表及其特点：

采用链式存储结构的线性表为链表，不能计算元素的地址。

23，链表的基本运算：

链表的基本运算：

见P17—21。

其特点是：

平均时间复杂度为：

O（n）量级。

只能顺序访问数据元素，插，删不要移动元素，不须估计所需空间。

24，带头结点的单链表点的单链表：

带头结点的单链表：

有一个不放数据的结点作头结点的单链表，此为空表，其优点是，空表，非空表，以及任一一个结点的操作方式都一样。

25，循环链表：

循环链表：

尾结点地址域放头结点地址的单链表称循环链表，其优点是：

从任一结点出发都能访问完所有的结点。

26，双向链表：

双向链表：

每个结点有前后二个指针域的链表。

其优点是：

可方便访问前趋结点。

其链结特点是：

前一结点的右指针域==后一结点的左指针域。

27，栈及其特点：

只能从一端进行插，删操作的线性表称为栈。

有栈顶（只能从这儿插，栈及其特点：

删操作），栈底之分。

其访问特点是：

先进后出，或后进先出。

其基本运算见P23。

28，顺序栈及其基本运算其基本运算：

顺序栈及其基本运算：

见P23—25，采用顺序存储结构的栈称为顺序栈，其插入，删除只能从栈顶进行，平均时间复杂度为：

O（n）量级。

其特点是：

结构简单，估计所需空间易不准确。

估大浪费，估小不够。

29，链栈及其特点：

链栈及其特点：

采用链式存储结构的栈为链栈，另外有单链表的特点30，链表的基本运算：

链表的基本运算：

其基本运算见P24--25。

其特点是：

平均时间复杂度为：

O（n）量级。

不须估计所需空间。

31，队列及其特点：

队列及其特点：

只能尾插，头删的线性表称为队列。

有队尾（只能从这儿插，删操作），队头之分。

其访问特点是：

先进先出，或后进后出。

其基本运算见P25。

32，顺序队列及其基本运算本运算：

顺序队列及其基本运算：

见P27，采用顺序存储结构的队列称为顺序队列，只能从队尾插入，队头删除，平均时间复杂度为：

O（n）量级。

其特点是：

结构简单，估计所需空间易不准确。

估大浪费，估小不够。

33，顺序队列特点：

直形队列不足：

顺序队列特点：

直形队列不足：

易形成假满，为此用循环队列，循环队列，队空判据：

rear==front,队满判据：

（rear+1）%m==front.。

循环队列的指针移动规定。

Front=（front+1）%m。

rear=（rear+1）%m。

34，链队及其特点：

链队及其特点：

采用链式存储结构的队列为链队，另外有单链表的特点。

35，链队的基本运算：

链队的基本运算：

其基本运算见P28。

其特点是：

平均时间复杂度为：

O（n）量级。

36，数组：

数组：

二维数组中：

先行序存储：

每行存储满了，再存储下一行。

先列序：

每列存储满了，再存储下一列。

任一元素地下计算公式。

（ai,j）LOC=LOC（a1,1）+（（i-1）*n+（j-1））*m。

m为数据类型字节数。

37，关于树和二叉树：

关于树和二叉树：

树的定义请看P33，没有空树，最少有一个结点，只有根结点无前趋，其它结点只有一个前趋，可有多个后继。

树的基本术语看P34。

38，树的存储结构：

树的存储结构：

链式存储结构，有结点异构型，即每个结点的指针域数目（度）不同。

结点同构型，即每个结点指针域（度）相同。

第2页

39，二叉树：

二叉树：

结点的度最大为2的树，可以有空及非空二叉树。

二叉树的五种形态请见P35。

i-1k40，二叉树的性质：

二叉树的性质：

二叉树第i层最多结点数为：

2个。

最多结点数为：

2-1。

叶结点数n0=n2+1。

对完全二叉树，其树的深度=［log2n］+1。

41，完全二叉树父子结点间编号关系是二叉树父子结点间编号关系是：

完全二叉树父子结点间编号关系是：

父结点号=子结点号/2，左孩号=父号*2，右孩号=父号*2+1，若父号*2>n，无左孩。

父号*2+1>n无右孩。

42，二叉树的存储结构：

二叉树的存储结构：

有顺序二叉树，结点编号为下标，依次存入数据元素内。

按父结点号=子结点号/2，左孩号=父号*2，右孩号=父号*2+1关系，访问各结点。

对于非完全二叉树采用加虚结点变为完全二叉树的方式存储。

见P3743，完全二叉树：

完全二叉树：

树结点按从上到下，从左到右顺序排放的二叉树为完全二叉树。

满二叉树：

有2k-1个结点的二叉树为满二叉树。

44，二叉树链式存储结构：

二叉链表存储结构见二叉树链式存储结构：

二叉链表存储结构P37。

45，树转换成二叉树方式：

横连仅留左子树再顺时针转45度。

二叉树转换成树则反之。

树转换成二叉树方式：

46，二叉树遍历：

二叉树遍历：

前根序：

根—左—右。

中根序：

左—根—右。

后根序：

左—右—根。

有关代码见P41。

47，二叉排序树特点：

二叉排序树特点：

对于升序：

根结点值>=左孩值，根结点值<=右孩值。

48，平均查找长度：

平均查找长度：

为查找元素在表中的位置而与关键字比较次数的期望值。

用ASL表示，其计算公式见P45。

49，线性查找法特点：

线性查找法特点：

事先不要求排序，对存储结构无要求，但查找速度慢，特别是对长表的查找速度慢。

其平均查找长度ASL=（n+1）/2。

50，二分查找法特点：

二分查找法特点：

需事先对表排序，比较次数少，速度快，但事先排序耗费资源，其平均查找长度ASL=log2n。

mid=（low+high）/2，如果小于中间值，要往左找因此要改high的值，此时，high=mid-1，如果大于中间值，要往右找因此要改low的值，low=mid+1，会图形法画出查找过程，见P4651，散列查找特点：

散列查找特点：

不需多次比较，一次就能访问所查元素的查找法。

由关键字值利用散列函数计算查找元素的位置值。

主要查找函数有：

直接地址法，求模运算法（%），平方到中法，折叠法。

52，构造散列函数的冲突概念：

构造散列函数的冲突概念：

二个记录的关键字值争夺同一个存储位置的现象称为冲突，这二个关键字值称为同义词。

解决冲突的方法有：

链地址法，见P49—50。

开地址法，见P50—52。

53，排序有关概念直接选择排序法：

总比较次数=（n2-n）/2，最坏情况下总移动次有关概念：

排序有关概念：

直接选择排序法数=3（n-1）,平均时间复杂度为：

O（n2）量级。

会图形法画出排序过程。

见P52。

54，直接插入排序法：

插入排序法（n-1）/2，最坏情况下的移动次直接插入排序法：

最坏情况下的比较次数=（n+2）2数=（n+3-4）.见P52。

最好情况下的比较次数=n-1，最好情况下的移动次数=2（n-1），2平均时间复杂度为：

O（n）量级。

特点：

算法易实现，当n比较小时是一种较佳的排序方法。

n很大时不适用。

会图形法画出排序过程见P53。

55，二分插入排序法：

二分插入排序法：

比较次数比线性查找法少得多。

比较的平均时间复杂度为O（nlog2n）量级，其移动次数与直接插入排序法同其时间复杂度为O（n2）量级。

要会图形法画出排序过程。

56，冒泡排序法：

：

最坏情况下的比较次数=（n2-n）/2，最好情况下的比较次数=n-1，冒泡排序法：

：

最好情况下的移动次数=0，平均时间复杂度为：

O（n2）量级。

会图形法画出排序过程P55.57，快速排序法：

快速排序法：

最坏情况下的比较次数=（n2-n）/2，最好情况下的比较次数=nlog2n，最好情况下的移动次数=0，平均时间复杂度为：

O（nlog2n）量级。

会图形法画出排序过程P57

第3页

第三章.第三章操作系统58，操作系统的类型：

操作系统的类型：

多道批处理系统：

多个作业同时放入内存，在一段时间内并行运行，它们可以交替使用CPU及外设。

它不适于运行时要用户干预的作业，只适于运行处理时间要求不严，运行步骤严格。

比较成熟的作业。

分时操作系统：

见第一章有关内容。

它适于运行时要用户干预的作业，如程序调试，软件开发等。

实时操作系统：

能及时响应请求，快速反馈处理的操作系统。

适于生产控制类的应用情况。

另个还有，单用户，多用户操作系统，单任务多任务操作系统。

DOS是单任务的，windows是多任务的。

网络操作系统。

60.操作系统的五大功能：

操作系统的五大功能：

处理机管理：

管理CPU的合理分配与回收。

即分配策略。

实施方法，回收方式。

处理机管理存储管理：

内存的合理分配和回收，数据的保护，实现虚拟内存。

存储管理文件管理：

文件管理：

实现文件的存储，检索，修改，解决文件的共享和保密保护。

设备管理：

实现外设的合理分配与回收。

实现外设启动，实现处设与CPU并行工作。

设备管理给用户提供一个好的工作环境。

作业管理：

为用户提供一个使用系统的良好环境与结口，制定好的调度策略，组织作作业管理业运行，提高系统效率。

61．进程：

有独立功能的程序在某数据集上的运行称为进程。

它是操作系统中可以并行工作进程：

进程的最基本单位。

它是动态的，它有生命过程，是暂时存在的。

一个进程可以包含多个程序。

程序是有独立功能的一组指令的集合，它是静态的，可以永久存在，一个程序运行在不程序同的数据集上可以产生多个进程。

62：

进程的三种状态：

就绪态：

进程获得除CPU外一切资源所处的状态。

作业进入内存就：

进程的三种状态：

就绪态：

处于这一状态。

运行态运行态：

进程占用CPU时的状态。

等待态：

进程因等待某种事等待态：

运行态等待态件发生，如等待资源分配，等待故障修好等，所处的状态。

63，三种状态转换：

运行态可转入就绪态或等待态或完成任务结束生命，等待态只能转入就，三种状态转换：

绪态，就绪态只能转入运行状态。

进程运行毕从运行态进入结束，进程占用时间到进入就绪态，进程需要重新分配资源或等待故障修理毕从运行态进入等待态。

64．进程控制块：

PCB，它是进程存在的标志，是描述进程基本情况，和运行变化过程的一．进程控制块：

种数据结构，作业进入内存就建立一PCB，由它来控制管理进程。

它由四大部份组成，标识信息标识信息：

进程名；说明信息说明信息：

说明进程的现在状态。

等待原因，程序标识信息说明信息和数据的内存地址；现场信息：

记录进程退出CPU时，在CPU中所处的现场信现场信息：

现场信息息，如在通用，控制，程序状态寄存器中的内容。

管理信息：

进程的优先级队列管理信息：

管理信息地址。

PCB加程序加数据构成进程实体。

65．进程队列：

运行态队列，就绪态队列，等待态队列。

均为链队。

．进程队列：

，66．进程常用调度算法．进程常用调度算法：

先来先服务调度法；优先数法：

优先级高的先占用CPU；又分不可抢占式及抢占式；时间片轮转法：

它和先来先服务法结合进行调度。

进程时间片用完必须退出CPU，让下一个进程占用。

它常用于分时操作系统中。

见P7067．进程通信：

进程互斥进程通信：

进程通信进程互斥：

不允许二个进程同时访问同一临界资源的临界区称为进程互斥。

一次只允许一个进程访问的资源称为临界资源，临界资源的那段程序代码称为临界区。

互斥访问临界区的原则：

一次只许一个进程进临界区，临界区有进程互斥访问临界区的原则：

互斥访问临界区的原则时其它里程只能等待。

进都不能久呆，等待者不能久等。

例见P71。

进程同步同步：

一个进程的执行只有等到接到另一个进程的消息时才能实现，称进程同步

第4页

为进程同步。

它们间有依赖关系。

68，PV操作，操作：

解决进程同步与互斥而用到的原语操作。

原语操作原语操作是指：

由若干条指令组成原语操作的可完成特定功能，执行中不能中断执行中不能中断的一段程序。

它们都对信息号量S进行操作。

执行中不能中断P操作P（S）操作（）操作：

执行时，将S－１；S＞＝０，进程可进临界区，S＜０则进程不能进临界区，且置它于等待队列中等待。

V操作V（S）操作：

执行时，将S＋１；S（）操作：

＞０，临界区仍有进程，其它进程还不能进临界区仍要等待，S＜＝０则从等待队列移出一进程进入就绪态队列准备访问临界区。

69．用PV操作实现互斥：

此时设S初值等于１。

S＝１，再执行上述的PV操作，见73。

操作实现互斥：

．S等于-n就有n个进程处于等待队列。

70.用PV操作实现同步：

SP（信号量）=1表示缓冲区只能放一个产品，SP（信号量）操作实现同步：

（（=0表示缓冲区已满有能放产品。

生产者执行P（SP）操作放产品，执行V（SG）操作通知消费者可以取产品。

SG（信号量）=0表示缓冲区无产品消费者不能取。

SG（信号（（量）=1表示缓冲区有一个产品消费者可以取，消费者执行P（SG）操作取产品，执行V（SP）操作通知生产者可以再放产品。

参见P74。

如果SP=n，则缓冲区可以放n件产品。

71．死锁：

系统中二个或多个进程无限期地等待对方的资源，而不能运行的状态称为死锁。

．死锁：

这种状态的进程称为死锁进程。

产生死锁的四个必要条件：

一，进程要互斥使用资源，二。

不可抢夺资源，三，只能部份分配资源，四，进程间循环等待对方资源。

72．预防死锁的方法：

破坏死锁四个必要条件中的一个，就能预防死锁。

方法有：

一，预先．预防死锁的方法：

一静态分配资源，即一次性分配给进程所需全部资源。

二，编号分配资源法，即将资源编号，只有获得小号资源的进程才能获得大号资源。

三。

抢夺式分配资源法。

见P7673．避免死锁的方法：

在系统运行中关注死锁的发生情况，如会发生则避免其发生，银行家．避免死锁的方法：

算法能比较好避免死锁的发生。

银行家算法方式是：

如果系统当前资源数能满足进程的全部需要就分配给它，否则不分配。

这样能保证进程执行完毕，放出资源给别的进程使用。

如果资源分配会产生死锁则不分配。

这样系统处于安全状态。

74．死锁的检测与解除：

系统运行时用死锁检测程序检测是否存在死锁，如果存在则用一定．死锁的检测与解除：

方法解除死锁，一般用二张表记录进程占用和等待资源的情况。

有死锁就解除，解除方法有。

一。

抢占资源法。

二。

撤消进程法。

75．DOD进程管理特点：

它是一个单用户单任务操作系统，无并发进程出现。

用户进程由进程管理特点：

．程序，程序段前缀PSP，环境块EVB（可视为进程控制快的扩充）三部份组成。

其中PSP是一个有256字节的类似于进程控制块的控制块，是DOS与程序的结口，其内的信息供DOS内核进行文件操作，进程运行及管理时使用。

EVB是一个字符串块，由一系列环境变量组成，由它设置进程的运行环境。

详情请参见P78—79。

76．DOS系统进程运行情况：

COMMAND.COM是袓先进程，然后由它建立用户进程（分系统进程运行情况：

．配空间，建立PSP和EVB），二者只能串行，而不能并行运行。

不会产生死锁。

77．存储管理方面：

存储管理的任务有：

合理分配，回收主存空间；保护文件不被破坏。

实．存储管理方面：

现逻辑地址和物理地址之间的转换。

实现主存空间的共享。

实现虚拟内存建立。

78．存储管理方式有：

单一连续存储管理；分区存储管理；页式存储管理；段式存储管理；．存储管理方式有：

段页式存储管理。

79．分区存储管理：

它是将内存分为若干连续分区，用连续分配方式将一个区分给一个作业。

．分区存储管理：

又分为固定分区和可变分区二种形式。

固定式：

内存分为若干大小不等，且固定的连续分区，将比较适合大小的分区分给作业。

固定式此种方式用分区分配表方式管理分区的分配与回收。

用静态重定位方式进行地址转换。

这种方式因会产生较多的碎片而浪费空间。

但简单易行。

参看P81。

第5页

可变式第一次分配空间多个作业进入内存时，依次划出与作业大小相同的连续分区分可变式：

配给各作业，此时仅一个空闲区，但系统运行一段时间后，也会产生多个碎片，此时可用移动技术合并碎片成大的空闲区，但为此要消耗大量的计算机资源。

此种方式用空闲区表和已分配分区分表二张表管理分区的分配与回收。

用动态重定位方式进行地址转换，参看P82。

80.页式存储管理：

页式存储管理将内存分为大小相等的块作业也分为大小相等的页，存储管理：

且块与页大小相等，作业按其页数分配相等的块数，各块地址可不连续。

其优点是：

基本无碎片，其不足是共享和保护方面不理想。

页式存储管理的地址结构：

页式存储管理的地址结构：

由页号和页内相对地址二部分构成。

逻辑地址%页字的节数，余数为此页的页内地址，商为此页的页号。

用页表（每一作业一张页表），系统作业表和存储块表三张表管理块的分配与回收。

参同见P83--84页式存储管理的地址转换公式转换公式：

页式存储管理的地址转换公式：

绝对地址=块号*快长+页内相对地址。

一个计算例见P84页中部。

每一主存指令执行要访问二次内存，一次访问页表一次访问实际单元。

81页式虚拟存储管理：

实现虚拟内存的方式：

只将作业的第一页和少量的重要页装入内存。

页式虚拟存储管理存储管理：

其它页放硬盘的内存虚拟区。

运行时如果所需要的页不在内存，则产生一个缺页中断，将它从内存虚拟区调入内存，如果内存不够，则先调出一页，再调入一页。

用页式虚拟存储管理页表进行有关的地址转换。

参见P84。

82页式虚拟存储管理常用调度算法：

先进先出法FIFO，最近最久没用法LRU，最近最少页式虚拟存储管理常用调度算法：

存储管理常用调度算法使用法LFU。

参见P85。

抖动：

抖动：

一页频繁调入调出称为抖动。

82.段式存储管理：

将作业分为大小不等的段，作业按其段数分配相应的段内存区，各段内段式存储管理存储管理：

地址连续，但各段区地址可不连续。

其优点是：

共享和保护方面理想。

用段表管理内存的分配与回收见，这方面类似于页式管理，P86。

段式虚拟存储管存储管理段式虚拟存储管理：

类似于页式虚拟存储管理，只不过调入，调出单位是段而已。

段页式存储管理存储管理：

段页式存储管理：

就是段式管理和页式管理相结合，作业先分成若干段，每段再分为，若干页。

逻辑地址格式是：

段号，页号，页内地址。

用段，页表进行内存分配与管理。

参见P8783.DOS存储管理的特点：

采用单一连续区存储管理模式，用静态重定位实现地址转换。

存储管理的特点的特点：

用内存控制块MCB控制管理内存空间。

84．文件管理。

．文件管理。

文件。

文件。

逻辑上有完整意义的一组相关信息的有序集合。

用它实现文件按名名存取。

一张软盘，一个硬盘，一盘磁带称为一卷，一卷分为若干块，块是存储器交换信息的最小物理单位。

85文件系统的功能：

实现文件名到外存空间的地址转换，即文件按名访问。

合理分配回收文件系统的功能：

外存；建立文件目录；实现对文件的控制和存取操作。

实现文件的共享。

保护和保密。

参见P9186文件分类：

参见P91—92文件逻辑结