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