《2015年桂林电子科技大学考研专业课试题823数据结构+操作系统（A）.doc》由会员分享，可在线阅读，更多相关《2015年桂林电子科技大学考研专业课试题823数据结构+操作系统（A）.doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、桂林电子科技大学2015年研究生统一入学考试试题科目代码：823科目名称：数据结构+操作系统请注意：答案必须写在答题纸上（写在试题上无效）。PART I数据结构部分一、 选择题（24分。共8小题，每小题3分）1. 关于数据结构的描述，正确的是（）。A数据的逻辑结构可以划分为：线性结构、树型结构和索引结构B一种逻辑结构可采用多种存储结构实现C一种存储结构只能实现一种逻辑结构D现实世界中数据对象的1对多联系可以采用线性结构表达2. 关于顺序表和链接表的描述，错误的是（）。A顺序表和链接表是线性表的不同存储结构实现B顺序表将线性表中数据元素之间的相邻关系映射为数据物理位置上的相邻关系C分别在具有n个
2、数据元素的顺序表和链接表中查找数据元素K，链接表的查找效率要高于顺序表。D数组可以作为线性表的一种顺序表实现3. 图1中，（a）是结点结构，（b）是指针s指向的待插入结点，（c）是双向链表片段，则在（c）中p指针指向的结点前面插入指针s指向的结点的操作是（）。图1双向链表As-rlink=p; s-llink=p-llink; p-llink-rlink=s; p-llink=s; Bp-llink=s; s-rlink=p; s-llink=p-llink; p-llink-rlink=s;Cp-llink-rlink=s; p-llink=s; s-rlink=p; s-llink=p-l
3、link;Ds-rlink=p; s-llink=p-llink; p-llink=s; p-llink-rlink=s;4. 若出栈的顺序是a, b, c, d, e，则入栈的顺序不可能是（）。Aa, b, c, d, e Be, d, c, b, a Cd, e, c, b, a Da, e, d, c, b5. 二叉树的前序序列是：ABDCGEF，中序遍历序列是：DBCGAEF，则该二叉树的叶子结点数目是（）。A2 B3 C4 D56. 给定四个符号X, Y, Z, P，它们被使用的频率分别是0.2、0.4、0.3和0.1，采用哈夫曼编码后，Z的编码长度是（）。A1B2C3D47. 若待
4、排序的元素序列基本有序，则（）算法效率最高。A 插入排序B选择排序C快速排序D归并排序8. 一个无向图具有n个顶点m条边，则该无向图中所有顶点的度数之和是（）。A2n Bn+m C2m Dn*m二、 应用与分析题（36分。共4小题，每小题9分）1.请给出下面算法的功能描述。（9分）struct Node;typedef struct Node* PNode;struct Node DataType info; PNode link;typedef struct Node * LinkList;int Test(LinkList list, DataType value) LinkList tm
5、p=list; int m=0; while(tmp!=null) if(tmp-info=value) m+; tmp=tmp-link;return m;2.线性表B=（6，21，45，55，20，3，78，31，15）。给定数组HT0.8作为散列表的存储空间，散列函数为H(key) = key % 9，且采用线性探查法解决冲突。（1）若采用给定散列表存储线性表B，请画出对应的散列表。（5分）（2）若B中少于等于40的数据元素的查找概率为2/15，大于40的数据元素的查找概率为1/15，请计算查找成功的平均查找长度。（4分）3.无向带权图的邻接矩阵如下所示 请用Kruskal算法构造此图的
6、最小生成树，要求给出详细的构造过程。（9分）4.给定一待排序关键字序列(40，25，64，18，21，36，9，30)。（1）请以每一个待排序区间的最后一个元素为基准记录，给出前3趟快速排序每一趟排序的结果。（6分。注：按照升序进行排序）（2）请问需要经过几趟快速排序，上述序列才排序结束。（3分）三、 算法设计题（15分）一个长度为N的字母序列STR是对称的是指对任意的序号i（0iN-1），有STRi=STRN-i-1，例如“ABA”或者“ABBA”等。若采用带有头结点的双向循环链表来存储字母序列，链表中的每个结点存储一个字母（如图2所示）。请设计一个判定字母序列是否对称的算法，如果对称返回T
7、RUE（或者1），否则返回FALSE（或者0），要求时间复杂度不超过O(n)。图2带头结点的双向循环链表PARTII 操作系统部分一、选择题（每题2分，共20分）1. 下列指令中，_可以在用户态运行。A.加载PSW B.访管指令 C. 启动I/O指令 D.改变存储器映像图2. 操作系统提供给应用程序员的接口是_。A.库函数 B.进程 C. 线程 D.系统调用3.对于5个并发的进程，设信号量mutex的初值为2，若mutex=-1，则_。A.表示没有进程进入临界区 B.表示有二个进程进入临界区C.表示有二个进程进入临界区，另一个进程等待进入D.表示有一个进程进入临界区，另一个进程等待进入 4.
8、以下调度算法中，会出现饥饿的是。A. 短作业优先 B. 先来先服务 C. 时间片轮转 D. 最高响应比优先5. 产生系统死锁的原因可能是由于_。A.进程释放资源B.一个进程进入死循环C.多个进程竞争,资源出现循环等待D.进程退出6. 采用动态重定位方式装入的作业，其地址转换工作是在_完成的。A.装入作业时 B.作业被选中时C. 每次被移动时 D.每执行一条指令时7. 设备独立性的含义是_。A每一台设备都有一个唯一的编号B程序中使用的设备与实际使用哪台设备无关C多台设备不能并行工作D一个通道上只准连接一台设备8. 页式存储管理中，作业的逻辑地址空间为16MB，其中每页的大小4KB，则作业的页数为
9、_页。 A. 1K B. 2K C. 4K D. 8K9. 如果不允许不同用户的文件可以具有相同的文件名，通常采用_来保证按名存取的安全。A. 重名翻译机构B. 建立索引表C. 建立指针D. 多级目录结构10. 按逻辑结构可把文件分为记录式文件和_两类。 A. 流式文件B.索引文件 C.链式文件 D.顺序文件二、简答题（每题5分，共15分）1.进程的三种基本状态是什么？有哪些状态转换？哪些事件可能引起不同状态间的转换？2.系统中有8个资源被3个进程共享，每个进程一次只能申请/释放一个资源，请问每个进程最多需要多少资源时，系统不会死锁？为什么？3.何谓SPOOLing系统？SPOOLing系统是
10、如何实现虚拟设备的？三、计算题（每题9分，共27分）1. 某请求分页存储系统，其页表存放在主存中。（1）如果对主存的一次存取需要100ns，则访问一个数据的时间是多少？（2）若系统增加了快表，在快表命中或失误时均需要20ns，若快表的命中率为85%，则访问一个数据的时间是多少？回答以上两问题时请说明原因。2. 系统有R1,R2,R3,R4四种资源，在T0时刻进程P0,P1,P2,P3,P4的资源占用和需求情况如图3所示： 资源进程 MAX ALLOCATION AvailableR1 R2 R3 R4R1 R2 R3 R4R1 R2 R3 R4 P00 0 1 20 0 1 2 1 5 2 0
11、 P11 7 5 0 1 0 0 0 P22 3 5 6 1 3 5 6 P30 6 5 2 0 6 3 2 P40 6 5 6 0 0 1 2图3 T0时刻资源占用和需求情况（1） 系统此时是否处于安全状态，为什么？（2） 若此时P4进程发出Request(0,0,0,2),系统能否将资源分配给它？为什么？3. 在一个具有三道作业的批处理系统中，作业调度采用先来先服务（FCFS）调度算法，进程调度采用短进程优先调度算法。现有如表1所示的作业序列，填充表1计算出作业的就绪时间（进入内存时间）、开始时间、完成时间、周转时间以及平均周转时间。表1 作业序列及调度作业号到达输入井时间运行时间(分钟)进入内存时间开始时间完成时间周转时间(分钟)P18:0030P28:1015P38:255P48:3020P58:3510平均周转时间（分钟）四、程序设计题（共13分） 某银行负责办理业务有3个柜台，每个柜台有一名银行职员负责相关业务，有N个供用户等待的椅子。如果没有顾客，则银行职员便休息；当有顾客到来时，唤醒银行职员。每位顾客进入银行后，如果还有空椅子则顾客到取号机领取一个号并且坐在椅子上等待，如果顾客进入银行后发现没有空椅子就离开银行。请用信号量和PV操作正确编写银行职员进程和顾客进程并发的程序。第5页共5页