苏 州 大 学
二○○三年攻读硕士学位研究生入学考试试题
学科、专业：???????研究方向：???????考试科目：计算机综合题
2、叙述操作系统提供系统调用的原因，并举例说明应用程序使用这些系统功能调用的两种方式。（10）
3、为了支持请求式分页内存管理，通常页表项内存有一标志位，用来记录相应的页是否被写过，请解释该标志位的操作者及其作用。
4、假设有一组任务序列{（x、y）}，x表示到达时间，y表示需要运行的时间，在FCFS和最短作业优先下的平均周转时间。（10）
5、给出一种文件目录结构的设计，并评价这种设计的优缺点。
6、超市可容纳500人同时购物，有6扇可供出入的门，既可进又可出，每扇门 只允许一个人通过：
6.1 用PV操作及信号量描述进入和离开该超市的算法，使得该超市的购物 容量得到最大发挥。
6.2如再加一个限制条件：同一个顾客进出必须通过同一扇门，那么相应算 法如何写。 注意：答案请不要做在试题纸上 试卷编号：550
04年计算机专业课试卷 数据结构部分:
一. 设有字符串次序为’a+b*c-d’,试用栈将次序改为’abc*+d-‘.假定用
t表示扫描该字符串过程中顺序取一个字符进栈的操作,s表示从栈中取1个字符加入到新字符串尾的出栈操作,写出操作序列.
二. 试分别写出下列2种排序算法的最好.最坏.及平均排序时间(用数量级
表示);(1)插入排序,(2)快速排序. 三. 试用递归算法求出数组A中的最大值.
四. 设有一个双向链表L,每个结点中含有数值域data和访问频度域freq.
在链表被起用前,频度域freq的结构初始化为0,而每当对链表进行了一次visited(L,X)的操作后,则data值为 X的结点的频度域增1,并且同时调整链表中的结点次序使其按频度域值递减次序排列.试编写符合上述要求的visited(L,X)算法.
五. 试编写一算法,判别某一二叉树是否为二叉排序树. 六. 设有向图的邻接表定义如下:
typedef struct node {int adjvex;
struct Arcnode *nextarc; }Arcnode;
typedef struct {Vertextype data; Arcnode *firstarc;
}Vnode;AdjList[MAX_VERTEX_NUM]; typedef struct {AdjList vertices; int vexnum,arcnum; }ALGraph;
请写出计算图中度大于2的顶点个数的算法.
操作系统部分:
一.什么是线程和进程?举例说明他们分别使用的场合?
二.抖动(也称颠簸,Thrashing)是在虚拟存储技术中出现的一个问题,请你描述这个问题的由来,并解释如何采用工作集模型来预防抖动的产生.
三.一个文件有100个磁盘块(块号为0—99),假设文件控制块在内存.在下列情况下,请分别计算并说明在连续分配和链接分配方式下,分别需要执行多少次磁盘I/O操作?(假设每读或写一块磁盘块就是一次磁盘操作;假设在连续分配方式下,文件头部无空闲的磁盘块,但文件尾部有空闲的磁盘块.) (1)在文件开始处添加一个磁盘块(需要往添加的磁盘块中写数据);
(2)在文件第50块前添加一个磁盘块(不需要往添加的磁盘块中写数据); (3)删除文件第50块磁盘块;
(4)在文件结尾处删除一个磁盘块.
四.一个程序P的用户空间为16K,存储管理采用请求式分页系统,每个页面大小为2K,存在以下的页表;
页框号 有效位
12 1 3 1 0 1 0 1 25 1 15 1 0 1 8 1
其中,有效位=1表示页面在内存;0表示页面不在内存.
请将虚地址0x060C,0x1502C,0x1d71,0x2c27,0x4000转换为物理地址. 五.有以下的进程需要调度执行: 进程名 到达时间 运行时间 P1 0.0 9 P2 0.4 4 P3 1.0 1 P4 5.5 4 P5 7 2 (1)如果采用非抢占的短进程优先调度算法,请问这5个进程的平均周转时
间.平均响应时间是多少?
(2)如果采用抢占的短进程优先调度算法, 请问这5个进程的平均周转时
间.平均响应时间是多少?
(3)采用非强占的短进程优先调度算法,存在平均周转时间较大的问题,为
了降低平均周转时间,有这样的一种解决方案:依旧采用非抢占的短进程优先调度算法,但当就绪队列中只有一个进程等待运行时,不马上运行这个进程,而是让这个进程等待1个单位的时间,然后再选择一个运
行时间短的进程投入运行.请问采用这种方法5个进程的平均周转时间.平均响应时间是多少?
六.在经典的同步问题中有一个读者—写者问题,他的实现方法一般都在基于读者优先策略的,现在请用P.V操作来实现基于先来先服务策略的读者—写者问题,具体要求描述如下:
(1)存在m个读者和n个写者,共享同一个缓冲区;
(2)当没有读者在读,且没有写者在写时,读者,写者均可进入读或写; (3)当有读者在读时:
i. 写者来了,则写者等待;
ii. 读者来了,分两种情况处理:无写者等待,则读者可
以直接进入读操作;如果有写者等待,则读者必须依次等待;
(4)当有写者写时,写者或读者来了,均需等待;
(5)当写者写完后,如果等待队列中第一个是写者,则唤醒该写者;如果等待
队列中的第一个是读者,则唤醒该队列中从该读者开始连续的所有读者;
(6)当最后一个读者读完后,如果有写者在等待,则唤醒第一个等待的写者.
苏大05年计算机真题
数据结构部分（算法用类C，C++或类pascal语言编写，要有说明） 一（10分） 什么叫平衡二叉树？一棵结点数为N的平衡二叉数的平均查找时间为多少？请简述之。
二（15分）有1000个无序的数值，希望从快速排序，基数排序，堆排序，归并排序中选一种排序算法，能以最快的速度排出10个最大的数据来，试问选哪种排序算法？为什么？
三（15分）试编写在单向链表中删除值相同的多余结点的算法（要求不使用辅助空间）。
四（20分）设稀疏矩阵M（m*n）中有t个非零元素，用三元组顺序表的方式存储，请设计一个算法，计算矩阵M的转置矩阵N，要求转置算法的时间复杂度为O（n+t）。
五（15分）试设计一个递归算法，产生n！个不同的全排列。
操作系统部分
六（15）请解释并比较以下概念
1，共享设备和独占设备
