苏州大学 - 话题

专业名称：计算机应用技术、计算机软件以理论 考试科目：数据结构与操作系统 （B）卷

一． 数据结构部分
注意：算法可以用类C、类C++、类JAVA或类PASCAL任一语言编写，并有类型说明。

1、（15分）名词解释
（1）堆栈
（2）最小生成数
（3）折半（二分）查找
（4）堆排序
（5）连通分量

2、(15分)双端队列是限定插入和删除操作在表的两端进行的线性表。假设
依次输入数据元素为1、2、3、4、5和6，试问通过使用（a）队列；（b）双
端队列，能否得到下列输出序列？
（1）1 2 3 4 5 6 （2）2 4 3 6 5 1 （3）1 5 2 4 3 6
（4）4 2 1 3 5 6 （5）1 2 6 4 5 3 （6）5 2 6 3 4 1

3、（15分）试设计一个算法，将二叉树中的叶子结点按从左到右的顺序放入
一个线性表。假设二叉树采用二叉链表存储结构，线性表采用动态分配顺序
存储结构。

4、（15分）子串的定位操作index(s,t)通常称为串的模式匹配（其中t称为
模式），试编写一个模式匹配算法，匹配过程为：先匹配模式的首尾字符，若
匹配成功，调用函数substr（取子串）求检查模式的首尾之间的字符是否与
目标的相应字符相匹配，若匹配不成功，则进行下一次匹配。

5、（15分）请采用递归方式对一单链表进行归并排序。假设单链表中每个
元素皆为整数，试设计算法完成次操作。










二、操作系统部分
6、（15分）请判断以下说法是否正确，并说明理由。
（1）在单CPU的计算机系统中，进程是不能并行操作的。
（2）在死锁发生后，参与死锁的所有进程都占有资源。
（3）存储管理中的请求式分页系统必定需要重定位机制的支持。

7、（15分）请解释以下的概念：
（1）中断
（2）虚拟设备
（3）中级调度
（4）Cache
（5）LRU算法

8、（15分）在虚拟存储技术中，系统将进行进程运行时所缺的页面调入内存的
时机有预调页策略和请求式调页策略两种。请说明这两种策略的原理，并结合
具体的实例比较这两种策略的优劣。

9、（15分）有一个数据采集和处理系统，出3个负责采集数据的设备，一个
缓冲区和2个数据处理程序组成。其工作原理如下：
（1） 每个采集数据的设备分别由一个进程控制，标记为D1、，D2和D3，
并且每次采集到的数据大小固定为K。
（2） 缓冲区的大小为2*K（可以存放采集到的2份数据）。
（3） 两个数据处理程序运行后，演变为进程P1和P2。
（4） 仅当缓冲区中有D1和D2采集到的各一份数据时，P1取出这两份数
据并处理。
（5） 仅当缓冲区中有D1和D3采集到的各一份数据时，P2取出这两份数
据并处理。
请用信号量机制实现以上5个进程的同步，并保证系统不会发生死锁。

10、（15分）有一批数据，共有32000条记录，每条记录的结构如下：
字段 姓名 地址 年龄 专业
类型 字符 字符 数字 字符
长度（字符） 4-8 0-100 1 0-20
该数据的内容固定不变，其用途主要是用于根据姓名来检索其他相关信
息。现把这些数据以文件形式存放在磁盘上，该磁盘的物理块大小为4KB。
请设计存放该批数据的文件的逻辑结构（可以不存储在一个文件中）和物理
结构（在磁盘上的存储结构），使得检索操作能尽可能少访问磁盘。并计算
在该结构下，每次检索平均需要访问多少个物理块。（假设文件的目录已经
调人内存，文件存放在外存）
zz

在中国7月1日是什么节？（答案为两个字）

考研论坛提示：
1、请勿发布个人联系方式或询问他人联系方式，包括QQ和手机等。
2、未经允许不得发布任何资料出售、招生中介等广告信息。
3、如果发布了涉及以上内容的话题或跟帖，您在考研网的注册账户可能被禁用。