浙江工商大学 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, 9 3. 给定表 （ 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 ;}:
struct node ＊手u nc(st r、uct node *head )
struct node *middle,*tail,*lead ; tail = middle = NUL L; lead = head; while ( lead )
｛
midd le = lead ;
lead = lead -> next ; midd le- > next = tail; tail= midd le;
ret u俨n middle;
｝
二、程序设计 〈共 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 ） 最近最久未使用算法 C LRU ）。 2. (15 分〉 某电信营业厅提供 1个取号机 、2 个服务窗口和 10 个供客户等待的座位 。客户 到达后，如有空位则取号 ，然后等待叫号：当营业员空闲时，则叫号选取一位客户 ，并提 供服务 。请用 P, V C 或 wai t 、signal) 操作来同步上述过程 ，要求：(1） 写出所需要的信 号量及初始值 ：（ 2 ） 用伪码写出上述过程 。 3. (15 分） 某文件系统采用混合索引分配方式 ，如图 2 所示，有 10 个直接块 （每个直接块 指向一个数据块） ， 1 个一级间接块 ，1个二级间接块和 1个三级间接块 ，间接块指向的是 一个索引块，每个索引块和数据块的大小均为 512 字节，索引块编号大小为 4 字节。曰： (1） ！如只使用直接块 ，文件最大为多少字节 ？ ( 2 ） 在该系统中能存储的文件最大是多少 ? ( 3 ） 如读取某文件第 lOM 字节的内容 ，需要访问磁盘几次 ？
答案写在答题纸上 ，写在试卷上无效
第 2 页 （ 共 2 页〉
浙江工商大学2017考研真题之845计算机基础综合
