2013年山东科技大学数据结构与操作系统--真题及参考答案

《数据结构》部分

一、简答题（10分，每题5分）

1、数据元素之间的关系在计算机中的存储有几种表示方法？各有什么特点？（P6） 解：数据元素之间的关系在计算机中有四种不同的表示方法：

(1)顺序存储方法。数据元素顺序存放，每个结点只含有一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作(如插入、删除)效率较差。

(2)链式存储方法。每个结点除包含数据元素信息外还包含一组指针。指针反映数据元素间的逻辑关系。这种操作不要求存储空间连续，便于进行插入和删除等操作，但存储空间利用率较低。另外，由于逻辑上相邻的数据元素在存储空间上不一定相邻，所以不能对其进行随机存取。

(3)索引存储方法。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表。索引表中的索引指示结点的存储位置，兼有动态和静态特性。

(4)哈希(或散列)存储方法。通过哈希函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将哈希函数的值作为该数据元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存储，也不能折半存取。

2、对于堆排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其中哪种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？（P289）

答：若只从存储空间考虑，则应首先选取堆排序 方法，其次选取 快速排序 方法，最后选取 归并排序 方法；

若只从排序结果的稳定性考虑，则应选取归并排序方法； 若只从平均情况下最快考虑，则应选取快速排序方法；

若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。

二、应用题（55分）

1、证明：同一棵二叉树的所有叶子结点，在前序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同）。（8分）（例如先序abc，后序bca，中序bac。）(P128)

答：【答案】先序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。

2、设有正文AADBAACACCDACACAAD，字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。（10分）(P144;P148)

3、对于下图完成下列指定操作。（12分）

(1)从顶点A出发，求它的深度优先生成树。(P167;)

(2)从顶点E出发，求它的广度优先生成树。(P169;) (3)根据普利姆(Prim) 算法，求它的最小生成树。(P173)

4. 设哈希(Hash)表的地址范围为0～17，哈希函数为：H (K)=K MOD 16, K为关键字，用

线性探测再散列法处理冲突，输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)构造哈希表，试回答下列问题：（15分）（P257）

(1) 画出哈希表示意图。

(2) 若查找关键字63，需要依次与哪些关键字比较? (3) 若查找关键字60，需要依次与哪些关键字比较?

(4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 答：

（1）画表如下

（2） 查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

（4） 对于黑色数据元素，各比较1次；共6次；

对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，

ASL=1/11（6＋2＋3×3）＝17/11≈1.55 5．奇偶交换排序如下所述：对于初始序列A[1]，A[2],…,A[n],第一趟对所有奇数i（1<=iA[i+1]，则将两者交换；第二趟对所有偶数i（2<=iA[i+1]，则将两者交换；第三趟对所有奇数i（1<=i

(2) 写出用这种排序方法对35，70，33，65，24，21，33进行排序时，每一趟的结果。

【解答】

(1) 排序结束条件为，连续的第奇数趟排序和第偶数趟排序都没有交换。 (2)

第一趟奇数：35,70,33,65,21,24,33 第二趟偶数：35,33,70,21,65,24,33 第三趟奇数：33,35,21,70,24,65,33 第四趟偶数：33,21,35,24,70,33,65 第五趟奇数：21,33,24,35,33,70,65 第六趟偶数：21,24,33,33,35,65,70

第七趟奇数：21,24,33,33,35,65,70(无交换) 第八趟偶数：21,24,33,33,35,65,70(无交换) 结束

三、算法设计题（25分)

答题要求：

①用自然语言说明所采用算法的思想；

②给出每个算法所需的数据结构定义，并做必要说明； ③用C语言写出对应的算法程序，并做必要的注释。

1、编程实现单链表的就地逆置（额外存储空间只能使用指针）。 (10分)

答：

void reverse(LinkList &L)//单链表的就地逆置 { p=L->next;

if(p==NULL || p->next==NULL)

return OK;//空表和表中只有一个结点时，不用逆置。 while(p->next!=NULL) { q= p->next;

p->next=q->next; //删除结点q，但未释放 q->next=L->next;

L->next=q; //将q插入头结点之后

}

return OK; }//reverse

2、二叉树采用二叉链表存储结构，设计算法统计二叉树的深度（二叉树的最大层数）和宽度（二叉树中所有层中结点的最大个数）。（15分）

标准答案： ①求树的高度

思想：对非空二叉树，其深度等于左子树的最大深度加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

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

p=rear; /* p指向下一层最右边的结点*/

}

}

/* endwhile*/ return (flag); }

《操作系统部分》

一： 简单题 （共27分）

1：操作系统的四个基本特征是什么？并请分析它们之间的关系。（本小题3分）(P15)

答:操作系统的特征有并发,共享,虚拟和异步性.它们的关系如下:

(1)并发和共享是操作系统最基本的特征.为了提高计算机资源的利用率,操作系统必然要采用多道程序设计技术,使多个程序共享系统的资源,并发的执行.

(2)并发和共享互为存在的条件.一方面,资源的共享以程序(进程)的并发执行

为条件,若系统不允许程序并发执行,自然不存在资源的共享问题;另一方面,若系统不能对资源共享实施有效管理,协调好各个进程对共享资源的访问,也必将影响到程序的并发执行,甚至根本无法并发执行.

(3)虚拟以并发和共享为前提条件.为了使并发进程能更方便,更有效地共享资源,操作系统经常采用多种虚拟技术来在逻辑上增加CPU和设备的数量以及存储器的容量,从而解决众多并发进程对有限的系统资源的竞争问题.

(4)异步性是并发和共享的必然结果.操作系统允许多个并发进程共享资源,相互合作,使得每个进程的运行过程受到其他进程的制约,不再\一气呵成\这必然导致异步性特征的产生.

2：请简述进程和程序的差异、进程和线程的差异。（本小题6分）(P37;P72)

(定义：

一 程序只是一组指令的有序集合，

二 进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位；

三 线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),一个线程可以创建和撤销另一个线程；)

进程和程序区别和联系

（1)程序只是一组指令的有序集合，它本身没有任何运行的含义，它只是一个静态的实体。而进程则不同，它是程序在某个数据集上的执行。进程是一个动态的实体，它有自己的生命周期。反映了一个程序在一定的数据集上运行的全部动态过程。

（2)进程和程序并不是一一对应的，一个程序执行在不同的数据集上就成为不同的进程，可以用进程控制块来唯一地标识每个进程。而这一点正是程序无法做到的，由于程序没有和数据产生直接的联系，既使是执行不同的数据的程序，他们的指令的集合依然是一样的，所以无法唯一地标识出这些运行于不同数据集上的程序。一般来说，一个进程肯定有一个与之对应的程序，而且只有一个。而一个程序有可能没有与之对应的进程(因为它没有执行),也有可能有多个进程与之对应(运行在几个不同的数据集上)。

（3)进程还具有并发性和交往性，这也与程序的封闭性不同。

进程与线程区别与联系

(1)划分尺度:线程更小，所以多线程程序并发性更高；

(2)资源分配：进程是资源分配的基本单位，同一进程内多个线程共享其资源； (3)地址空间：进程拥有独立的地址空间，同一进程内多个线程共享其资源； (4)处理器调度：线程是处理器调度的基本单位；

(5)执行：每个线程都有一个程序运行的入口，顺序执行序列和程序的出口，但线程不能单独执行，必须组成进程，一个进程至少有一个主线程。简而言之,一个程序至少有一个进程,一个进程至少有一个线程。

3：处理死锁的基本方法有哪几种？并请分析它们的优缺点。（本小题4分）（P105）

(1)预防死锁---事先预防法破坏一个或几个产生死锁的必要条件。

实现简单，常用资源利用率和系统吞吐量低；

(2)避免死锁---事先预防法利用算法动态分配资源防止系统进入不安全状态。

实现较难，资源利用率和系统吞吐量较高；

(3)检测死锁---允许运行中发生死锁及时检测到死锁及其有关进程和资源 ；

实现很难，资源利用率和系统吞吐量高。

(4)解除死锁---与检测死锁配套使用，挂起或撤销相关进程，回收资源并重新分配检测和解除。

实现很难，资源利用率和系统吞吐量高。

4：“根据链接时间的不同，可把链接分为三种”，请问是哪三种？并请分析DLL方式的优点。（本小题4分）（程序的链接P120；P121）

静态链接，装入时动态链接，运行时动态链接。

（DLL是Dynamic Link Library的缩写，意为动态链接库。在Windows中，许多应用程序

并不是一个完整的可执行文件，它们被分割成一些相对独立的动态链接库，即DLL文件，放置于系统中。当我们执行某一个程序时，相应的DLL文件就会被调用。一个应用程序可有多个DLL文件，一个DLL文件也可能被几个应用程序所共用，这样的DLL文件被称为共享DLL文件。）

DLL方式的优点： （1）便于修改和更新。

（2）便于实现对目标模块的共享。

5：什么是SPOOLING技术？一个SPOOLING系统主要由哪几部分组成？（本小题4分）（P190）

SPOOLing是Simultaneous Peripheral Operation On-Line （即外部设备联机并行操作）的缩写，它是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。

1、输入井输出井

2、输入缓冲区和输出缓冲区 3、输入SPi和输出SPo

（参考资料：SPOOLing技术如何使一台打印机虚拟成多台打印机？ 答：将一台独享打印机改造为可供多个用户共享的打印机，是应用 SPOOLing技术的典型实例。具体做法是：系统对于用户的打印输出，并不真正把打印机分配给该用户进程，而是先在输出井中申请一个空闲盘块区，并将要打印的数据送入其中；然后为用户申请并填写请求打印表，将该表挂到请求打印队列上。若打印 机空闲，输出程序从请求打印队首取表，将要打印的数据从输出井传送到内存缓冲区，再进行打印，直到打印队列为空。）

6：连续分配、链接分配和索引分配是外存管理中常用的分配方式。请分析三者的优点和缺点。（本小题6分）

连续分配（P214）

优点：（1）顺序访问容易（2）顺序访问速度快

缺点：（1）要求有连续的存储空间（2）必须事先知道文件的长度 链接分配（P215）

优点：（1）不需要分配连续的空间（2）消除了外部碎片（3）可动态分配盘块，无需事先知道文件的大小。（4）文件增删改方便

缺点：（1）对随机访问低效（2）可靠性较差（3）存在内部碎片 索引分配 (P221)

优点：（1）支持直接访问（2）不会产生外部碎片 缺点：（1）可能花费较多的外存空间

二：算法和计算题（共33分）

1：设A、B两进程共用一个缓冲区Q进行通信，A向Q写入信息，B则从Q读出信息。为了保证进程A、B之间的通信顺利进行，某同学设计了一个如下图所示的算法，该算法使用一个信号量S进行进程A、B之间的同步。请问，该算法是否正确?若有错，请指出原因并予以改正。（本题10分）（生产者-消费者问题P58）

解：这个算法不对。

因为A、B两进程共用一个缓冲区Q，如果A先运行，且信息数量足够多，那么缓冲区Q中的信息就会发生后面的冲掉前面的，造成信息丢失，B就不能从Q中读出完整的信息。

进行改正： A、B两进程要同步使用缓冲区Q。为此，设立两个信号量：

empty表示缓冲区Q为空，初值为1； full表示缓冲区Q为满，初值为0。 算法框图如图所示。

2：某虚拟存储器的用户空间共有32个页面，每页1KB，而主存为16KB。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7，而该用户作业的长度为6页。请问：（本题总计10分）（提示：请注意逻辑地址是由哪两部分组成的）（虚拟存储器P141）

1）十六进制的逻辑地址（也称为虚拟地址）0A5C对应的物理地址是什么？

（2分）(P130)

2）如果要访问的十六进制的逻辑地址是103C，那么会出现什么现象？操作系统是如何处理这种现象的，并请说明处理过程。（6分）（P145）

缺页中断就是要访问的页不在主存，需要操作系统将其调入主存后再进行访问。在这个时候，被内存映射的文件实际上成了一个分页交换文件。

缺页中断作为中断，它们同样需要经历诸如保护cpu环境、分析中断原因、转入缺页中断处理程序进行处理、恢复cpu环境等几个步骤。

3）如果要访问的十六进制的逻辑地址是1A5C，那么会出现什么现象？ （2分）

3：假设磁盘有200个磁道，磁盘请求队列中都是随机请求，它们按照到达的次序分别处于55、58、39、18、90、160、150、38、184号磁道上，当前磁头在100号磁道上，并向磁道号增加的方向移动。请给出按着FCFS、SSTF算法进行磁盘调度时的次序，并计算平均寻道长度。（本题7分）（P194）

分析：FCFS算法按进程请求访问磁盘的先后次序进行服务;SSTF算法优先为距离当前磁头所在磁道最近的请求进行服务;SCAN算法则优先为在磁头当前移动方向上、与当前磁头所在磁道最近的请求进行服务;CSAN算法类似于SCAN算法,但它规定磁头只能作单向移动。

答:磁盘调度的次序以及它们的平均寻、道长度如表6.1所示。

表6.1磁盘调度的次序以及平均寻道时间

FCFS SSTF SCAN CSCAN 被访问的移动的 被访问的移动的 被访问的移动被访问的移动的 下一个磁磁道数 下一个磁磁道数 下一个磁的 下一个磁磁道数 道号 道号 道号 磁道道号 数 55 45 90 10 150 50 150 50 58 3 58 32 160 10 160 10 39 19 55 3 184 24 18 21 39 16 90 94 90 72 38 1 58 32 160 70 18 20 55 3 150 10 150 132 39 16 38 112 160 10 38 1 184 146 184 24 18 20 平均寻道长度:55.3 平均寻道长度:27.6 平均寻道度:27.8 184 24 18 166 38 20 39 1 55 16 58 3 90 32 平均寻道长度:35.8

4：随着CPU速度的不断提升，IO设备的速度逐渐成为系统性能的瓶颈之一。请分析、说明现代操作系统是如何缓解这一问题的，并列举多个解决方案。（本题6分）(SPOOLing技术？P189;多通道？；这个真不会，看书总结)

39 19 55 3 184 24 18 21 39 16 90 94 90 72 38 1 58 32 160 70 18 20 55 3 150 10 150 132 39 16 38 112 160 10 38 1 184 146 184 24 18 20 平均寻道长度:55.3 平均寻道长度:27.6 平均寻道度:27.8 184 24 18 166 38 20 39 1 55 16 58 3 90 32 平均寻道长度:35.8

4：随着CPU速度的不断提升，IO设备的速度逐渐成为系统性能的瓶颈之一。请分析、说明现代操作系统是如何缓解这一问题的，并列举多个解决方案。（本题6分）(SPOOLing技术？P189;多通道？；这个真不会，看书总结)

本文来源：https://www.bwwdw.com/article/3ykh.html