2014年重慶理工大學(xué)考研專業(yè)課試題計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合

重慶理工大學(xué)碩士研究生試題專用紙第頁重慶理工大學(xué)2014年攻讀碩士學(xué)位研究生入學(xué)考試試題學(xué)院名稱：計(jì)算機(jī)科學(xué)與工程學(xué)院學(xué)科、專業(yè)名稱：計(jì)算機(jī)科學(xué)與技術(shù)考試科目（代碼）：計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合（810）A卷（試題共6頁）注意：1.所有試題的答案均寫在專用的答題紙上，寫在試題紙上一律無效。2.試題附在考卷內(nèi)交回。一．單選題(每題2分，共50分)1．順序表的第1個(gè)元素存儲(chǔ)地址是100，每個(gè)元素占用2個(gè)存儲(chǔ)單元，則該順序表的第4個(gè)元素地址是（）A．110B．108C．112D．1062．一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖的邊數(shù)為（）A．n(n+1)/2B．n(n-1)/2C．n(n-1)D．3．深度為2（根結(jié)點(diǎn)的層次為1）的滿二叉樹的葉子節(jié)點(diǎn)個(gè)數(shù)為（）A．2B．4C．6D．84．雙向鏈表中每個(gè)結(jié)點(diǎn)的指針域的個(gè)數(shù)為（）A．0B．1C．2D．35．完全二叉樹，按層次序列對(duì)每個(gè)結(jié)點(diǎn)編號(hào)（根結(jié)點(diǎn)編號(hào)為1），則編號(hào)為7的結(jié)點(diǎn)的雙親編號(hào)為（）A．1B．2C．3D．46．下列屬于線性結(jié)構(gòu)的是（）A．線性表B．樹C．查找D．圖7．在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）A．1倍B．2倍C．4倍D．8倍8．棧的特點(diǎn)是（）A．先進(jìn)后出B．先進(jìn)先出C．后進(jìn)后出D．前出前進(jìn)9．深度為3（根的層次號(hào)為1）的滿二叉樹結(jié)點(diǎn)個(gè)數(shù)為（）A．4B．6C．7D．810．不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）A．head==NULLB．head->next==NULLC．head!=NULLD．head->next!=NULL11．有一個(gè)有序表為{2，3，8，10，30}，當(dāng)折半查找到8時(shí)，需要的比較次數(shù)為（）A.1B.2C.3D.412．棧的插入與刪除操作在（）A．棧頂B．棧底C．隊(duì)頭D．隊(duì)尾13．一個(gè)棧的入棧順序是a,b,c，則該棧的不可能的輸出序列是（）A．a(chǎn)bcB．cbaC．a(chǎn)cbD．cab14．設(shè)先序遍歷某二叉樹的序列為ABC，中序遍歷該二叉樹的序列為BAC，則后序遍歷該二叉樹的序列為（）A．ABCB．CBAC．ACBD．BCA15．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（）A．2，3，5，6B．5，2，3，6C．3，2，5，6 D．16．在計(jì)算機(jī)中配置操作系統(tǒng)的主要目的是()A.增強(qiáng)計(jì)算機(jī)的功能B.提高系統(tǒng)資源的利用率C.提高系統(tǒng)的運(yùn)行速度D.合理組織系統(tǒng)的工作流程17．從靜態(tài)角度講，進(jìn)程由程序段、數(shù)據(jù)段和()組成，它是進(jìn)程存在的唯一標(biāo)志。A．JCBB.PCBC.FCBD.代碼段18．臨界區(qū)是指()A.進(jìn)程中用于訪問共享資源的那段代碼。B.進(jìn)程中用于實(shí)現(xiàn)進(jìn)程同步的那段代碼。C.進(jìn)程中用于實(shí)現(xiàn)進(jìn)程互斥的那段代碼。D.進(jìn)程中用于訪問臨界資源的那段代碼。19．下面哪種情況不會(huì)引發(fā)進(jìn)程調(diào)度？()A.進(jìn)程正常結(jié)束或異常中止。B.正在執(zhí)行的進(jìn)程因I/O請(qǐng)求而被阻塞。C.某等待打印機(jī)的進(jìn)程發(fā)現(xiàn)其它使用打印機(jī)的進(jìn)程已經(jīng)打印完畢。D.在引入時(shí)間片的系統(tǒng)中，時(shí)間片用完。20．內(nèi)存管理的基本任務(wù)是提高內(nèi)存的利用率，使多道程序能在不受干擾的環(huán)境中運(yùn)行，這主要是通過下面哪種功能實(shí)現(xiàn)的？()A.內(nèi)存分配 B.內(nèi)存擴(kuò)充C.內(nèi)存保護(hù)D.兌換21．在一般大型系統(tǒng)中，主機(jī)對(duì)外圍設(shè)備的控制可通過通道、控制器和設(shè)備三個(gè)層次來實(shí)現(xiàn)。從下述中選擇一個(gè)正確的敘述。()A.通道控制控制器，設(shè)備在控制器控制下工作。B.控制器可控制通道，設(shè)備在通道控制下工作。C.通道和控制器分別控制設(shè)備。D.控制器控制通道和設(shè)備。22．在文件系統(tǒng)中，必須為每個(gè)文件建立(),其中包括文件名和文件的物理地址等信息。A.用戶文件描述符表B.索引結(jié)點(diǎn)C.文件控制塊D.索引表23．磁盤調(diào)度的策略主要是為了優(yōu)化()A.交換時(shí)間B.尋道時(shí)間C.旋轉(zhuǎn)延遲時(shí)間D.傳輸時(shí)間24．動(dòng)態(tài)重定位的主要目的是使作業(yè)在內(nèi)存中移動(dòng)，動(dòng)態(tài)重定位發(fā)生在()A.編譯過程B.裝入過程C.鏈接過程D.運(yùn)行過程25．在命令行接口中，使命令的執(zhí)行結(jié)果不在屏幕上顯示，用于把第一條命令的輸出作為第二條命令的輸入，第二條命令的輸出作為第三條命令的輸入的功能設(shè)施稱為()A.管道B.鏈接C.脫機(jī)輸入D.聯(lián)機(jī)輸出二．簡(jiǎn)答題(每題5分，共60分)26．計(jì)算程序段的時(shí)間復(fù)雜度。（5分）for(i=1;i<=n;i++)x++;27．設(shè)給定權(quán)集W={2，3，4，7}，試構(gòu)造關(guān)于W的一棵赫夫曼樹，并求其帶權(quán)路徑長(zhǎng)度WPL。（5分）28．設(shè)有一序列30,19,3,61，請(qǐng)按該序列構(gòu)成一棵二叉排序樹，并求其查找成功時(shí)的平均查找長(zhǎng)度ASL。（5分）

29．寫出下圖所示二叉樹的先序，中序和后序遍歷序列。（5分）AABDE30．什么是線性表?線性表的元素之間的關(guān)系是什么?（5分）31．已知待散列的線性表為（8，15，40，63），散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H（K）=Kmod7，若發(fā)生沖突采用線性探查法處理，計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫出散列表。（5分）012345632.請(qǐng)畫圖說明進(jìn)程的三種基本狀態(tài)及各狀態(tài)間的轉(zhuǎn)換，并說明引發(fā)狀態(tài)轉(zhuǎn)換的典型事件。（5分）33.什么是操作系統(tǒng)，簡(jiǎn)述操作系統(tǒng)的主要功能。（5分）34.什么是死鎖，分析死鎖發(fā)生的主要原因。（5分）35.虛擬存儲(chǔ)器的基本特征有哪些？為什么說請(qǐng)求分頁系統(tǒng)是實(shí)現(xiàn)虛擬存儲(chǔ)器是一種方式？（5分）36.什么是中斷，描述CPU訪問中斷的一般過程。（5分）37.在公共汽車上，司機(jī)與售票員的工作流程如下圖所示。為保證乘客安全，司機(jī)和售票員必須密切配合協(xié)調(diào)工作，售票員在關(guān)車門之后向司機(jī)發(fā)送開車信號(hào)，司機(jī)接到開車信號(hào)后啟動(dòng)車輛，汽車正常行駛時(shí)售票員可以售票，到站時(shí)司機(jī)停車，售票員在停車后開門讓乘客下車，請(qǐng)用信號(hào)量來實(shí)現(xiàn)司機(jī)與售票員之間的同步。（5分）三．綜合題(每題10分，共40分)38．編寫一個(gè)函數(shù)，實(shí)現(xiàn)對(duì)數(shù)組a(元素個(gè)數(shù)為n)中元素進(jìn)行冒泡排序的算法。（10分）voidbubblesort(inta[])39．編寫兩個(gè)函數(shù)，分別實(shí)現(xiàn)對(duì)二叉樹的先序遍歷(preorder)和中序遍歷(inorder)的遞歸算法。（10分）二叉樹結(jié)點(diǎn)的結(jié)構(gòu)體為structBiTreeNode{intdata; structBiTreeNode*leftChild; structBiTreeNode*rightChild; };typedefstructBiTreeNodeNode;voidpreorder(Node*t)/*t為指向二叉樹的根結(jié)點(diǎn)的指針*/voidinorder(Node*t)/*t為指向二叉樹的根結(jié)點(diǎn)的指針*/40.（本題10分）有四個(gè)進(jìn)程P1,P2,P3,P4，它們進(jìn)入就緒隊(duì)列的先后順序?yàn)镻1,P2,P3,P4，它們的優(yōu)先級(jí)和需要的處理機(jī)時(shí)間如下表。假定這四個(gè)進(jìn)程在執(zhí)行過程中不會(huì)發(fā)生等待事件，忽略進(jìn)程調(diào)度所花費(fèi)的時(shí)間，從某個(gè)時(shí)刻開始進(jìn)程調(diào)度，請(qǐng)回答下面的問題：進(jìn)程要求的處理時(shí)間優(yōu)先級(jí)P183P261P3225P444(1)采用“先來先服務(wù)”調(diào)度算法時(shí)，寫出進(jìn)程的執(zhí)行順序，計(jì)算各進(jìn)程在就緒隊(duì)列中等待的時(shí)間以及平均等待時(shí)間；（4分）(2)采用“非搶占式的優(yōu)先級(jí)”調(diào)度算法時(shí)，寫出進(jìn)程的執(zhí)行順序，計(jì)算各進(jìn)程在就緒隊(duì)列中等待的時(shí)間以及平均等待時(shí)間；（4分）(3)說明采用“時(shí)間片輪轉(zhuǎn)法”調(diào)度算法時(shí)，寫出進(jìn)程的執(zhí)行順序，計(jì)算各進(jìn)程在系統(tǒng)中停留的時(shí)間以及平均停留的時(shí)間。（2分）41.（本題10分）某系統(tǒng)采用頁式存儲(chǔ)管理策略，請(qǐng)回答