2006－2007年苏州大学论坛资源共享计划--计算机专业07年数据结构和操作系统试题

gyjingling

苏州大学
二00七年攻读硕士学位研究生入学考试试题
一．        数据结构部分
1名词解释
（1）        逆波兰式
（2）        自由树
（3）        外部排序
（4）        邻接表
（5）        占位程序
2队列的实现方法有哪些？试比较各种实现方法的优缺点，并举例说明队列在计算机系统中有何应用。
3设L1和L2为单链表表示的有序表，试编写算法，求解L1∩L2，即求解既在L1中又在L2中的元素，结果放在L1中。
4试编写一个算法，将两棵二叉排序树合并为一棵二叉排序树。
5试设计一个求有向无环图中最长路径的算法，并估计时间复杂度。
二．        操作系统部分
6请判断下述说法的对错，并说明原因。
（1）        分时操作系统必然建立在多道程序技术的基础之上。
（2）        进程是指令的集合。
（3）        存储保护的功能是限制内存存取。
（4）        位示图可用于主存空间的共享。
7假设某个请求页式管理系统，具有16G的物理内存，48位的虚拟地址，每页大小为8K字节：
（1）        请以图示的形式给出虚拟地址向物理地址映射的过程，要求明确给出以下内容：
        逻辑地址和物理地址各部分的说明；
        地址各部分的大小，以位（bit）为单位；
        每个页表的最多的表项数；
        每个页表的最大尺寸，以字节（byte）为单位。
（2）        对这样的系统，页表可能变得很大，特别是当它们被稀疏存放时。请描述一种更有效的存储页表的技术，并解释为什么这个技术能够提高页表的存储效率。
8有三种文件分配方案：连续分配。链接分配。UNIX inode,请详细说明下列的文件访问需求，采用哪中分配方案最合适？
（1）        大文件顺序访问
（2）        大文件直接访问
（3）        小文件直接访问
9什么是虚拟设备？为什么在操作系统中要引入虚拟设备？
10设有五个哲学家，他们花费一生中的时光思考和吃饭。这些哲学家共用一个圆桌，每个哲学家都有一把椅子。桌子中央是一碗米饭。桌子总共有6根筷子，在每个人两边分开各放一根，桌子中央还有一根。当一个哲学家思考时，他与其他同事不交互，一个哲学家一次只能拿起一根筷子。显然他不能从其他哲学家里抢走筷子，吃完后放下所有的筷子。哲学家只有在饥饿时才试图从两边或者桌子中央取2根筷子就餐。
试问：（1）P﹑V操作系统描述满足上述要求的哲学家进程，要求不能产生死锁；
（2）分析上述解决方案的利弊。

[ 本帖最后由 elast 于 2007-11-3 09:12 编辑 ]

horsechestnut

谢谢阿

jot1984

昏，还以为是扫描的呢，

gyjingling

照片版的我也有，
只是太大，附件不好发

jinling1015

谢谢啊。。。。太感谢了啊。。要是不要钱就更 好了

jinling1015

再跟一个

jinling1015

再跟一个
楼主辛苦

jinan007

谢谢 谢谢 谢谢 谢谢

jinan007

谢谢 谢谢

jinan007

楼主辛苦