浙江省中國(guó)計(jì)量大學(xué)數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)考研模擬題

2021年浙江省中國(guó)計(jì)量大學(xué)數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)考研模擬試題一、單項(xiàng)選擇題：1～40小題，每題2分，共80分。在每題給出的四個(gè)選項(xiàng)中，請(qǐng)選出一項(xiàng)最切合題目要求的。在下邊的C語(yǔ)言程序段中，加法操作的時(shí)間復(fù)雜度為（）。Inti,j,k,sum=0;For(i=0;i<n;++i)For(j=0;j<i*i;++j)Sum++;A．Ο(2n2)B．Ο(2n3)C．Ο(n3)．Ο(n2)對(duì)于線性表的描繪正確的選項(xiàng)是（）。A．接見(jiàn)次序表中第k個(gè)元素的時(shí)間復(fù)雜度是Ο(N)B．接見(jiàn)單鏈表中第k個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度是Ο(N)C．把新數(shù)據(jù)插入到次序表中第k個(gè)地點(diǎn)的時(shí)間復(fù)雜度是Ο(1)D．把新數(shù)據(jù)插入到單鏈表中第k個(gè)地點(diǎn)的時(shí)間復(fù)雜度是Ο(1)對(duì)于行列描繪正確的選項(xiàng)是（）。A．用鏈表表示行列時(shí)，也不能夠插隊(duì)（插隊(duì)指在行列中間插入新數(shù)據(jù)）B．用環(huán)形數(shù)組表示行列時(shí)，能夠循環(huán)使用數(shù)組，因此行列永久不會(huì)滿C．用數(shù)組表示行列時(shí)，數(shù)據(jù)入隊(duì)的時(shí)間復(fù)雜度是Ο(N)D．用數(shù)組表示行列時(shí)，數(shù)據(jù)出隊(duì)的時(shí)間復(fù)雜度是Ο(N)對(duì)于棧描繪正確的選項(xiàng)是（）。數(shù)據(jù)出入棧的原則是“先入先出”用數(shù)組表示棧時(shí)，棧的操作速度要比用鏈表表示的棧操作快已知一顆完整二叉樹(shù)的第6層有7個(gè)結(jié)點(diǎn)，則該完整二叉樹(shù)總合有多少個(gè)結(jié)點(diǎn)?（）。對(duì)以下圖從A出發(fā)進(jìn)行廣度優(yōu)先遍歷，正確的選項(xiàng)是（）。A．ABECFDGHB．ADGHFCBEC．ABCDEFGHD．ADCBGHFE7.對(duì)下邊一個(gè)有向圖進(jìn)行拓?fù)渑判颍Y(jié)果正確的選項(xiàng)是（）。A．ABDECB.ABCDEC．ABDCED．ACEBD8.采納平方探測(cè)方法解決矛盾時(shí)，散列表的裝載因子一般應(yīng)低于（）。A．0.8B．0.7C．0.6D．0.5一個(gè)有序數(shù)據(jù)序列中有31個(gè)數(shù)據(jù)，采納二分查找法在此中查找一個(gè)數(shù)據(jù)，最多要比較幾次就能獲得查找結(jié)果（）。當(dāng)待排記錄序列已經(jīng)按重點(diǎn)字次序有序時(shí)，再使用以下算法，其時(shí)間復(fù)雜度最小的是（）。11.以下圖所示這棵樹(shù)的先序遍歷結(jié)果是（）。A．ABDCEF

B.ABCDEF

C.BDACEF

D.BDAECF對(duì)于散列表的表長(zhǎng)度，正確的選項(xiàng)是( )。表長(zhǎng)度一定大于數(shù)據(jù)個(gè)數(shù)的兩倍，且一定是素?cái)?shù)數(shù)據(jù)個(gè)數(shù)的兩倍即可C.數(shù)據(jù)個(gè)數(shù)的10倍D.采納分別鏈接法時(shí)，只需稍大于數(shù)據(jù)個(gè)數(shù)即可，且一定是素?cái)?shù)13.在有31個(gè)節(jié)點(diǎn)的二叉排序樹(shù)中查找一個(gè)數(shù)據(jù)，以下描繪正確的選項(xiàng)是（）。A.最多比較5次就能夠獲得結(jié)果B.可能比較31次才能獲得結(jié)果C.最多比較6次就能夠獲得結(jié)果D.一定比較30次才能獲得結(jié)果若數(shù)據(jù)序列4,5,3,9,6,1,2是采納以下方法之一獲得的第一趟排序后的結(jié)果，則該排序算法是（）。A．冒泡排序B．直接插入排序C．迅速排序D．合并排序15.對(duì)數(shù)據(jù)7，3，9，2，5進(jìn)行排序時(shí)，第一趟的排序結(jié)果以下：

3,7,2,5,9

；則采納的排序算法是（）。A．冒泡排序B．直接插入排序C．迅速排序D．合并排序16.把數(shù)據(jù)1，2，3，4，5，6，7經(jīng)過(guò)插入操作結(jié)構(gòu)一棵AVL樹(shù)時(shí)，以下描繪正確的選項(xiàng)是（）A．依據(jù)1，2，3，4，5，6，7的插入次序結(jié)構(gòu)的AVL樹(shù)的查找效率最高B．依據(jù)7，6，5，4，3，2，1的插入次序結(jié)構(gòu)的AVL樹(shù)的查找效率最高

。已知一個(gè)數(shù)據(jù)序列中有15個(gè)數(shù)據(jù)，且其已經(jīng)有序擺列，若采納最快的查找算法和必需的儲(chǔ)存結(jié)構(gòu)，在該序列中要查找一個(gè)數(shù)據(jù)元素，則均勻比較次數(shù)最少要多少次（）。分別采納線性表、二叉查找樹(shù)、AVL樹(shù)、散列表儲(chǔ)存數(shù)據(jù)并進(jìn)行查找，以下說(shuō)法正確的選項(xiàng)是（）。線性表的查找速度最慢散列表的查找速度最快一棵滿二叉樹(shù)共有3層（樹(shù)根為第一層），則葉子節(jié)點(diǎn)個(gè)數(shù)為（）。20.若要進(jìn)行大數(shù)據(jù)（比方：十進(jìn)制數(shù)的位數(shù)超出20）之間的數(shù)學(xué)運(yùn)算，采納的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（）。A．圖B.二叉樹(shù)C.鏈表D.會(huì)合21．以下哪一種特征不是操作系統(tǒng)的基本特征？( )A．虛構(gòu)性B.并行性C.異步性D.共享性設(shè)置目前工作目錄的主要目的是（）。23.進(jìn)度從堵塞狀態(tài)進(jìn)入就緒狀態(tài)的原由可能是( )在可變式分劃分派方案中，某一作業(yè)達(dá)成后，系統(tǒng)回收其主存空間，并與相鄰安閑區(qū)合并，為此需改正安閑區(qū)表，造成安閑區(qū)數(shù)目無(wú)變化的狀況是( )無(wú)上鄰安閑區(qū)，也無(wú)下鄰安閑區(qū)有上鄰安閑區(qū)，也有下鄰安閑區(qū)假定某一機(jī)器的內(nèi)存有4G,硬盤(pán)為500G,請(qǐng)問(wèn)使用虛構(gòu)內(nèi)存技術(shù)后，其虛構(gòu)內(nèi)容的容量為（）在基安分頁(yè)儲(chǔ)存管理中，邏輯地點(diǎn)變換為物理地點(diǎn)時(shí)，若頁(yè)號(hào)超出頁(yè)表長(zhǎng)度，則會(huì)惹起( )。對(duì)于某個(gè)進(jìn)度而言，其運(yùn)轉(zhuǎn)的場(chǎng)所一定在( )中。A.內(nèi)存B.硬盤(pán)C.SWAPING互換區(qū)D.輸入井或輸出井成組鏈接法可用于( )A.磁盤(pán)安閑盤(pán)塊的組織B.磁盤(pán)的驅(qū)動(dòng)調(diào)動(dòng)C.文件目錄的查找D.懇求分頁(yè)虛構(gòu)管理中的頁(yè)面調(diào)動(dòng)以下算法頂用于磁盤(pán)調(diào)動(dòng)的是( )A.優(yōu)先級(jí)高者優(yōu)先算法B.FIFO算法在I/O設(shè)施管理中，通道是一種（）。假定磁頭目前位于100道，正在向磁道序號(hào)增添的方向挪動(dòng)?，F(xiàn)有一個(gè)磁道接見(jiàn)懇求序列為35，45，12，68，110，180，170，195，采納先來(lái)先服務(wù)調(diào)動(dòng)（FCFS）算法獲得的磁道接見(jiàn)序列是（）。A.110,170,180,195,68,45,35,12B.35,45,12,68,110,180,170,195C.110,170,180,195,12,35,45,68D.12,35,45,68,110,170,180,19532.在文件索引分派時(shí)，如有一文件的索引塊以以下圖所示：請(qǐng)問(wèn)，儲(chǔ)存該索引文件總合需占用磁盤(pán)多大（幾塊）（）？33.在基安分頁(yè)儲(chǔ)存管理中，若采納最正確頁(yè)面置換算法OPT，則當(dāng)進(jìn)度分派到的物理塊數(shù)目增添時(shí)，缺頁(yè)中止的次數(shù)（）可能減少或不變必定減少基安分段內(nèi)存管理系統(tǒng)中，接見(jiàn)一條指令需要幾次接見(jiàn)內(nèi)存（）？35.某鑒于動(dòng)向分區(qū)儲(chǔ)存管理的計(jì)算機(jī)，假定其主存容量為配（BestFit）算法，分派和開(kāi)釋內(nèi)存的次序?yàn)椋悍峙煞峙?MB,此時(shí)主存中最大安閑區(qū)的大小是( )。

55MB(初始為安閑15MB,分派30MB,開(kāi)釋

)，采納最正確適15MB,分派8MB,36.某計(jì)算機(jī)系統(tǒng)中有K臺(tái)打印機(jī)，由能達(dá)成任務(wù)。該系統(tǒng)不行能發(fā)存亡鎖時(shí)，

4個(gè)進(jìn)度競(jìng)爭(zhēng)使用，每個(gè)進(jìn)度最多需要K的最小值是（）。

3臺(tái)打印機(jī)才采納SPOOLing技術(shù)的主要目的是（）。A.把獨(dú)占設(shè)施改造成共享設(shè)施，提升I/O速度B.提升CPU主機(jī)效率C.減少用戶編程負(fù)擔(dān)D.提升程序的運(yùn)轉(zhuǎn)速度38．考慮以下頁(yè)表結(jié)構(gòu)：假定頁(yè)的大小為512字節(jié)（即頁(yè)內(nèi)陸點(diǎn)長(zhǎng)度為9位），請(qǐng)把以下以十六進(jìn)制表示的邏輯地點(diǎn)0x567，經(jīng)過(guò)頁(yè)表變換為物理地點(diǎn)（也用十六進(jìn)制表示）是（）。A.0x3417B.地點(diǎn)變換錯(cuò)誤以下不是設(shè)施分派算法的是（）A.先來(lái)先服務(wù)B.短作業(yè)優(yōu)先C.優(yōu)先級(jí)高的優(yōu)先D.ABC選項(xiàng)都是對(duì)兩個(gè)并發(fā)進(jìn)度，其互斥信號(hào)量為mutex；初值為1，若mutex＝0，則表示（）。A．沒(méi)有進(jìn)度進(jìn)入臨界區(qū)B．有一個(gè)進(jìn)度進(jìn)入臨界區(qū)但沒(méi)有進(jìn)度處于堵塞狀態(tài)C．一個(gè)進(jìn)度進(jìn)入臨界區(qū)而另一個(gè)進(jìn)度正處于堵塞狀態(tài)D．有兩個(gè)進(jìn)度進(jìn)入臨界區(qū)二、綜合應(yīng)用題：41～45小題，共70分。（25分）帶有頭、尾節(jié)點(diǎn)的雙向鏈表，其節(jié)點(diǎn)結(jié)構(gòu)為prev

data

next請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法對(duì)兩個(gè)有序鏈表進(jìn)行合并，

合并結(jié)果仍舊要保擁有序。

比如：假定有序鏈表L1,以以下圖所示有序鏈表L2以以下圖所示：合并后結(jié)果鏈表L3為：要求：（1）請(qǐng)描繪算法的基本設(shè)計(jì)思想（5分）（2）用偽代碼描繪算法的詳盡實(shí)現(xiàn)步驟（5分）（3）請(qǐng)采納某一程序設(shè)計(jì)語(yǔ)言寫(xiě)一個(gè)函數(shù)，其功能是：在雙向鏈表尾部插入新節(jié)點(diǎn)。（5分）（4）依據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采納某一程序設(shè)計(jì)語(yǔ)言描繪算法（可C、C++、Java），關(guān)鍵之處請(qǐng)給出簡(jiǎn)要說(shuō)明。（5分）（5）請(qǐng)采納某一程序設(shè)計(jì)語(yǔ)言寫(xiě)一個(gè)函數(shù)，其功能是：在雙向鏈表頭部刪除節(jié)點(diǎn)。（5分）（15分）把7個(gè)字母ABCDEFG，挨次插入到樹(shù)上，請(qǐng)：（1）結(jié)構(gòu)一棵AVL樹(shù)，要求：每插入一個(gè)字母，畫(huà)一棵AVL樹(shù)，共7棵（7分）（2）結(jié)構(gòu)一棵二叉查找樹(shù)，要求：畫(huà)出最后的這棵樹(shù)（4分）（3）剖析這棵二叉查找樹(shù)與AVL樹(shù)的差別（4分）43.(10分)在銀專(zhuān)家算法中，若出現(xiàn)下述資源分派狀況(5個(gè)進(jìn)度，4類(lèi)資源)：processMax(最大需求)Allocation（已分派）Available（系統(tǒng)資源）試問(wèn)：（1）該狀態(tài)能否安全？假如，請(qǐng)給出此中一個(gè)安全序列，若不是，也請(qǐng)說(shuō)明原由（此題要求對(duì)能否存在安全狀態(tài)，都要寫(xiě)出詳盡的推導(dǎo)過(guò)程）。(7分)2）若P3提出懇求Request(1，2，1,1)，系統(tǒng)可否將資源分派給它？為何？要求詳盡說(shuō)明你的原由。（3分）44.(10分)考慮下述頁(yè)面走向：2，3，1，4，2，3，5，2，3，1，4，5，當(dāng)內(nèi)存物理塊數(shù)目分別為3和4時(shí)，試問(wèn)FIFO（先進(jìn)先出）、LRU(近來(lái)最少使用)算法這兩種內(nèi)存置換算法的缺頁(yè)次數(shù)和置換次數(shù)分別是多少？最后，比較這兩種算法后，你有何發(fā)現(xiàn)？上述過(guò)程