资源描述
计算机软件技术基础复习2012
第二章 操作系统
【内容】
操作系统
1) 操作系统
ü 概念；引入操作系统的目的（系统管理人员角度、用户角度）
ü 操作系统的分类和功能；
2) 存储器管理
ü 存储器的层次；
ü 程序的逻辑地址、物理地址；重定位的概念；
ü 存储器管理的功能；
ü 虚拟存储器的概念和基本特征；
ü 分页存储和分段存储的概念、实现思想、区别；
ü 分页系统中逻辑地址到物理地址的转换；
3) 文件管理
ü 文件管理系统的功能；文件、文件系统、文件目录的概念；
ü 常见的目录结构；
4) 进程管理
ü 进程管理功能；进程的定义；进程的实体组成；进程控制块PCB的作用；
ü 进程的状态和转换（哪些状态之间可以直接转换、哪些之间不可以直接转换）；
ü [{]进程的协调（互斥与同步）；临界资源和临界区的概念
ü [{]信号量和P、V操作；利用信号量和PV操作，实现进程互斥和进程同步的方法；
ü 进程死锁的概念；死锁的原因；死锁的四个必要条件；死锁的预防和避免；
5) 作业管理
ü 作业管理功能；作业的概念；
ü 作业的四种状态；
第三章 基本数据结构及其运算
【内容】
3.1 数据结构的基本基本概念
\ o ng5Xy8`6Q K 数据结构研究的三个方面： I&F6WK @8V
（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；
(U8f.l'j.?Yn（3）对各种数据结构进行的运算。 BeY&L@
数据结构是指相互有关联的数据元素的集合。 &RI/cV
数据的逻辑结构包含：
~!\8l-K2l;p IEC （1）表示数据元素的信息；
:?6A9G;h*rZ5|4m(}V （2）表示各数据元素之间的前后件关系。
Qd!] V0z | 数据的存储结构有顺序、链接、索引等。
线性结构条件：
9R~%Zl\ }h （1）有且只有一个根结点；
_3`ziY （2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。 ;N?O$OJx?
3.2 线性表及其顺序存储结构A A@
3.2.1线性表及其运算
线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 g\G3V(\"|.r
在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表
又称为文件。
非空线性表的结构特征：
（1）且只有一个根结点a1，它无前件；
（2）有且只有一个终端结点an，它无后件；
_:F@A Lc z rx XE（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。
#P,S x/E J:C 线性表的顺序存储结构具有以下两个基本特点：
b qae6F} （1）线性表中所有元素的所占的存储空间是连续的；
S zH5kCT ? （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
9|6W T/k2w Dv r ai的存储地址为：ADR(ai)=ADR(a1) (i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。 0eM B p([{ l
顺序表的运算：插入、删除。 （详见14--16页）
3.2.2 栈及其运算 "s*SzxE1_ s
栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。
3a0f~L D k 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。
3.2.3 队列及其运算
队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。
队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。
队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。 5
循环队列：s=0表示队列空，s=1且front=rear表示队列满
4k{*{N9T~^(bP h4m$hO%]2.2.3
2.3线性链表及其运算
3F1Tg Fy @$E数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。
,` U'z8W} ^ l`在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
,G1Mi WvY,dg3b 链式存储方式即可用于表示线性结构，也可用于表示非线性结构。
线性链表，HEAD称为头指针，HEAD=NULL（或0）称为空表，如果是两指针：左指针（Llink）
指向前件结点，右指针（Rlink）指向后件结点。
线性链表的基本运算：查找、插入、删除。
3.4*it^$\Ef/}1s2.52.52.522222树与二叉树
qIW;v0O 树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
0O HY/Di 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。
&~ S^:P6].s5e8K 二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 hL j-N
二叉树的基本性质： W SK J.M
（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点； 2K6~v {8@]
（2）深度为m的二叉树最多有2m-1个结点；
/Z `en s（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；
2CW T#v/UkM'Otx'm（4）具有n个结点的二叉树，其深度至少为[log2n] 1,其中[log2n]表示取log2n的整数部分；
^1T,I J0J3m5l（5）具有n个结点的完全二叉树的深度为[log2n] 1；
2O:X)D"e] e9Q IB（6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n），有以下结论：
① 若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)；
② n K VjS}-o②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；
③ 若2k 1≤n，则编号为k的结点的右子结点编号为2k 1；否则该结点无右子结点。
④ 满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。
⑤ 完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
⑥ B+C/yj l 二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。+_
二叉树的遍历： .a*]
（1） 前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；
(w/n`z(kT（2） 中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；
（3） 后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。
第四章（一） 算法
【内容】
算法：是指解题方案的准确而完整的描述。3\JH$_ B 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 T.AKM
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：
（1）可行性；
` O i }E9gx#_hM（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；
（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；
（4）拥有足够的情报。
y(i^)YT@,b&mG2X$s _算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。
基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 +RU_
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、回溯法。
,[cFi]{^ [算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
用平均性态，最坏情况复杂性两种方法来分析算法的工作量。
owC8T3n E4D算法空间复杂度是指执行这个算法所需要的内存空间。
第四章（二） 查找与排序技术
【内容】
一． 基本-g6}2H*[Ww a6W'X-{3.13.查找技术
顺序查找的使用情况：
（1）线性表为无序表；
（2）表采用链式存储结构。
二分法查找只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n
次。
二． 基本排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
交换类排序法：（1）冒泡排序法，需要比较的次数为n(n-1)/2； （2）快速排序法。
插入类排序法：（1）简单插入排序法，最坏情况需要n(n-1)/2次比较；（2）希尔排序法，最坏情况需要O(n1.5)次比较。
选择类排序法：（1）简单选择排序法, 最坏情况需要n(n-1)/2次比较；（2）堆排序法，最坏情况需要O(nlog2n)次比较。
第五章 数据库技术
【内容】
5．1 数据库系统的基本概念
数据：实际上就是描述事物的符号记录。
数据的特点：有一定的结构，有型与值之分，如整型、实型、字符型等。而数据的值给出了符合定型的值，如整型值15。
数据库：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。
数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。
数据库管理系统：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。
数据库管理系统功能：
（1）数据模式定义：即为数据库构建其数据框架；
（2）数据存取的物理构建：为数据模式的物理存取与构建提供有效的存取方法与手段；
（3）数据操纵：为用户使用数据库的数据提供方便，如查询、插入、修改、删除等以及简单的算术运算及统计；
（4）数据的完整性、安生性定义与检查；
（5）数据库的并发控制与故障恢复；
（6）数据的服务：如拷贝、转存、重组、性能监测、分析等。
为完成以上六个功能，数据库管理系统提供以下的数据语言：
（1）数据定义语言：负责数据的模式定义与数据的物理存取构建；
（2）数据操纵语言：负责数据的操纵，如查询与增、删、改等；
（3）数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。
数据语言按其使用方式具有两种结构形式：交互式命令(又称自含型或自主型语言)宿主型语言（一般可嵌入某些宿主语言中）。
数据库管理员：对数据库进行规划、设计、维护、监视等的专业管理人员。
数据库系统：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。
数据库应用系统：由数据库系统、应用软件及应用界面三者组成。
文件系统阶段：提供了简单的数据共享与数据管理能力，但是它无法提供完整的、统一的、管理和数据共享的能力。
层次数据库与网状数据库系统阶段 ：为统一与共享数据提供了有力支撑。
关系数据库系统阶段
数据库系统的基本特点：数据的集成性 、数据的高共享性与低冗余性 、数据独立性（物理独立性与逻辑独立性）、数据统一管理与控制。
数据库系统的三级模式：
（1）概念模式：数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图；
（2）外模式：也称子模式与用户模式。是用户的数据视图，也就是用户所见到的数据模式；
（3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。
数据库系统的两级映射：
（1）概念模式到内模式的映射；
（2）外模式到概念模式的映射。
5.2 数据模型
数据模型的概念：是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表与操作提供一个抽象的框架。描述了数据结构、数据操作及数据约束。
E-R模型的基本概念
（1）实体：现实世界中的事物；
（2）属性：事物的特性；
（3）联系：现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多的联系。
E-R模型三个基本概念之间的联接关系：实体是概念世界中的基本单位，属性有属性域，每个实体可取属性域内的值。一个实体的所有属性值叫元组。
E-R模型的图示法：（1）实体集表示法； （2）属性表法； （3）联系表示法。
层次模型的基本结构是树形结构，具有以下特点：
（1）每棵树有且仅有一个无双亲结点，称为根；
（2）树中除根外所有结点有且仅有一个双亲。
从图论上看，网状模型是一个不加任何条件限制的无向图。
关系模型采用二维表来表示，简称表，由表框架及表的元组组成。一个二维表就是一个关系。
在二维表中凡能唯一标识元组的最小属性称为键或码。从所有侯选健中选取一个作为用户使用的键称主键。表A中的某属性是某表B的键，则称该属性集为A的外键或外码。
关系中的数据约束：
（1）实体完整性约束：约束关系的主键中属性值不能为空值；
（2）参照完全性约束：是关系之间的基本约束；
（3）用户定义的完整性约束：它反映了具体应用中数据的语义要求。
4.3关系代数
关系数据库系统的特点之一是它建立在数据理论的基础之上，有很多数据理论可以表示关系模型的数据操作，其中最为著名的是关系代数与关系演算。
关系模型的基本运算：
（1）插入 （2）删除 (3)修改 （4）查询（包括投影、选择、笛卡尔积运算）
5.4 数据库设计
数据库设计是数据应用的核心。
数据库设计的两种方法：
（1）面向数据：以信息需求为主，兼顾处理需求；
（2）面向过程：以处理需求为主，兼顾信息需求。
数据库的生命周期：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。
需求分析常用结构析方法和面向对象的方法。结构化分析（简称SA）方法用自顶向下、逐层分解的方式分析系统。用数据流图表达数据和处理过程的关系。对数据库设计来讲，数据字典是进行详细的数据收集和数据分析所获得的主要结果。
数据字典是各类数据描述的集合，包括5个部分：数据项、数据结构、数据流（可以是数据项，也可以是数据结构）、数据存储、处理过程。
数据库概念设计的目的是分析数据内在语义关系。设计的方法有两种
（1）集中式模式设计法（适用于小型或并不复杂的单位或部门）；
（2）视图集成设计法。
设计方法：E-R模型与视图集成。
视图设计一般有三种设计次序：自顶向下、由底向上、由内向外。
视图集成的几种冲突：命名冲突、概念冲突、域冲突、约束冲突。
关系视图设计：关系视图的设计又称外模式设计。
关系视图的主要作用：
（1）提供数据逻辑独立性；
（2）能适应用户对数据的不同需求；
（3）有一定数据保密功能。
数据库的物理设计主要目标是对数据内部物理结构作调整并选择合理的存取路径，以提高数据库访问速度有效利用存储空间。一般RDBMS中留给用户参与物理设计的内容大致有索引设计、集成簇设计和分区设计。
数据库管理的内容：
（1）数据库的建立；
（2）数据库的调整；
（3）数据库的重组；
（4）数据库安全性与完整性控制；
（5）数据库的故障恢复；
（6）数据库监控。
附：题型
三． 单选题（每题1分，共30分）
四． 填空题（每空1分，共20分）
五． 名词解释（每题3分，共15分）
六． 简答题（每题4分，共20分）
七． 应用题（两题，共15分）
一、选择题
1. 已知： int x; 下列语句正确的是（ A ）。
A. int *p=&x; B. int *p=x;
C. int p=&x; D. int *p=*x;
2. int a[ ]={1,2,3,4,5},b[5],*p; 则下列语句中不正确的语句是（ D ）。
A. p=b+1; B.p=&a[3];
C. p=a; D.b=a;
3. 设有以下说明语句
struct node{ int a；float b；}；
struct node node1,node2,*pnode;
则下列语句中正确是（ A ）。
A. node1=node2； B. pnode.a=10；
C. return (node1+node2)； D. scanf(“%d %f”,node1);
4. 线性链表不具有的特点是（ A ）。
A. 可随机访问任一个结点 B．不必事先估计所需存储空间大小
C. 插入与删除时不必移动元素 D．所需空间与线性表长度成正比
5. 若让元素1，2，3依次进栈，则出栈次序不可能出现（ C ）种情况。
A．3，2，1 B．2，1，3
C．3，1，2 D．1，3，2
6. 有向图的邻接表中，顶点Vi的出度是（ B ）。
A. 依附于Vi的弧数 B.Vi链表中的邻接结点个数
C. Vi在表结点中出现的次数 D. Vi度的一半
7. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ B ）的二叉树。
A．空或只有一个结点 B．深度等于其结点数
C．任一分支结点均无左子树 D．任一分支结点均无右子树
8. 在一个单链表中,若指针p指向某一结点，指针q指向p的前驱结点，要在q与p之间插入一个由s所指的结点，则执行（ D ）。
A．s→next=p→next；p→next=s； B．p→next =s；s→next =q；
C．p→next =s→next；s→next =p； D．q→next =s；s→next =p；
9. 如果以链表作为栈的存储结构，则出栈操作时（ C ）。
A．必须判别栈是否满 B．对栈不作任何判别
C．必须判别栈是否空 D．判别栈元素的类型
10. 设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针操作为（ A ）。
A. p->next=p->next->next B．p=p->next
C．p=p->next->next D．p->next=p
11. 具有6个顶点的无向图至少需要（ D ）条边才能确保是一个连通图。
A. 6 B．7
C．4 D．5
12. 对线性表进行二分查找时，要求线性表必须满足（ C ）。
A、以顺序方式存储 B、以链接方式存储
C、以顺序方式存储，且结点按关键字有序排列 D、以链接方式存储，且结点按关键字有序排列
13. 对于进程的描述，下列说法错误的是（ C ）。
A．一个进程可以包含若干个程序 B. 一个程序可能被多个进程执行
C．一个程序仅对应一个进程 D.进程是程序的一次执行过程
14. 临界区是指并发进程中访问共享变量的（ D ）段。
A.管理信息 B.信息存储
C.数据 D.程序
15. 若当前进程因时间片用完而让出处理机时，该进程应转变为（ B ）状态。
A、执行 B、就绪 C、阻塞 D、唤醒
二．填空题
1. 数据结构作为一门学科，主要研究数据的 逻辑结构 、存储结构以及 数据操作集合 三方面内容。
2. 当对一个线性表经常进行插入或删除操作时，则宜采用 链式 存储结构；而经常进行的是访问操作，而很少进行插入或删除操作时，则宜采用 顺序 存储结构。
3. 在线性结构中，首结点有 0 个前驱结点，其余每个结点有且只有 1 个前驱结点。
4. 限定在表的一端进行插入，在表的另一端进行删除的线性表称为 队列 ；限定在表的一端进行插入和删除运算的线性表称为 栈 。
5. 一个8阶的下三角矩阵B按行优先顺序压缩存储在一维数组中，则数组的大小应设为 36 。
6. 按照二叉树的定义，具有3个结点的二叉树形态有 5 种；具有65个结点的完全二叉树其深度为 7 ; 深度为10的完全二叉树最多有 1023 个结点
7. 在长度为n的顺序表的第i个位置上插入一个元素，元素的移动次数为 n-i+1 ；删除第i个元素时，需要从前向后依次前移 n-i 个元素。(1≤i≤n+1)
8. 顺序存储结构的循环队列中，设front 和rear分别为队头和队尾指示器，该队列中能存放的最大元素的个数为M AX-1，则判断队列为满的条件为 front == (rear + 1) % MAX ，而判断队列为空的条件是 front==rear 。
9. 设D={A，B，C，D，E}，R={<A，B>，<C，D>，<D，B>，<C，E>}，结构（D，R）描述的数据结构是 图 。
10. 系统出现死锁一定是同时保持了 互斥条件 ， 部分分配条件 ， 不可剥夺条件 和环路条件这四个必要条件。
11. 操作系统通过 pcb（进程控制块） 记载、跟踪、控制进程的执行，它是进程存在的唯一标志。作业调度程序是从处于 后备 状态的作业中选取一个作业并把它装入主存。
12. 算法的复杂度主要包括______复杂度和空间复杂度。答：时间
13 算法的基本特征是可行性、确定性、______和拥有足够的情报。答：有穷性
14.数据结构包括数据的______结构和数据的存储结构。答：逻辑
15.数据的逻辑结构在计算机存储空间中的存放形式称为数据的______。答：存储结构
16. 设一棵完全二叉树共有500个结点，则在该二叉树中有______个叶子结点。答：250
17. 数据结构包括数据的逻辑结构、数据的 ______以及对数据的操作运算。答：存储结构
18. 顺序存储方法是把逻辑上相邻的结点存储在物理位置______的存储单元中。答：相邻
19 Jackson结构化程序设计方法是英国的M.Jackson提出的，它是一种面向______的设计方法。答：数据结构
20、操作系统的形成经历了（手工操作）、（成批处理系统）、（执行系统）和（多道程序系统）阶段。
21、通常所说操作系统的五大功能是文件管理、设备管理、（处理机管理）、（存储器管理）和（作业管理）。
22、多道批处理系统的主要优点是资源利用率高、系统吞吐量大。
23、作业调度是从（后备作业）中选一道作业，为它分配资源，并为它创建（相应的进程）。
24、程序顺序执行具有（顺序性）、（封闭性）和（可再现性）。
25、程序并发执行时具有（间断性）、（失去封闭性）和（不可再现性）。
26 数据库管理系统常见的数据模型有层次模型、网状模型和______三种。答：关系模型
27 一个项目具有一个项目主管，一个项目主管可管理多个项目，则实体"项目主管"与实体"项目"的联系属于______的联系。答：1对多#1：N
28 数据库设计分为以下6个设计阶段：需求分析阶段、______、逻辑设计阶段、物理设计阶段、实施阶段、运行和维护阶段。答：概念设计阶段#数据库概念设计阶段
29 关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、______和自定义完整性。答：参照完整性
三．名词解释
1．数据
数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。
2。数据元素
数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
3。满二叉树
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
满二叉树的特点：① 叶子结点都在最下一层；② 只有度为0和度为2的结点。
4。完全二叉树
对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。
完全二叉树的特点是：① 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在左面连续的位置；② 如果有度为1的结点，只可能有一个，且该结点只有左孩子。
5.原语：它是由若干条机器指令所构成，用以完成特定功能的一段程序，为保证其操作的 正确性，它应当是原子操作，即原语是一个不可分割的操作。
6.操作系统：操作系统是控制和管理计算机硬件和软件资源，合理地组织计算机的工作流程，以及方便用户的程序的集合。其主要功能是实现处理机管理、内存管理、I/O设备管理、文件管理和用户接口。
7．虚拟存储器
指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。从用户观点看，虚拟存储器具有比实际内存大得多的容量。这既方便了用户，又提高了内存的利用率和系统的吞吐量。
8.逻辑地址与物理地址:
在具有地址变换机构的计算机中，允许程序中编排的地址和信息实际存放在内存中的地址有所不同。逻辑地址是指用户程序经编译后，每个目标模块以0为基地址进行的顺序编址。逻辑地址又称相对地址。物理地址是指内存中各物理存储单元的地址从统一的基地址进行的顺序编址。物理地址又称绝对地址，它是数据在内存中的实际存储地址。
9.外视图(个别用户视图): 外视图是数据库的三个抽象层次中最靠近用户的一层，反映各个用户看待数据库的方式，是概念视图的某一部分的抽象表示。
10.内视图(存储视图): 内视图是数据库的三个抽象层次中最靠近物理存储的一层，反映数据的实际存储方式，是整个数据库实际存储的表示。
四．简答题
1.何时选用顺序表，何时选用链表作为线性表的存储结构？
答：因为在顺序表中插入或删除时，需要移动大量的数据，所以在需要提高查找效率，而较少插入或删除的情况下，可以采用顺序储存；链式存储结构便于插入和删除。但是不便于查找结点。所以对于需要经常修改线性表结点位置的情况下，采用链式存储为宜。
2.简述栈与队列的不同之处。
答：栈，队列都是一种线性结构，只是他们的运算规则不同。栈是遵循先进后出的运算规则，堆栈的操只能在栈的一端（栈顶）进行；队列则遵循先进先出的运算规则，队的操作只能在队列的队首删除，队尾插入。
3.假设图的顶点是A，B，C，D，…请根据下述邻接矩阵画出相应的有向图和无向图。
（1）0 1 1 1 （2） 0 1 1 0 0
1 0 1 1 0 0 0 1 0
1 1 0 1 1 0 0 0 1
1 1 1 0 0 1 0 1 0
答：（1）的无向图如图1.27（a）所示；（2）的有向图如图1.27（b）所示。
B
A
C
B
D
D
A
C
E
（a） （b）
4.对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题：
（1）图中有多少条边？
（2）任意两个顶点i和j是否有边相连？
答：（1）采用邻接矩阵表示时，无向图的总边数为所有数值之和除以2；有向图的总边数为各行数值之和。采用邻接表表示时，无向图的边数为内部顶点个数除以2；有向图的边数为内部顶点个数。
（2）对于无向图是以图中i行和j列的交叉点的值是否为1；对于有向图是以图中i行j列交叉点或i列j行交叉点的值是否为1来判断顶点i和j是否有边相连。
5. 试比较单道与多道批处理系统的特点及优缺点.
答：a. 单道批处理系统是最早出现的一种 OS，它具有自动性，顺序性和单道性的特点；---多道批处理系统则 具有调度性，无序性和多道性的特点；
b. 单道批处理系统是在解决人机矛盾及 CPU 和 I/O 设备之间速度不匹配的矛盾中形成的，旨在提高系统 资源利用率和系统吞吐量，但是仍然不能很好的利用系统资源；---多道批处理系统是对单道批处理系统 的改进，其主要优点是资源利用率高，系统吞吐量大；缺点是平均周转时间长，无交互能力.
6. 实现分时系统的关键问题是什么?应如何解决?
答：a. 关键问题：及时接收，及时处理;
b. 对于及时接收，只需在系统中设置一多路卡，多路卡作用是使主机能同时接收用户从各个终端上输入 的数据；---对于及时处理，应使所有的用户作业都直接进入内存，在不长的时间内，能使每个作业都运 行一次.
7. 试说明进程在三个基本状态之间转换的典型原因.
答：a. 处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态变为执行状态.
b. 当前进程因发生某事件而无法执行，如访问已被占用的临界资源，就会使进程由执行状态转变为阻塞 状态.
c. 当前进程因时间片用完而被暂停执行，该进程便由执行状态转变为就绪状态.
8. 为什么要引入挂起状态?该状态具有哪些性质?
答：a. 引入挂起状态处于 5 中需要: 终端用户的需要，父进程的需要，操作系统的需要，对换的需要和负荷 调节的需要.
b. 处于挂起状态的进程不能接收处理机调度.
9.数据库体系结构中的三级结构 ：
答：数据库的体系结构分为三级：内部级、概念级、外部级。
外部级：最接近用户，是单个用户所能看到的数据特性。单个用户使用的数据视图的描述称为“外模式”。
概念级：涉及到所有用户的数据定义，是全局的数据视图。全局数据视图的描述称为“概念模式”。
内部级：最接于物理存储设备，涉及到实际数据存储的结构。物理存储数据视图的描述称为“内模式”。
10.DBMS的组成：
答：DBMS是由两大部分组成：查询处理器和存储管理器。
（1） 查询处理器有四个主要成分：DDL编译器、DML编译器、嵌入型DML的预编译器、查询运行核心程序。
（2） 存储管理器有四个主要成分：授权和完整性管理器、事务管理器、文件管理器、缓冲区管理器。
五．应用题
1. 已知一顺序表L={78，91，66，95，35，88，52，100}，编写一函数void dellist(listtype *L，int x)：删除顺序表L中第一个值小于x的元素，若该表中没有小于x的元素则不作任何操作。（10分）typedef struct
{ int data [10];
int num ;
} listtype ;
void dellist(listtype *L，int x); /* 删除函数声明 */
main( )
{ listtype list={78，91，66，95，35，88，52，100},*L; /* 初始化顺序表 */
int x;
L=&list;
l->num=8;
scanf(“%d”,&x);
dellist(L,x);
}
void dellist(listtype *L，int x)
{int i,j;
for(i=0;i<L->num;i++)
{ if(L->data[i]<x)
{ for (j=i+1; j<l->num; j++)
L->data[j-1]=L->data[j];
L->num--;
break;
}
}
}
2. 设有一个带头结点的单链表，表中各数据元素为无序的正整数，编写下列2个函数。（10分）
（1）node *find_min_node(node *h) ：找出头指针h指向的单链表中数据值最小的结点，打印该结点的数据值，并返回该结点指针；（5分）
（2）void switch_next_node(node *p) ：若指针p指向的结点数据值为奇数，则将该结点与其直接后继结点的数值交换，若指针p指向的结点无后继结点或数据值为偶数，则不做任何操作；（5分）
typedef struct node
{ int data;
struct node *next;
}node;
void main()
{
node *head,*p;
head=creat( ); /*创建单链表*/
p=find_min_node(head); /*查找数据值最小的结点*/
switch_next_node(p);
}
node *find_min_n
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
