浙江工商大学 2018 年全国硕士研究生入学考试试卷 （A ）卷考试科曰 ：845计算机基础综合总分：150分考试时间：3小时I数据结构(75分）一问答（每小题10分，共30分〉1.(10分）给定二叉树的两种遍历序歹1j，分别是： 前序遍历序列：D,A,C,E,B,H,F,G,I;中序遍历序列 ：D,C,B,E,H ,A ,G ,I,F;请给出这棵二叉树的后序遍历序列，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。2.(10分〉已知排序码值序列｛19,2,20,7,23,5,65,15｝，请写出快速排序第一趟的排序结果（假 设我们选择第一个元素19做为基数），并描述快速排序算法思想。3.(10 分） 选取哈希函数 H (k ) = C k ) MOD11。用二次探测处理冲突 ，试在一10的散列地址空间中对关键字序列（22,41,53,46,30,13,01）造哈希表，并求等概率情况下查找成功时的平均查找长度。二算法和程序设计 （每小题 15 分，共 45 分）1.(15分〉编写一算法，在不增加辅助空间的前提下，将两个递增的单链表合并为一个递增的单链表。2.(15分〉编写一算法，描述如何将一个中序表达式转化为后序表达式。例如，输入如果是2+3*4+5,则输出为234＊十肘。3.05分〉编写一函数intheight(structtree丰root），求二叉树的高度。假设空二叉树的高度为Oostructtree定义如下：structtree{intdata;structtree*lef t,*right ;II操作系统（75分）三简答题（每小题6分，共30分）1.(6分〉简述操作系统主要功能。2.( 6 分〉 进程状态有哪些 ？这些状态之间如何转换？3.(6分）产生死锁的四个必要条件。4.(6分）TLB(TranslationLookasideBuffer）快表的作用。5.(6分）简述SCAN扫描算法（电梯算法）。四综合题 （每小题 15 分，共 45分）1.C15分〉一个采用请求式页面存储的系统，其物理内存为512M字节，虚拟地址空间大小为 4G字节，页面大小为 4K字节，试问：(1）物理地址应设为多少位？( 2 ） 主存中有多少物理页？( 3 ）虚拟地址应该设多少位？( 4 ）虚拟地址空间最多可以有多少页？(5）页内最大和最小偏移量是多少？2.(15分）有M个生产者凹，P2，…，PM和K个消费者Cl,C2，…，CK，一个大小为n的环形缓 冲区，生产者把产品放入缓冲区，消费者从缓冲区取产品来消费。请用wait和signal原语实现生产者 和消费者的同步操作。3.Cl5 分〉 设系统中物理页的数量为 150。在 TO 时刻按表 I 所示分配给三个进程 Pl P2 和 P3。系统采用银行家算法实施死锁避免策略。对下列内存请求，请分别判断是否安全，如果是安全的，请给出一个可能的进程安全执行序列：如果不是安全的，请说明原因。c1) 进程问到达，共需要60个物理页，当前请求分配25页：(2）进程问到达，共需要50个物理页，当前请求分自己35页半岛在线注册高分咨询罗老师电话/微信：**咨询QQ：**