1、桂林电子科技大学2016年硕士研究生统一入学考试试题科目代码: 823科目名称: 数据结构+操作系统请注意：答案必须写在答题纸上（写在试题上无效）。答题纸请注明页码与总页数。PART I： 数据结构一、判断题。对每小题描述的正确性进行判定，正确的标记为T，错误的标记为F（5小题，每小题3分，共15分）1）在线性表的顺序存储结构中，逻辑上相邻的数据元素在物理位置上也是相邻的（ ）2）哈夫曼树中不存在度为 1 的结点（ ）3）直接插入排序、简单选择排序、冒泡排序均具有相同的最坏时间复杂度（ ） 4）迪杰斯特拉算法用于在无向连通图中找出最小生成树（ ）5）给定二叉树的前序周游序列和后序周游序列，可以
2、唯一地确定一棵二叉树（ ）二、单项选择题（5小题，每小题3分，共15分）1）下列给定程序段的时间复杂度是（ ）for(i=0; im; i+) for(j=0; jt; j+) cij=0;for(i=0; im; i+) for(j=0; jt; j+) for(k=0; kn; k+) cij=cij+aik*bkj;AO(m*n*t) B.O(m+n+t) C.O(m*t)D.O(m*t+n)2）单向循环链表不具有的特点是（ ）A随机访问 B不必事先估计所需存储空间大小C插入与删除时不必移动元素结点 D所需空间与线性表长度成正比3）有向图的边集为, , , , , , ，下面正确的拓扑排
3、序是（ ） Aaebdcf Bacefbd Caecdcf Dacefbd4）二分查找法适用于存储结构为（ ）且按关键字排序的线性表A. 顺序存储 B. 链接存储 C. 顺序存储或链接存储 D. 索引存储5）对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（ ）方法。A.归并排序 B.直接插入排序 C.直接选择排序 D.快速排序三、分析与算法设计题（4小题，共45分）1）采用长度为7的一维数组（下标是0.6）表示哈希表。采用双散列函数解决哈希冲突，h(key)=(h1(key)+i*h2(key) mod 7，i=0,1,2，。其中h1(key) =
4、 key mod 7，h2(key)= (1+k) mod 5。如果到达的键值分别是8, 1, 15, 4，16，请（a）请构造哈希表（5分）（b）计算上述哈希表在等概率情况下成功检索时的平均检索长度（5分）2）下面的算法对一个由非零整数组成的序列进行重排列，将负数排在前面， 正数排在后面voidswap(intarray,inti,intj) inttmp=arrayi; arrayi=arrayj; arrayj=tmp;voidSort(intarray,intn) inti,j; i=0; j=n-1; while(ij) while(arrayi0) ; （S2）if( )break
5、; （S3）swap(array,i,j);i+; j-; （a）请将空白处的代码补充完整（6分） （b）若有数组inta=10,-6,-3,20,-18,5,9,-16，则执行Sort(a,8)后，请给出数组a的值（4分）3）图G=V1,V2,V3,V4,V5,V6,V7,V8，其邻接表存储如图1所示。请基于该邻接表存储结构：（a）给出从顶点V4出发的广度优先遍历序列（请注意该答案唯一，5分）（b）给出从顶点V2出发的深度优先遍历序列（请注意该答案唯一，5分） 图1 邻接表4）下面代码的主要功能是借助于栈的作用，将循环队列的内容倒置，循环队列和栈均采用数组存储（假设队列和栈的存储空间均足够大
6、），图2给出了将队列进行倒置的示意图。请根据上述要求将下面的代码补充完整。（15分）图2 队列内容逆置示意图#define MAXSIZE 100 /队列定义typedef struct Queue DataType dataMAXSIZE; int front, rear; /队头指针和队尾指针，队头指针始终指向队列第一个元素的前一个位置，队尾指针始终指向队列的最后一个元素Queue;/栈定义typedef struct Stack DataType dataMAXSIZE; int top; /栈顶指针，其始终指向栈顶元素Stack;Queue * Reverse(Queue *q) St
7、ack *s=(Stack *) malloc (sizeof(Stack); s-top=-1; while ( (a) ) (b) ; (c) ; s-datas-top=q-dataq-front;while ( s-top!=-1 ) q-rear+; (d) ; (e) ; return q;PART II：操作系统一、单项选择题（每题2分，共20分）1. 处理器执行的指令被分成两类，其中有一类称为特权指令，它只允许_使用。 A. 操作员 B. 联机用户 C. 用户程序 D.内核程序2. 进程从等待状态进入就绪状态可能是由于_。A现运行进程运行结束B现运行进程执行了P操作C现运行进程
8、执行了V操作D现运行进程时间片用完3. 下列关于进程和线程的叙述中，正确的是_。A一个进程只可拥有一个线程 B一个进程可拥有若干个线程C一个线程只可拥有一个进程 D一个线程可拥有若干个进程4.设有5个进程共享一个互斥段，如果最多允许有1个进程同时进入互斥段，则所采用的互斥信号量的初值应是_。A1 B3 C 5 D 05.如果进程对信号量S执行一次P操作，则信号量S的值应_。A. 加1 B. 小于0 C.大于0 D.减16. 通常用户编写的程序中所使用的地址是 。A. 逻辑地址 B. 物理地址 C. 绝对地址 D. 内存地址7.在分页系统中，与缺页率无关的是_。A. 页面替换算法 B. 进程地址
9、空间大小 C. 程序特性 D. 主存页框数8.页面置换算法中，如果采用LRU页面调度算法，则总是选择_页面先淘汰。A最先装入主存的 B驻留时间最长的C. 最久未被访问的D被访问的次数最少的9. 进程P1：申请资源S1，申请资源S2，释放资源S1，释放资源S2；进程P2：请求资源S2，申请资源S1，释放资源S2，释放资源S1。S1和S2只有一个资源，系统并发执行进程P1，P2，系统将_。A.必定产生死锁 B.可能产生死锁 C.不会产生死锁 D.以上说法都不对10. 如果允许不同用户的文件可以具有相同的文件名，通常采用_来保证按名存取的安全。A. 重名翻译机构B. 建立索引表C. 建立指针D. 多
10、级目录结构二、 在哲学家进餐问题中，是否会产生死锁？请简述一种避免死锁的方法。（10分） semaphore fork5;for (int i=0;i5;i+)forki=1;cobegin process philosopher_i( ) /i= 0,1,2,3,4while(true) think( ); P(forki); P(fork(i+1)%5); eat( ); V(forki); V(fork(i+1)%5); coend三、计算题（每题10分，共30分）1、A、B两个程序，程序A按顺序使用CPU 10s，使用设备甲5s，使用CPU 5s，使用设备乙5s，最后使用CPU 10s
11、。程序B按顺序使用设备甲10s，使用CPU 10s，使用设备乙5s，使用CPU 5s，使用设备乙10s，试问：（画出调度过程图）(1)在顺序环境下执行程序A和程序B，CPU的利用率是多少?(2)在多道程序环境下，A的优先级比B高，采用基于优先级剥夺式调度，CPU的利用率是多少?2. 在一个操作系统中，inode节点中分别含有12个直接地址索引和一、二、三级间接地址索引。设每个盘块大小为512B，每个盘块可存放128个盘块地址，则一个2MB的文件占用多少间接盘块，至少需要几级间接地址索引？3. 某请求分页系统中页面大小为2KB，逻辑地址空间为10KB，主存地址空间为32KB，现有逻辑地址为0D7
12、8H和2489H（均为16进制数）, 进程页表对应关系如下所示，计算其对应的物理地址是多少？请给出对应的物理地址的计算过程。 页号 块号 0 91 4 2 0 3 8 4 12四、程序设计（共15分）桂电花江校区A、B两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下:当AB之间有车辆在行驶时同方向的车可以同时驶入AB段，但另一方向的车必须在AB段外等待；当AB段无车辆在行驶时，到达A点(或B点)的车辆可以进入AB段，但不能从A 点和B点同时驶入；当某方向在AB段行驶的车辆驶出了AB段且暂无同向车辆进入AB段时，应让另一方向等待的车辆进入AB段行驶。请用PV操作和信号量设计一进程同步算法，对AB段实现正确管理以保证行驶安全。第 7 页 共 7 页
