2006—2009 复试试题整理

数据结构

2006

• 数据结构部分（共25分，第1题10分，第2题15分）
• 在（下图）所示的有向图中：

v1 v2

v4 v3

• 该图是强连通图吗？若不是，则给出其强连通分量。
• 请给出所有的简单路径及有向环。
• 请给出每个顶点的度，入度和出度。
• 请给出其邻接表及逆邻接表。
• 一棵n个结点的完全二叉树以向量作为存储结构，试写一非递归算法实现对该树的前序遍历。

6.28 一棵n个结点的完全二叉树以向量作为存储结构，试写一非递归算法实现对该树的前序遍历。



解：
　　以向量为存储结构的完全二叉树，其存储在向量中的结点其实是按层次遍历的次序存放的，可以根据课本第74页的内容设计出算法：

　typedef char DataType;//设结点数据类型为char
　#define M 100//设结点数不超过100
　typedef DataType BinTree[M];

　void Preorder(BinTree T)
　　{ //前序遍历算法
　　　int n=T[0];
　　　int p[M];//设置一队列存放结点值
　　　int i,j;
　　　for(i=1;i<=n;i++)
　　　　{
　　　　　if (i==1)//根结点
　　　　　　　j=1;
　　　　　else if(2*j<=n)//左子树
　　　　　　　　　j=2*j;
　　　　　　　else if(j%2==0&&j<n)//右兄弟
　　　　　　　　　　　j=j+1;
　　　　　　　　　else if(j>1)//双亲之右兄弟
　　　　　　　　　　　　j=j/2+1;
　　　　　p[i]=T[j];//入队
　　　　　printf("%c",p[i]);//打印结点值
　　　　}
　　}2007

二、 数据结构部分（共25分，第1题10分，第2题15分）

• 1、 已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点（若表中又这样的结点），同时释放被删结点的空间，这里的min和max是两个给定的参数。请分析你的算法时间复杂度。

解：
　　要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和min比较，然后删除这个结点。由于为已知其是有序链表，则介于min 和max之间的结点必为连续的一段元素序列。所以我们只要先找到所有大于min结点中的最小结点的直接前趋结点*p后，依次删除小于max的结点，直到第一个大于等于max结点*q位置，然后将*p结点的直接后继指针指向*q结点。


　　算法如下：
　　void DeleteList ( LinkList L, DataType min , DataType max )
　　　{
　　　　ListNode *p , *q , *s;
　　　　p=L;
　　　　while( p->next && p->next->data <=min ) 
　　　　//找比min大的前一个元素位置
　　　　　p=p->next;
　　　　q=p->next;//p指向第一个不大于min结点的直接前趋，q指向第一个大于min的结点
　　　　while(q &&q->data<max)
　　　　　{s=q;q=q->next;
　　　　　　free(s);//删除结点，释放空间
　　　　　}
　　　　p->next=q;//将*p结点的直接后继指针指向*q结点
　　　}

• 以二叉链表为存储结构，分别写出求二叉树高度算法及高度算法，所谓宽度是指二叉树的各层上，具有结点数最多的那一层上的结点总数。

(1)根据递归定义：二叉树的高度为：当为空树时，高度为0；当只有一个结点时，高度为1；其他情况：高度为max(根的左子树高度，根的右子树高度)+1

int Height(BinTree T){int hl,hr;if(T){//非空树if(t->lchild==NUll)&&(t->rchild==NULL)//只含一个根结点return 1;else{hl=height(t->lchild);//根的左子树高度hr=height(t->rchild);//根的右子树高度if (hl>=hr)return hl+1;else return h2+1;}}else return 0;}

(2)要求二叉树的宽度的话，则可根据树的高度设置一个数组temp。temp[i]用于存放第i层上的结点数(即宽度)。在访问结点时,把相应计算该结点下一层的孩子数并存入相应数组元素中，遍历左子树后向上返回一层计算右子树的宽度，并取出最大的一个数组元素作为树的宽度。

#define M 10 //假设二叉树最多的层数int Width(BinTree T){int static n[M];//向量存放各层结点数int static i=1;int static max=0;//最大宽度if(T){if(i==1) //若是访问根结点{n[i]++; //第1层加1 i++; //到第2层if(T->lchild)//若有左孩子则该层加1 n[i]++;if(T->rchild)//若有右孩子则该层加1 n[i]++;}else{ //访问子树结点i++; //下一层结点数if(T->lchild)n[i]++;if(T->rchild)n[i]++;}if(max<n[i])max=n[i];//取出最大值Width(T->lchild);//遍历左子树i--; //往上退一层Width(T->rchild);//遍历右子树}return max;}//算法结束

另：层序遍历6.29 以二叉链表为存储结构，一算法对二叉树进行层次遍历(层次遍历的定义见6.13).提示：应使用队列来保存各层的结点。



答： 
　#define M 100 //假设结点数最多为100
　typedef char DataType;//队列结点值类型
　typedef struct//定义一个队列
　　{
　　　int front;
　　　int rear;
　　　int count;
　　　DataType data[M];
　　}QBTree;

　static QBTree Q;//设一全局静态变量保存遍历结果
　void Levelorder(BinTree T)
　　{//层次遍历
　　　if(T)
　　　　{
　　　　　if(QueueEmpty(&Q))
　　　　　　{ //根结点及子树结点入队
　　　　　　　EnQueue(&Q,T->data);
　　　　　　　if(T->lchild)
　　　　　　　　EnQueue(&Q,T->lchild->data);
　　　　　　　if(T->rchild)
　　　　　　　　EnQueue(&Q,T->rchild->data);
　　　　　　}
　　　　　else
　　　　　　{ //子树结点入队
　　　　　　　if(T->lchild)
　　　　　　　　EnQueue(&Q,T->lchild->data);
　　　　　　　if(T->rchild)
　　　　　　　　EnQueue(&Q,T->rchild->data);
　　　　　　}
　　　　　Levelorder(T->lchild);//遍历左子树
　　　　　Levelorder(T->rchild);//遍历右子树
　　　　}
　　}2008

二、数据结构（共25分）

• 1、请写出二叉树的中序非递归遍历的基本思想，然后写出算法，实现对二叉树的中序非递归遍历。

基本思想：根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：

对于任一结点P，1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；3)直到P为NULL并且栈为空则遍历结束/* c6-2.h 二叉树的二叉链表存储表示 */typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild; /* 左右孩子指针 */}BiTNode,*BiTree;Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType)){ /* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。

算法6.2 *//* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */SqStack S;BiTree p;InitStack(&S);Push(&S,T); /* 根指针进栈 */while(!StackEmpty(S)){while(GetTop(S,&p)&&p)Push(&S,p->lchild); /* 向左走到尽头 */Pop(&S,&p); /* 空指针退栈 */if(!StackEmpty(S)){ /* 访问结点,向右一步 */Pop(&S,&p);if(!Visit(p->data))return ERROR;Push(&S,p->rchild);}}printf("\n");return OK;}

• 2、（15分）对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为0的邻接到的顶点进行递归。

（1）、给出完成上述功能的图的邻接表的定义（结构）。（3分）（2）、定义在算法中使用的全局辅助数组。（2分）（3）、写出在遍历图的同时进行拓扑排序的算法。（10分）//stack.h头文件

#include <stdio.h>#include <malloc.h>#include <stdlib.h>

#define STACKSIZE 50#define STACKINCREMENT 20#define OVERFLOW -1#define OK 1#define ERROR -1

typedef struct{int *base;int *top;int stacksize;}Stack;

int InitStack(Stack &s) //创建一个空栈{s.base=(int*)malloc(STACKSIZE*sizeof(int));if(!s.base)return (OVERFLOW);s.top=s.base;s.stacksize=STACKSIZE;return (OK);}

int Push(Stack &s,int e){if((s.top-s.base)>s.stacksize){s.base=(int*)realloc(s.base,(STACKSIZE+STACKINCREMENT)*sizeof(int));if(!s.base)return(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}

• s.top++=e;

return (OK);}

bool Empty(Stack s){if(s.base==s.top)return true;else return false;}

int Pop(Stack &s){int e;e=*--s.top;return e;}//graph.h文件

//有向无环图的拓扑排序

#include <stdio.h>#include <malloc.h>#include <stdlib.h>

#define MAX 20#define NULL 0

typedef struct ArcNode //头节点{int adjvex; //该边所指向的顶点的位置struct ArcNode *nextarc; //指向下一条边}ArcNode;

typedef struct VNode //表节点{int data; //顶点信息int indegree; //节点的入度ArcNode *firstarc; //指向第一条依附该节点的边的指针}VNode,AdjList[MAX];

typedef struct{AdjList vertices; //表节点int vexnum; //节点的个数int arcnum; //边的条数}Graph;

int LocateVex(Graph G,int v) //返回节点v在图中的位置{int i;for(i=0;i<G.vexnum;++i)if(G.vertices[i].data==v)break;else continue;if(i<G.vexnum)return i;else return -1;}

void CreateGraph(Graph &G){int m,n;printf("请输入图的节点数: ");scanf("%d",&m);while(m<0){printf("Error!\n顶点数不能小于.\n");printf("请重新输入图的顶点数: ");scanf("%d",&m);}printf("请输入图的边数: ");scanf("%d",&n);while(n<0){printf("Error!

\n图的边数不能小于.\n");printf("请重新输入图的边数: ");scanf("%d",&n);}G.vexnum=m; //顶点数目G.arcnum=n; //边的数目int i,j,k;for(i=0;i<G.vexnum;++i) //初始化图的信息{G.vertices[i].data=i+1; //顶点信息G.vertices[i].firstarc=NULL;G.vertices[i].indegree=0; //开始时入度都为}//顶点信息printf("输出顶点信息:\n");for(i=0;i<G.vexnum;++i)printf("v%d\n",G.vertices[i].data);

int v1,v2,flag=0;for(k=0;k<G.arcnum;++k){printf("请输入第%d边的起点和终点: ",k+1);scanf("%d%d",&v1,&v2);

i=LocateVex(G,v1); //顶点v1在图中的位置j=LocateVex(G,v2); //顶点v2在图中的位置

if(i >=0 && j>=0){++flag;(G.vertices[j].indegree)++;ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=NULL;ArcNode *p1;if(! G.vertices[i].firstarc)G.vertices[i].firstarc=p;else{for(p1=G.vertices[i].firstarc;p1->nextarc;p1=p1->nextarc); //求该顶点的最后一个邻接顶点p1->nextarc=p; //将p插入到最后一个邻接顶点的后面}}else //没有该弧，删除掉{printf("没有该边!\n");k=flag;}}

//输出邻接表printf("构造的邻接表为:\n");printf("位置顶点弧\n");for(i=0;i<G.vexnum;++i){printf(" %d v%d",i,G.vertices[i].data);ArcNode *p=G.vertices[i].firstarc;if(p){while(p->nextarc){printf("->v%d",

p->adjvex+1);p=p->nextarc;}printf("->v%d\n",p->adjvex+1);}else printf("\n");}printf("输出个顶的的入度:\n");for(i=0;i<G.vexnum;++i){printf("%d顶点的入度为: %d\n",G.vertices[i].data,G.vertices[i].indegree);}}

int FirstAdjVex(Graph G,int v) //返回v的第一个邻接顶点{if(G.vertices[v].firstarc)return G.vertices[v].firstarc->adjvex;else return -1;}

int NextAdjVex(Graph G,int v,int w) //返回v中相对于w的下一个邻接顶点{int flag=0;ArcNode *p;p=G.vertices[v].firstarc;while(p){if(p->adjvex==w){flag=1;break;}p=p->nextarc;}if(flag && p->nextarc)return p->nextarc->adjvex;else return -1;}

bool Visited[MAX];

//深度优先遍历void DFS(Graph G,int v){Visited[v]=true;printf("v%d ",G.vertices[v].data);int w;for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!Visited[w])DFS(G,w);}

void DFSTraverse(Graph G){int v;for(v=0;v<G.vexnum;++v)Visited[v]=false;for(v=0;v<G.vexnum;++v)if(!Visited[v])DFS(G,v); //递归}//main.cpp文件

#include "graph.h"#include "stack.h"

void TopologicalSort(Graph G) //拓扑排序函数{int i,j,k;int count=0; //用来统计顶点的个数Stack s; //定义一个栈，用来保存入度为的顶点InitStack(s); //初始化栈for(i=0;i<G.vexnum;++i)if(G.vertices[i].indegree==0) //若第i个顶点的入度为，i表示顶点在图中的位置Push(s,i); //将第i个顶点入栈while(!Empty(s)){j=Pop(s); // 将为入度的顶点位置出栈，并保存到j中count++; //统计顶点的个数printf("v%d ",G.vertices[j].data); //输出入度为的顶点ArcNode *p;for(p=G.vertices[j].firstarc; p ;p=p->nextarc) //找与第j个顶点的邻接顶点，并将其入度减{k=p->adjvex;

• -(G.vertices[k].indegree);

if(G.vertices[k].indegree==0) //如果入度为,就入栈Push(s,k);}}if(count<G.vexnum) //count小于顶点的个数时候，说明有环，不符合拓扑排序的要求{printf("Error!\n图中有环!不是有向无环图!

\n");exit(0); //退出}}//主函数的实现void main(){Graph G;CreateGraph(G);printf("\n深度优先遍历输出为:\n");DFSTraverse(G);printf("\n拓扑排序为: \n");TopologicalSort(G);printf("\n");}/*请输入图的节点数: 5 8请输入图的边数: 输出顶点信息:v1 v2 v3 v4 v5请输入第边的起点和终点: 1 2请输入第边的起点和终点: 1 3请输入第边的起点和终点: 1 4请输入第边的起点和终点: 1 5请输入第边的起点和终点: 2 3请输入第边的起点和终点: 2 4请输入第边的起点和终点: 5 4请输入第边的起点和终点: 3 4构造的邻接表为:位置顶点弧0 v1->v2->v3->v4->v5 1 v2->v3->v4 2 v3->v4 3 v4 4 v5->v4输出个顶的的入度:1顶点的入度为: 0 2顶点的入度为: 1 3顶点的入度为: 2 4顶点的入度为: 4 5顶点的入度为: 1

深度优先遍历输出为:v1 v2 v3 v4 v5拓扑排序为:v1 v5 v2 v3 v4请按任意键继续. . .

• /

2009

二、数据结构部分（共25分）

• 1、以二叉链表为存储结构，分别写出求二叉树高度算法及高度算法，所谓宽度是指二叉树的各层上，具有结点数最多的那一层上的结点总数。

①求树的高度
思想：对非空二叉树，其深度等于左子树的最大深度加1。
Int Depth(BinTree *T)
{
int dep1,dep2;
if(T==Null) return(0);
else
{
dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
if(dep1>dep2) return(dep1+1);
else return(dep2+1);
}
②求树的宽度
思想：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
int Width(BinTree *T)
{
int
front=-1,rear=-1;/*
队列初始化*／
int flag=0,count=0,p;
/* p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*／if(T!

=Null)
{
rear++;
q[rear]=T;
flag=1;
p=rear;
}
while(front<p)
{
front++;
T=q[front];
if(T->lchild!=Null)
{
rear++;
q[rear]=T->lchild;
count++;
}
if(T->rchild!

=Null)
{
rear++;
q[rear]=T->rchild;
count++;
}
if(front==p)
/* 当前层已遍历完毕*/
{
if(flag<count)
flag=count;
count=0;
p=rear; /* p指向下一层最右边的结点*/ 
 }
}
/* endwhile*/
return(flag);
}//层序遍历void LevelOrderTraverse(BITree T,void(*Visit)(TElemType) ){LinkQueue q;QElemType a;if(T){InitQueue(q);EnQueue(q,T);While(!QueueEmpty(q)){DeQueue(q,a);Visit(a->data);If(a->lchild!=NULL)EnQueue(q,a->lchild);If(a->rchild!

=NULL)EnQueue(q,a->rchild);

}printf("\n");}}

• 2、（15分）对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为0的邻接到的顶点进行递归。

（1）、给出完成上述功能的图的邻接表的定义（结构）。（3分）（2）、定义在算法中使用的全局辅助数组。（2分）（3）、写出在遍历图的同时进行拓扑排序的算法。（10分）见2008

操作系统

2006

• 叙述进程上下文在进程执行活动中起什么作用，它（指进程上下文）都包括哪些部分，举例简述Unix System V上下文的组成情况。

所谓的“进程上下文”，可以看作是用户进程传递给内核的这些参数以及内核要保存的那一整套的变量和寄存器值和当时的环境等。进程上下文实际上是进程执行活动全过程的静态描述。我们把已执行过的进程指令和数据在相关寄存器与堆栈中的内容称为上文，把正在执行的指令和数据在寄存器和堆栈中的内容称为正文，把待执行的指令和数据在寄存器与堆栈中的内容称为下文。进程上下文包含：每个进程执行过的、执行时的以及待执行的指令和数据；在指令寄存器、堆栈、状态字寄存器等中的内容。进程上下文是可以按照层次规则组合起来的。在UNIX System V中，进程上下文由用户级上下文，寄存器上下文以及系统级上下文组成。

• 按照下面的要求，说出页式管理的实现过程.
• 虚拟空间如何划分页；
• 内存空间如何划分页面；
• 地址变换如何实现；
• 请求调页和预调页解决什么问题。

a用固定大小的页(Page)来描述逻辑地址空间，用相同大小的页框(Frame)来描述物理内存空间，由操作系统实现从逻辑页到物理页框的页面映射，同时负责对所有页的管理和进程运行的控制.每个进程以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的快空间。B将主存空间划分为大小相等的的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的快空间。

C页表在内存中起始地址F，页表长度M，页面大小L，逻辑地址A到物理地址E的变换过程如下：1：计算页号P（P=A/L）和页内偏移量W（W=A%L）2：比较页号P和页表长度M,若P>=M，越界中断，否则继续3：页表中页号P对应的页表项的地址=页表起始地址F+页号P*页表项长度，取出该页表项内容b，即为物理地址4：计算E=b*L+W，用得到的物理地址E去访问内存d页式管理采用请求调页或预调页技术实现了内外存存储器的统一管理，逻辑上扩大了内存的容量。//知识补充动态页式管理是在静态页式管理的基础上发展起来的。它分为请求页式管理和预调入页式管理。 请求页式管理和预调入页式管理在作业或进程开始执行之前，都不把作业或进程的程序段和数据段一次性地全部装入内存，而只装入被认为是经常反复执行和调用的工作区部分。其它部分则在执行过程中动态装入。请求页式管理与预调入页式管理的主要区别在它们的调入方式上。

请求页式管理的调入方式是，当需要执行某条指令而又发现它不在内存时或当执行某条指令需要访问其它的数据或指令时．这些指令和数据不在内存中，从而发生缺页中断，系统将外存中相应的页面调入内存。预调入方式是，系统对那些在外存中的页进行调入顺序计算。估计出这些页中指令和数据的执行和被访问的顺序，并按此顺序将它们顺次调入和调出内存。除了在调入方式上请求页式管理和预调入管理有些区别之外，其它方面这两种方式基本相同。因此，下面我们主要介绍请求页式管理。

虚拟内存是在磁盘上的一块区域，用以扩充主存的容量。虚拟内存里放的数据是内核不常用的信息，内存管理机制会把这些不常用的内存块保存到磁盘上，当要使用时再重新调入主存。虚拟内存的速度比主存慢很多。用作虚拟内存的磁盘空间叫交换空间(swap)。在Linux下，交换空间可以是一个分区，叫交换分区；也可以是一个文件，叫交换文件。交换分区速度快，但一旦设置，不易修改分区大小；交换文件速度较交换分区慢，但它的容量可随意调整。建议使用交换分区的形式。2007

• 回答有关进程管理的问题。
• 进程调度可分为哪两种基本方式？
• 对于这两种进程调度的基本方式，哪一种系统的开销更大？为什么？
• 常见的进程调度的算法又哪些？

a 非剥夺调度方式 剥夺调度方式b 剥夺调度方式开销更大，由于调度程序的执行涉及到多个进程和必须进行上下文切换，如果调度程序过于繁琐和复杂，将会耗去较大的系统开销。这在用户进程调用系统调用较多的情况下，将会造成响应时间大幅度增加。c FCFS,SJF,时间片轮转，优先级调度算法，高响应比优先调度算法，多级反馈队列调度算法

• 回答有关存储管理的问题。

（1）什么是动态链接？（2）用何种内存分配方法可以实现这种链接技术？为什么？a 动态链接分装入时动态链接和运行时动态链接，装入时动态链接：将用户源程序编译后所得的一组目标模块，在装入内存时，采取边装入边链接的链接方式。运行时动态链接时在执行时需要该目标模块时，才对它进行链接，其优点是便于修改和更新，便于实现对目标模块的共享。的共享。b 可以用分页和分段内存分配来实现，因为通过地址映射可以实现逻辑地址和物理地址的对应。2008

• 1、进程与线程的主要区别是什么？（12分）

a:进程和线程区别1拥有资源：无论是传统还是有线程的操作系统，进程都是拥有资源的基本单位，但线程可访问隶属于进程的资源。2并发性：引入线程操作系统中，不仅进程间可以并发，同一进程中多线程也可以并发3调度：在引入线程的操作系统中，线程是独立调度的基本单位，进程是拥有资源的基本单位。同一进程中，线程切换不会引起进程切换，而不同进程进行切换会引起线程切换。4：地址空间和其它资源：地址空间互相独立，同一进程各线程间共享进程的资源，某进程内线程对其它进程不可见。

另：进程和程序的区别1进程为程序及其数据在计算机上的一次运行活动，为一个动态概念。静态来看包括程序，数据和PCB。而程序是一组有序的指令集合，静态概念。2 进程是程序的一次执行过程，动态创建和消亡，有一定的生命周期。程序为一组指令集合，可长期保存。3：一进程可以执行一个或几个程序，一个程序也可以构成多个进程。进程可创建进程，程序不可以创建程序。

• 2、比较分段式与分页式存储管理方式的主要差别。（13分）

2：分段和分页存储管理方式区别和联系

分页分段目的页是信息物理单位，分页为实现离散分配方式，提高内存利用，提高内存利用率是信息逻辑单位，它含有一组其意义相对完整的信息。分段目的是为了更好地满足用户的需要长度页大小固定且由系统决定，由系统将逻辑地址分为页号和页内地址，是由机器硬件实现的段长不固定，通常由编译程序对流程序编译时根据信息性质来划分的。地址空间作业地址空间是一维的，即单一线性地址线性空间，只需一个标志符即可表示一个地址。作业地址空间是二维的，程序员在标志一个地址时，既需要给出段名，又需要给出段内地址碎片有内部碎片，无外部碎片有外部碎片无内部碎片动态链接和共享不易实现容易实现

2009

• 1、进程的最基本特征是（ ）和（ ），在Unix系统中，可通过调用系统（ ）来创建进程，系统调用（ ）来实现进程的自我终止，引入进程的主要目的是（ ）。

进程最基本的特征是（动态）和（并发）Unix系统中，可以通过调用系统调用(fork)来创建进程，系统调用（exit）来自我终止，引入进程主要目的是（为了更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性）。

• 2、什么是多道程序设计？在OS中引入该技术，带了什么好处？

计算机内存中同时存放几道相互独立的程序，他们爱内存管理程序的控制下相互交替的运行。其特征为：多道，宏观并行，微观串行。提高了资源利用率和系统吞吐量

• 3、虚拟存储器具有哪些基本特征？实现虚拟存储器的几个关键技术是什么？

多次性，对换性和虚拟性一定容量的内存和外存；页表机制，作为主要的数据结构；中断机构，当用户要访问的部分尚未调入内存，则产生中断；地址变换机构，逻辑地址到物理地址的变换。组成原理2006

• 提高存储器速度可以采用哪些措施？简要说明之。（10）

1 采用并行主存系统，有双端口存储器（空间并行）和多模块存储器（时间并行）双端口RAM是指同一个存储器有左右两个独立的端口，分别具有两组相互独立的地址线数据线和读写控制线，允许两个独立的控制器同时异步地访问存储单元多模块存储器分为单体多字存储器和多体低位交叉存储器，CPU速度比存储器快，故而能同时从存储器中取出N条指令，就可以充分利用CPU资源，提高运行速度，多体交叉存储器就是基于此种思想。高速缓存存储器，采用存储体系，通常将存储系统分为“Cache-主存”和“主存-辅存”层次。高速缓冲存储器就是利用程序访问的局部性原理，把程序中正在使用的部分放在一个高速且容量较小的Cache中，使CPU的访存操作大多针对Cache进行，从而使程序的执行速度大大提高。

• 画出DMA工作过程中数据传送的流程图。（8）

A预处理，主存地址->DAR,I/O设备地址->AR,传送数据个数->WC, 启动IO设备B数据传送，继续执行主程序，同时完成一批数据的传送C后处理，中断服务程序，做DMA结束处理D继续执行主程序数据传输阶段的细化

• B．1DMA请求->允许传送?->主存起始地址送总见，数据送I/O设备，修改主存地址->数据块传输结束->向CPU申请程序中断

• 解释“多重中断”，说明其处理原则。（7）

在CPU执行中断服务程序的过程中，又出现了新的更高优先级的中断请求，CPU暂停现行的中断服务程序，转去处理新的中断请求，种种中断为多重中断，又称中断嵌套。多重中断需用到中断屏蔽技术，在中断服务程序镇南关提前设置开中断指令，优先级别高地中断源有权中断优先级别低的中断源。2007 1即使停电，所偶的存储器的内容也不会丢失的半导体存储器叫（非易失性半导体存储器），可以分为：ROM,PROM,EPROM,Flash Memory（6）2简答题（8分）简述告诉缓冲存储器（Cache）工作原理2Cache和主存被分为若干大小相等的快，每块由若干字节组成，块的长度称为块长，由于Cache容量远小于主存容量，所以Cache中块数要远少于主存中的块数，它仅保存主存中最活跃的若干块的副本。故而Cache按照某种策略，预测CPU在未来一段时间内欲访存的数据，将其装入Cache。

当CPU发出读请求时，如果访存地址在Cache命中，就此将地址转换成Cache地址，直接对Cache进行读操作，与主存无关；若Cache未命中，则需继续访问主存，并把此字所在地块一次由主存调入Cache内。若此时Cache已满，则按某种算法将该块替换掉Cache中原来某个块的信息。当CPU发出写请求时，如果Cache命中，可能遇到Cache中内容和主存不一样的情况。如果Cache命中，按照一定的写策略处理，常见的方法有：全写法和写回法。3：举例说明ASIC芯片的应用。7目前，在集成电路界ASIC被认为是一种为专门目的而设计的集成电路。是指应特定用户要求和特定电子系统的需要而设计、制造的集成电路。ASIC的特点是面向特定用户的需求，ASIC在批量生产时与通用集成电路相比具有体积更小、功耗更低、可靠性提高、性能提高、保密性增强、成本降低等优点。ASIC可翻译为专用集成电路，一般它的ROM和RAM都在出厂前经过掩膜MASK。

如常用的红外遥控器发射芯片就是这种芯片。2008

• 1.1Cache存储器介于（CPU）和（主存）之间，它的工作（速度）数倍于主存，全部功能由（SRAM）实现，并对程序员是（透明）的。

1.2 伪指令格式大体上可以分为两类，一是（水平）型伪指令，二是（垂直）型伪指令。

• 1.3 所谓指令流水实际上是将一条指令的实现过程分成（时间）大体相等的几个阶段，然后使几条指令不同阶段在时间上（并行）起来执行。例如，执行浮点数加法运算，可以分成（取指），（译码和执行）和（写回）。（12）
• 2、（7分）计算机的指令格式与哪些计算机指标有关？一条指令必须包含哪些信息？指令字长是指一条指令中包含的二进制代码的位数，取决于操作码的长度，操作数地址码的长度和操作数地址的个数。一条指令中通常包含指令操作码字段和操作数地址码字段。
• 3、（6分）何谓计算机总线？从总线的组织方法区分，计算机总线有哪两个类型？他们各自的优缺点是什么？总线是一组能为多个部件分时共享的公共信息传输线路。

分为单总线和多总线///单总线是指所有模块都连接到单一的总线上，多总线是指系统中包含了多种类型不同的总线系统，为计算机系统中不同分级上的器件和设备提供性能不同的通信通道。单总线结构简单便于扩充，多总线结构则对于计算机的性能提高非常有限2009

• 1、I/O与主机交换信息，共有（ ）、（ ）、（ ）、（ ）和（ ）五种控制方式。

1I/O与主机交换信息，共有程序查询方式，程序中断方式，DMA方式，通道方式和（IO处理机方式）方式

• 2、在计算机系统中，为了管理中断，硬件上通常有哪些设置？各有什么作用？

2中断判优 用于多重中断中断隐指令 关中断，保存断点，引出中断服务程序中断屏蔽 用于多重中断

• 3、若计算机主频为100MHz，每个指令周期平均包含2个机器周期，每个机器指令周期包含2个时钟周期。求该系统平均指令执行速度。若频率不变，但每条指令平均含有5个机器周期，每个机器周期含有4个时钟周期，求平均指令执行速度。

经典算法