電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)歷年考研真題及詳解附答案

電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)

基礎(chǔ)歷年考研真題及詳解邵THROUGHTRFUN最新資料，WORD格式，可編輯修改!2014年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題 錯(cuò)誤!未定義書(shū)簽。TOC\o"1-5"\h\z2013年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題 82013年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題及詳解 162012年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題 252012年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題及詳解 312011年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題及詳解 402010年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題及詳解 522008年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題及詳解 642007年電子科技大學(xué)413計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題及詳解 752006年電子科技大學(xué)413計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題及詳解 842005年電子科技大學(xué)計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題及詳解 922003年電子科技大學(xué)429計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題 104說(shuō)明：電子科技大學(xué)計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)專(zhuān)業(yè)的科目代碼2003年是429,2005年不詳，2006年改為413,2008年改為820.電子科技大學(xué)信息與軟件工程學(xué)院、計(jì)算機(jī)科學(xué)與工程學(xué)院、電子科學(xué)技術(shù)研究院、自動(dòng)化工程學(xué)院均考此科目。電子科技大學(xué)2014年攻讀碩士學(xué)位研究生入學(xué)考試試題考試科目：820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)注：所有答案必須寫(xiě)在答題紙上，寫(xiě)在試卷或草稿紙上均無(wú)效.《計(jì)算機(jī)操作系統(tǒng)》一、填空題（10分，每空2分）1.現(xiàn)有3個(gè)同時(shí)到達(dá)的作業(yè)J1、J2和J3,它們的執(zhí)行時(shí)間分別為T(mén)l、T2和T3,且T1<T3<T2。若這三個(gè)作業(yè)在同一臺(tái)處理器上以單道方式運(yùn)行，則平均周轉(zhuǎn)時(shí)間最小的執(zhí)行順序是?.看二個(gè)信號(hào)量的初值是5,經(jīng)過(guò)多次P、V操作以后，其值變?yōu)?3,則此時(shí)等待進(jìn)入臨界區(qū)的進(jìn)程數(shù)目是—..某基本分頁(yè)存儲(chǔ)管理系統(tǒng)具有快表，內(nèi)存訪問(wèn)時(shí)間為2M5,檢索快表的時(shí)間為0.5若快表的命中率為80%,且忽略快表更新時(shí)間，則有效訪問(wèn)時(shí)間是—.在段頁(yè)式存儲(chǔ)管理系統(tǒng)中，若不考慮快表，為獲得一條指令或數(shù)據(jù)，至少需要訪問(wèn)次內(nèi)存。.某虛擬存儲(chǔ)器中的用戶空間共有32個(gè)頁(yè)面，每頁(yè)1KB,主存16KB。假設(shè)某時(shí)刻系統(tǒng)為用戶的第0、1、2、3頁(yè)分別分配的物理塊為5、10、4、7,則虛擬地址0A6F對(duì)應(yīng)的物理地址是（請(qǐng)使用十六進(jìn)制表示）.二、選擇題（14分，每題2分）.現(xiàn)代操作系統(tǒng)中最基本的兩個(gè)特征是（）.A.共享和不確定 B.并發(fā)和虛擬C.并發(fā)和共享 D.虛擬和不確定.引入多道程序技術(shù)的前提條件之一是系統(tǒng)具有（）.A.分時(shí)功能 B.中斷功能C.多CPU技術(shù) D. SPOOLing技術(shù).操作系統(tǒng)是根據(jù)（）來(lái)時(shí)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的.A.進(jìn)程的基本狀態(tài) B.進(jìn)程調(diào)度第法C.進(jìn)程的優(yōu)先級(jí) D.進(jìn)程控制塊.在段頁(yè)式存儲(chǔ)管理系統(tǒng)中，地址映射表是（）A.每個(gè)進(jìn)程一張段表，一張頁(yè)表.B.每個(gè)進(jìn)程一張段表，每個(gè)段?張頁(yè)表.C.每個(gè)進(jìn)程的每個(gè)段一張段表，一張頁(yè)表。D.每個(gè)進(jìn)程的每個(gè)段?張段去,多張頁(yè)表。.為使虛擬存儲(chǔ)管理系統(tǒng)具有良好的性能，應(yīng)用程序應(yīng)具備的特征是（）.A.程序模塊化程度高，由許多小模塊組成B.程序應(yīng)具備良好的局部性特征C.程序的I/O操作較少D.程序?qū)嶋H大小應(yīng)小于實(shí)際物理內(nèi)存容M：.（ ）的基本含義是指應(yīng)用程序獨(dú)立于具體使用的物理設(shè)備A.設(shè)備獨(dú)立性 B.設(shè)備共享性C.可擴(kuò)展性 D. SPOOLing技術(shù).從用戶的角度看，文件系統(tǒng)主要是實(shí)現(xiàn)（ ）A.數(shù)據(jù)存儲(chǔ) B.數(shù)據(jù)保護(hù)C.數(shù)據(jù)共享 D.按名存取三、分析計(jì)算題（30分）.某操作系統(tǒng)的文件系統(tǒng)采用混合索引分配方式，索引節(jié)點(diǎn)中包含文件的物理結(jié)構(gòu)數(shù)組iaddr[10]o其中前7項(xiàng)iaddr[0卜iaddr[6]為直接地址，iaddr[7]~iaddr[8]為?次間接地址，iaddr[9]為二次間接地址。系統(tǒng)盤(pán)塊的大小為4KB,磁盤(pán)的每個(gè)扇區(qū)大小也為4KB。描述磁盤(pán)塊的數(shù)據(jù)項(xiàng)需要4個(gè)字節(jié)，其中1個(gè)字節(jié)標(biāo)示磁盤(pán)分區(qū)，3個(gè)字節(jié)標(biāo)示物理塊。請(qǐng)回答一下問(wèn)題：（I）該文件系統(tǒng)支持的單個(gè)文件的最大程度是多少？（8分）（2）若某文件A的索引節(jié)點(diǎn)信息已位于內(nèi)存，但其它信息均在磁盤(pán)。現(xiàn)在需要訪問(wèn)文件A中第i個(gè)字節(jié)的數(shù)據(jù)，列舉出所有可能的磁盤(pán)訪問(wèn)次數(shù)，并說(shuō)明原因。（6分）.3個(gè)進(jìn)程P0、Pl、P2互斥使用一個(gè)僅包含1個(gè)單元的緩沖區(qū)。P0每次用produce（件成1個(gè)正整數(shù)，并用put。送入緩沖區(qū)。對(duì)于緩沖區(qū)中的每個(gè)數(shù)據(jù)，P1用get1（）取出一次并用compute1（）計(jì)算其平方值,P2用get2（）取出一次并用compute2（）計(jì)算其立方值.請(qǐng)用信號(hào)依機(jī)制實(shí)現(xiàn)進(jìn)程P0、Pl>P2之間的同步與互斥關(guān)系，并說(shuō)明所定義信號(hào)般的含義，要求用偽代碼描述.（16分）四、簡(jiǎn)答題（21分）.在存儲(chǔ)器管理中，什么是重定位？為什么要引入重定位技術(shù)？（5分）.在分頁(yè)存儲(chǔ)管理系統(tǒng)中，頁(yè)表的主要作用是什么？現(xiàn)代大多數(shù)計(jì)修機(jī)系統(tǒng)都支持非常大的邏輯地址空間（2”~2"），這給頁(yè)衣設(shè)計(jì)帶來(lái)了什么樣的新問(wèn)題，應(yīng)如何解決。（5分）.以從I/O設(shè)備讀入數(shù)據(jù)為例，請(qǐng)用流程圖方式說(shuō)明程序I/O、DMA傳輸控制的處理過(guò)程。（6分）.在哲學(xué)家就餐問(wèn)題中，如果將先拿起左邊筷子的哲學(xué)家成為左撇子，而將先拿起右邊筷子的哲學(xué)家稱(chēng)為右撇戶.在同時(shí)存在左撇子和右撇子的前提下，我們安排哲學(xué)家隨意就座.請(qǐng)問(wèn)是否可能產(chǎn)生死鎖，為什么？（5分）《數(shù)據(jù)結(jié)構(gòu)》一、填空題（共10分，每空1分）.一個(gè)“好”的算法應(yīng)考慮達(dá)到以下目標(biāo)：正確性、可讀性、健壯性、..廣義表（（），3），（!）,（（：,（1）/））的深度是。.遍歷二叉樹(shù)實(shí)質(zhì)上是對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)行操作。.對(duì)有n個(gè)頂點(diǎn)、e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法復(fù)雜度是..若一個(gè)具有n個(gè)頂點(diǎn)，e條邊的無(wú)向圖是一個(gè)森林，則該森林中必有棵樹(shù)。.求圖的最小生成樹(shù)有兩種克法，克法適合于求邊稀疏的圖的最小生成樹(shù)。.最短路徑迪杰斯特拉（Dijkstra）律法的復(fù)雜度..二叉樹(shù)上有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于.則該二叉樹(shù)就是不平衡的。.哈希表的地址區(qū)間為0-8,哈希函數(shù)為H（K）=Kmod9。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列（12,21,43,5,39）依次存儲(chǔ)到哈希表中，則元素39存放在哈希表中的地址是..排序律法不需要進(jìn)行記錄關(guān)鍵字間的比較。二、單選題（共2。分，每題2分）.某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表TOC\o"1-5"\h\z.下述哪一條是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（ ）A.存儲(chǔ)密度大B.插入、刪除運(yùn)算方便C.存儲(chǔ)單元連續(xù)D.隨機(jī)存取第i個(gè)元索方便.一個(gè)棧的輸入序列為12345,則下列序列中不可能是棧的輸出序列的是（ ）。A.23415B.54132C,23145D.15432.最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear,隊(duì)頭是front,則隊(duì)滿的條件是（ ）。A.（rear+1）MODn=front B.rear:frontC.rear+1=front D.（rear-1）MODn=front.若一棵二叉樹(shù)具有20個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（）A.10 B.11 C.21D.30.二叉樹(shù)的第i層上最多有（ ）結(jié)點(diǎn)。A.2' B.2"'-1 C.2'-1 D.2"1一棵小空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)?定是（ ）A.完全二叉樹(shù)B.只有一個(gè)節(jié)點(diǎn)C.高度等于其節(jié)點(diǎn)數(shù)D.二叉排序樹(shù).對(duì)圖進(jìn)行廣度優(yōu)先搜索遍歷類(lèi)似尸二叉樹(shù)的（ ）丸法.A.先序遍歷B,中序遍歷C.后序遍歷D.層次遍歷.對(duì)下圖進(jìn)行拓?fù)渑判?，可以得到不同拓?fù)湫蛄械膫€(gè)數(shù)是（A.6B.5C.4D.310.有一組數(shù)據(jù)(43,21,52,60,12,15)利用快速排序，以第一個(gè)元素為基準(zhǔn)得到一次劃分結(jié)果為( ).A.(15,21,12,43,52,60) 8.(15,12,21,43,52,60)C.(12,15,21,43,60,52) 0.(15,21,12,43,60,52)三、簡(jiǎn)答題（30分，每題6分）1.2.3.畫(huà)出算術(shù)表達(dá)式（2+1＞）*（0（1）-（6”+9）1.2.3.若通信系統(tǒng)中只可能出現(xiàn)5種字符A、B、C.D和E其概率分別為0.12、0.15、0.19、0.21和0.33,（1）試設(shè)計(jì)赫夫曼編碼：（2）畫(huà)出相應(yīng)的赫夫夏樹(shù)。給出下圖G的（1）鄰接表表示圖：（2）并根據(jù)畫(huà)出的鄰接表，以頂點(diǎn)1為根，畫(huà)出深度優(yōu)先生成樹(shù)。.輸入一個(gè)正整數(shù)序列（45,14,11,52,63,32,56,24）,（1）按此次序構(gòu)造一顆二叉排序樹(shù)：（2）如果刪除52,畫(huà)出刪除后的二叉樹(shù)結(jié)構(gòu)。.堆排序的基本思想是什么？其優(yōu)點(diǎn)是什么？四、算法題（15分，共2題）1.設(shè)計(jì)一個(gè)算法，逆序單鏈表中的數(shù)據(jù)。（5分）2,采用二叉鏈友的存儲(chǔ)結(jié)構(gòu)，分別寫(xiě)出統(tǒng)計(jì)二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)和樹(shù)高的函數(shù)，并分別分析時(shí)間復(fù)雜度。（10分）2013年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題考試科目：820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)注：所有答案必須寫(xiě)在答題紙上，寫(xiě)在試卷或草稿紙上均無(wú)效?！队?jì)算機(jī)操作系統(tǒng)》一、填空題（10分，每空2分）.文件目錄是的有序集合..某計(jì)算機(jī)系統(tǒng)中有11臺(tái)打印機(jī)，由k個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程最多需要4臺(tái)打印機(jī)*該系統(tǒng)可能會(huì)發(fā)生死鎖的k的最小值是一..一個(gè)簡(jiǎn)單分段存儲(chǔ)管理系統(tǒng)中，地址長(zhǎng)度為32位，其中段號(hào)占12位，則最大段長(zhǎng)是一字節(jié)..操作系統(tǒng)提供給應(yīng)用程序的接口是...現(xiàn)代操作系統(tǒng)實(shí)現(xiàn)了設(shè)備無(wú)關(guān)性，應(yīng)用程序使用來(lái)請(qǐng)求使用某類(lèi)設(shè)備.二、選擇題（14分，每題2分）.進(jìn)程調(diào)度時(shí)，下列進(jìn)程狀態(tài)的變化過(guò)程哪一項(xiàng)是不可能發(fā)生的？（）A.阻塞掛起-＞阻塞 B.就緒掛起-＞就緒C.就緒掛起-〉阻塞掛起 D.阻塞掛起-＞就緒掛起.關(guān)于線程和進(jìn)程，下面說(shuō)法正確的是（）A.終止一個(gè)進(jìn)程比終止一個(gè)線程花費(fèi)的時(shí)間少.B.進(jìn)程切換比同一進(jìn)程內(nèi)部的線程切換花費(fèi)的時(shí)間少..C.線程提高了不同執(zhí)行程序間的通信效率。D.進(jìn)程和線程都是資源分配和調(diào)度的基本單位..下列事件最可能導(dǎo)致系統(tǒng)產(chǎn)生死鎖的是（）.A.進(jìn)程釋放資源 B.一?個(gè)進(jìn)程進(jìn)入死循環(huán) ?C.多個(gè)進(jìn)程競(jìng)爭(zhēng)獨(dú)占資源 D.多個(gè)進(jìn)程競(jìng)爭(zhēng)共享資源.關(guān)于子進(jìn)程和父進(jìn)程的說(shuō)法，下面哪一個(gè)是正確的？（）A.一個(gè)父進(jìn)程可以創(chuàng)建若干個(gè)子進(jìn)程，一個(gè)子進(jìn)程可以從屬于若干個(gè)父進(jìn)程B.父進(jìn)程被撤銷(xiāo)時(shí)，其所有子進(jìn)程也被相應(yīng)撤銷(xiāo)。 2013年—士研究生入學(xué)考試試題匯編3C.子進(jìn)程被撤銷(xiāo)時(shí)，其從屬的父進(jìn)程也被撤銷(xiāo).D.一個(gè)進(jìn)程可以沒(méi)有父進(jìn)程或子進(jìn)程..文件系統(tǒng)采用二級(jí)文件目錄可以（）.A.縮短訪問(wèn)存儲(chǔ)器的時(shí)間 B.實(shí)現(xiàn)文件共享C.節(jié)省內(nèi)存空間 D.解決不同用戶間的文件命名沖突.一種既有利于短小作業(yè)又兼顧到長(zhǎng)作業(yè)的作業(yè)調(diào)度算法是（ ）A.先來(lái)先服務(wù) B.輪轉(zhuǎn)C.最高響應(yīng)比優(yōu)先 D.均衡調(diào)度.設(shè)計(jì)批處理多道系統(tǒng)時(shí)，首先要考慮的是（ ）.A.靈活性和可適應(yīng)性 B.系統(tǒng)效率和吞吐量C.交互性和響應(yīng)時(shí)間 D.實(shí)時(shí)性和可靠性三、分析計(jì)算題（30分）.考慮一個(gè)使用32位地址和1KB大小的頁(yè)的分頁(yè)虛擬內(nèi)存系統(tǒng).每個(gè)頁(yè)表項(xiàng)需要32位，限制頁(yè)表的大小為一個(gè)頁(yè)，請(qǐng)回答：（1）頁(yè)表一共需要幾級(jí)？（5分）（2）請(qǐng)?jiān)O(shè)計(jì)每一級(jí)的頁(yè)表大小,使得所需的頁(yè)數(shù)個(gè)數(shù)總和最小.（8分）.桌上有一空盤(pán)，允許存放最多兩個(gè)水果.爸爸可向盤(pán)中放蘋(píng)果或橘子，兒子專(zhuān)等吃盤(pán)中的橘子，女兒專(zhuān)等吃盤(pán)中的蘋(píng)果。規(guī)定當(dāng)盤(pán)子不滿時(shí),一次只能放一只水果：當(dāng)盤(pán)子不空時(shí)，一次只能取一只水果：父親放水果時(shí)，兒子女兒不能?。簝鹤优畠喝∷麜r(shí)，父親不能放.（1）請(qǐng)分析，本例中臨界資源是什么？（1分）（2）下面是用P、V操作實(shí)現(xiàn)的爸爸、兒子、女兒三個(gè)進(jìn)程的同步，請(qǐng)完成程序中的空行部分.（每空1分） *Semaphoremutex= ;〃定義互斥信號(hào)量intempty二,apple=,orange= ;〃定義同步信號(hào)量Father:〃父親進(jìn)程While（l）（Putanappleororange;If(fruit=apple)ElseDaughter:〃女兒進(jìn)程While(l){Fetchariapple;}Son:〃兒子進(jìn)程While(l){Fetchanorange;）四、簡(jiǎn)答題C21分）.操作系統(tǒng)中什么是虛擬存儲(chǔ)器？為什么要引入虛擬存儲(chǔ)技術(shù)？（5分）.考慮文件系統(tǒng)的外存分配，簡(jiǎn)述什么是連續(xù)分配方式和索引分配方式.（5分）.什么是DMA方式？它與中斷方式的主要區(qū)別是什么？（6分）.簡(jiǎn)述利用位示圖進(jìn)行文件存儲(chǔ)空間管理的思想.這種方法的優(yōu)缺點(diǎn)是什么？（5分）《數(shù)據(jù)結(jié)構(gòu)》一、填空題（共10分，每空1分）.一顆有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，葉子結(jié)點(diǎn)的數(shù)量為n0,度為2的結(jié)點(diǎn)數(shù)量為n2,則n0與n2的關(guān)系是：如果用二叉鏈表存儲(chǔ)該二叉樹(shù)，則空指針數(shù)量為..一個(gè)有向圖的鄰接表和逆鄰接表中結(jié)點(diǎn)的個(gè)數(shù)..將101,186,16,163,752,334,61等7個(gè)數(shù)據(jù)存入長(zhǎng)度為10的線性施.哈希函數(shù)h（K）=K%7,解決沖突策略為線性探測(cè)再散列，則采用存儲(chǔ)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，其中163存儲(chǔ)在哈希表的第個(gè)位置（H（k）=O為第1個(gè)位置）..輸入n個(gè)數(shù)據(jù)，2路歸并排序的時(shí)間復(fù)雜度為..無(wú)向圖G=（V,E）,有n個(gè)頂點(diǎn)，e條邊，則鄰接矩陣有個(gè)0元素，其鄰接矩陣

是對(duì)稱(chēng)矩陣，只需用空間可實(shí)現(xiàn)壓縮存儲(chǔ)..對(duì)二叉排序樹(shù)可以得到線性有序序列..一個(gè)有向無(wú)環(huán)圖的拓?fù)渑判蛘伭惺俏ㄒ坏?二、單選題（共20分，每題2分）.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類(lèi).A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu) -D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu).以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)TOC\o"1-5"\h\z.A.樹(shù)B.字符串C.隊(duì) D.棧.設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用（）最節(jié)省時(shí)間.A.單鏈表B.單循環(huán)卷表 C.帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表.對(duì)于血序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）.A.0（n）0（n）B.0（n）0（1）C.0（1）0（n）D.0（1）0（1）.對(duì)于隊(duì)列操作數(shù)據(jù)的原則是（ ）.A.先進(jìn)先出 B.后進(jìn)先出 C.先進(jìn)后出 D.不分順序.要保證連通具有10個(gè)頂點(diǎn)的無(wú)向圖，至少需要（ ）條邊.A.9 B.90 C. 37 D. 45.設(shè)棧的初始狀態(tài)為空，當(dāng)字符序列a3一作為棧的輸入時(shí)，輸出長(zhǎng)度為3的且可以用作C語(yǔ)言標(biāo)識(shí)符的字符序列有（ ）個(gè)A.4 B.6 C.3 D.5.完全二叉樹(shù)采用（ ）存儲(chǔ)結(jié)構(gòu)，滿足存儲(chǔ)空間少，方便的查找任意結(jié)點(diǎn)的雙親與孩子.A.順序 B.單鏈表 C.二叉鏈表 D.三叉鏈表.下面（ ）數(shù)據(jù)結(jié)構(gòu)常用于函數(shù)調(diào)用.A.隊(duì)列 B.棧 C.鏈表 D.數(shù)組.下面（ ）排序算法在輸入數(shù)據(jù)逆序情況下排序速度最快.A.歸并排序B.直接插入排序C.冒泡排序D.簡(jiǎn)單選擇排序~三、簡(jiǎn)答題（共30分,共5題）.已知4個(gè)字符A,B,C,D的宦夫曼編碼分別是1.01,000,001.下列01串是由以上4個(gè)字母構(gòu)成的一段文本的霍夫曼編碼：

1001000011011010011010011請(qǐng)將上述01串還原為編碼前的文本。以字符在文本中出現(xiàn)的次數(shù)為權(quán)值，求出這棵樹(shù)的帶權(quán)路徑長(zhǎng)度.（共5分）.輸入元素序列32,18.63,5,1,11,44,33,78,請(qǐng)構(gòu)造AVL樹(shù).假設(shè)所有元素的查找概率相等，請(qǐng)分別求出這棵AVL樹(shù)的查找成功的平均查找長(zhǎng)度ASL（成功）與失敗的平均查找長(zhǎng)度ASL（失?。?（共5分）.海量數(shù)據(jù)分布在100臺(tái)電腦中,想個(gè)辦法高效統(tǒng)計(jì)出所有數(shù)據(jù)的前10個(gè)最大關(guān)鍵字?jǐn)?shù)據(jù)，并分析時(shí)間發(fā)雜度（共6分）..若輸入數(shù)據(jù)存儲(chǔ)在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，下面各種排序算法是否仍然適用？為什么？（共6分）（1）快速排序（2）直接插入排序（3）簡(jiǎn)單選擇排序（4）堆摔序.已知某工程各工序之間的優(yōu)先關(guān)系和各工序所需的時(shí)間（其中“一”表示無(wú)先驅(qū)工序,如下表所示.請(qǐng)根據(jù)工序表畫(huà)出對(duì)應(yīng)的A0E圖，并指明完成該工程所需的最短時(shí)間和關(guān)鍵路徑.（共8分）工序代號(hào)ABCDEFGHI所需時(shí)間351466732先驅(qū)工序—AAABBDG四、算法題（共15分，共2題）.線性表（al,a2,…,an）中元素遞增有序且按順序存儲(chǔ)于計(jì)算機(jī)內(nèi)的數(shù)組a中.要求設(shè)計(jì)一算法用函數(shù)實(shí)現(xiàn)下列功能：（共10分） -（1）用最少時(shí)間在表中查找值為x的元素：（2）若找到則將其與直接后繼元素交換：（3）若找不到則將其插入表中使其表中元素仍然遞增有序.假設(shè)Header指向如下循環(huán)單鏈表，請(qǐng)問(wèn)執(zhí)行下列2個(gè)程序段后各自的輸出結(jié)果是什么？（共5分）Header

單鏈表結(jié)點(diǎn)定義如F：typedefstructnode(intdata;structnode*next;}Node,*ptr,?List;〃第一個(gè)程序段ptrp=Header;for(inti=0;i<5;iH)(printf("%d”,p->data);p=p->next;p=p->next：)〃第二個(gè)程序段ptrp=Header;for(inti=0;i<5;iH)(printf("%d”,p->data);p=p->next;p=p->next;p=p->next：)第15頁(yè)2013年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題及詳解第16頁(yè)參考答案：820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)_ 《計(jì)算機(jī)操作系統(tǒng)》一、填空題.文件控制塊.4.220.系統(tǒng)調(diào)用.邏輯設(shè)備名稱(chēng)二、選擇題CCCDDCBr三、分析計(jì)算題（30分）.考慮一個(gè)使用32位地址和1KB大小的頁(yè)的分頁(yè)虛擬內(nèi)存系統(tǒng)，每個(gè)頁(yè)表項(xiàng)需要32位，限制頁(yè)表的大小為一個(gè)頁(yè)，請(qǐng)回答；（1）答：由于頁(yè)面大小占用lObit,還剩22bit,即有24個(gè)頁(yè)表項(xiàng).一個(gè)頁(yè)表項(xiàng)32bit,即占用4個(gè)字節(jié)，一頁(yè)最多含2K74-28個(gè)頁(yè)表項(xiàng)，所以需要3級(jí)頁(yè)表.（5分）（2）答：若一線頁(yè)表長(zhǎng)度為6位，二級(jí)和三級(jí)頁(yè)表長(zhǎng)度各為8位，則需要的頁(yè)數(shù)總數(shù)為1+2'+2”=16449：若一級(jí)頁(yè)表長(zhǎng)度為8位，二級(jí)頁(yè)表長(zhǎng)度為6位，三級(jí)頁(yè)表長(zhǎng)度為8位，則總共需要頁(yè)數(shù)為：1+2,2“=16641：若一級(jí)頁(yè)表和二級(jí)頁(yè)表長(zhǎng)度分別為8位，三級(jí)頁(yè)表為6位，則總共需要1+2'+2愀=65793頁(yè).因此，三級(jí)頁(yè)表的長(zhǎng)度分別為6,8.8時(shí)，總頁(yè)數(shù)和最小.（9分） *2.每格一分，共16分（1）臨界資源是盤(pán)子（2）Semaphoremutcx=_1_;〃定義互斥信號(hào)量intempty=_2_,apple=_0_,orange=_0_;//定義同步信號(hào)量Father〃父架連程While（l）P(empty)_

P(mutex) ;Putanappleororange;If(fhiit=applc)_V(apple)_;Else_V(orange) ;)Daughter:〃女兒進(jìn)程While(l)(_P(apple)_; P(mutex) ;Fetchanapple;_V(mutex)_;_V(empty)_;)Son:〃兒子進(jìn)程WhUe(l){ P(orange)_; P(mutex) ;Fetchanorange; Wmutex) ; V(empty) ;)四、簡(jiǎn)答題（21分）.答：在具有層次結(jié)構(gòu)存儲(chǔ)器的計(jì)算機(jī)系統(tǒng)中，自動(dòng)實(shí)現(xiàn)部分裝入和部分替換功能，能從邏輯上為用戶提供一個(gè)比物理貯存容量大得多,可尋址的“主存儲(chǔ)器乙虛擬存儲(chǔ)區(qū)的容量與物理主存大小無(wú)關(guān)，而受隨于計(jì)算機(jī)的地址結(jié)構(gòu)和可用磁盤(pán)容量。.

計(jì)算機(jī)操作系統(tǒng)引入和使用虛擬存儲(chǔ)技術(shù)的主要目的是提高系統(tǒng)的內(nèi)存利用率和系統(tǒng)吞吐量（5分）.答：連續(xù)分配方式：在創(chuàng)建文件時(shí)需要給文件分配一組連續(xù)的盤(pán)塊。連續(xù)分配的優(yōu)點(diǎn)主要有兩個(gè)，分別是順序訪問(wèn)文件時(shí)比較容易，并且順序訪問(wèn)時(shí)速度快.缺點(diǎn)是要求有連續(xù)的存儲(chǔ)空間，并且隨著外存空間的分配和回收，會(huì)產(chǎn)生很多外存碎片.降低了外存空間的利用率.索引分配方式：為文件的每個(gè)分區(qū)單獨(dú)建立一張索引表。該索引表記錄了分配給該文件的所有的塊號(hào)。優(yōu)點(diǎn)：直接訪問(wèn)和順序訪問(wèn)的速度都比較快.缺點(diǎn)：存儲(chǔ)索引表花費(fèi)了較多外存空間.（5分）.答：DMA是直接存儲(chǔ)器存取.DMA傳輸將數(shù)據(jù)從一個(gè)地址空間復(fù)制到另外一個(gè)地址空間.當(dāng)CPU初始化這個(gè)傳輸動(dòng)作，傳輸動(dòng)作本身是由DMA控制器來(lái)實(shí)行和完成,在實(shí)現(xiàn)DMA傳輸時(shí)，是由DMA控制器直接掌管總線，因此，存在著一個(gè)總線控制權(quán)轉(zhuǎn)移問(wèn)題。即DMA傳輸前,CPU要把總線控制權(quán)交給DMA控制器，而在結(jié)束DMA傳輸后，DMA控制器應(yīng)立即把總線控制權(quán)再交回給CPU.它和中斷的主要區(qū)別在于，DMA只需要CPU在開(kāi)始和完成傳輸時(shí)進(jìn)行」干預(yù)，其他時(shí)候不需要CPU干預(yù).（6分） '.答：若磁盤(pán)塊空閑，則用1表示，否則用0表示.從而得到一張位式圖表，反映了所有磁盤(pán)塊的信息。其優(yōu)點(diǎn)在于很容易找到一個(gè)連續(xù)的空閑塊.缺點(diǎn)在于整個(gè)磁盤(pán)的位式圖文件比較大，另外，在磁盤(pán)空閑快較少時(shí)，搜索空閑塊要花費(fèi)一些時(shí)間.（5分）《數(shù)據(jù)結(jié)構(gòu)》一、填空題（共10分，每空1分）TOC\o"1-5"\h\z\o"CurrentDocument".n0=n2+l; n+1.相同（一樣）.順序； 6 ?.O（nlogn）.n'-2e ： n（n+l）/2.中序遍歷\o"CurrentDocument".不/不一定 ?二、單選題（共20分，每題2分）1-5.CADCA6-10.CCABA

三、簡(jiǎn)答題（共30分，共5題）.答：霍夫曼編碼是前綴編碼，滿足任意字符的編碼都不會(huì)是另外一個(gè)字符編碼的前綴,因此譯碼不會(huì)產(chǎn)生歧義.1001000011011010011010011還原出來(lái)的文本為：1001000011011010011010011TOC\o"1-5"\h\z\o"CurrentDocument"ADCBABABDABDA （2分）其中A出現(xiàn)5次，B出現(xiàn)4次，C出現(xiàn)I次,D出現(xiàn)3次， （2分）帶權(quán)路徑長(zhǎng)度為WPL=（l+3）*3+4*2+5=25 （1分）.答：AVL樹(shù)如下圖所示. （3分）ASL（成功）=（1+2*2+4*3+2*4）/9=25/9 （1分）ALS（失?。?（3*6*4*4）/10=34/10=3.4 （1分）.答：先分別求出每臺(tái)電腦的前10個(gè)最大關(guān)鍵字?jǐn)?shù)據(jù)，再根據(jù)這100臺(tái)電腦的最大前10個(gè)最大關(guān)鍵字?jǐn)?shù)據(jù)，共1000個(gè)數(shù)據(jù)求出前10大關(guān)鍵字?jǐn)?shù)據(jù)即可.具體分析如下：（1）先求出每臺(tái)電腦的前10大數(shù)據(jù),由于只需要求出部分?jǐn)?shù)據(jù)，因此不需要對(duì)n不數(shù)據(jù)全部排序，采用部分排序算法即可，比如簡(jiǎn)單選擇排序、堆排序、桶排序.。分）（2）求n個(gè)數(shù)據(jù)的前k（這里k=10）大數(shù)據(jù)，當(dāng)k?n時(shí)，最佳的方法是將后面的n-k個(gè)數(shù)據(jù)依次與前面的k個(gè)數(shù)據(jù)的最小直比較，如果比最小值逐小.則扔掉該數(shù)據(jù)，繼續(xù)比較下一個(gè)數(shù)據(jù)，否則扔掉更小的數(shù)據(jù)，把這個(gè)新數(shù)加入，直到余下的n-k個(gè)數(shù)據(jù)都處理完。由于每次需要與存儲(chǔ)的k個(gè)數(shù)據(jù)比較并可能刪除最小元素，加入新的元素，最好的結(jié)構(gòu)是小頂堆。即將前k個(gè)元素調(diào)整為小頂堆（時(shí)間復(fù)雜度為0（k】ogk）,余下元素依次與小頂堆根結(jié)點(diǎn)比較，比根結(jié)點(diǎn)小則扔掉，比根結(jié)點(diǎn)大則用當(dāng)前值替換根結(jié)點(diǎn)并調(diào)整為小頂堆,中劇復(fù)雜度為O（Iogk）.所以總的最壞時(shí)間復(fù)雜度為O（klogk）+0（（n-k）logk）=0（nlogk）（小頂堆1分，分析過(guò)程與時(shí)間復(fù)雜度分析共2分）（3）再?gòu)膍（這里m=100）臺(tái)電腦的共km（這里km=1000）個(gè)數(shù)據(jù)中選擇所有數(shù)據(jù)的最大k個(gè)，

采用(1)類(lèi)似的方法即可求出。即將一臺(tái)電腦的小頂堆作為初始小頂堆，余下mT臺(tái)電腦的母人k個(gè)元素依次與小頂堆的根結(jié)點(diǎn)元素比較，大于根結(jié)點(diǎn)則替換根結(jié)點(diǎn)元素并調(diào)整為小頂堆，宜到余下的數(shù)據(jù)都處理完成，時(shí)間爰雜度為。(加-Dklogk) (1分)(4)綜合上面3步，最終選擇小頂堆能夠最快統(tǒng)計(jì)出所有數(shù)據(jù)的前k(k=IO)個(gè)最大關(guān)鍵字?jǐn)?shù)據(jù),總的最壞時(shí)間復(fù):雜度為O(nlogk)+0((m-1)klogk)=0((n+mk-k)logk).如果k?km〈〈n,則T(n)=0(n)(l分).答：(1)快速排序適用(0.5分)，因?yàn)榭梢钥焖俣ㄎ坏降谝粋€(gè)元素與最后一個(gè)元素結(jié)點(diǎn)(0.5分)，然后通過(guò)1個(gè)指針從頭部向后移動(dòng)，另外一個(gè)指針從尾部向前移動(dòng)，逐一與樞紐進(jìn)行比較并能夠通過(guò)修改指針完成結(jié)點(diǎn)交換操作(0.5分)(2)插入排序適用(0.5分).因?yàn)榭梢苑奖愕恼仪摆吅缶S(0.5分)和通過(guò)修改指針完成結(jié)點(diǎn)交換操作(0.5分)(3)選擇排序適用(0.5分)，因?yàn)橹恍枰苿?dòng)指針遍歷鏈表(0.5分)并通過(guò)修改指針完成結(jié)點(diǎn)交換(0.5分)(4)堆排序不適用(0.5分),因?yàn)殡p向循環(huán)鏈表無(wú)法方便的找完全_叉樹(shù)的雙親與孩子結(jié)點(diǎn)(1分)》5.答：根據(jù)先序關(guān)系畫(huà)出AOE圖如下:(5.答：根據(jù)先序關(guān)系畫(huà)出AOE圖如下:(3分)V4VI則各個(gè)事件Vi(i=l,2,…,6)的最早開(kāi)始時(shí)間VE(i)和最晚開(kāi)始時(shí)間VL(i)如下嚷所示:事件iVIV2V3V4V5V6VE(i)03571214Vl(i)045111214

各個(gè)活動(dòng)的最早開(kāi)始時(shí)間ae(i)與最晚開(kāi)始時(shí)間al(i)如下表所示(3分):活動(dòng)iABCDEFGHIae(i)0033355712al(i)10478851112所以，完成該工程所需最短時(shí)間為14天.關(guān)鍵路徑有：B,G,I (2分)四、算法題(共15分，共2題)1.解：順序存儲(chǔ)的線性表遞增有序，可以順序查找也可以折半查找，題目要求“最少時(shí)間查找值為x的元素”，選用折半查找 (2分).算法如下：#definestatusintWefinetrue14definefalse0statusSearchExchangelnsert(ElemTypea[]>int*n,ElemTypex)(intlow=0,high=*n-l,mid,i;statuss=false;〃數(shù)組長(zhǎng)度檢查 (1分)if(low>high)returns：if(*n<=0)returns;〃折半查找 (2分)while(low<=high)(mid=(low+high)/2;if(a[mid]=x){break;)elseif(a[mid]<x) ?{low=mid+l;}elsehigh=mid-l;})〃查找成功if(low〈二high)(〃是否最后一個(gè)元素s=true;if(mid=*n-l)returns;〃不是最后一個(gè)元素，則與后繼交換a[mid]=a[niid+l]:a[midH]=x;)Rise〃查找失敗(for(i=*n-l;i>=low：i—)a[lov]=x;(*n)++;)returns;)2.答：(1)程序輸出結(jié)果為：13524(2)程序輸出結(jié)果為：14253(3分)（2分）（2分）（3分）-用ND貝第24頁(yè)2012年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題考試科目：820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)注：所有答案必須寫(xiě)在答題紙上，寫(xiě)在試卷或草稿紙上均無(wú)效?！队?jì)算機(jī)操作系統(tǒng)》單項(xiàng)選擇題（每小題2分，共14分）頁(yè)式存儲(chǔ)管理系統(tǒng)中的頁(yè)面大小是由（）決定的。A.用戶 B.系統(tǒng) C.系統(tǒng)和用戶 D.不確定下面哪一種表述不屬于操作系統(tǒng)的主要功能？（ ）A.處理機(jī)管理 B.存儲(chǔ)器管理C.設(shè)備管理和文件管理 D.可移植下面哪一種描述不是操作系統(tǒng)的主要目標(biāo)？（）A.有效性B.方便性C.可擴(kuò)充性 D.多路復(fù)用文件目錄是（）的有序集合。A、文件控制塊 B,文件信息C,文件名 D、文件屬性文件系統(tǒng)采用二級(jí)文件目錄可以（）A.縮短訪問(wèn)存儲(chǔ)器的時(shí)間 B.節(jié)省存儲(chǔ)空間C.節(jié)省內(nèi)存空間 D.解決不同用戶間的文件命名沖突在一段時(shí)間內(nèi)，只允許一個(gè)進(jìn)程訪問(wèn)的資源被稱(chēng)為（）A.共享資源B.臨界區(qū)C.臨界資源D.共享區(qū)在單處理器系統(tǒng)中，如果同時(shí)存在有12個(gè)進(jìn)程，則處于就緒隊(duì)列中的進(jìn)程數(shù)量最多為（）A.1 B.9C.10D.11二、填空限（每空2分，共10分）TOC\o"1-5"\h\z.根據(jù)對(duì)截止時(shí)間的要求不同，實(shí)時(shí)任務(wù)可以劃分為硬實(shí)時(shí)任務(wù)和（ ）..重定位是指程序的虛地址到（）的轉(zhuǎn)換，根據(jù)定位時(shí)機(jī)可一分為（ ）和（ ）兩種..文件的物理分配方法包括連續(xù)分配、鏈?zhǔn)椒峙浜停?）.三、簡(jiǎn)答題（共21分）1.什么是順序文件？試說(shuō)明順序文件的優(yōu)點(diǎn)和缺點(diǎn).（4分）2,闡述什么是SPOOLING技術(shù)。（4分）.什么是死鎖？如何預(yù)防死鎖？（4分）.闡述基本分頁(yè)存儲(chǔ)管理和請(qǐng)求分由存儲(chǔ)管理的異同之處.（5分）.闡述計(jì)豫機(jī)系統(tǒng)中緩沖的作用和分類(lèi)14分）四、計(jì)算踵（30分）.在請(qǐng)求式分頁(yè)管理系統(tǒng)中，某一作業(yè)有4個(gè)頁(yè)面，分別被裝入到內(nèi)存的3,4,6,8號(hào)頁(yè)框中，假設(shè)頁(yè)面和頁(yè)框的大小都為1024字節(jié)，當(dāng)該作業(yè)在CPU上運(yùn)行時(shí)，執(zhí)行到其地址空間

第500號(hào)處遇到一條傳送指令MOV22003100,請(qǐng)計(jì)算出MOV指令中兩個(gè)操作數(shù)的物理地址，并給出計(jì)算過(guò)程.（8分）.磁盤(pán)共有200個(gè)柱面，其編號(hào)為0T99,假定磁頭正停在99號(hào)柱面上訪問(wèn).現(xiàn)有一個(gè)請(qǐng)求隊(duì)列在等待訪問(wèn)柱面，該請(qǐng)求隊(duì)列訪問(wèn)的柱面號(hào)分別為：190、97、54、30、87.若采用FCFS（先來(lái)先服務(wù)）和SSTF（最短尋道時(shí)間優(yōu)先）的磁盤(pán)調(diào)度算法，請(qǐng)分別計(jì)算磁頭移動(dòng)的總磁道數(shù).（10分）.針對(duì)下面進(jìn)程集合，考慮兩種調(diào)度算法：先來(lái)先服務(wù)和最短進(jìn)程優(yōu)先.分別計(jì)算各個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間以及平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間.請(qǐng)完成下列兩個(gè)表格，并說(shuō)明哪種調(diào)度算法性能好？（12分）進(jìn)程名到達(dá)時(shí)間處理時(shí)間P103P215P332P484P5105先來(lái)先服務(wù):進(jìn)程到達(dá)時(shí)間處理時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間P103P215P332P484P5105最短進(jìn)程優(yōu)先:進(jìn)程到達(dá)時(shí)間處理時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間P103P215P332P484P5105《數(shù)據(jù)結(jié)構(gòu)》一、單項(xiàng)選擇題（20分,每題2分）：下面算法的時(shí)間復(fù)雜度是（）.for（i=n;i>l;i-）for（j=i-l;j>l：j~）x++：A.0（n） B.O（n'） C.0（n（n-D）D.O（nlogn）以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。A.圖B.字符串 C.數(shù)組 D.堆棧3、鏈表不具有的特點(diǎn)是（）.A.插入、刪除不需要移動(dòng)元素 B.不必事先估計(jì)存儲(chǔ)空間C.可隨機(jī)訪問(wèn)任一元素 D.所需空間與線性表長(zhǎng)度成正比一個(gè)枝的輸入序列為123…n,若輸出序列的第一個(gè)元素是n,輸出的第i（l<=i<=n）個(gè)元素是（）.A.不確定B.n-i C.i D.n-i+15、若一棵二叉樹(shù)具有12個(gè)度為2的結(jié)點(diǎn)，6個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（）.A.10B.11 C.13 D.不確定6、下列哪種算法使用了隊(duì)列作為輔助存儲(chǔ)結(jié)構(gòu)（）.A.二叉樹(shù)的先根序遍歷算法 B.二叉樹(shù)的層次遍歷算法C.圖的深度優(yōu)先遍歷算法 D.圖的拓?fù)渑判蛩惴?,以下哪種二叉樹(shù)左右子樹(shù)可以交換（）.A.二叉排序樹(shù) B.線索二叉樹(shù) C.平衡二叉樹(shù) D.哈夫曼樹(shù)8、下列哪種圖的鄰接矩陣是對(duì)稱(chēng)矩陣（）.A.有向圖 B.無(wú)向圖 C,AOV網(wǎng) D.AOE網(wǎng)9,在長(zhǎng)度為n的順序線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長(zhǎng)度（假定查找每個(gè)元素的概率均相等）為（）.A.n B.（n-I）/2 C.n/2 D.（n+l）/210.下列排序算法中，（）在某趟排序結(jié)束后不一定能選出一個(gè)元素放到其最終的位置上。A.選擇排序B.冒泡排序 C.希爾排序 D.堆排序二、填空題（10分，每空2分）：I,判定循環(huán)隊(duì)列的滿與空，有三種方法，它們是 ，和.2、一顆第5層有6個(gè)葉子節(jié)點(diǎn)的完全二叉樹(shù)，最多可能擁有的結(jié)點(diǎn)個(gè)數(shù)為.3,在無(wú)權(quán)的無(wú)向圖G的鄰接矩陣A中，若（v“v,）屬于圖G的邊集合，則對(duì)應(yīng)元素等于 ?三、簡(jiǎn)答題（30分）：試描述堆棧和遞歸的關(guān)系.（5分）2、已如二叉樹(shù)的中序遍歷序列為DEBAFCG,后序遍歷序列為EDBFGCA,試畫(huà)出該二叉樹(shù)（7分）3、給定25個(gè)字符組成的電文：(6分)DDDDAAABEEAAFCDAABCCCBADD試為字符A,B,C、D、E、F設(shè)計(jì)哈夫曼(Huffman)編碼。(1)畫(huà)出相應(yīng)的哈夫曼樹(shù)；(2)分別列出A、B、C,D、E、F的哈夫曼編碼；(3)計(jì)算該樹(shù)的帶權(quán)路徑長(zhǎng)度WPL.4、已知帶權(quán)圖G如圖所示，試用Prim算法構(gòu)造對(duì)應(yīng)的娘小生成樹(shù)，請(qǐng)給出構(gòu)造步驟.(7分)5,一個(gè)線性表為B=(14,23,43,52,20,35,79,31,17,36),設(shè)散列表為HT[0..20],散列函數(shù)為H(key)=key%11并用線性探測(cè)法解決沖突(增僦&=1,2…)，試寫(xiě)出散列表.(5分)四、算法設(shè)計(jì)題(15分)：如果以二叉鏈表做為存儲(chǔ)結(jié)構(gòu)，試用類(lèi)C語(yǔ)言編寫(xiě)統(tǒng)計(jì)二叉樹(shù)非葉子結(jié)點(diǎn)個(gè)數(shù)的層次遍歷算法.(15分)第30頁(yè)參考答案：820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)《計(jì)算機(jī)操作系統(tǒng)》選擇題l.B2,D 3.D 4.A5.D6.C 7.D填空題.軟實(shí)時(shí)任務(wù).物理地址，靜態(tài)重定位，動(dòng)態(tài)重定位.索引分配簡(jiǎn)答題順序文件是指由一系列記錄按照某種順序排列所形成的文件.順序文件的優(yōu)點(diǎn)在于當(dāng)需要對(duì)記錄進(jìn)行批量存取時(shí)，它的存取效率最高。其缺點(diǎn)在于當(dāng)文件較大時(shí)，記錄的檢索效率較低。另一個(gè)缺點(diǎn)是記錄的增加和刪除比較困難.SPOOLING技術(shù)是同時(shí)聯(lián)機(jī)外圍操作技術(shù)的簡(jiǎn)稱(chēng)。它是關(guān)于慢速字符設(shè)備如何與計(jì)算機(jī)主機(jī)進(jìn)行數(shù)據(jù)交換的一種技術(shù)，通常又稱(chēng)假脫機(jī)技術(shù).在多道程序環(huán)境下，利用多道程序中的一道或者兩道程序來(lái)模擬脫機(jī)輸入/輸出中的外圍控制機(jī)的功能，以達(dá)到“脫機(jī)”輸入/輸出的目的。利用這種技術(shù)可把獨(dú)占設(shè)備轉(zhuǎn)變成共享的虛擬設(shè)備，從而提高獨(dú)占設(shè)備的利用率和進(jìn)程的推進(jìn)速度.死鎖是因進(jìn)程競(jìng)爭(zhēng)資源或推進(jìn)順序不當(dāng)而引發(fā)的一種膠著狀態(tài).死鎖的四個(gè)必要條件分別是：互斥、占有且等待、不可剝奪以及循環(huán)等待.為了預(yù)防死鎖，必須破壞死鎖的四個(gè)必要條件.由于互斥條件不能改變，因此可以采取破壞四個(gè)必要條件中的后三個(gè).在基本分頁(yè)存儲(chǔ)管理系統(tǒng)中，系統(tǒng)將每個(gè)程序按固定的大小分成若干頁(yè)，每頁(yè)對(duì)應(yīng)一個(gè)物理塊號(hào).程序的所有頁(yè)面都被袋入到內(nèi)存當(dāng)中,在請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中，程序仍然被系統(tǒng)分成若干頁(yè)，但并不是所有的頁(yè)面都被袋入到系統(tǒng)中.而是僅僅裝入程序運(yùn)行所必須的頁(yè)面。當(dāng)需要某一個(gè)頁(yè)面時(shí)，再請(qǐng)求從外部調(diào)入.如果沒(méi)有空閑的空間，則利用置換技術(shù)進(jìn)行頁(yè)面的海汰與置換.為了緩和CPU和外設(shè)之間的矛盾，操作系統(tǒng)引入了單緩沖、雙緩沖以及循環(huán)緩沖.所謂單緩沖，就是在CPU和外設(shè)之間設(shè)置了一個(gè)緩沖區(qū)，當(dāng)有數(shù)據(jù)交換時(shí)，先把數(shù)據(jù)發(fā)往緩沖區(qū)，再?gòu)木彌_區(qū)中讀數(shù)據(jù).雙緩沖就是具有兩個(gè)緩沖，當(dāng)一個(gè)進(jìn)程正在往一個(gè)緩沖區(qū)讀數(shù)據(jù)的時(shí)候,操作系統(tǒng)可能正在讀或?qū)懥硗庖粋€(gè)緩沖區(qū).循環(huán)緩沖就是具有多個(gè)緩沖區(qū)的組合，它更加能夠緩和CPU和外設(shè)之間速度的不匹配.計(jì)算題.苜先要為該作業(yè)建立頁(yè)表如下：

每個(gè)頁(yè)面的大小為1024字節(jié)，則邏輯地址2200的頁(yè)號(hào)應(yīng)該為2,對(duì)應(yīng)物理塊號(hào)6,頁(yè)內(nèi)位移量為152,實(shí)際物理為：6X1024+152=6296.邏輯地址3100的頁(yè)號(hào)為3,對(duì)應(yīng)物理塊號(hào)8,頁(yè)內(nèi)位移量為28,則物理地址為8X1024+28=8220..FCFS訪問(wèn)順序?yàn)椋?9、190、97、54、30、87,因此磁頭移動(dòng)數(shù)為：(190-99)+(190-97)+(97-54)+(54-30)+(87-30)=308SSTF訪問(wèn)順序?yàn)椋?9、97、87,54、30、190,因此磁頭移動(dòng)數(shù)為:(99-97)+(97-87)+(87-54)+(54-30)+(190-30)=2293.先來(lái)先服務(wù)進(jìn)程到達(dá)時(shí)同處理時(shí)間完成時(shí)問(wèn)周轉(zhuǎn)時(shí)向帶權(quán)周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間P1033316.41.84P215871.4P3321073.5P4841461.5P51051991.8最夜進(jìn)程優(yōu)先:進(jìn)程到達(dá)時(shí)間處理時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)問(wèn)帶權(quán)周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間P1033315.81.42P2151091.8P332521P4841461.5P51051991.8由上可知，在本例中，最短進(jìn)程優(yōu)先的調(diào)度庫(kù)法性能最優(yōu).《數(shù)據(jù)結(jié)構(gòu)》單項(xiàng)選擇題(20分，每題2分)：1、下面算法的時(shí)間復(fù)雜度是(B).for(i=n;i>l;i-)for(j=i-l;j>l：j—)x++;A.0(n)B.0(n!)C.0(n(n-l))D.O(nlogn)2,以下數(shù)據(jù)結(jié)構(gòu)中，(A)是非線性數(shù)據(jù)結(jié)構(gòu).A.圖B.字符串C,數(shù)組 D.堆棧3、鏈表不具有的特點(diǎn)是(C).A.插入、刪除不需要移動(dòng)元素B.不必事先估計(jì)存儲(chǔ)空間C.可隨機(jī)訪問(wèn)任一元素 D.所需空間與線性表長(zhǎng)度成正比4、一個(gè)棧的輸入序列為】23…n,若輸出序列的第一個(gè)元素是n,輸出第i(l<=i〈=n)個(gè)元素是(D).A.不確定 B.n-i C.iD.n-i+l5,若一棵二叉樹(shù)具有12個(gè)度為2的結(jié)點(diǎn)，6個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是(C).A.10 B.11 C.13D.不確定6,下列哪種算法使用了隊(duì)列作為輔助存儲(chǔ)結(jié)構(gòu)(B).A.二叉樹(shù)的先根序遍歷算法B.二叉樹(shù)的層次遍歷算法C.圖的深度優(yōu)先遍歷算法 D.圖的拓?fù)渑判蛩惴?,以下哪種二叉樹(shù)左右子樹(shù)可以交換(D).A.二叉排序樹(shù)B.線索二叉樹(shù)C.平衡二叉樹(shù)D.哈夫曼樹(shù)8、下列哪種圖的鄰接矩陣是對(duì)稱(chēng)矩陣(B).A.有向圖B.無(wú)向圖C.AOV網(wǎng)D.AOE網(wǎng)9、在長(zhǎng)度為n的順序線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長(zhǎng)度(假定查找每個(gè)元素的概率均相等)為(D).A.nB.(n-l)/2C.n/2D.(n+l)/210,下列排序算法中，(C)在某趟排序結(jié)束后不一定能選出一個(gè)元素放到其最終的位置上.A.選擇排序B.冒泡排序C.希爾抻序D.堆排序二、填空題(10分，每空2分)：1、判定循環(huán)隊(duì)列的滿與空，有三種方法，它們是計(jì)數(shù)器法，標(biāo)志位法，和犧牲…個(gè)存儲(chǔ)單元法。2、一顆第5層有6個(gè)葉子節(jié)點(diǎn)的完全二叉樹(shù)，最多可能擁有的結(jié)點(diǎn)個(gè)數(shù)為3、在無(wú)權(quán)的無(wú)向圖G的鄰接矩陣A中，若(vj,vl屬于圖G的邊集合，則對(duì)應(yīng)元素等于」一三、簡(jiǎn)答題(30分)：試描述堆棧和遞歸的關(guān)系。(5分)遞歸過(guò)程是一種調(diào)用自身的函數(shù)，在調(diào)用的過(guò)程中存在轉(zhuǎn)入子程序的過(guò)程.(2分)在每次轉(zhuǎn)子時(shí)需要保護(hù)現(xiàn)場(chǎng)，則將相應(yīng)參數(shù)和中間結(jié)果壓入系統(tǒng)堆棧，而在子程序返回的時(shí)候，需要恢復(fù)現(xiàn)場(chǎng)，則將之前壓棧的數(shù)據(jù)從系統(tǒng)堆棧彈出，因此，遞歸過(guò)程存在隱含的堆棧操作,而

且子程序的調(diào)用過(guò)程滿足堆棧先進(jìn)后出的特性。（3分）根據(jù)答案相關(guān)程度，可以酌情給分.2、已知二叉樹(shù)的中序遍歷序列為DEBAFCG,后序遍歷序列為EDBFGCA,試畫(huà)出該二叉樹(shù)（7分）AE 畫(huà)錯(cuò)一個(gè)結(jié)點(diǎn)扣1分3,給定25個(gè)字符組成的電文：（6分）DDDDAAABEEAAFCDAABCCCBADD試為字符A、B、C、D,E、F設(shè)計(jì)哈夫曼（Huffman）編碼.（1）畫(huà)出相應(yīng)的哈夫曼樹(shù)：（3分）（2）分別列出A、B、C,D、E,F的哈夫曼編碼；（2分）（3）計(jì)算該樹(shù)的帶權(quán)路徑長(zhǎng)度WPL.（1分）（1）權(quán)值A(chǔ):8B:3C:4D:7E:2F:1TOC\o"1-5"\h\z哈夫曼樹(shù)答案不唯一，可根據(jù)其正確性酌情給分. （4分）（2）A:01B:101C:11D:00E:1000F:1001 （3分）答案不唯一，可根據(jù)其正確性酌情給分.（3）WPL=7*2+8*2+4*2+3*3+2*4+1*4=59 （1分）4、已知帶權(quán)圖G如下所示，試用Prim算法構(gòu)造對(duì)應(yīng)的最小生成樹(shù)，須給出構(gòu)造步驟.（7分）

(6)(6)5、一個(gè)線性表為B=（14,23,43,52,20,35,79,31,17,36）,設(shè)散列表為HT[0..20],散列函數(shù)為H（key）=key%11并用線性探測(cè)法解決沖突（增量d尸1,2…），試寫(xiě)出散列表。（5分）0123456789111111111120123456789023351731524349672031每寫(xiě)錯(cuò)一個(gè)，扣0.5分四、算法設(shè)計(jì)題（15分）：1、如果以二叉鏈表做為存儲(chǔ)結(jié)構(gòu)，試用類(lèi)C語(yǔ)言編寫(xiě)統(tǒng)計(jì)二叉樹(shù)非葉子結(jié)點(diǎn)個(gè)數(shù)的層次遍歷算法.（15分）typedefstructBiTreeNode{ 給出存儲(chǔ)結(jié)構(gòu)定義得3分Datatypedata：structBiTreeNode*lchild,rchild;}BiTreeNode,*BiTree：intLevelOrder(BiTreebt){BiTreeNodeQueue[MAXNODE];/*定義隊(duì)列*/intfront,rear,count;if(bt==NULL)return0：/*空二叉樹(shù)，遍歷結(jié)束*/ 1分front=-l;rear=0：count=0;Queue[rear]=bt;/*根結(jié)點(diǎn)入隊(duì)列*/ 1分TOC\o"1-5"\h\zwhile(rear!:front){/*隊(duì)列不空,繼續(xù)遍歷，否則，遍歷結(jié)束*/—1分front-H-;/*出隊(duì)*/ 1分if(Queue[front]->lchiId!=NULL||Queue[front]->rchiId!=NULL) 1分count++;/*統(tǒng)計(jì)非葉子節(jié)點(diǎn)個(gè)數(shù) 1分if(queue[front]->lchild!二NULL){/*如果有左孩子，左孩子入隊(duì)*/ 1分rear++; 1分Queue[rear]-Queue[front]->lchiId; 1分)if(queue[front]->rchild!=NULL){/*如果有右孩子，右孩子入隊(duì)*/ 1分rear++; 1分Queue[rear]=Queue[front]->rchiId; 1分))Returncount;}第39頁(yè)2011年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題及詳解電子科技大學(xué)* 2011年攻讀碩士學(xué)位研究生入學(xué)試題考試科目：820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)注：所有答案必須寫(xiě)在答題紙上，做在試卷或草稿紙上無(wú)效數(shù)據(jù)結(jié)構(gòu)75分一、選擇題(每小題1分，共8分).若結(jié)點(diǎn)的存儲(chǔ)地址與其關(guān)鍵字值之間存在某種對(duì)應(yīng)關(guān)系，則稱(chēng)這種存儲(chǔ)結(jié)構(gòu)為( )A.順序存儲(chǔ)結(jié)構(gòu) B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu) D.散列存儲(chǔ)結(jié)構(gòu).能在0(1)時(shí)間內(nèi)訪問(wèn)線性表的第i個(gè)元素的結(jié)構(gòu)是()A.順序表 B.單鏈表 C.單向循環(huán)鏈表 D.雙向鏈表.一個(gè)nxn的對(duì)稱(chēng)矩陣，如果以行主序存儲(chǔ)，每個(gè)元素占一個(gè)單元，則其需要的最大存儲(chǔ)空間為()AnxnBnxn/2C(n+l)*n/2D(n+l)x(n+l)/2.已知一稀疏矩陣的三元組表為：(1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3),則其轉(zhuǎn)置矩陣的三元組表中第3個(gè)三元組為()A.(2,1,3) B.(3,1,5) C.(3,2,-1) D.(2,3,-1)TOC\o"1-5"\h\z.在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為空的鏈域的個(gè)數(shù)為( )A.n-1B.n+1C.2n-lD.2n+l.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接表表示，則存放表頭結(jié)點(diǎn)的數(shù)組的大小為( )A.n B.n+1 C.n-1 D.n+1邊數(shù).下圖所示的二叉樹(shù)是( )A.二叉判定樹(shù)B.二叉排序樹(shù)C.二叉平衡樹(shù)D.堆.用某種排序方法對(duì)關(guān)鍵字序列(25,84,21,47,15,27,68,35,20)行排序時(shí)，序列的變化情況如下：TOC\o"1-5"\h\z20, 15, 21, 25, 47, 27, 68, 35, 8415, 20, 21, 25, 35, 27, 47, 68. 8415, 20, 21, 25, 27, 35, 47, 68, 84則所采用的排序方法是()A.選擇排序 B.希爾排序 C.歸并排序 D.快速排序二、填空題(每小題1分，共8分).若一個(gè)算法中的語(yǔ)句頻度之和為T(mén)(n)=3720n+4nlogn,則算法的時(shí)間復(fù)雜度為?.在長(zhǎng)度為n的順序表的第i(lG9+l)個(gè)位置上插入一個(gè)元素，元素的移動(dòng)次數(shù)為..一個(gè)隊(duì)列的入隊(duì)序列是a、b、c、d,則隊(duì)列的輸出序列為..廣義表A=(A(b),0，(c,d,e))的長(zhǎng)度為..在有n個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)中，其葉子結(jié)點(diǎn)數(shù)是..已知某二叉樹(shù)的先序序列為ABDECF,中序序列為DBEAFC,則其后序序列為..在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為一..在以｛4,5,6,7,8｝作為葉子結(jié)點(diǎn)權(quán)值構(gòu)造的二叉樹(shù)中，其帶權(quán)路徑長(zhǎng)度最小是.三、簡(jiǎn)答題(每小題6分，共36分).已知一棵完全二叉樹(shù)共有893個(gè)結(jié)點(diǎn)，試求:(1)樹(shù)的高度；(2)葉子結(jié)點(diǎn)數(shù)目.

.用Dijkstra算法求出下圖中從頂點(diǎn)vl到其余各頂點(diǎn)的最短路徑，按求解過(guò)程依次寫(xiě)出各條最短路徑及其路徑長(zhǎng)度。3.已知關(guān)鍵字序列在a[L.8]中的初始狀態(tài)為1 2 3 4 5 6 7 84870336524561292寫(xiě)出將其調(diào)整為大根堆的過(guò)程中每一次篩選后a的狀態(tài).4.已知圖G的存儲(chǔ)結(jié)構(gòu)如下.假設(shè)對(duì)其訪問(wèn)時(shí)每行元素必須從右到左，請(qǐng)寫(xiě)出從vl開(kāi)始按深度優(yōu)先搜索時(shí)各連通分量的訪問(wèn)序列ioir0101100000001000,ioir0101100000001000,1/=（〃，》,為,〃，！）A=05.根據(jù)中序、先序、后序遍歷二叉樹(shù)的特點(diǎn)，將根結(jié)點(diǎn)、葉結(jié)點(diǎn)、葉結(jié)點(diǎn)或無(wú)左子樹(shù)結(jié)點(diǎn)、葉結(jié)點(diǎn)或無(wú)右子樹(shù)結(jié)點(diǎn)填入下表空白處.第一個(gè)被訪問(wèn)的結(jié)點(diǎn)最后一個(gè)被訪問(wèn)的結(jié)點(diǎn)先序遍歷二叉樹(shù)中序遍歷二叉樹(shù)后序遍歷二叉樹(shù)6.選取散列函數(shù)H(key)=(key)%11,用線性探測(cè)法處理沖突，對(duì)下列關(guān)鍵碼序列{1,13,12,34,38,33,27,22},構(gòu)造一個(gè)表長(zhǎng)為11的散列表，并求其查找成功的平均長(zhǎng)度.

四、算法題（共23分）1.(6分)閱讀算法testOl,說(shuō)明其功能.inttest01(inta[],intlo'high,intx){//low和high分別為數(shù)據(jù)區(qū)的下界和上界intij,t;i=low;J=high;while(i<J){while(i<J&&while(i<J&&a0J>=x)i++；if(i<j){t^a[j];a[}]=a[i];a[i]=t;})if(a[i]<x)returni;elsereturni-l：)（6分）閱讀算法test02.若root為指向右圖A的指針，試給出其執(zhí)行結(jié)果。structnode{chardata;structnode^Ichild,*rchild;};voidtest02(structnode*root){if(root){printf("%c",root->data);test02(root->lchild);printf("%c",root->data)：test02(root->rchild);})3.（11分）編寫(xiě)一算法將順序表轉(zhuǎn)存為帶頭節(jié)點(diǎn)的單循環(huán)鏈表。算法中所用到的數(shù)據(jù)結(jié)構(gòu)需自行定義.操作系統(tǒng)部分75分一、單項(xiàng)選擇題（每小題2分，共16分，下面每題給出的四個(gè)選項(xiàng)中，只有一個(gè)最符合試題要求）1、機(jī)票訂購(gòu)系統(tǒng)處理來(lái)自各個(gè)終端的服務(wù)請(qǐng)求，處理后通過(guò)終端回答用戶，所以它是一個(gè)（）.A.分時(shí)系統(tǒng) B.多道批處理系統(tǒng)C.計(jì)算機(jī)網(wǎng)絡(luò) D.實(shí)時(shí)信息處理系統(tǒng)2、操作系統(tǒng)在計(jì)算機(jī)系統(tǒng)中位于（）之間。A.CPU和用戶之間 B.中央處理器CPUC.計(jì)算機(jī)硬件和用戶 D.計(jì)算機(jī)硬件和軟件之間3、在單處理機(jī)系統(tǒng)中，可并行的是（）I進(jìn)程與進(jìn)程II處理機(jī)與設(shè)備in處理機(jī)與通道iv設(shè)備與設(shè)備A,I、II和卬 B.I、n和wc.I、ni和w d.ii,in和w4、進(jìn)程具有3種基本狀態(tài)：就緒狀態(tài)、執(zhí)行狀態(tài)和阻塞狀態(tài).進(jìn)程在執(zhí)行過(guò)程中，其狀態(tài)總是不停地發(fā)生變化下面關(guān)于進(jìn)程狀態(tài)變化的說(shuō)法中正確的是（）.A.一個(gè)進(jìn)程必須經(jīng)過(guò)進(jìn)程的3種基本狀態(tài)才能結(jié)束B(niǎo).在分時(shí)系統(tǒng)中，一個(gè)正在運(yùn)行進(jìn)程的時(shí)間片如果終結(jié)，該進(jìn)程將轉(zhuǎn)入就緒狀態(tài)C.三種進(jìn)程狀態(tài)是進(jìn)程運(yùn)行過(guò)程中的基本狀態(tài)，進(jìn)程可能同時(shí)處于某幾種狀態(tài)中D.進(jìn)程一旦形成，首先進(jìn)入的是運(yùn)行狀態(tài)5、采用中斷屏蔽技術(shù)，會(huì)封鎖《）的響應(yīng).A.與自己級(jí)別相同的中斷事件 B.比自己級(jí)別高的中斷事件C.與中斷屏蔽標(biāo)志相對(duì)應(yīng)的事件 D.比自己級(jí)別低的中斷事件6、頁(yè)表的作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的（）.A.邏輯映射 B.物理映射C.地址映射 D.邏輯地址映射7、分頁(yè)式虛擬存儲(chǔ)管理系統(tǒng)中，頁(yè)面的大小與可能產(chǎn)生的缺頁(yè)中斷次數(shù)（）.A.成正比 B.成反比C.無(wú)關(guān) D.成固定值8、下面4個(gè)選項(xiàng)中不屬于SPOOLing系統(tǒng)特點(diǎn)的是（）.A.提高了內(nèi)存的利用率 B.提高了I/O操作的速度C.將獨(dú)占設(shè)備改造為共享設(shè)備D.實(shí)現(xiàn)了虛擬設(shè)備功能二、填空題（每空2分，共11題，22分）1、文件系統(tǒng)的主要目標(biāo)是提高存儲(chǔ)空間的利用率和.2、可變分區(qū)管理方式常用的主存分配算法有：最先適應(yīng)分配算法、和.3、進(jìn)程可以并發(fā)執(zhí)行，若干個(gè)并發(fā)執(zhí)行的進(jìn)程交替占用處理器，而進(jìn)程各種狀態(tài)的轉(zhuǎn)換不是事先預(yù)定的，也不是完全由操作系統(tǒng)來(lái)確定的，而是在硬件和操作系統(tǒng)的相互配合下281完成的，起主要作用的是.4、在存儲(chǔ)管理方案中，可用上、下限寄存器實(shí)現(xiàn)存儲(chǔ)保護(hù)的是.5、位圖可以用來(lái)指示磁盤(pán)存儲(chǔ)空間的使用情況，一個(gè)磁盤(pán)組的分塊確定后，根據(jù)可分配的總塊數(shù)決定位圖由多少個(gè)字組成，位圖中的每一位與一塊對(duì)應(yīng)，“1”狀態(tài)表示相應(yīng)塊已 ，“0”狀態(tài)表示該塊.6,死鎖的4個(gè)必要條件是、不可搶奪資源和循環(huán)等待資源。-7、當(dāng)一個(gè)進(jìn)程獨(dú)占處理器順序執(zhí)行時(shí)，具有兩個(gè)特性：和.三、簡(jiǎn)答題（每小題6分，共5小題，30分）1、請(qǐng)描述在當(dāng)前運(yùn)行進(jìn)程狀態(tài)改變時(shí)，操作系統(tǒng)進(jìn)行進(jìn)程切換的步驟.2、試寫(xiě)出P（S）操作的主要操作步驟。3、闡述對(duì)于互斥臨界區(qū)的管理要求.4、為什么要在設(shè)備管理中引入緩沖技術(shù)？操作系統(tǒng)如何實(shí)現(xiàn)緩沖技術(shù)？5、解釋頁(yè)式存儲(chǔ)管理中為什么要設(shè)置頁(yè)表和快表.四、計(jì)算題（7分）現(xiàn)有一個(gè)僅460個(gè)字節(jié)的程序的下述內(nèi)存訪問(wèn)序列（該序列的下標(biāo)均從。開(kāi)始10、11、104、170、73、309、185、245、246、434、458、364.且頁(yè)面大小為100字節(jié)：（1）寫(xiě)出頁(yè)面的訪問(wèn)序列.（2分）（2）假設(shè)內(nèi)存中僅有200字節(jié)可供程序使用且采用FIFO算法，那么共發(fā)生多少次缺頁(yè)中斷？（3分）（3）如果采用最近最久未使用的算法，則又會(huì)發(fā)生多少次缺頁(yè)中斷？（3分）操作系統(tǒng)答案、DCDBCCCA二wI、減少存取時(shí)間2、最優(yōu)適應(yīng)分配算法最壞適應(yīng)分配算法3、中斷系統(tǒng)4、分區(qū)式存儲(chǔ)管理5、占用空閑6、互斥條件請(qǐng)求和保持條件7,封閉性可再現(xiàn)性1、拳考答案，進(jìn)程切換的步驟如下?(1)保存當(dāng)前進(jìn)程上下文環(huán)境.(2)對(duì)當(dāng)前運(yùn)行進(jìn)程的PCB進(jìn)行更新.并將其移入適當(dāng)?shù)年?duì)列.(3)挑選其他進(jìn)程執(zhí)行.(4)對(duì)挑選進(jìn)程PCB進(jìn)行更新，包括將其狀態(tài)改為運(yùn)行.(5)對(duì)存儲(chǔ)器管理數(shù)據(jù)結(jié)構(gòu)進(jìn)行更新.(6)恢復(fù)被選擇進(jìn)程上次移出時(shí)的處理器狀態(tài).2、參考答案：(1)S產(chǎn)S-l,(S為信號(hào)量).(2分)(2)若S<0,阻塞當(dāng)前進(jìn)程，將其插入S的等待隊(duì)列，調(diào)度另一進(jìn)程運(yùn)行.(2分)(3)若S>=0,當(dāng)前進(jìn)程繼續(xù)運(yùn)行.(2分)3參考答案：為實(shí)現(xiàn)進(jìn)程互斥，可利用軟件方法，也可在系統(tǒng)中設(shè)置專(zhuān)門(mén)的同步機(jī)制來(lái)協(xié)調(diào)諸進(jìn)程，但所有的同步機(jī)制都應(yīng)遵循下述4條準(zhǔn)則：(2分)(1)空閑讓進(jìn)(1分).無(wú)進(jìn)程處于臨界區(qū)時(shí)，相應(yīng)的臨界資源處于空閑狀態(tài)，因而可允許下個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源?(2)忙則等待(1分).己有進(jìn)程進(jìn)入自己的臨界區(qū)時(shí)，相應(yīng)的臨界資源正被訪問(wèn)，所有其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證諸進(jìn)程互斥地訪問(wèn)臨界資源.(3)有限等待(1分).對(duì)要求訪問(wèn)臨界資源的進(jìn)程，應(yīng)保證該進(jìn)程能在有效時(shí)間內(nèi)進(jìn)入自己的臨界區(qū)，以免陷入“死等”狀態(tài).(4)讓權(quán)等待(I分).當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”.4、參考答案：在操作系統(tǒng)中，引入緩沖的主要原因，可歸結(jié)為以下幾點(diǎn),(1)改善CPU與I/O設(shè)備間速度不匹配的矛盾(2分).例如一個(gè)程序，它時(shí)而進(jìn)行長(zhǎng)時(shí)間的計(jì)算而沒(méi)有輸出，時(shí)而又陣發(fā)性把愉出送到打印機(jī).由于打印機(jī)的速度跟不上CPU,而使得CPU長(zhǎng)時(shí)間的等待.如果設(shè)置了緩沖區(qū)，程序輸出的數(shù)據(jù)先送到緩沖區(qū)暫存，然后由打印機(jī)慢慢地輸出.這時(shí)，CPU不必等待，可以繼續(xù)執(zhí)行程序.實(shí)現(xiàn)了CPU與I/O設(shè)備之間的并行工作.事實(shí)上，凡在數(shù)據(jù)的到達(dá)速率與其離去速率不同的地方，都可設(shè)置緩沖，以緩和它們之間速度不匹配的矛盾.眾所周知，通常的程序都是時(shí)而計(jì)算，時(shí)而輸出的.(2)可以減少對(duì)CPU的中斷頻率，放寬對(duì)中斷響應(yīng)時(shí)間的限制(1分).如果I/O操作每傳送一個(gè)字節(jié)產(chǎn)生一次中斷，那么設(shè)置了n個(gè)字節(jié)的緩沖區(qū)后，則可以等到緩沖區(qū)滿才產(chǎn)生中斷，這樣中斷次數(shù)就減少到lln,而且中斷響應(yīng)的時(shí)間也相應(yīng)地放寬.283（3）提高CPU和I/O設(shè)備之間的并行（1分）性.緩沖的引入可顯著提高CPU和設(shè)備的并行操作程度，提高系統(tǒng)的吞吐量和設(shè)備的利用率.根據(jù)I/O控制方式，緩沖的實(shí)現(xiàn)方法有兩種：（1）采用專(zhuān)用硬件緩沖器。（1分）（2）在內(nèi)存劃出一個(gè)具有n個(gè)單元的專(zhuān)用緩沖區(qū)，以便存放輸夕口輸出的數(shù)據(jù)。內(nèi)存緩沖區(qū)又稱(chēng)為軟件緩沖（1分）.5、參考答案：頁(yè)式存儲(chǔ)管理首先把主存儲(chǔ)器分成大小相等的分塊,作為主存分配的物理單位，同時(shí)要求程序邏輯地址也分成與塊大小一致的頁(yè)面，這樣就可以把作業(yè)信息按頁(yè)面存放在塊中.進(jìn)行存儲(chǔ)分配時(shí)，根據(jù)作業(yè)大小，確定其頁(yè)面數(shù)，在裝入主存時(shí)給它分配相應(yīng)數(shù)目的主存塊.這些主存塊可以不相鄰，為了在作業(yè)執(zhí)行過(guò)程中準(zhǔn)確地查找邏輯地址與絕對(duì)地址的對(duì)應(yīng)關(guān)系，系統(tǒng)為每個(gè)作業(yè)建立一張頁(yè)表，指出邏輯地址中的頁(yè)號(hào)與主存塊中塊號(hào)的對(duì)應(yīng)關(guān)系.（2分）頁(yè)表一般存放在主存儲(chǔ)器中，當(dāng)要按給定的邏輯地址進(jìn)行讀/寫(xiě)時(shí)，必須兩次訪問(wèn)主存，延長(zhǎng)了指令的執(zhí)行周期,降低了執(zhí)行速度，為了提高存取速度，系統(tǒng)設(shè)置一個(gè)小容量的高速緩沖存儲(chǔ)器，利用高速緩沖存儲(chǔ)器存放頁(yè)表的一部分，這部分頁(yè)表即“快表”，利用快表可以一次訪問(wèn)主存完成讀/寫(xiě)，大大縮短地址轉(zhuǎn)換時(shí)間，從而提高查找速度和執(zhí)行指令速度.（4分）四、參考答案；（1）訪問(wèn)順序，如下表所示:101110417073309185245246434458364001103122443（2）采用FIFO算法的情況如下所示.001103122443塊號(hào)0001113322443塊號(hào)10001133224海汰頁(yè)號(hào)0132缺頁(yè)中斷VJJV采用FIFO算法產(chǎn)生的缺頁(yè)中斷為6次.（3）采用LRU算法的情況如下表所示.001103122443塊號(hào)0001103122443塊號(hào)10010311224淘汰頁(yè)號(hào)10312缺頁(yè)中斷VVV7采用LRU算法產(chǎn)生的缺頁(yè)中斷為7次.數(shù)據(jù)結(jié)構(gòu)參考答案一、選算題(每小題1分，共8分)TOC\o"1-5"\h\zl.D 2A 3.C 4.AS.B 6.A 7.B 8.D二、填空題(?小題1分，共8分)1.O(nlogn) 2.n-i+l 3.abed 4.45.(n+iy2 6.DEBFCA7.n2-2c 8.69三、曾答題(每小題6分，共36分)(1)10; (3分)(2)447 。分)路徑 長(zhǎng)度(vt,v5) 10(vl,v2) 20(vl,v5.v6) 30(vl,v5,v6,v3) 45(vl,v5,v6,v3,v4) 854870336524561292487056922433126548925670243312659270566524331248V|,V4,V3,V2,V5第一個(gè)被訪問(wèn)的結(jié)點(diǎn)最后一個(gè)被訪問(wèn)的結(jié)點(diǎn)先序遍歷二叉樹(shù)根結(jié)點(diǎn)葉結(jié)點(diǎn)中序遍歷二叉樹(shù)葉結(jié)點(diǎn)或無(wú)左子樹(shù)結(jié)點(diǎn)葉結(jié)點(diǎn)或無(wú)右子樹(shù)結(jié)點(diǎn)后序遍歷二叉樹(shù)葉結(jié)點(diǎn)根結(jié)點(diǎn)6.哈希表01 2 3 4 5 6 7 8 9 1033~1~I 13 I12 I34 I38 T27 I22ASL=13/8285

四、算法題（共23分）（6分）該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a[]中的元素并返回分界值i,使所有Vx的元素均落在使所有Nx的元素均落在a[i+l..h]±o（6分）ABBCCADD(11分)本題有多種實(shí)現(xiàn)方法，一種實(shí)現(xiàn)方法如下，(1)定義所需數(shù)據(jù)結(jié)構(gòu)(3分)^defineMaxSize100typedefstructSeqList{ 、Elemlypedata[MaxSize];intlength;/SeqList;typedefstructnode{ElemTypedata;structnode*nxt;}ListNode;typedefListNode^LinkedList;(2)算法(8分)voidans(SeqListL,LinkList*L2){/*L是順序存儲(chǔ)的線性表;L2為新建鏈表的頭指鏟/乜2=(LinkList)malloc(sizeof(ListNode));（建空鏈表2分）（1（建空鏈表2分）（1分）（生成新節(jié)點(diǎn)2分）（正確鏈入3分）fori^L.length;i>O;i){p=(ListNode^)malloc(sizeof(ListNode));p->data=L.elem[i-1];p->next=L2->next;L2->next=p;}第51頁(yè)2010年電子科技大學(xué)820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)考研真題及詳解電子科技大學(xué)2010年碩士研究生入學(xué)試題

考試科目：820計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)注：所有答案必須寫(xiě)在答題紙上，做在試卷或草稿紙上無(wú)效。一、單項(xiàng)選擇題（在每小2分，共20分）.無(wú)結(jié)構(gòu)文件的含義是（ ）A.變長(zhǎng)記錄的文件 B.索引文件C.流式文件 D.索引順序文件.鏈接文件的正確概念（ ）A.鏈接文件是文件邏輯組織的一種方式 B.鏈接文件是以空間換時(shí)間C.鏈接文件不適合隨機(jī)存取 D.鏈接文件是索引結(jié)點(diǎn).處理器執(zhí)行的指令被分成兩類(lèi)，其中一類(lèi)稱(chēng)為特權(quán)指令，它只允許（ ）使用.A.操作員 B.聯(lián)機(jī)用戶C.操作系統(tǒng) D.目標(biāo)程序TOC\o"1-5"\h\z.索引順序文件的正確描述（ ）A.按索引值查找 B.按記錄關(guān)鍵字順序查找C.既要按索引值查找又要按記錄關(guān)鍵字順序查找D.利用關(guān)鍵字找到該記錄組中第一個(gè)記錄的表項(xiàng)，然后，順序查找所要求的記錄..頁(yè)面置換算法在計(jì)算機(jī)系統(tǒng)中的作用是（ ）.A.存儲(chǔ)文件信息 B.實(shí)現(xiàn)虛擬存儲(chǔ)管理C.地址變換 D.存儲(chǔ)通道程序.能實(shí)現(xiàn)緊湊技術(shù)的存儲(chǔ)管理（ ）.A.可變分區(qū)管理B.分區(qū)存儲(chǔ)管理C.頁(yè)式存儲(chǔ)管理 D.可重定位存儲(chǔ)管理.文件系統(tǒng)的主要目的是（ ）.A.實(shí)現(xiàn)對(duì)文件的按名存取 B.實(shí)現(xiàn)虛擬存儲(chǔ)C.提高外存的讀寫(xiě)速度 D.用于存儲(chǔ)系統(tǒng)文件.下面關(guān)于檢測(cè)死鎖的敘述埼譯的是（ ）A.檢測(cè)死鎖方法對(duì)系統(tǒng)資源的分配不加限制，只要有則可以進(jìn)行分配B.檢測(cè)死鎖中系統(tǒng)需要反復(fù)檢測(cè)各進(jìn)程資源申請(qǐng)和分配情況C.檢測(cè)死鎖是預(yù)防系統(tǒng)卷入了死鎖D.檢測(cè)死鎖只能發(fā)現(xiàn)死鎖,而不能消除死鎖

.采用多道程序設(shè)計(jì)的主要目的是（B.提高CPUB.提高CPU的利用率D.充分利用磁盤(pán)C.充分利用0/1設(shè)備.不是文件的邏輯結(jié)構(gòu)（B.順序結(jié)構(gòu)D.B.順序結(jié)構(gòu)D.樹(shù)型結(jié)構(gòu)C.層次結(jié)構(gòu)二、多項(xiàng)選擇題（在每小題的五個(gè)備選答案中，選出二個(gè)至五個(gè)正確的答案，并將其號(hào)碼分別填在題干的括號(hào)內(nèi)，多選，少選、錯(cuò)選，均無(wú)分,每小182分，共10分）TOC\o"1-5"\h\z.虛擬設(shè)備的正確描述（ ）A.虛擬設(shè)備與物理設(shè)備無(wú)關(guān)B.用戶不知道，系統(tǒng)也不知道C.虛擬設(shè)備與物理設(shè)備有關(guān) D.用戶不知道，系統(tǒng)知道E.由SPOOLING技術(shù)實(shí)現(xiàn)虛擬設(shè)備.在虛擬存儲(chǔ)管理的調(diào)頁(yè)技術(shù)有（ ）.A.LRU算法 B.中斷請(qǐng)求調(diào)頁(yè) C.預(yù)調(diào)頁(yè)技術(shù)clock算法 E.FIFO算法3.假設(shè)有N個(gè)進(jìn)程，M個(gè)資源，每個(gè)進(jìn)程需要的資源數(shù)為W,請(qǐng)按以下給出的N、M和W,計(jì)算以下那個(gè)可能引起死鎖（ ）A.N=2,M=2,W=1 B.N=2,M=3,W=2C.N=2,M=3,W=3 D.N=3,M=5,W=2N=3,M=6,W=3.操作系統(tǒng)是一個(gè)龐大的系統(tǒng)軟件，可采用那些操作方式來(lái)為用戶服務(wù)（ ）A.命令接口 B.系統(tǒng)調(diào)用 C.作業(yè)控制語(yǔ)言D.軟中斷 E.通過(guò)應(yīng)用軟件提供服務(wù).以下那一些算法對(duì)執(zhí)行時(shí)間短的進(jìn)程有利（ ）A.時(shí)間片輪轉(zhuǎn)法 B.多級(jí)反饋隊(duì)列調(diào)度算法 C.搶占式調(diào)度算法D.FCFS（先來(lái)先服務(wù)）調(diào)度算法 E.高響應(yīng)比優(yōu)先調(diào)度算法三、判斷并改錯(cuò)（每小題2分，共14分）.（ ）在不同進(jìn)程中的線程切換不會(huì)引起進(jìn)程切換。.（ ）引入信號(hào)量的目的是為了正確實(shí)現(xiàn)進(jìn)程間的并發(fā)執(zhí)行..（ ）采用高級(jí)調(diào)度是確認(rèn)作業(yè)的運(yùn)行資格，而不考慮資源問(wèn)題..（ ）在系統(tǒng)運(yùn)行中采用死鎖定理的算法.可避免死鎖的發(fā)生..（ ）采用重定位技術(shù)能夠?qū)崿F(xiàn)程序的浮動(dòng)..（ ）unix系統(tǒng)在磁盤(pán)存儲(chǔ)管理中采用成組鏈接法比其他管理方式更能利用空間.

.（ ）通道接到CPU的命令后，通過(guò)執(zhí)行通道程序便可完成CPU指定的I/O任務(wù).四、簡(jiǎn)答題（共31分）（10分）在虛擬存儲(chǔ)管理系統(tǒng)中，假設(shè)訪問(wèn)快表中的頁(yè)需要20ns的定位時(shí)間；如果該頁(yè)在主存儲(chǔ)器中不在快表中，則需要60ns的時(shí)間載入快表，然后再重新開(kāi)始定位；如果該頁(yè)既不在主存儲(chǔ)器中，也不在快表中，則需要12ms的時(shí)間從磁盤(pán)中提取，然后霰要60ns復(fù)制到快表中，然后才開(kāi)始定位.快表的命中率是0.9,主存儲(chǔ)器的命中率是0.6,在該系統(tǒng)中訪問(wèn)一個(gè)被定位的頁(yè)所需要的平均時(shí)間為多少（單位：ns）?（10分）假定一個(gè)操作系統(tǒng)的進(jìn)程調(diào)度采用搶占式短進(jìn)程優(yōu)先調(diào)度策略（單CPU）系統(tǒng)，各進(jìn)程的到達(dá)時(shí)間如下表所示.請(qǐng)給出各進(jìn)程的調(diào)度次序，并計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間.進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間P115P223P342P439（11分）在UNIX文件系統(tǒng)中，采用混合索引結(jié)構(gòu)搜索文件內(nèi)容.設(shè)塊長(zhǎng)為512字節(jié)，每個(gè)塊號(hào)長(zhǎng)4字節(jié)，如果不考慮邏輯塊號(hào)在物理塊中所占的位置，請(qǐng)求出該文件最大搜索文件的長(zhǎng)度。數(shù)據(jù)結(jié)構(gòu)（75分）一、單項(xiàng)選擇題：從備選答案中選擇一個(gè)正確的答案（每小題1分，共10分）.線性表是一個(gè)（ ）.①有限序列，可以為空 ②有限序列，不能為空③無(wú)限序列，可以為空 ④無(wú)序序列，不能為空.在下列4種排序算法中，不能保證每趟排序至少能將一個(gè)元素放到其最終位置上的排序方法是（ ）.②冒泡排序排序④堆排序）.②冒泡排序排序④堆排序）.②一定不連續(xù)④連續(xù)與否無(wú)所謂③希爾排序.單鏈表中各結(jié)點(diǎn)之間的地址（①必須連續(xù)③部分地址必須連續(xù).能正確完成刪除單鏈表中p所指結(jié)點(diǎn)的后繼的操作是（ ）①p=p->next； ②p->next=p->next->nexts③p->next=pi ④p=p->next->next；.與Hash查找效率無(wú)關(guān)的因素是（ ）.①哈希函數(shù)是否均勻 ②處理沖突的方法③哈希表的裝填因子 ④縮小查找范圍的大小.在下列關(guān)于平衡二叉樹(shù)的敘述中，不正確的是( ).