2016年桂林电子科技大学考研专业课试题823数据结构+操作系统（A）.doc

1、桂林电子科技大学2016年硕士研究生统一入学考试试题科目代码:823科目名称:数据结构+操作系统请注意：答案必须写在答题纸上（写在试题上无效）。答题纸请注明页码与总页数。PART I：数据结构一、匹配题。下面分别给出了一组问题以及一组结构（或算法），请根据问题的描述，为其选择最合适的数据结构或算法（5小题，每小题3分，共15分）问题列表数据结构（或算法）列表1）对一组接近有序的记录进行排序A顺序循环队列2）对1000个随机无序的记录进行排序B迪杰斯特拉算法3）在一个无向带权图中寻找指定顶点到其它顶点的最短路径C 哈希表4）按照先来先服务的原则，将到达任务分配到服务器上执行D插入排序5）以近似O

2、(1)的时间复杂度实现数据元素的查找E快速排序二、单项选择题（5小题，每小题3分，共15分）1）在一个长度为n（n0）的顺序表的表尾插入一个新元素的时间复杂度是（ ）A. O(n) B. O(n/2) C. O(1) D. O(n2)2）设顺序循环队列Q0：M-1的队头指针和队尾指针分别为F和R，队头指针F总是指向队头元素的前一位置，队尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）AR-F B.F-R C. (R-F+M)M D. (F-R+M)M3）按照先左子树、后右子树的原则对二叉树进行深度优先遍历，则在先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( )A.

3、都不相同 B.完全相同 C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同4）用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下：25 84 21 47 15 27 68 35 2020 15 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则采取的排序方法是 （ ）A.直接选择排序 B.冒泡排序 C.快速排序 D.二路归并排序5）下面哪一种情况的图最适合采用二维数组进行存储？（ ）A1000个顶点，1200条边的图B100

4、个顶点，4000条边的图C10000个顶点，100000条边的图D10000个顶点，500条边的图三、分析与算法设计题（4小题，共45分）1）给定关键字集合（9， 23， 31， 16， 30， 29， 45， 46， 39， 62， 48），若哈希函数 H(key)= key % 13，且用线性探测法处理冲突。（a）请构造哈希表（5分）（b) 计算等概率情况下成功检索的平均检索长度ASL（5分）2） 已知二叉树的存储结构为二叉链表，请阅读下面算法。 typedefstructTreeNodeintinfo; structTreeNode*lchild; structTreeNode*rchi

5、ld; TreeNode;typedefstructListNode intvalue; struct ListNode*link;ListNode;typedefTreeNode*BinTree;typedefListNode*LinkList;LinkListhead=NULL;voidInorder(BinTreeT)LinkLists;if(T!=NULL) Inorder(T-lchild); if(T-lchild=NULL)&(T-rchild=NULL) s=(ListNode*)malloc(sizeof(ListNode); s-value=T-info; s-link=h

6、ead; head=s; Inorder(T-rchild); （a）说明Inorder函数的主要功能（5分） （b）对于如图1所示的二叉树，画出执行上述算法后所建立的结构（5 分） 图1 二叉树3）已知一个图的顶点集V和边集E分别为：V=a, b, c, d, e, f, g； E= (a,b,3),(a,c,5),(a,d,8),(b,e,10),(b,c,6),(c,d,15),(c,e,12),(c,f,9),(d,f,4),(d,g,20),(e,f,18),(f,g,25)（注：每条边采用三元组（起点，终点，权值）表示）。请用克鲁斯卡尔算法构造最小生成树，写出在构造过程中依次得到的

7、各条边。（10分）4）具有n个整数的无序序列采用带头结点的单向循环链表进行存储，请基于给定的函数，实现Sort函数，将所有奇数移到所有偶数之前，要求在原链表中进行操作，时间复杂度为O(n)。（15分）structNode;typedefstructNode*PNode;structNode intvalue; PNodelink;typedefPNodeLinkList;LinkListcreateEmptyList() LinkListlist; PNodenode=(PNode)malloc(sizeof(structNode); node-link=node; list=node; re

8、turnlist;LinkListinsertElement(LinkListlist,intx)PNodenode=(PNode)malloc(sizeof(structNode); node-value=x; node-link=list-link; list-link=node; list=node; returnlist;/将所有奇数移到所有偶数之前LinkListSort(LinkListlist)PART II：操作系统一、单项选择题（每题2分，共20分）1、系统调用是_。 A.一条机器指令 B.提供给编程人员的接口C.中断服务程序 D.用户程序2、进程在执行中发生了缺页中断，经操

9、作系统处理后，应让其执行_ 指令。A.被中断的前一条 B. 被中断的后一条C. 被中断的那一条 D.启动时的第一条3、下列指令中，_能在用户态运行。A. 访管指令 B. 启动I/O C.加载PSW D. 设置时钟日期4、下列进程调度算法中，不可能导致饥饿现象的是_。A. 抢占式短作业优先 B.静态优先级调度 C.非抢占式短作业优先 D. 时间片轮转 5、某系统有n台互斥使用的同类设备，3个并发进程各需要2台设备，可确保系统不发生死锁的设备数n最小为_。A.3 B.4 C.5 D.66、某页式存储管理系统向用户提供的逻辑地址16页，每页大小为1024B，则作业的逻辑地址为 。 A、16位 B、1

10、4位 C、12位 D、10位7、对于2个并发的进程，设信号量mutex的初值为1，若mutex=-1，则_。A.表示没有进程进入临界区 B.表示有一个进程进入临界区C.表示有一个进程进入临界区，另一个进程等待进入 D.表示有两个进程进入临界区8、使用SPOOLing系统的目的是为了提高_的使用效率。A.操作系统 B.内存 C.CPU D.I/O设备9、 用户程序发出磁盘I/O请求后，系统的处理流程是：用户程序系统调用处理程序设备骆动程序中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是_。 A. 用户程序 B. 系统调用处理程序 C. 设备驱动程序 D. 中断处理程序10、

11、如果文件系统中有两个文件重名，不应采用_。 A.单级目录B多级目录C.二级目录D三级目录二、（10分）阐述进程和线程的概念，在操作系统中为什么要引入进程和线程？三、计算题（每题10分，共30分）1、在一个请求分页系统中，页面大小为100个字,进程访问地址的序列为：10,150,104,85,330,185,220,255,450,456,120,467,202。（1）请给出页面访问序列。（2）假如分配给该作业的物理块数M为3，试用FIFO（先进先出）和LRU（最近最久未使用）页面置换算法计算各自页面淘汰顺序及其缺页次数。（初始时，页框为空）2、有两个优先级相同的进程P1和P2，各自执行的操作如

12、下，信号量S1和S2的初值为0。试问P1和P2并发执行后，x,y,z的值各为多少？写出所有可能情况。(Z的初值为0）P1( )P2( ) y=1; x=2;y=y+4;x=x*6;V(s1);P(s1);Z=3+y;x=x+y;P(S2);V(S2);y=z+y;z=z+x; 3、在道数不受限制的多道程序系统中（单CPU），作业进入系统的后备队列时立刻进行作业调度。现有6个作业进入系统，有关信息如下表所示，作业调度采用最短剩余时间优先调度算法（基于抢占式的短作业优先调度）。完善以下列表信息，并给出6个作业的执行时间序列图。作业名进入后备队列的时间执行时间（分钟）开始时间完成时间周转时间A8:0060B8:2035C8:2520D8:3025E9:355F9:4010平均周转时间平均带权周转时间作业调度次序四、程序设计题（15分）有一材料保管员负责管理纸和笔，另有A,B两组工人，A组工人每个都有染料，B组工人每个都有布，但一个工人只要能得到其他一种材料就可以染布。有一个可以放材料的盒子。当盒子为空时保管员取一件材料放入盒子中。当盒子有工人所需材料时，每次只允许一个工人从盒子中取出自己所需材料。试用信号量和PV操作描述他们的同步关系。第 6 页 共 6 页