浙江工商大学2018硕士考研真题之845计算机基础综合

由天下分享时间：2024/9/14 14:01:15 加入收藏我要投稿点赞

浙江工商大学 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 ) MOD 11。用二次探测处理冲突，试在一10 的散列地址空间中对关键字序列（ 22, 41, 53, 46, 30, 13, 01 ）造哈希表，并求等概率情况下查找成功时的平均查找长度。二、算法和程序设计（每小题 15 分，共 45 分） 1. (15 分〉编写一算法，在不增加辅助空间的前提下，将两个递增的单链表合并为一个递增的单链表。 2. (15 分〉编写一算法，描述如何将一个中序表达式转化为后序表达式。例如，输入如果是 2+3*4+5, 则输出为 234＊十肘。

3. 05 分〉编写一函数 in t he ight (struct tree 丰root ），求二叉树的高度。假设空二叉树的高度为 O o struct tree 定义如下： struct tree{ int data ;

struct tree *lef t, *right ;

II 、操作系统（ 75 分）三、简答题（每小题 6 分，共 30 分） 1. ( 6 分〉简述操作系统主要功能。

2. ( 6 分〉进程状态有哪些？这些状态之间如何转换？ 3. ( 6 分）产生死锁的四个必要条件。

4. ( 6 分） TLB ( Translat ion Lookasi de Buf f er ）快表的作用。

(6 分）简述 SCAN 扫描算法（电梯算法）。四、综合题（每小题 15 分，共 45 分）

1. C 15 分〉一个采用请求式页面存储的系统，其物理内存为 512M 字节，虚拟地址空间大小为 4G 字节，页面大小为 4K 字节，试问： (1）物理地址应设为多少位？ ( 2 ）主存中有多少物理页？ ( 3 ）虚拟地址应该设多少位？

( 4 ）虚拟地址空间最多可以有多少页？

( 5 ）页内最大和最小偏移量是多少？

答案写在答题纸上，写在试卷上无效

第 l 页（其 2 页）

2. (15 分）有 M 个生产者凹，P2 ，…，PM 和 K 个消费者 Cl , C2 ，…，CK ，一个大小为 n 的环形缓冲区，生产者把产品放入缓冲区，消费者从缓冲区取产品来消费。请用 wai t 和 signal 原语实现生产者和消费者的同步操作。