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)=KMOD16,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%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）查找60,首先要与H(60)=60%16=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.555．奇偶交换排序如下所述：对于初始序列A[1]，A[2],…,A[n],第一趟对所有奇数i（1=in）,将A[i]和A[i+1]进行比较，若A[i]A[i+1]，则将两者交换；第二趟对所有偶数i（2=in），将A[i]和A[i+1]进行比较，若A[i]A[i+1]，则将两者交换；第三趟对所有奇数i（1=in）；第四趟对所有偶数i（2=in）,…，依次类推直至到整个序列有序为止。（10分）(1)分析这种排序方法的结束条件。(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分)答：voidreverse(LinkList&L)//单链表的就地逆置{p=L-next;if(p==NULL||p-next==NULL)returnOK;//空表和表中只有一个结点时，不用逆置。while(p-next!=NULL){q=p-next;p-next=q-next;//删除结点q，但未释放q-next=L-next;L-next=q;//将q插入头结点之后}returnOK;}//reverse2、二叉树采用二叉链表存储结构，设计算法统计二叉树的深度（二叉树的最大层数）和宽度（二叉树中所有层中结点的最大个数）。（15分）标准答案：①求树的高度思想：对非空二叉树，其深度等于左子树的最大深度加1。IntDepth(BinTree*T){intdep1,dep2;if(T==Null)return(0);else{dep1=Depth(T-lchild);dep2=Depth(T-rchild);if(dep1dep2)return(dep1+1);elsereturn(dep2+1);}}②求树的宽度思想：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。intWidth(BinTree*T){intfront=-1,rear=-1;/*队列初始化*／intflag=0,count=0,p;/*p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*／if(T!=Null){rear++;q[rear]=T;flag=1;p=rear;}while(frontp){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(flagcount)flag=count;count=0;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是DynamicLinkLibrary的缩写，意为动态链接库。在Windows中，许多应用程序并不是一个完整的可执行文件，它们被分割成一些相对独立的动态链接库，即DLL文件，放置于系统中。当我们执行某一个程序时，相应的DLL文件就会被调用。一个应用程序可有多个DLL文件，一个DLL文件也可能被几个应用程序所共用，这样的DLL文件被称为共享DLL文件。）DLL方式的优点：（1）便于修改和更新。（2