1、桂林电子科技大学2015年研究生统一入学考试试题科目代码：823科目名称：数据结构+操作系统请注意：答案必须写在答题纸上（写在试题上无效）。PART I 数据结构部分一、 选择题（24分。共8小题，每小题3分）1. 设数据结构B=，其中K=a，b，c，d，R=，, ，则B是（）。A线性结构 B树型结构C图型结构 D索引结构2.若线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则下面最适合的存储结构是（）。 A带头指针的单链表 B带头指针的双链表 C带头指针的单循环链表 D带尾指针的单循环链表3.图1中，（a）是结点结构，（b）是双向链表片段，若要删除（b）中p指针指向结点的
2、后继结点，则正确的操作是（）。图1双向链表Ap-rlink-data=p-data; p-llink-rlink=p-rlink; p-rlink-llink=p-llink; free(p);Bp-rlink-data=p-data; p-rlink=p-rlink-llink; p-rlink-rlink-llink=p; free(p);Cp-rlink=p-rlink-llink; p-rlink-rlink-llink=p; free(p-rlink);Dp-rlink-rlink-llink=p; p-rlink=p-rlink-llink; free(p-rlink);4. 设栈
3、S和队列Q的初始状态为空，元素a，b，c，d ，e，f依次进栈，一个元素出栈后即进入队列Q。如果6个元素出队列的顺序是b，d，c，f，e，a，则栈S的容量至少应该是（）。 A2B3C4D55给定有序表 16，23，32，45，51，62，73，79，80 ，若采用二分检索法查找关键码值为62的数据元素，（）次比较后查找成功。A1 B2 C3 D46. 给定一棵具有n个结点的二叉树，在不违背二叉树定义以及不改变根结点的基础上，向二叉树中任意一个可插入结点的位置插入一个新的结点，则生成的新二叉树有（）。种可能。 An-1BnCn+1D2n7. 下列排序方法中，哪一种方法的比较次数与记录的初始排列状
4、态无关？（） A、直接插入排序 B、冒泡排序 C、快速排序 D、直接选择排序8.若让一个具有n个顶点的有向图是强连通图，则至少需要（）条狐。 An Bn+1 C2n Dn(n-1)二、应用与分析题（36分。共4小题，每小题9分）1.请给出下面算法的功能描述。struct Node;typedef struct Node* PNode;struct Node DataType info; PNode link;typedef struct Node * LinkList;int Test(LinkList list, DataType value) LinkList first=list; wh
5、ile( ( first!=null ) & (first-link!=null) LinkList tmp=first-link;if ( tmp-info=value )first-link=tmp-link;free tmp; elsefirst=first-link;2.设哈希函数 H（k）=（3 * k） mod 11 ，散列地址空间为 010。给定关键字序列（35，13，49，24，62，21，14，81，12）。（1）若采用拉链法解决冲突，请构造哈希表。（6分）（2）请基于（1）的结果，给出等概率情况下查找成功时的平均查找长度。（3分）3. 请证明：任意一棵具有N个结点的满二叉树
6、（N0）的叶子结点数目为（N+1）/2。（9分）4. 给出一组排序码：56，32，65，24，16，9，43，39，若对其进行堆排序（按升序排列），（1）请给出构建的大根堆（6分）（2）请给出前3趟堆排序，每一趟排序后堆的结果。（3分）三、算法设计题（15分）拟采用带头结点的单链表来存储线性表中的数据元素，但要求单链表中数据元素的存储顺序与线性表中数据元素的顺序逆序。即若线性表中的数据元素序列是a1,a2,an-1,an,则实现的单链表的数据元素的序列是an,an-1, ，a2,a1（请见图2）。图2 逆序建单链表示意图PART II 操作系统部分一、选择题（每题2分，共20分）1.操作系统的
7、基本类型主要有_。A批处理系统、分时系统及多任务系统B实时操作系统、批处理操作系统及分时操作系统C单用户系统、多用户系统及批处理系统D实时系统、分时系统和多用户系统2. 操作系统中采用多道程序设计技术是为了提高CPU和外部设备的。 A.利用率 B.可靠性 C.稳定性 D.兼容性3. 对于两个并发的进程，设信号量的初值为mutex=1，若mutex=0，则表示_。A.没有进程进入临界区B. 有一个进程进入临界区，另一个进程等待进入临界区C.有一个进程进入临界区D.有两个进程进入临界区4._算法综合考虑了作业等待时间和计算时间。A.先来先服务 B.计算时间短的优先C.均衡调度 D.响应比最高者优先
8、5.某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是_。A.9 B.10 C.11 D.126.两个进程合作完成一个任务。在并发执行中，一个进程要等待其合作伙伴发来消息，或者建立某个条件后再向前执行，这种制约关系性合作关系被称为进程的_。 A.同步 B.互斥 C.调度 D.执行7. 通过硬件和软件的功能扩充，把原来独占的设备改造成若干用户共享的设备，这种设备称为_。A.存储设备 B.系统设备 C.虚拟设备 D.用户设备8. 在段式存储管理中，若逻辑地址为16位、每个段的最大长度为2K，则最多允许_段。A.4个 B.8个 C.16个 D.32个9. 在可变分区管理
9、方式下若把空闲区按长度递增次序登记在空闲区表中，则对分配算法是最方便的。 A. 最优适应 B.最先适应 C.最坏适应 D.最后适应10.既可以采用顺序访问，又可以采用直接访问的文件物理结构是_。A. 顺序文件 B. 连接文件C. 索引文件D. 以上都不是二、简答题（每题5分，共15分）1.请简述进程与线程的主要区别。2.何谓程序的局部性原理？给出虚拟存储器的设计原理。3.为什么要引入缓冲技术？给出缓冲的基本思想以及常用的缓冲技术。三、计算题（每题9分，共27分） 1. 在一个请求分页系统中，某作业的大小为1000个字，考虑如下逻辑地址访问序列：202,610,825,110,50,332,51
10、0,434,358,210,108,95,276,101。页的大小为100个字。(1)请给出页面访问序列。(2)假如分配给该作业的物理块数M分别为3，请用LRU（最近最久未使用）页面置换算法计算页面淘汰顺序及其缺页次数。 2.假定某磁盘上共有200个柱面，编号为0-199，当前磁头的位置位于90号柱面，当前正在向199号柱面方向前进。同时有若干请求者在等待服务，它们依次要访问的柱面号为：85、132、188、94、155、100、170、125。假设每移动一个柱面所需的时间为2s，试分别采用最短寻道优先算法（SSTF）和电梯调度算法计算实际的服务次序，并计算各个算法的平均寻道时间。 3.有一个
11、具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，在表1所示的作业序列中作业优先数即为进程优先数，优先数越小优先级越高。列出所有作业进入内存时间、开始时间、结束时间、周转时间，计算平均周转时间。表1 作业序列及调度作业号到达输入井时间运行时间(分钟)优先数进入内存时间开始时间完成时间周转时间（分钟）A10:00403B10:20301C10:30502D10:50204平均周转时间（分钟）四、程序设计题（共13分） 某工厂有2个生产配件的车间A、B和一个装配车间C，A、B两个车间分别生产两种配件，C的任务是取一个A车间的配件和一个B车间的配件组装成一个产品。A、B车间各有一个存放配件的仓库，每个仓库最多只能存放50个配件；C车间从A、B仓库各取一个配件，装配好的产品及时运到测试车间测试，无需考虑容量问题。请用信号量和PV操作正确编写A、B、C三个车间的同步关系的程序。第6页共6页
