苏 州 大 学
二○○○年攻读硕士学位研究生入学考试试题
学科、专业：???????研究方向：???????考试科目：数据结构及程序设计卷
四、试编写广度优先遍历图的算法（10分）
五、已知二叉树前根遍历序列和后根遍历序列，试编写生成该二叉树的算法。 算法的输入为二个以字符串形式表示的前根遍历序列和后根遍历序列，算法的输出为该二叉树，用根结点指针表示。（10分）
六、生成一个按蛇形方式排列的自然数1，2，3，4，??,n(n+1)/2的上三角N阶方阵，N阶方阵用二维数组表示，试编写程序。（10分） N＝5的N阶方阵的上三角为：
?1341011??25912????6813??714?o?????15?
七、选取哈希函数 H(k)=(3k)MOD11,d1=H(k),
di=(di-1+(7k)MOD10+1)MOD11(I=1,2,3,??). 试在0到10的地址空间里对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求在等概率情况下查找成功与不成功时的平均查找长度。（15分）
八、有若干条红色，黄色的色条随机摆满一行，试用复杂度为O（n）的算法把它们按颜色有序摆放（颜色相同放在一起），最多使用一个单元的额外附加空间。（15分） 注意：答案请不要做在试题纸上
试卷编号：96 第（2）页共（2
苏 州 大 学
二○○○年攻读硕士学位研究生入学考试试题
学科、专业：???????研究方向：???????考试科目：操作系统原理
一、简述题
1．1、请简述进程和线程之间的异同。
1．2、程序的链接方法中有一种是运行时的动态链接，什么是运行时的动态链
接，有什么特点？
1．3、如何区分分时操作系统的客户运行的程序和网络操作系统所支持的客户
端的运行程序？
1．4、简述设备管理的基本功能。
二、如果一个作业在执行中，按下列页号访问：1，2，3，4，2，1，5，6，2，1，
2，3，7，6，3，2，1，2，3，6作业固定占用4块内存空间，采用先进先出的淘汰算法和最少调用淘汰算法时，各产生多少次缺页中断？写出在淘汰时在内存中的页面号和被淘汰的页面号。（18’）
三、试用管程的方法解决生产者-消费者问题：有若干个生产者和消费者共享一
个容量为m的缓冲区。（10’）
四、描述请求分页存储管理方式的实现过程。（20’）
五、请叙述Unix的文件管理系统的设计和实现。（20’） 注意：答案请不要做在试题纸上
试卷编号：97 第（1）页共（1）页
苏 州 大 学
二○○一年攻读硕士学位研究生入学考试试题
学科、专业：???????研究方向：???????考试科目：数据结构及程序设计卷
注意：算法请用类PASCAL或类C语言编写，程序请用PASCAL或类C语言编写
一、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（注意不设头指针），试编写相应的置空队列、入队列和出队列的算法。（10分）
二、假设有两个按元素值递增有序排列的线性表A和B，A和B均以单链表表示，请编写算法将表A、B归并成一按元素值递减有序排列的线性表C，并要求利用原表（即表A和表B）结点空间存放表C。（10分）
三、1、何谓排序方法的稳定性？（3分）
2、下列排序方法那些是稳定的，那些是不稳定的？（4分） 3、对不稳定的方法举实例说明之。（8分） 直接插入排序，希尔排序，快速排序，归并排序
四、试编写归并排序算法。（10分）
五、有下列关键字：（10分）
15，23，29，31，47，66，74，85，90，98，102 1、画出描述折半查找过程的判别树。
2、对含关键字的有序表，采用折半查找，在查找成功时，关键字比较的次数至多是多少？在查找不功时，关键字比较的次数至多是多少？
六、编写一算法，判别以邻接表方式存储的有向图中是否存在顶点Vi到顶点Vj的路径。（10分） 注意：答案请不要做在试题纸上
试卷编号：90 第（1）页共（2）页
苏 州 大 学
二○○一年攻读硕士学位研究生入学考试试题
学科、专业：???????研究方向：???????考试科目：操作系统原理
一、 是非题：判断是非并给出解释。（5’*4）
1.1、 分布式操作系统和网络操作系统没有本质区别。
1.2、 使用快表技术事实上将增加一次快表的访问时间，所以在内存管理中
应该慎用该技术。
1.3、 死锁在操作系统的设计和实现中绝对不允许出现。
1.4、 原语操作是不可中断的。
二、 简述题（5’*4）
2.1、 进程和线程的异同。
2.2、 操作系统本质上也需要时空开销的，怎样解释这些开销还是值得的。
2.3、 简述存储器管理的基本目的和基本问题。
2.4、 简述设备分配的基本类型和基本策略。
三、 叙述中断机制在操作系统中的地位和作用。（10’）
四、 试给出一种实现虚存的解决方案。(10’)
五、 举出设备管理子系统中利用中断、轮询和DMA的例子。(12’)
六、 以下是文件系统的四个相关的结构定义中的一部分：
6.1、 请描述这些结构的作用和相互关系；(8’)
6.2、 根据这些结构，请描述文件的物理结构；(8’)
6.3、 基于这些结构，请设计至少四条有关文件系统功能调用的实现。(12’) 注意：答案请不要做在试题纸上
试卷编号：91 第（1）页共（2）页
