重慶理工大學2021年計算機學科基礎(chǔ)綜合考研真題

重慶理工大學2021年[計算機學科基礎(chǔ)綜合]考研真題一、單選題1．算法分析的目的是（）。A．找出數(shù)據(jù)結(jié)構(gòu)的合理性B．研究算法中的輸入和輸出的關(guān)系C．分析算法的效率以求改進D．分析算法的易懂性和穩(wěn)定性（）。3．若某鏈表最常用的操作是在最后一個結(jié)點之后插入一個元素和刪除最后一個元素，則采用（）存儲方式最節(jié)省運算時間。A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．帶頭結(jié)點的雙循環(huán)鏈表4．在中綴表達式轉(zhuǎn)化為后綴表達式與后綴表達式求值算法中，都需要用到哪種特殊的數(shù)據(jù)結(jié)構(gòu)（）。A．棧B．隊列C．二叉樹D．堆5．一個隊列的入隊序列是1，2，3，4，則隊列的出隊序列只能是（）。A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，16．將含有100個結(jié)點的完全二叉樹從根結(jié)點開始編號，根為0號，后面按從上到下、從左到右的順序?qū)Y(jié)點編號，那么編號為41的結(jié)點的雙親結(jié)點編號為（）。A．42B．40C．21D．20（）8．某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，其前序遍歷序列是（）。A．a(chǎn)cbedB．decabC．deabcD．cedba9．下述編碼中，哪一個不是前綴碼（）。A．(0,10,110,111)B．(11,10,001,101,000)C．(00,010,011,1)D．(1,01,000,001)10．一個有n個頂點的無向圖最多有（）條邊。A．nB．n(n-1)C．n(n-1)/2D．2n11．在現(xiàn)代操作系統(tǒng)中，采用緩沖技術(shù)的主要目的是（）A．改善用戶編程環(huán)境B．提高CPU的處理速度C．實現(xiàn)與設(shè)備無關(guān)D．提高設(shè)備與CPU之間的并行程度12．下列哪個事件不可能在用戶態(tài)發(fā)生？（）A．系統(tǒng)調(diào)用B．外部中斷C．進程切換D．缺頁13．操作系統(tǒng)是對（）進行管理的軟件。A．軟件B．硬件C．計算機資源D．應(yīng)用程序14．子程序調(diào)用和中斷處理子程序都是以壓入堆棧的方式來保護現(xiàn)場的，下面哪個寄存器中的內(nèi)容是中斷處理一定會保存而子程序調(diào)用不用保存的？（）A．程序計數(shù)器B．通用地址寄存器C．通用數(shù)據(jù)寄存器D．程序狀態(tài)寄存器15．進程和程序的一個本質(zhì)區(qū)別是（）A．進程是動態(tài)的，程序是靜態(tài)的B．進程存儲在內(nèi)存，程序存儲在外存C．進程在一個文件中，程序在多個文件中D．進程分時使用CPU，程序獨占CPU16．下列不屬于I/O控制方式的是（）A．程序查詢方式B．覆蓋方式C．DMA方式D．中斷方式17．在內(nèi)存采取分區(qū)管理方式時，分區(qū)的保護措施主要是（）A．界限寄存器進行地址保護B．程序狀態(tài)保護C．用戶權(quán)限保護D．存取控制保護18．在一個文件被用戶進程首次打開的過程中，操作系統(tǒng)需做的是（）A．將文件內(nèi)容讀入內(nèi)存B．將文件控制塊讀入內(nèi)存C．修改文件控制塊的讀寫權(quán)限D(zhuǎn)．將文件的數(shù)據(jù)緩沖區(qū)首指針返回給用戶進程19．計算機系統(tǒng)的二級存儲包括（）A．CPU寄存器和主存緩存B．超高速緩存和內(nèi)存儲器C．主存儲器和輔助存儲器D．ROM和RAM20．在不同速度的設(shè)備之間傳送數(shù)據(jù)（）A．必須采用同步控制方式B．必須采用異步控制方式C．可用同步方式，也可以用異步方式D．必須采用應(yīng)答方式

二、綜合題21．有如下遞歸函數(shù)fact(n)，分析其時間復雜度。fact(intn){if(n<=1)return(1)；①elsereturn(n*fact(n-1))；②}22．有一種數(shù)據(jù)結(jié)構(gòu)B1=（D，R），其中：D={48，25，64，57，82，36，75}，R={<25，36>，<36，48>，<48，57>，<57，64>，<64，75>，<75，82>}，畫出其邏輯結(jié)構(gòu)表示（3分），指出是什么類型的邏輯結(jié)構(gòu)？23．有數(shù)據(jù){43，54，90，46，31}，列出冒泡排序每趟的結(jié)果。編寫冒泡排序算法BubbleSort(RecTypeR[]，intn)的實現(xiàn)程序。24．假設(shè)哈希表長度m=13，采用除留余數(shù)法哈希函數(shù)建立如下關(guān)鍵字集合的哈希表：(16，74，60，43，54，90，46，31，29，88，77)。并采用線性探查法解決沖突。25．有一組關(guān)鍵字序列{66，89，8，123，9，44，55，37，200，127，98}，請將其調(diào)整成初始大根堆，畫出初始大根堆的樹型表示。有一份電文中，使用了a、b、c、d這4個字符，各字符出現(xiàn)頻率如下表。試構(gòu)造對應(yīng)的哈夫曼樹（請按左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)的次序構(gòu)造），并求出每個字符的哈夫曼編碼。字符abcd出現(xiàn)頻率231135對于如圖所示的帶權(quán)無向圖，給出利用普里姆算法（從頂點0開始構(gòu)造）構(gòu)造出的最小生成樹的結(jié)果。（注意：按求解的順序給出最小生成樹的所有邊，每條邊用(i，j)表示，順序錯誤不給分！）28．有如下工程項目的AOE圖，其中數(shù)字表示該項活動需要的天數(shù)：（1）列出圖中各頂點（事件）的最早發(fā)生時間和最遲發(fā)生時間。（2）計算完成該項目所需的時間，指出哪些是關(guān)鍵活動。（3）縮短任一關(guān)鍵活動的時間，是否會縮短整個工程的時間？29．現(xiàn)代操作系統(tǒng)采用分層設(shè)計，用戶程序發(fā)出磁盤I/O請求后需經(jīng)過4個層次的調(diào)用才能進行實際的I/O操作，闡述系統(tǒng)進行I/O操作的4個層次和具體的處理流程。30．在多道系統(tǒng)中，由于有多個進程運行可能導致死鎖，闡述什么是死鎖，有哪些情況可能會導致死鎖，并簡要說明闡述死鎖的條件。31．一個多道批處理系統(tǒng)中僅有A1和A2兩個作業(yè)，A2比A1晚10ms到達，它們的計算和I/O操作順序如下：A1：計算60ms，I/O80ms，計算20msA2：計算120ms，I/O40ms，計算40ms若不考慮調(diào)度和切換時間，則完成兩個作業(yè)需要的時間最少是多少？說明計算依據(jù)？并用示意圖表示進程的運行時間圖。解釋什么是最佳適應(yīng)分區(qū)分配算法和最壞適應(yīng)分區(qū)分配算法？各自的空閑分區(qū)是怎樣組織的？各有什么缺點？設(shè)主存的分配情況如下圖所示。當有一個用戶進程U需申請45KB的存儲區(qū)時，若采用最佳適應(yīng)和最壞適應(yīng)進行分配，U所分到的分區(qū)首地址分別為多少？33．某企業(yè)有多個生產(chǎn)線和多個銷售人員，他們共用可存放100個產(chǎn)品的倉庫，當倉庫未裝滿時，生產(chǎn)線可以將生產(chǎn)的