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

《数据结构》部分一、简答题（20分，每题5分）1、请给出4类常用的基本数据结构类型。（课本p5第6行）答：根据数据元素之间关系的不同特征，通常有下列4类的基本结构：（1）集合。。。（2）线性结构。。。（3）树形结构。。。（4）图状结构或网状结构。。。2、什么是哈希表？（课本P253第2行）答：根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的、连续的地址集（区间）上，并以关键字在地址集上的“像”作为记录在表中的存储位置，这种表便称为哈希表。3、请比较简单排序、快速排序、堆排序、归并排序的算法效率和稳定性。（课本P289）（算法效率的概念P14；稳定性的概念P263;简单排序也就是除希尔排序之外的所有插入排序P265;快速排序P272;堆排序P279;归并排序P283）答：4、请比较普里姆算法与克鲁斯卡尔算法解决图最小生成树问题的时间复杂度。(课本P175)(最小生成树：P173;普里姆算法P173;克鲁斯卡尔算法P175)答：普里姆算法的时间复杂度为O(n2)（假设网中有n个顶点），与网中的边数无关，因此适用于求边稠密的网的最小生成树。而克鲁斯卡尔算法恰恰相反，它的时间复杂度为O(eloge)(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。二、应用题（50分）1、已知二叉树的前序遍历、中序遍历的结果分别是：ABDEFGCHIJ和DBFEGAHCIJ，请画出对应的二叉树，给出后序遍历的结果，并将它转换成等价的树或森林。（10分）（二叉树的前序遍历、中序遍历P128；树P137；森林P138）答：2、某带权有向图及它的邻接表如下：(1)试写出它的深度优先搜索序列。(深度优先搜索P167；邻接表P163；广度优先搜素P169)答：A--B--D--C--F--E--G--H（提示：不要画图，直接根据邻接表画）(2)根据普里姆(Prim)算法，求它的从顶点A出发的最小生成树。（10分）（普里姆算法P173;克鲁斯卡尔算法P175）答：（没有有向图，也就没权重，没法做，领会精神）3、画出向小顶堆中加入数据4,2,5,8,3,6,10,1时，每加入一个数据后堆的变化。（15分）（堆P280;）4.一组关键字集合为(25，10，8，27，32，68)，设哈希函数H(k)=kmod7，分别用线性探测和链地址法两种解决冲突的方法构造长度为8的哈希表，要求画出具体的哈希表并求查找成功且等概率情况下各自的平均查找长度。（15分）(线性探测和链地址法两种解决冲突的方法P257和P258；平均查找长度P260)答：哈希表如下:线性探测平均查找长度：（1*4+2*1+3*1）/6=9/6链地址法平均查找长度：（1*5+2*1）/6=7/6三、算法设计题（30分)答题要求：①用自然语言说明所采用算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③用C语言写出对应的算法程序，并做必要的注释。1、已知一个带表头结点的单链表，结点的结构为假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找该链表中倒数第k个位置上的结点（k为正整数）。查找成功，输出结点的data值，并返回1；否则，只返回0。(15分)（单链表P27；单链表c语言结构定义P28）【解析】本题详细解析如下：(1)算法的基本设计思想：问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k个结点的位置。算法的基本设计思想是：定义两个指针变量p和q，初始时均指向头结点的下一个结点（链表的第一个结点）。p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。(2)算法的详细实现步骤：①count=0，p和q指向链表表头结点的下一个结点；②若p为空，转⑤；③若count等于k，则q指向下一个结点；否则，count=count+1；④p指向下一个结点，转②；⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，说明k值超过了线性表的长度，查找失败，返回0；⑥算法结束。(3)算法实现：typedefstructNode{ElemTypedata;structNode*next;}*Pointer;PointerLinkList;intSearch_k(Pointer&list,intk)//查找链表list倒数第k个结点，并输出该结点data域的值{p=list-next;q=list-next;//指针p、q指示第一个结点intcount=0;while(p!=NULL){//遍历链表直到最后一个结点if(countk)count++;//计数，若countk只移动pelseq=q-next;p=p-next;//之后让p、q同步移动}//whileif(countk)return0;//查找失败返回0else{//否则打印并返回1printf(%d,q-data);return1;}}//Search_k提示：算法程序题，如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。2、请给出统计二叉树中叶子结点个数的算法。（15分）（二叉树P121;二叉树链式存储结构P127;遍历算法伪码P129、P130）算法分析:首先要明白其本质还是二叉树的遍历.只不过是带额外有条件的输出.即找出叶子结点并进行计数.下面是比较好记的一个算法，简单，但是一定不要记错！intleaf(bitreet){if(!t)return0;//空树，返回0elseif(!t-lch&&!t-rch)return1;elsereturn(leaf(t-lch)+leaf(t-rch));}/************************算法分析:首先要明白其本质还是二叉树的遍历.只不过是带额外有条件的输出.即找出叶子结点并进行计数.1.提到计数的话,一开始的反应就是建立一个int型变量(如count),然后找到一个符合条件的就进行count++;但在这里就不是那么合适了.因为若是要遍历,选择递归遍历,则每次调用一次递归函数都会创建一个count,各个count都不相同.而且都会被初始化为0,这样就没什么意义了.2.所以采取的方法就是利用函数返回值.把函数定义为返回值为int型的函数.3.然后进行判断:if(!t-lch&&!t-rch)如果左右结点都为NULL,则返回1(也就是计数+1).否则就调用递归函数,先左子树,后右子树.这个算法真正精髓的一句就是:return(leaf(t-lch)+leaf(t-rch));在调用递归的同时把各个递归函数的返回值都加了起来.而最终返回到主函数的值就是叶子节点的个数!巧妙!:D**************************/《操作系统》部分四、简答题（每小题6分，共30分）1、什么是操作系统？试列举三种你所熟悉的操作系统名称及类型？（P1;P13）操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。MS-DOS:单用户单任务操作系统Windows95/98/xp:单用户多任务操作系统LinuxOS：多用户多任务操作系统2、何谓虚拟？OS中利用的虚拟技术有哪些？(P16;)操作系统中的所谓虚拟，是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。在操作系统中利用了两种方式实现虚拟技术，即时分复用技术和空分复用技术。利用时分复用技术实现了：虚拟处理机技术和虚拟设备技术利用空分复用技术实现了：虚拟磁盘技术和虚拟存储器技术3、进程死锁产生的原因是什么？处理死锁的基本方法有哪些？(P103;P105)进程死锁产生的原因可归结为如下两点：（1）竞争资源。当系统中供多个进程共享的资源如打印机等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。（2）进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。处理死锁的基本方法可以归结为以下四种：（1）预防死锁（2）避免死锁（3）检测死锁（4）解除死锁4、在具有快表的段页式存储管理方式中，如何实现地址变换？（教材习题（P159--15题）；答案：P137）答：在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段长TL。进行地址变换时，首先利用段号S，将它与段长TL进行比较。若STL，表示未越界，利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址。在段页式系统中，为了获得一条指令或数据，须三次访问内存。第一次访问内存中的段表，从中取得页表始址；第二次访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正从第二次访问所得的地址中，取出指令或数据。显然，这使访问内存的次数增加了近两倍。为了提高执行速度，在地址变换机构中增设一个高速缓冲寄存器。每次访问它时，都须同时利用段号和页号去检索高速缓存，若找到匹配的表项，便可从中得到相应页的物理块号，用来与页内地址一起形成物理地址；若未找到匹配表项，则仍须再三次访问内存。5、文件控制块的作用是什么？它通常包括哪三类信息？(P224;)为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为“文件控制块”。文件管理程序可借助于文件控制块中的信息，对文件施以各种操作。为了能对系统中的大量文件施以有效管理，在文件控制块中，通常应含有三类信息，即基本信息、存取控制信息及使用信息。五、算法和计算题（每小题10分，共20分）1、从读卡机上读进N张卡片，然后复制一份，要求复制出来的卡片与读进来的卡片完全一致。这一工作由三个进程get,copy和put以及两个缓冲区buffer1和buffer2完成。进程get的功能是把一张卡片上的信息从读卡机上读进buffer1；进程copy的功能是把buffer1的信息复制到buffer2；进程put的功能是取出buffer2中的信息并从行式打印机上打印输出。试用信号量机制完成三个进程间的尽可能并发正确运行的关系（用程序表示），并指明信号量的作用及初值。（生产者-消费者问题P58;信号量P53）解答：这3个进程间的关系可用下图来表示：分析这3个进程之间的关系，可以得知，get和copy进程之间通过buffer1进行合作，这是一种生产者-消费者问题；同理，进程copy和put之间通过buffer2进行合作，两者之间也是一种生产者-消费者问题。为此，设计互斥信号量mutex1，mutex2来实现对buffer1和buffer2的互斥访问；为实现get和copy之间的同步，设置两个信号量semptybuffer1和sfullbuffer1，分别表示缓冲区buffer1是空的还是满的；为实现copy和put之间的同步，设置两个信号量semptybuffer2、sfullbuffer2，分别表示缓冲区buffer2是空的还是满的。Varmutex1,mutex2,semptybuffer1,sfullbuffer1,semptybuffer2，sfullbuffer2:semaphore:=1,1,1,0,1,0;Get:beginRepeat从读卡机读入一张卡片信息；P(semptybuffer1);P(mutex1);将信息放入buffer1;V(sfullbuffer1);V(mutex1);Untilfalse;EndCopy:beginRepeatP(sfullbuffer1);P(mutex1);从buffer1复制信息;V(semptybuffer1);V(mutex1);P(semp