《2019年10月自考计算机软件基础(二)复习必看资料》由会员分享，可在线阅读，更多相关《2019年10月自考计算机软件基础(二)复习必看资料（21页珍藏版）》请在金锄头文库上搜索。
1、自考计算机软件基础（二）考前必备资料复习资料第一章 概论1 裸机，虚拟机; 由处理器，存储器，输入输出设备组成的没有软件的硬件系统称为裸机，加上软件系统称为虚拟机。2 软件：程序加相关文档加所需数据，构成软件。3 汇编语言及其特点：用指令助记符组成的语言为汇编语言，其特点是：其源程序需由汇编程序编译成由机器指令组成的目标程序后，才能运行。它是面向机器的语言执行速度比较快，但难记，难理解，难编写。4 高级语言及其特点：按一定的语法规则，用词和数学公式组成的语言为高级语言。它的源程序也需经编译程序编译成目标程序后才能运行。它是面向过程的语言，运行速度比较慢，但是易懂，易理解，易编写。5 操作系统及
2、其概念：负责控制和管理及调度计算机系统资源，合理组织计算机工作流程，方便用户使用计算机的系统软件称为操作系统，它的发展经历了五个阶段：手工操作，批处理系统，执行程序系统，多道程序系统，分时系统阶段。6 手工操作阶段特点：没有操作系统，纯人工操作计算机，所有资源由一个用户程序独占，处理器所牌等待状态。机器利用率不高。7 批处理阶段特点：用监控程序对计算机资源进行管理，减少了人工干预，提高了计算机的效率，但很多时间化在输入输出上，处理机大部份时间仍处于等待状态。8 执行系统阶段特点：此阶段使用了通道和中断技术，实现了输入输出操作与处理器并行工作，减少了处理器的等待时间，但没有完全消除处理器对外设的
3、等待现象。9 多道程序系统阶段特点：此系统可在内存同时放入多个程序，它们可以交替占用CPU和外设，即多个程序可以同时运行，便某一刻仅一道程序运行。它显著提高了计算机资源利用率，并用调度程序，存储管理程序，设备管理程序，文件调度程序来管理计算机系统相关资源。10 分时系统阶段特点：此系统用时间片算法调度CPU，当用户在各自终端用交互方式操作各自程序时，使得每个用户感觉到自己在使用一立的高速计算机。11 软件分类： 系统软件：为应用软件服务的软件，如操作系统等。应用软件：解决实际问题所使用的软件。它又分事务处理软件，工程与科学计算软件，实时应用软件，嵌入式应用软件，微机应用软件，人工智能软件等。
4、第二章 数据结构 12 数据：描述客观事物的数，字符，及所有能输入到计算机中并被计算机程序处理的符号的集合。13 数据元素：数据运算的基本单位，又称结点，记录，它的形式可以是一个数，字符串，或由多个数据项组成的记录。构成数据元素的项目称为数据项。14 程序：由算法加数据结构组成。15 数据结构：相互间存在一种或多种特定关系的数据元素的集合。16 数据的逻辑结构：从逻辑上反映数据元素间的结构（邻接）关系的组织形式。种类有，线性结构，非线性结构的树形，网状，集合结构，共四种l17 数据的存储结构：数据逻辑结构在存储器上的具体体现（组织形式），它有顺序结构，链式结构，索引结构，散列结构四种。18 顺
5、序存储结构：逻辑上相邻的元素存储在物理上也相邻（地址连续）的存储单元上的存储形式。其特点是：存储密度大，空间利用率高，可以随机和顺序访问，插入，删除一个元素耗费资源高。因为要移动元素。19 链式存储结构：逻辑上相邻的元素可以存储在物理上不相邻的存储单元上的存储形式。其特点是：存储密度低，空间利用率低，只能顺序访问，插入，删除一个元素耗费资源低。因为不要移动元素。20 线性表及其特点：元素间存在线性逻辑关系的逻辑结构，其特点是：首结点只有一个直接后继，尾结点只有一个直接前趋，其它结点只有一个直接前趋，一个直接后继。21 顺序表及其特点：采用顺序存储结构的线性表为顺序表。其任一元素i的地址计算公式
6、为：i元素地址=首元素地址+（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 关于树和二叉树：树的定
10、义请看P33，没有空树，最少有一个结点，只有根结点无前趋，其它结点只有一个前趋，可有多个后继。树的基本术语看P34。39 树的存储结构：链式存储结构，有结点异构型，即每个结点的指针域数目（度）不同。结点同构型，即每个结点指针域（度）相同。40 二叉树： 结点的度最大为2的树，可以有空及非空二叉树。二叉树的五种形态请见P35。41 二叉树的性质：二叉树第i层最多结点数为：2i-1个。最多结点数为：2k-1。叶结点数n0=n2+1。对完全二叉树，其树的深度=log2n+1。42 完全二叉树父子结点间编号关系是：父结点号=子结点号/2，左孩号=父号*2， 右孩号=父号*2+1，若父号*2n，无左孩。
11、父号*2+1n无右孩。43 二叉树的存储结构：有顺序二叉树，结点编号为下标，依次存入数据元素内。按父结点号=子结点号/2，左孩号=父号*2， 右孩号=父号*2+1关系，访问各结点。对于非完全二叉树采用加虚结点变为完全二叉树的方式存储。见P3744 完全二叉树：树结点按从上到下，从左到右顺序排放的二叉树为完全二叉树。满二叉树：有2k-1个结点的二叉树为满二叉树。45 二叉树链式存储结构：二叉链表存储结构见P37。46 树转换成二叉树方式：横连仅留左子树再顺时针转45度。二叉树转换成树则反之。47 二叉树遍历：前根序：根左右。中根序：左根右。后根序：左右根。有关代码见P41。48 二叉排序树特点：
12、对于升序：根结点值=左孩值，根结点值=右孩值。49 平均查找长度：为查找元素在表中的位置而与关键字比较次数的期望值。用ASL表示，其计算公式见P45。50 线性查找法特点：事先不要求排序，对存储结构无要求，但查找速度慢，特别是对长表的查找速度慢。其平均查找长度ASL=(n+1)/2。51 二分查找法特点：需事先对表排序，比较次数少，速度快，但事先排序耗费资源，其平均查找长度ASL=log2n。mid=(low+high)/2，如果小于中间值，要往左找因此要改high的值，此时，high=mid-1，如果大于中间值，要往右找因此要改low的值，low=mid+1，会图形法画出查找过程，见P465
13、2 散列查找特点：不需多次比较，一次就能访问所查元素的查找法。由关键字值利用散列函数计算查找元素的位置值。主要查找函数有：直接地址法，求模运算法（%），平方到中法，折叠法。53 构造散列函数的冲突概念： 二个记录的关键字值争夺同一个存储位置的现象称为冲突，这二个关键字值称为同义词。解决冲突的方法有：链地址法，见P4950。开地址法，见P5052。54 排序有关概念： 直接选择排序法：总比较次数=（n2-n）/2，最坏情况下总移动次数=3（n-1）,平均时间复杂度为：O(n2)量级。会图形法画出排序过程。见P52。55 直接插入排序法：最坏情况下的比较次数=（n+2）（n-1）/2，最坏情况下的
14、移动次数=（n2+3-4）.见P52。最好情况下的比较次数=n-1，最好情况下的移动次数=2（n-1），平均时间复杂度为：O(n2)量级。特点：算法易实现，当n比较小时是一种较佳的排序方法。n很大时不适用。会图形法画出排序过程见P53。56 二分插入排序法：比较次数比线性查找法少得多。比较的平均时间复杂度为O（nlog2n）量级，其移动次数与直接插入排序法同其时间复杂度为O(n2)量级。要会图形法画出排序过程。57 冒泡排序法：最坏情况下的比较次数=（n2-n）/2，最好情况下的比较次数=n-1，最好情况下的移动次数=0，平均时间复杂度为：O(n2)量级。会图形法画出排序过程P55.58 快速
15、排序法：最坏情况下的比较次数=（n2-n）/2，最好情况下的比较次数= nlog2n，最好情况下的移动次数=0，平均时间复杂度为：O(nlog2n)量级。会图形法画出排序过程P5759 第三章 操作系统60 操作系统的类型：61 多道批处理系统：多个作业同时放入内存，在一段时间内并行运行，它们可以交替使用CPU及外设。它不适于运行时要用户干预的作业，只适于运行处理时间要求不严，运行步骤严格。比较成熟的作业。62 分时操作系统：见第一章有关内容。它适于运行时要用户干预的作业，如程序调试，软件开发等。63 实时操作系统：能及时响应请求，快速反馈处理的操作系统。适于生产控制类的应用情况。另个还有，单用户，多用户操作系统，单任务多任务操作系统。DOS是单任务的，windows是多任务的。网络操作系统。64 操作系统的五大功能：65 处理机管理：管理CPU的合理分配与回收。即分配策略。实施方法，回收方式。66 存储管理：内存的合理分配和回收，数据的保护，实现虚拟内存。67 文件管理：实现文件的存储，检索，修改，解决文件的共享和保密保护。68 设备管理：实现外设的合理分配与回收。实现外设启动，实现处设与CPU并行工作。给用户提供一个好的工作环境。69 作业管理：为用
