试题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)
                         {
                        }