苏州大学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) 当最后一个读者读完后,如果有写者在等待,则唤醒第一个等待的写者. |
