浙江工商大学2017年全国硕士研究生入学考试试卷（A）卷考试科目 ：845计算机基础综合总分：150分考试时间：3小时第I部分数据结构（75分〉一简答题（每小题7分，共42分）1.有一份电文中共使用五种字符 ：a,b,c,d,e ，它们的出现频率依次为 15,18,16,13,110，请画出对应的编码赫夫曼树（请按照左子树根结点的权小于等于右子树根结点的权的次 序构造），并求出该树的带权路径长度。2.已知一棵二叉树的前序和中序序列，建立该二叉树，并求该二叉树的后序序列。前序序列 ：8,6,3,1.2,5,4,9,7中序序列：1,2,3,4,5,6,8,7,93.给定表（23，”，42，”，78, 95,22,35），请将表调整成初始最大堆。4.请描述克鲁斯卡尔（Kruskal）构造最小生成树算法。5.设一数列的输入顺序，为1234，若采用堆枝结构，试问通过入出挽操作，能否得到合法序列3241，如果能，则给出得到这个序列相应的push和pop操作。6. 阅读下列程序，说明该函数实现了，什么功能。若原单链表中数据结点的值按顺序分别为1,3,6,4,2,S，调用该函数后，结点值有何变化？typedef struct node{int data;st俨uct node *next;}:structnode＊手u nc(st ructnode*head)struct node *middle,*tail,*lead;tail =middle =NULL;lead =head;while(lead )｛midd le =lead;lead = lead -> next ;middle->next=tail;tail=middle;ret u俨nmiddle;｝二程序设计〈共33分〉1. ( 12 分） 若以单链表作为存储结构 ，编写一算法，删除该线性表中所有大于 a 且小于b的元素（若表中存在这样的元素）同时释放被删除结点空间，假设线性表中的元素按递增有序排列。2.(9分）设棵二叉树以二叉链表为存储结构，结点结构为!child !data jrchild。设计一个算法 ，求在前根序列中处于第 k个位置的结点。3. ( 12 分） 试写一算法 ，将两棵二叉排序树合并为一棵二叉排序树 。答案写在答题纸上，写在试卷上无效第1页（共2页）第口部分操作系统（75分〉 三简答题〈每小题6分，共30分〉 1.简述引起进程调度的原因。2.比较分段和分页两种内存管理机制的不同。3.产生死锁条件及解决方法。4.SPOOLing技术。5.电梯调度算法。四综合题（每小题15分，共45分）1.(15分） 在分页存储管理系统中 ，按如下次序访问页：10→6→8→7→10→6→20→10→6→8→7→20 ，假定分配的物理块数为3，试分别计算采用如下页面置换算法时的缺页次数:(1）先进先出置换算法（FIFO);(2）最近最久未使用算法CLRU）。2.(15分〉某电信营业厅提供1个取号机2个服务窗口和10个供客户等待的座位。客户 到达后，如有空位则取号，然后等待叫号：当营业员空闲时，则叫号选取一位客户，并提 供服务。请用P,VC或waitsignal)操作来同步上述过程，要求：(1）写出所需要的信 号量及初始值：（2）用伪码写出上述过程。3.(15分）某文件系统采用混合索引分配方式，如图2所示，有10个直接块（每个直接块 指向一个数据块），1个一级间接块，1个二级间接块和1个三级间接块，间接块指向的是 一个索引块，每个索引块和数据块的大小均为512字节，索引块编号大小为4字节。！曰： (1）如只使用直接块，文件最大为多少字节？(2）在该系统中能存储的文件最大是多少?(3）如读取某文件第lOM字节的内容，需要访问磁盘几次？考研高分咨询罗老师电话/微信：**咨询QQ：**