電子科技大學820計算機專業(yè)基礎歷年考研真題及詳解附答案

電子科技大學820計算機專業(yè)

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

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

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

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

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

計算機操作系統(tǒng)引入和使用虛擬存儲技術的主要目的是提高系統(tǒng)的內(nèi)存利用率和系統(tǒng)吞吐量（5分）.答：連續(xù)分配方式：在創(chuàng)建文件時需要給文件分配一組連續(xù)的盤塊。連續(xù)分配的優(yōu)點主要有兩個，分別是順序訪問文件時比較容易，并且順序訪問時速度快.缺點是要求有連續(xù)的存儲空間，并且隨著外存空間的分配和回收，會產(chǎn)生很多外存碎片.降低了外存空間的利用率.索引分配方式：為文件的每個分區(qū)單獨建立一張索引表。該索引表記錄了分配給該文件的所有的塊號。優(yōu)點：直接訪問和順序訪問的速度都比較快.缺點：存儲索引表花費了較多外存空間.（5分）.答：DMA是直接存儲器存取.DMA傳輸將數(shù)據(jù)從一個地址空間復制到另外一個地址空間.當CPU初始化這個傳輸動作，傳輸動作本身是由DMA控制器來實行和完成,在實現(xiàn)DMA傳輸時，是由DMA控制器直接掌管總線，因此，存在著一個總線控制權轉(zhuǎn)移問題。即DMA傳輸前,CPU要把總線控制權交給DMA控制器，而在結(jié)束DMA傳輸后，DMA控制器應立即把總線控制權再交回給CPU.它和中斷的主要區(qū)別在于，DMA只需要CPU在開始和完成傳輸時進行」干預，其他時候不需要CPU干預.（6分） '.答：若磁盤塊空閑，則用1表示，否則用0表示.從而得到一張位式圖表，反映了所有磁盤塊的信息。其優(yōu)點在于很容易找到一個連續(xù)的空閑塊.缺點在于整個磁盤的位式圖文件比較大，另外，在磁盤空閑快較少時，搜索空閑塊要花費一些時間.（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

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

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

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

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

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

且子程序的調(diào)用過程滿足堆棧先進后出的特性。（3分）根據(jù)答案相關程度，可以酌情給分.2、已知二叉樹的中序遍歷序列為DEBAFCG,后序遍歷序列為EDBFGCA,試畫出該二叉樹（7分）AE 畫錯一個結(jié)點扣1分3,給定25個字符組成的電文：（6分）DDDDAAABEEAAFCDAABCCCBADD試為字符A、B、C、D,E、F設計哈夫曼（Huffman）編碼.（1）畫出相應的哈夫曼樹：（3分）（2）分別列出A、B、C,D、E,F的哈夫曼編碼；（2分）（3）計算該樹的帶權路徑長度WPL.（1分）（1）權值A:8B:3C:4D:7E:2F:1TOC\o"1-5"\h\z哈夫曼樹答案不唯一，可根據(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、已知帶權圖G如下所示，試用Prim算法構(gòu)造對應的最小生成樹，須給出構(gòu)造步驟.（7分）

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

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

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

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

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

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