試題1：現有的操作系統(tǒng)對進程狀態(tài)的定義不盡相同，有的還引入了掛起（suspend）狀態(tài)。試簡要分析掛起狀態(tài)的意義。

    試題2：下述關于雙進程臨界區(qū)問題的算法（對編號為id的進程）是否正確：

    do{
       blocked[id]=true;
       while(turn !=id
       {
         while(blocked[I-id]);
         turn=id;
        }
        編號為id的進程的臨界區(qū)

        blocked[id]=false;
        編號為id的進程的非臨界區(qū)
    }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：已知某系統(tǒng)頁面長4K字節(jié)，頁表項4字節(jié)，采用多層分頁策略映射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：現代操作系統(tǒng)必須支持多種文件系統(tǒng)類型（如CD-ROM的ISO9660、DOS的FAT等）。若要求用如下所示的file_system_type結構描述文件系統(tǒng)類型，用vfsmount結構描述一個已安裝（mount）的文件系統(tǒng)：

struct file_system_type  {
  struct super_block *(*read_super) (struct super_block *, void *, int);
  /* read_super所指的函數用于讀出該文件系統(tǒng)在外存的超級塊 */
  const char *name;  /*所描述文件系統(tǒng)的類型名，如FAT */
  int requires_dev;   */支持文件系統(tǒng)的設備 */
  struct file_system_type * next;  */指向另一種文件系統(tǒng)類型 */
};
struct vfsmount{
  kdev_t mnt_dev;                     /* 文件系統(tǒng)所在設備的主設備號、次設備號*/
  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;               /*指向另一個已注冊的文件系統(tǒng) */
};
式設計一套數據結構，以描述一操作系統(tǒng)已經安裝的文件系統(tǒng)及其類型（答題時，如已知條件不夠，請作必要補充）。

數據庫管理系統(tǒng)（DBMS）有哪些主要功能？通常由哪幾部分組成？

二、有如下的某工廠管理系統(tǒng)的概念模型，依圖說明有哪些實體之間及實體內的值有對應聯系，如何對應，有否聯系屬性。

三、在關系數據庫中，有哪些專門的關系運算？請用集合的形式表示它們。等值連接與自然連接有否有區(qū)別？為什么？

四、有如下“學生_課程”數據庫：
    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

六、并發(fā)操作可能會產生哪幾類數據的不一致性？

《編譯原理》部分試題

一、名詞解釋

    a.句柄
    b.上下文無關文法
    c.LL(1)文法
    d.LR(1)文法
    e.語法制導的翻譯

二、通過一個簡單程序段的編譯過程，描述編譯程序的組成及工作流程。結合你舉的程序段例子，描述每個組成部分的輸入輸出，從而說明每個組成部分的功能。

三、寫出一個可識別C語言的所有正整數的正規(guī)表達式，下面的例子都應當被識別：

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