(单词翻译:单击)
考试科目:计算机专业课(甲)
试题1:现有的操作系统对进程状态的定义不尽相同,有的还引入了挂起(suspend)状态。试简要分析挂起状态的意义。
试题2:下述关于双进程临界区问题的算法(对编号为id的进程)是否正确:
do{
blocked[id]=true;
while(turn !=id
{
while(blocked[I-id]);
turn=id;
}
编号为id的进程的临界区
blocked[id]=false;
编号为id的进程的非临界区
}while(true);
其中,布尔型数组blocked[2]初始值为{false,false},整型turn初始值为0,id代表进程编号(0或1)。请说明它的正确性,或指出错误所在。
试题3:信号量如果只能取0或1为值,就变成了二元信号量。二元信号量更容易实现。而且,信号量可以由二元信号量替换。以下所列函数试图用二元信号量操作waitB()和singalB()替换信号量wait()、signal()
:
wait(semaphore s)
{
waitB(mutex);
s=s-i
if(s<0)
{
signalB(mutex);
waitB(delay);
}
else
signalB(mutex);
}
signalB(semaphore) s}
{
waitB(mutex);
s=s+1;
if(s<=0)
signalB(delay);
signalB(mutex);
}
其中,用于互斥的二元信号量mutex初始化为1,用于进程挂起的二元信号量dealy初始化为0。请指出该替换算法的错误所在。
试题4:已知某系统页面长4K字节,页表项4字节,采用多层分页策略映射64位虚拟地址空间。叵限定最高层页表占1页,问它可以采用几层分页策略。
试题5:一进程已分配到4个页帧(page frame),如下表(所有数字都为10进制数,且以0开始)。
虚拟页号 页帧 装入时间 最近访问时间 记问位 修改位
2 0 60 161 0 1
1 1 130 160 0 0
0 2 26 162 1 0
3 3 20 163 1 1
当进程访问第4页时,产生缺页中断。请分别用FIFO(先进先出)、LRU(最近最少使用)、NRU(最近
不用)算法,决定缺页中断服务程序选择换出的页面。
试题6:现代操作系统必须支持多种文件系统类型(如CD-ROM的ISO9660、DOS的FAT等)。若要求用如下所示的file_system_type结构描述文件系统类型,用vfsmount结构描述一个已安装(mount)的文件系统:
struct file_system_type {
struct super_block *(*read_super) (struct super_block *, void *, int);
/* read_super所指的函数用于读出该文件系统在外存的超级块 */
const char *name; /*所描述文件系统的类型名,如FAT */
int requires_dev; */支持文件系统的设备 */
struct file_system_type * next; */指向另一种文件系统类型 */
};
struct vfsmount{
kdev_t mnt_dev; /* 文件系统所在设备的主设备号、次设备号*/
char *mnt_devname; /*设备名,如/dev/hdal */
unsigned int mnt_flage; /*安装目录名称 */
struct semaphore mnt_sem; /*设备标志,如ro */
struct super_block *mnt_sb; /*对设备I/O操作时的信号量 */
struct file *mnt_quotas[MAXQUOTAS]; /*指向超级块 */
struct file *mnt_quotas[MAXQUOTAS]; /* 指向配额文件的指针 */
time_t mnt_iexp[MAXQUOTAS]; /*inode有效期 */
time_t mnt_bexp[MAXQUOTAS]; /*数据块有效期 */
struct vfsmount *mnt_next; /*指向另一个已注册的文件系统 */
};
式设计一套数据结构,以描述一操作系统已经安装的文件系统及其类型(答题时,如已知条件不够,请作必要补充)。
一、数据库管理系统(DBMS)有哪些主要功能?通常由哪几部分组成?
二、有如下的某工厂管理系统的概念模型,依图说明有哪些实体之间及实体内的值有对应联系,如何对应,有否联系属性。
三、在关系数据库中,有哪些专门的关系运算?请用集合的形式表示它们。等值连接与自然连接有否有区别?为什么?
四、有如下“学生_课程”数据库:
S(Sno, Sname, S***, Sage, Sdept)
学号 姓名 性别 年龄 学系
C(Cno, Cname, Cpno, Ccredit)
课号 课程名 先修课号 学分
SC(Sno, Cno, Grade)
成绩
1.用SQL语言定义模式时是如何说明参照完整性的。
2.用SQL语言的带NOT EXISTS谓词的嵌套查询,写出“查询选修了全部课程的学生姓名”的查询语句。
五、下面结论哪些是正确的,哪些是错误的?为什么?
1.任何一个二目关系都是属于BCNF的
2.当且仅当函数依赖A->B在R上成立,关系R(A,B,C)等于其投影RI(A,B)和R2(A,C)的自然连接。
3.若R.A->R.B, R.A->R.C,则R.A->R.(B, C)
4.若R.B->R.A, R.C->R.A,则R. (B, C)-R. A
5.若R. (B, C)->R.A, 则 R.B->R.A, R.C->R.A
六、并发操作可能会产生哪几类数据的不一致性?
《编译原理》部分试题
一、名词解释
a.句柄
b.上下文无关文法
c.LL(1)文法
d.LR(1)文法
e.语法制导的翻译
二、通过一个简单程序段的编译过程,描述编译程序的组成及工作流程。结合你举的程序段例子,描述每个组成部分的输入输出,从而说明每个组成部分的功能。
三、写出一个可识别C语言的所有正整数的正规表达式,下面的例子都应当被识别:0x89ab 0123 45 ‘z’ ‘/t’ ‘|xab|’ ‘/012’
四、下面的文法是LL(1)吗?为什么?如果不是,请把它转换为等价的LL(1)文法。
S à symbol stuff
∣ TOKEN TOKEN stuff
∣ star_list stuff
star_lish à star_lish STAR
∣ /*epsilon */
symbol à TOKEN
stuff à ANOTHER_TOKEN
五、写一个翻译程序,它的输入是含C语言的老式函数定义的方法,其翻译结果是C++的函数定义。例如:
老式函数定义
apostles(mat, mark, luke, juhn,fred)
char * mat;
long mark;
double luke;
{
}
其翻译结果将是C++的函数定义:
apostles(char *mat, long mark, double luke, int john, int fred)
{
}