桂林电子科技大学2015年研究生统一入学考试试题
请注意：答案必须写在答题纸上（写在试题上无效）。
PART I数据结构部分 一、 选择题（24分。共8小题，每小题3分） 1. 关于数据结构的描述，正确的是（）。 A．数据的逻辑结构可以划分为：线性结构、树型结构和索引结构 B．一种逻辑结构可采用多种存储结构实现 C．一种存储结构只能实现一种逻辑结构 D．现实世界中数据对象的1对多联系可以采用线性结构表达 2. 关于顺序表和链接表的描述，错误的是（）。 A．顺序表和链接表是线性表的不同存储结构实现 B．顺序表将线性表中数据元素之间的相邻关系映射为数据物理位置上的相邻关系 C．分别在具有n个数据元素的顺序表和链接表中查数据元素K，链接表的查效率要高于顺序表。 D．数组可以作为线性表的一种顺序表实现 3. 图1中，（a）是结点结构，（b）是指针s指向的待插入结点，（c）是双向链表片段，则在（c）中p指针指向的结点前面插入指针s指向的结点的操作是（）。 图1双向链表 A．s->rlink=p; s->llink=p->llink; p->llink->rlink=s; p->llink=s; B．p->llink=s; s->rlink=p; s->llink=p->llink; p->llink->rlink=s; C．p->llink->rlink=s; p->llink=s; s->rlink=p; s->llink=p->llink; D．s->rlink=p; s->llink=p->llink; p->llink=s; p->llink->rlink=s; 4. 若出栈的顺序是a, b, c, d, e，则入栈的顺序不可能是（）。 A．a, b, c, d, e B．e, d, c, b, a C．d, e, c, b, a D．a, e, d, c, b 5. 二叉树的前序序列是：ABDCGEF，中序遍历序列是：DBCGAEF，则该二叉树的叶子结点数目是（）。 A．2 B．3 C．4 D．5 6. 给定四个符号X, Y, Z, P，它们被使用的频率分别是0.2、0.4、0.3和0.1，采用哈夫曼编码后，‘Z’的编码长度是（）。 A．1 B．2 C．3 D．4 7. 若待排序的元素序列基本有序，则（）算法效率最高。 A． 插入排序B．选择排序C．快速排序D．归并排序鲤鱼怎么做 8. 一个无向图具有n个顶点m条边，则该无向图中所有顶点的度数之和是（）。 A．2n B．n+m C．2m D．n*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 tmp=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）。给定数组HT[0..8]作为散列表的存储空间，散列函数为H(key) = key % 9，且采用线性探查法解决冲突。 （1）若采用给定散列表存储线性表B，请画出对应的散列表。（5分） （2）若B中少于等于40的数据元素的查概率为2/15，大于40的数据元素的查概率为1/15，请计算查成功的平均查长度。（4分） 3.无向带权图的邻接矩阵如下所示 请用Kruskal算法构造此图的最小生成树，要求给出详细的构造过程。（9分） 4.给定一待排序关键字序列(40，25，64，18，21，36，9，30)。 （1）请以每一个待排序区间的最后一个元素为基准记录，给出前3趟快速排序每一趟排序的结果。（6分。注：按照升序进行排序） （2）请问需要经过几趟快速排序，上述序列才排序结束。（3分） 三、 算法设计题（15分） 一个长度为N的字母序列STR是对称的是指对任意的序号i（0≤i≤N-1），有STR[i]=STR[N-i-1]，例如“ABA”或者“ABBA”等。若采用带有头结点的双向循环链表来存储字母序列，链表中的每个结点存储一个字母（如图2所示）。请设计一个判定字母序列是否对称的算法，如果对称返回TRUE（或者1），否则返回FALSE（或者0），要求时间复杂度不超过O(n)。 图2带头结点的双向循环链表 PARTII 操作系统部分 一、选择题（每题2分，共20分） 1. 下列指令中，________可以在用户态运行。 A.加载PSW B.访管指令 C. 启动I/O指令 D.改变存储器映像图 2. 操作系统提供给应用程序员的接口是_________。 3.对于5个并发的进程，设信号量mutex的初值为2，若mutex=-1，则____________。 A.表示没有进程进入临界区 B.表示有二个进程进入临界区 C.表示有二个进程进入临界区，另一个进程等待进入 D.表示有一个进程进入临界区，另一个进程等待进入 4. 以下调度算法中，会出现饥饿的是。 5. 产生系统死锁的原因可能是由于_____________。 A.进程释放资源 B.一个进程进入死循环 C.多个进程竞争,资源出现循环等待 D.进程退出 6. 采用动态重定位方式装入的作业，其地址转换工作是在____________完成的。 A.装入作业时 B.作业被选中时 C. 每次被移动时 D.每执行一条指令时 7. ＂设备独立性＂的含义是__________。 A．每一台设备都有一个唯一的编号 B．程序中使用的设备与实际使用哪台设备无关 C．多台设备不能并行工作 D．一个通道上只准连接一台设备 8. 页式存储管理中，作业的逻辑地址空间为16MB，其中每页的大小4KB，则作业的页数为______页。 A. 1K B. 2K C. 4K D. 8K 9. 如果不允许不同用户的文件可以具有相同的文件名，通常采用_______来保证按名存取的安全。 A. 重名翻译机构 B. 建立索引表 C. 建立指针 D. 多级目录结构 10. 按逻辑结构可把文件分为记录式文件和______两类。 A. 流式文件B.索引文件 C.链式文件 D.顺序文件 二、简答题（每题5分，共15分） 1.进程的三种基本状态是什么？有哪些状态转换？哪些事件可能引起不同状态间的转换？ 2.系统中有8个资源被3个进程共享，每个进程一次只能申请/释放一个资源，请问每个进程最多需要多少资源时，系统不会死锁？为什么？ 3.何谓SPOOLing系统？SPOOLing系统是如何实现虚拟设备的？ 三、计算题（每题9分，共27分） 1. 某请求分页存储系统，其页表存放在主存中。 （1）如果对主存的一次存取需要100ns，则访问一个数据的时间是多少？ （2）若系统增加了快表，在快表命中或失误时均需要20ns，若快表的命中率为85%，则访问一个数据的时间是多少？ 回答以上两问题时请说明原因。 2. 系统有R1,R2,R3,R4四种资源，在T0时刻进程P0,P1,P2,P3,P4的资源占用和需求情况如图3所示：
图3 T0时刻资源占用和需求情况 （1） 系统此时是否处于安全状态，为什么？ （2）拔丝苹果怎么做 若此时P4进程发出Request(0,0,0,2),系统能否将资源分配给它？为什么？ 3. 在一个具有三道作业的批处理系统中，作业调度采用先来先服务（FCFS）调度算法，进程调度采用短进程优先调度算法。现有如表1所示的作业序列，填充表1计算出作业的就绪时间（进入内存时间）、开始时间、完成时间、周转时间以及平均周转时间。 表1 作业序列及调度
四、程序设计题（共13分） 某银行负责办理业务有3个柜台，每个柜台有一名银行职员负责相关业务，有N个供用户等待的椅子。如果没有顾客，则银行职员便休息；当有顾客到来时，唤醒银行职员。每位顾客进入银行后，如果还有空椅子则顾客到取号机领取一个号并且坐在椅子上等待，如果顾客进入银行后发现没有空椅子就离开银行。请用信号量和PV操作正确编写银行职员进程和顾客进程并发的程序。 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
发布评论