计算机软件基础

《计算机软件基础》由会员分享，可在线阅读，更多相关《计算机软件基础（2页珍藏版）》请在金锄头文库上搜索。

1、1、基础知识计算机的基本组成 控制器：计算机的控制部件，它控制计算机各部分自动协调工作，它完成对指令的解释和 执行。 运算器：对数据进行加工的部件，它可对数据进行算术运算和逻辑运算。 存储器：是计算机的记忆装置，用来存放程序和数据。 输入设备：是外部向计算机传送信息的装置 输出设备：将计算机内部二进制形式的信息转换成人们所需要的或其他设备能接受和识别 的信息形式。计算机的应用分类 数值计算（科学计算） 数据和数据处理 过程控制（实时控制） 辅助设计人工智能二、数据结构 1、概念：数据，二叉排序树,栈，队列，二叉树，树，数组，线性表，图。 2、了解每一种查找方法的思想，并会求查找成功的平均查找长

2、度。 3、什么是，二叉排序树查找的基本思想以及二叉排序树的生成。 4、排序分类：直接插入排序，简单选择排序，冒泡排序，快速排序，归并排序 5、查找的方法：顺序查找，折半查找，分块查找，哈希查找等。 6、二叉树的存储结构链式存储。树和森林转换为二叉树。 7、霍夫曼树的构造。算法分析 解一个问题，往往有若干不同的算法，这些算法决定着根据该算法编写的程序的 性能好坏。那么，在保证算法正确性的前提下，如何确定算法的优劣就是一个值得研究的 课题。在算法的分析中，一般应考虑以下 3 个问题： 1）算法的时间复杂度； 2）算法的空间复杂度； 3）算法是否便于阅读、修改和测试1线性表的定义线性表（linear

3、 list）是 n（n0）个数据元素 a1，a2，,an 组成的有限序列。其 中 n 称为数据元素的个数或线性表的长度，当 n=0 时称为空表，n0 时称为非空表 2线性表的特征 从线性表的定义可以看出线性表的特征： 有且仅有一个开始结点(表头结点) a1，它没有直接前驱，只有一个直接后继； 有且仅有一个终端结点(表尾结点) an，它没有直接后继，只有一个直接前驱； 其它结点都有一个直接前驱和直接后继； 元素之间为一对一的线性关系。 栈的定义栈(stack)是运算受限制的线性表，其元素的插入和删除只能在线性表的同一端进 行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(top)

4、，另一端为 固定的一端，称为栈底(bottom)。不含任何数据元素的栈称为空栈。 队列的定义 队列也是一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进 行删除的线性表称为队列(queue)。允许插入的一端称为队尾(rear)，允许删除的一端称为队 头（front） 。 队列是一种先进先出（First In First Out）的特殊线性表，或称 FIFO 表。若队 列中没有任何元素，则称为空队列，否则称为非空队列 树(Tree)是 n(n0)个结点的有限集合。当 n=0 时称为空树，否则在任一非空树中：(1) 有且仅有一个称为该树之根的结点；(2) 除根结点之外的其余结点可分为

5、m(m0)个互不相交的集合 T1，T2，Tm，且其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。基本术语： 结点的度：一个结点拥有的子树数目。如 A 结点的度为 3，它有三个子树 T1、T2 和 T3。E、F 结点的度为 0，它们没有子树。叶子：度为零的结点称叶子或终端结点。树的度：一棵树上所有结点的度的最大值就是这棵树的度。 结点的层次：根结点的层数为 1，其它任何结点的层数等于它的父结点的层数加 1。树的深度：一棵树中，结点的最大层次值就是树的深度。森林：森林是 m(m0)棵互不相交的树的集合。孩子(child)：某结点子树的根称为该结点的孩子结点。双亲(parent)：

6、一个结点是它的那些子树的根的双亲结点。兄弟(sibling)：同一个双亲的孩子之间互为兄弟。如 A 是 B、C、D 的双亲；B、C、D 是 A 的孩子；B、C、D 互为兄弟。堂兄弟(cousins)：其双亲在同一层的结点互为堂兄弟。如 G 与 E、F、H、I 互为堂兄弟。有序树：树 T 中各子树 T1，T2，Tn 的相对次序是有意义的，则称 T 为有序树。在有 序树中，改变了子树的相对次序就变成了另一棵树。二叉树的定义：一个二叉树是一个有限结点的集合，该集合或者为空，或由一个根结点和 两棵互不相交的被称为该根的左子树和右子树的二叉树组成。二叉树有下面两个主要特点：(1) 每个结点最多只能有两个

7、孩子，即二叉树中不存在度大于 2 的结点。(2) 二叉树的子树有左、右之分，其次序不能任意颠倒。二叉树可以有五种基本 形态。二叉树的三种遍历方式： (1) 先序遍历：若二叉树为空，则空操作；否则 访问根结点； 先序遍历左子树； 先序遍历右子树。 (2) 中序遍历：若二叉树为空，则空操作；否则 中序遍历左子树； 访问根结点； 中序遍历右子树。 (3) 后序遍历：若二叉树为空，则空操作；否则 后序遍历左子树； 后序遍历右子树。 访问根结点；树的二叉链表表示法二叉链表表示法又称二叉树表示法，或孩子兄弟表示法。即以二叉链表作为树 的存储结构。链表中结点的两个指针域分别指向该结点的第一个孩子和下一个兄弟

8、结点。树的遍历有两种次序：一种是先序遍历树；另一种是后序遍历树1一般树转换为二叉树步骤：(1) 加线：亲兄弟之间加一虚连线。 (2) 抹线：抹掉(除最左一个孩子外)该结点到其余孩子之间的连线。(3) 旋转：新加上去的虚线改实线且均向右斜(rchild)，原有的连线均向左斜(lchild)。2森林转换为二叉树步骤：(1) 将各棵树分别转换为二叉树。(2) 按给出森林中树的次序，依次将后一棵二叉树作为前一棵二叉树根结点的右 子树，则第一棵树的根结点是转换后二叉树的根。例如，给定一组权值2，7，4，8，图 3-20 给出了构造相应霍夫曼树的过程。二叉排序树(binary sort tree)或者是一

9、棵空树；或者是具有下列性质的二叉树。(1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2) 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；(3) 它的左、右子树也分别为二叉排序树。二叉排序树查找的思想是：(1) 当二叉排序树不空时，首先将给定值 K 与根结点的关键字进行比较，若相 等则查找成功；(2) 若给定值 K 小于根结点的值，则继续在根的左子树中查找；若给定值 K 大 于根结点的值，则继续在根的右子树中查找。2二叉排序树的生成对一组数据序列K1，K2，Kn，先设一棵空二叉树，然后依次将序列中的 元素生成结点后逐个插入到已生成的二叉排序树中。步骤

10、如下：(1) K1 是二叉排序树的根；(2) 若 K2K1，则 K2 所在的结点应插入到 K1 的左子树上；否则插入到 K1 的 右子树上；(3) 读 Ki，若 Ki K1(根)，则插入到根的左子树上，否则 Ki 插入到根的右子树上；(4) 若 in，则继续执行步骤(3)，否则结束。3、 操作系统 1、操作系统的功能、类型和基本特征。 2、一些基本概念，如：操作系统、进程、文件、作业、死锁、进程控制块、作业步、作 业控制块 3、进程管理、作业管理、文件管理。1进程的特性(1) 进程与程序的联系和区别。 联系：程序是构成进程的组成部分之一，一个进程的运行目标是执行它所对 应的程序。从静态的角度看

11、，进程是由程序、数据和进程控制块(PCB)三部分组成的。 区别：程序是静态的，而进程是动态的。进程是程序的执行过程，因而进程是有生命周期的，有诞生，也有消亡。因此， 程序的存在是永久的，而进程的存在是暂时的，它动态地产生和消亡。一个进程可以执行 一个或几个程序，一个程序亦可以构成多个进程。进程具有创建其它进程的功能，被创建 的进程称为子进程，创建者称为父进程，从而构成进程家族。2) 进程的特性。 动态性。进程是程序的执行过程， “执行”本身就是动态的。因此进程由“创建” 而产生，由“撤消”而消亡，因拥有处理机而得到运行。 并发性。进程是为了实现系统内并发执行而引入的概念，所以并发性是进程 与生

12、俱来的特性。 独立性。一个进程是一个相对完整的调度单位，它可以获得处理机并参与并 发执行。 异步性。每个进程按照各自独立的、不可预知的速度向前推进。3进程的状态及其状态转换根据进程在执行过程中的不同情况，通常可以将进程分成三种不同的状态。2进程调度算法 1) 先来先服务 2) 最短进程优先 3) 时间片轮转法 4) 优先级法1 设备管理的基本任务是： 向用户提供使用外部设备的统一的接口，按照用户的要求和设备的类型，控制设备进 行工作，完成用户的 I/O 请求。 在多道程序环境下，当多个进程竞争使用设备时，按照一定的策略分配和管理设备， 以使系统能有条不紊地工作。 充分利用中断技术、通道技术和缓

13、冲技术，提高 CPU 与设备、设备与设备之间的并 行工作能力，以充分利用设备资源，提高外部设备的使用效率。2设备的分类外部设备按其用途可分为输入型设备(如光电输入机、卡片输入机等)、输出型设 备(如各种类型打印机、绘图仪等)以及输入输出型设备(如磁盘、磁带、可读写光盘等)。外部设备按其所属关系可分为两类。(1) 系统设备。如输入机、打印机、终端、磁盘等。(2) 用户设备。如扫描仪、绘图仪等。 从资源分配角度来看，外部设备又可分为三类。(1) 独占设备。如打印机、终端等。(2) 共享设备。例如，多个进程可以交替地从磁盘上读取信息，所以磁盘是共享设 备。(3) 虚拟设备。2文件的分类文件按其性质和

14、用途可分为： (1) 系统文件：有关操作系统及其它系统程序的信息所组成的文件。这类文件对用户不直 接开放，只能通过系统调用为用户服务。(2) 库文件：由标准子程序及常用的应用程序组成的文件。这类文件允许用户调用，但不 允许用户修改。(3) 用户文件：由用户建立的的文件。这类文件根据使用情况又可以分为三种类型：临时 文件；档案文件；永久文件。根据文件的保护方式，文件可分为三类： (1) 只读文件允许文件主及核准的用户读，但不允许写。 (2) 读写文件允许文件主及核准的用户读、写，但禁止未核准的用户读、写。 (3) 不保护文件所有用户都可以存取。按文件的存取方式，可把文件分为： (1) 顺序文件只

15、能按顺序依次访问其中内容的数据文件。 (2) 随机文件可随时访问其内容的数据文件。 按信息的流向，又可把文件分为三类：(1) 输入文件只能读的文件，如读卡机或纸带输入机文件。(2) 输出文件只能写的文件，如打印机或穿卡机文件。(3) 输入输出文件既可读，又可写的文件。作业的基本概念作业：用户要求计算机处理的一个相对独立的任务。作业步：一个作业分解成几个必须顺序处理的工作步骤。作业一般由程序、数据、作业说明书三部分组成。程序是问题求解的算法描述； 数据是程序加工的对象，但有些程序未必使用数据；作业说明书是告诉操作系统本作业的 程序和数据按什么样的控制要求执行。作业说明书主要包括三方面内容：一是作

16、业基本情况描述，如作业名、用户名、所使用的编程语言等；二是作业的控制描述，如 C 语言程序先装入哪些模块、后再装入哪 些模块等各作业步的操作顺序以及某步不能正常执行时的出错处理方法等；三是作业的资 源要求描述，包括估计的主存需要量、计算时间、外设类型及数量、作业优先级等。在多道程序中，一个作业从提交给计算机，到最后产生结果，其间有多个作业状 态的转换，它们可以分为：(1) 提交。用户向计算机提交作业，此时称作业处于进入状态。(2) 收容。计算机通过设备管理程序，将用户作业送入后援存储器中，其后的状 态称为后备状态。处于后备状态的作业，实际上是一种随时等待调度的状态。(3) 执行。作业调度程序从处于后备状态的作业中选出若干作业，分配一定的资 源，使之投入运行，该状态也称为运行状态。(4) 完成。作业执行完毕后的状态，也称为完成状态，此时系统收回资源，并令 该作业退出系统。4、 数据库系统 1、基本概念：数据模型，实体，属