山东科技大学2019年硕士研究生自命题试题823.pdf
数据结构部分一、选择题(每题2分,共20分)1、将线性表La和Lb头尾连接,要求时间复杂度为O(1),且占用辅助空间尽量小,应该使用哪种结构?( )A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表2、在一个链队列中,front和rear分别为头指针和尾指针,则插入一个结点s的操作为()。A. front=front-nextB. s-next=rear;rear=sC. rear-next=s;rear=s;D. s-next=front;front=s;3、设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4,则最后一个出栈的元素必定是:( )A. 1B. 3C. 5D. 1或者54、由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树,该树的带权路径长度为:( )A. 23B. 37C. 44D. 465、如果AVL树的深度为5(空树的深度定义为0),则此树最少有多少个结点?( )A. 12B. 20C. 33D. 646、若无向图G=(V,E)中含10个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是:( )A. 45B. 37C. 36D. 97、有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100,当用二分法查找值82的结点时,()次比较后查找成功。A. 8B. 1C. 4D. 28、给定散列表大小为17,散列函数为H(Key)=Key%17。采用平方探测法处理冲突:h i (k)=(H(k)i 2 )%17将关键字序列6,22,7,26,9,23依次插入到散列表中。那么元素23存放在散列表中的位置是:( )A. 0B. 2C. 6D. 159、在快速排序的一趟划分过程中,当遇到与基准数相等的元素时,如果左指针停止移动,而右指针在同样情况下却不停止移动,那么当所有元素都相等时,算法的时间复杂度是多少?( )A. O(logN)B. O(N)C. O(NlogN)D. O(N 2)10、对下图进行拓扑排序,可以得到不同的拓扑序列的个数是:( )A. 4B. 3C. 2D. 1二、综合题(每题10分,共50分)1、设一棵二叉树的先序、中序遍历序列分别为先序遍历序列:ABDFCEGH中序遍历序列:BFDAGEHC。(1)画出这棵二叉树。(2)画出这棵二叉树的后序线索树。(3)将这棵二叉树转换成对应的树(或森林)。2、已知待排序的序列为(503,87,512,61,908,170,897,275,653,462),试完成下列各题。(1)根据以上序列建立一个堆(画出第一步和最后堆的结果图),希望先输出最小值。(2)输出最小值后,如何得到次小值(并画出相应结果图)。3、采用哈希函数H(k)=3*kmod13并用线性探测开放地址法处理冲突,在数列地址空间0.12中对关键字序列22,41,53,46,30,13,1,67,51。(1)构造哈希表(画示意图);(2)装填因子;等概率下(3)成功的和(4)不成功的平均查找长度。4、用一个数组S(设大小为MAX)作为两个堆栈的共享空间。请说明共享方法,栈满/栈空的判断条件,并用C设计公用的入栈操作push(i,x),其中i为0或1,用于表示栈号,x为入栈值。5、对于下图完成下列指定操作。(1)从顶点A出发,求它的深度优先生成树。(2)从顶点E出发,求它的广度优先生成树。(3)根据普利姆(Prim)算法,求它的最小生成树。三、算法设计题(每题10分,共20分)1、编写一个函数,输出二叉树中从每个叶子结点到根结点的路径。2、一个连通图采用邻接表作为存储结构,设计一个算法,实现从顶点v出发的深度优先遍历的非递归过程。操作系统部分四、简答题(每小题5分,共30分)1.处理机调度进程主要通过调度程序来完成,调度程序主要有三种策略:低级调度(也称为短程调度或者短期调度),中级调度(也称为中程调度、中期调度或者激活操作),高级调度(也称为作业调度或者长程调度)。请说明上述三种调度策略的区别。2.在解决进程同步问题时,经常使用信号量机制,最基本的信号量有整型信号量和记录型信号量,请简要说明对这两种信号量的操作过程。3.假设系统中有4个相同类型的资源R,这些资源被3个进程共享,每个进程最多需要2个资源R,请问该系统有没有可能发生死锁?并说明原因。4.分页内存管理和分段内存管理的区别有什么?5.计算机操作系统的目录是对相关文件信息进行说明的一个集合,通过目录对文件实施管理和操作。请说明操作系统目录主要包含哪些内容?6.简述计算机I/O系统的组成。哪些部分是操作系统提供的I/O功能。五、应用题(每小题10分,共30分)1.某虚拟存储器的用户进程共分为5页,内存为64KB,页面大小为4KB,系统为该进程分配了3个内存块(帧)。假定某时刻用户页表如下:页号块号页面调入内存时间2 5 15:010 10 15:303 4 14:55则逻辑地址0A5C(H)、7B32(H)和12D1(H)所对应的物理地址是什么?写出地址转换过程。2.某生产线有三道工序,分别是原料输入、产品加工和产品包装处理,这三道工序共享一个物品放置区。三道工序之间的关系如下:(1)原料输入工序把原料送到放置区,供产品加工工序使用;(2)产品加工工序从放置区取出原料进行加工,把加工后的产品送入放置区;(3)包装处理工序把放置区中的产品包装后输出来完整的产品。请利用信号量机制,写出同步上述工序的基本思想,并用伪代码写出实现过程。3.假设某磁臂在磁盘上刚处理完60号柱面的请求,目前正在65号柱面读信息,有下表中等待访问磁盘的序列:请求序列1 2 3 4 5 6 7 8将要访问的柱面号36 192 41 57 121 66 64 100请按两种磁盘调度算法SCAN算法(也称电梯调度算法)和最短寻道时间优先调度算法,回答以下两个问题:(1)分别给出请求序列的柱面号处理次序;(2)比较两种算法的优缺点。