南昌大學2003年考研專業課試卷數據結構操作系統A

一. 單項選擇題.(每題2分,共8分)
1.對由n個記錄組成的文件排序,如果n較小(n<50)且記錄的規模較大,則采用(   )排序方法節省時間.
     A.直接插入        B.直接選擇       C.快速            D.堆
2.假定有K個關鍵字互為同義詞,若用線性探測法把這些同義詞存入散列表中,至少要進行(    )次探測.
A.   K          B. K2(K的平方)     C.1/2K(K-1)       D.1/2K(K+1)
3.二維數組a[0…8, 1…10]按行存放時元素a[8, 5]的起始地址與按列存放時元素(   )的起始地址相同.
A. a[8,5]         B. a[3,10]          C. a[5,8]        D. a[0, 9]
4.有6個元素按6,5,4,3,2,1的順序進棧,下列(   )不是合法的出棧序列.
A. 5,4,3,6,1,2      B. 4,5,3,1,2,6    C. 3,4,6,5,2,1     D. 2,3,4,1,5,6
二.填空題(每題3分,共12分)
1. 設P指向二叉樹中某個S結點,結點有二個指針域lchild與rchild分別指向該結點的左,右孩子,則執行下列語句可找到結點P?的中序(對放序)后繼結點q?(假定該后繼結點存在):
       q:=p?.rchild;   ______________
2. 高度為6的AVL樹至少有________結點.(設空二叉樹高度為0)
3. 用數組Q[0..n-1]存放循環隊列, f, r分別為隊頭,隊尾指針,則隊列長度的計算公式是__________. 隊列長度的最大值是____________.
4. 高度為h的完全二叉樹上至少有_______個結點, 至多有_______個結點.
三. 簡答與畫圖題(共24分)
1. 設二叉樹的后根序列為HDEBIFGCA, 中根序列是DHBEAIFCG, 畫出此二叉樹和它所對應的森林.(9分)
2. 順序查找,二分法查找和分塊查找三種方法對查找表中元素各有什么要求? 平均的查找長度各是多少?(假設查找表的長度為n.) (9分)
3. 圖的廣度遍歷算法中既可以在一個點入隊時對其訪問,也可以在頂點出隊時對其訪問,請問前一種方法有何優點?后一種方法可能產生什么問題?并以下圖為例說明.(6分)
                        V0
                V1    V2………Vn
                       Vn+1
四. 算法題.(共31分)
1. 清除重復結點. 單鏈表中數據域的值相同的結點稱為重復結點.如線性表(2,1,1, 3,2,1,) 清除重復結點后為(2,1, 3).試用C語言寫一函數清除單鏈表head中的重復結點,并指出每個工作指針的作用.( 15分)
2. 找第k項. n個元素的第k項是把它們從小到大的排序后的第k個元素.如(16,12,99,95,18,87,10) 的第4項是18.假定n個整數放在數組a [1..n] 中,試寫一算法,不經對整個數組排序,找到第k項.并寫出此算法在最好和最壞情況下的時間復雜度. (提示,利用快速排序中的劃分方法.) (16分)
南昌大學2003年攻讀碩士學位研究生
                                         入  學  考  試  試  題
             報考專業:計算機應用             考試科目:數據結構操作系統(A)
                                                 操作系統部分
一.名詞解釋(每題2分,共10分)
1. 分時與分時系統
2. 進程控制塊
3. 系統顛簸(抖動)
4. 位示圖
5. 設備驅動程序
一. 簡答題(每題4分,共20分)
1. 操作系統的基本特征是什么?
2. 什么叫聯想存儲器?設CPU給出有效地址為(P.D),其中P表示頁號,D表示頁內位移量,試說明利用聯想存儲器實現動態地址變換的過程.
3. 文件存儲空間管理有哪幾種常用的方法?
4. 試給出兩種I/O調度算法,并說明為什么在I/O調度中不能采用時間片輪轉法?
5. 試說明信號量的物理意義?
三.單項選擇題(每題1分,共10分)
1. 存儲器的段頁式管理中,每次從主存中取出一條指令或一個操作數,需要(  )次訪問主存.
            A.1     B.2     C.3     D.4
2.設有n個進程共用一個相同的程序段(臨界區),如果每次最多允許m個進程(m<n)同時進入臨界區.則信號量的初始值為(   ).
            A.n     B.m     C.m-n     D.n-m
3.在操作系統中,一方面每個進程具有獨立性,另一方面進程之間又具有相互制約性.對于任何兩個并發進程,它們(   )
            A. 必定無關      B.必定相關     C.可能相關     D.可能相同
4.一個虛擬存儲器系統中,設主存的容量為16MB,輔存的容量為1GB,而地址寄存器的位數32位.在這樣的系統中,虛存的最大容量是(   ).
          A.1GB       B.16MB      C.1GB+16MB     D.4GB
5.采用直接存取法來讀寫磁盤上的物理記錄時,效率最高的是(    )
      A.連續結構的文件   B.索引結構的文件   C.鏈接結構文件   D.其他結構文件
6.下列算法中可用于進程調度,磁盤調度,I/O調度的是(   )
      A.先來先服務    B. SSTF服務   C.時間片輪轉   D.優先級高者優先
7.通道又稱I/O處理機,它能完成(    )之間的信息傳輸.
      A.主存與外設   B.CPU與外設   C.外設與外設    D.主存與CPU
8.死鎖的4個必要條件無法破壞的是(    ).
       A.互斥條件    B.請求與保持條件   C.非搶奪條件    D循環等待條件
9.文件系統采用多級目錄結構后,對于不同用戶的文件,其文件名(    ).
      A.應該相同    B.應該不同    C.可以不同,也可以相同    D.受系統約束
10最容易開成很多小碎片的可變分區分配算法是(    ).
A.首次適應算法    B.最佳適應算法    C.最壞適應算法    D.以上算法都不會
四,改錯題(劃出下列句子中的錯誤的地方并改正,簡單的否定無分.每小題2分,共10分)
1. 進程有三個狀態:運行態,就緒態和等待態.
2. 在分區存儲管理方案中,作業的大小只受主存加輔存之和大小的 限制,可以實現虛擬存儲.
3. 如果CPU正在執行一個P操作的時候,一個最高級中斷到來,那么中斷處理進程會搶奪CPU.
4. 為了正確地按名存取,操作系統規定不同的文件均不能有相同的文件名.
5. 通常,一個CPU可以連接多個通道,一個通道可以連接多個設備控制器,一個設備控制器可連接多臺外圍設備.
五,計算題(25分)
1. 設有兩個優先權相同的進程,P1,P2如下,令信號量S1,S2的初值均為0,已知Z=2,試問,P1,P2執行結束后,X=?,Y=?,Z=? (6分)
             進程P1                     進程P2
               .                             .
               .                             .
               .                             .
             Y:=1;                         X:=1;
             Y:=Y+Z;                      X:=X+1;
             V(S1);                        P(S1);
             Z:=Y+1;                       X:=X+Y;
             P(S2);                         V(S2);
             Y:=Z+Y;                       Z:=X+Z;
               .                               .
               .                               .
               .                               .
2. 設在單機系統內存中存放三道程序A,B和C,按A,B,C的優先次序運行,其內部計算機I/O操作的時間分配如下圖所示.
       程序A        計算30m->I/O 40ms->計算10ms
       程序B        計算60m->?I/O 30ms->計算10ms
      程序C        計算20m->?I/O 40ms->計算20ms
      
     試畫出按多道運行時的時間關系圖(設有兩個通道,取名為通道1, 通道2,調度程序的執行時間忽略不計),并計算完成這三道程序共花多少時間及比單道程序運行節省多少時間.(9分)
3. 桌子有一個盤子,每次只能放入一個水果,爸爸專向盤中放蘋果,媽媽專向盤中放桔子,女兒專等吃盤中的蘋果,兒子專等吃盤中的桔子.試用P, V操作寫出他們能正確同步的并發程序.(10分).