2007年江苏南京农业大学数据结构与操作系统考研真题.doc

发布时间：2022-09-15 发布人：admin 分类：说明书资料大小：0.05M 资料格式：doc 举报版权申诉

第1页 / 共3页

2007年江苏南京农业大学数据结构与操作系统考研真题.doc.pdf-第2页.jpg

第2页 / 共3页

2007年江苏南京农业大学数据结构与操作系统考研真题.doc.pdf-第3页.jpg

第3页 / 共3页

文本预览

2007 年江苏南京农业大学数据结构与操作系统考研真题一.简答题(每小题 10 分，共 50 分) 数据结构部分： 1. 设有一组关键字(9, 01, 23, 14, 55, 20, 84, 27),釆用哈希函数：H(key)-key Mod 7,釆用开放定址法的二次探测再散列方法解决冲突，试在 0-9 的散列地址空间中对该关键字序列构造哈希表，并计算查找成功时的平均查找长度。 2. 假设用于通信的电文仅由 8 个字母组成，字母在电文中出现的频率分别为 0.07, 0. 19, 0. 02, 0. 06, 0. 32, 0. 03, 0.21, 0. 10. (1) 构造哈夫曼树； (2) 给出对应字符的编码； 3. 假设一棵二叉树的先序序列为 EBADCFHGIKJ 和中序序列为 ABCDEFGHIJK. (1) .请画出该二叉树， (2) .说明建立这棵二叉树的原理 (3) .画岀这棵二叉树的后序线索树。 4. 如图所示为一个无向带权图，假设顶点 a> b> c> d、e、f 的序号分别是 1、2、3、 4、5、 6. (1) 写出其邻接矩阵； (2) 写出其邻接表； (3) 按 Prim 算法求其一棵最小生成树 5.对于关键字序列：83, 40, 63, 13, 84, 35, 96, 57, 39, 79,分别写出应用直接插入排序、快速排序、希尔排序(增量 dl=5),堆排序进行排序，排序第一趟结束时的关键字的状态。二.算法题(每小题 8 分，共 40 分) 1. 已知两个单链表 A 和 B,其元素值按递增次序排列。请编写算法将 A 和 B 归并为一个按元素值递减次序排列的单链表 C,并要求利用原来两个单链表的结点存放归并后的单链表。 2. 若已知两棵二叉树 B1 和 B2 皆为空，或者皆不空且 B1 的左、右子树和 B2 的左、右子树分别相似，则称二叉树 B1 和 B2 相似。试编写算法，判别给定两棵二叉树是否相似. 3. 已知无向图 G,设计算法求距离顶点 V0 的最短路径长度为 K 的所有顶点，要求尽可能节省时间。

4. 假设将循环队列定义为：以域变量 rear 和 length 分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法。 5. 已知无向图 G 釆用邻接表存储方式，试写出删除边(i, j)的算法。一.解释下列名词，并说明关系及区别(每小题 4 分，共 20 分) 操作系统部分： 1. 并发与并行 2. 管道与通道 3. 进程与线程 4. 临界区与临界资源 5. 用户态与核心态二分析及计算(每小题 8 分，共 40 分) 1、一个有快表的请页式虚存系统，设内存访问周期为 2 微秒，内外存传送一个页面的平均时间为 5 毫秒，如果快表命中率为 75%,缺页中断率为 10%。忽略快表访问时间，试求内存的有效存取时间。简要分析计算过程 2、用伪码描述 UNIX 文件系统的空闲块磁盘分配算法 alloc 及释放算法 free? 3、某系统在 TO 时刻按下表所示分配资源给 5 个进程：进程当前已分配(Allocation) 最大需求(Max) 剩余资源(Available) P1 P2 P3 P4 P5 0, 0, 1, 2 1, 0, 0, 0 1, 3, 5, 4 0, 6, 3, 2 0, 0, 1, 4 1, 5, 2, 0 0, 0, 1, 2 1, 7, 5, 0 2, 3, 5, 6 0, 6, 5, 2 0, 6, 5, 6 ⑴ 数组 Need 的内容是什么？ ⑵ 该系统处于安全状态吗？若是，给出一安全序列。 ⑶ 若进程 P2 的请求(0, 4, 2, 0)到过，该请求是否能立即满足？ 4、假设磁盘共有 200 个柱面，编号从 0-199o 当前磁头在 130 号柱面上服务，并刚刚完成了 105 号柱面的请求。如果现有进程 Pl、P2、P3 和 P4 分别请求的柱面号为 186, 158, 105, 90。寻道时每个柱面移动需要 5mso 计算按下列驱动调度算法调度时的寻道时间： (1) 最短寻道时间优先(SSTF)算法 (2) 电梯调度(SCAN)算法 (3) 循环扫描(C-SCAN)算法请给出计算过程。 5、在解决读者-写着问题中可使用管程机制，阅读以下有关管程、读者程序、写着程序及主调程序的程序描述： Monitor readr-Writer_l { int numberOfReaders=0; int numberOfWriters=0; boolean busy=FALSE; Public: startRead()( while(numberofWriters !=0)； numberOfReaders=numberOfReaders+1;};

finishRead()( numberOfReaders=numberOfReaders-1;} start Write()( numberofWriters=numberofWriters+1; while (busy || (numberOfReaders>0)); busy=TRUE; }; finishWrite()( numberofWriters^umberofWriters-1; busy=FALSE;}; }； Reader(){ while(TRUE){ readr-Writer_l .startRead(); readr-Writer_l .finishReadQ; ) } Writer(){ while(TRUE){ readr-Writer_l .startWrite (); readr-Writer_l .finishWrite (); ) Main{ fbrk(writer,O); fdrk(reader,O); } 回答以下问题： 1. 管程机制是解决什么问题的？ 2. 如果采用写者优先的调度策略，以上的管程机制会出现死锁现象？说明原因。 3. 如何改写管程保证读者-写者能够正确执行？用伪码描述

分享到：

赞收藏

资料库

2007年江苏南京农业大学数据结构与操作系统考研真题.doc

相关推荐

考研

热门标签

最新资料