1、2015年重慶理工大學計算機學科專業基礎綜合考研真題A卷一單選題(每題2分，共50分)1一個棧的入棧順序是a,b,c,d,e，則該棧的輸出序列不可能是（ ）Aabcde Baecbd Ccbade Dedcba2二叉樹的二叉鏈表的指針域的個數為（ ）A0 B1 C2 D33隊列的刪除操作在（ ）A隊頭 B隊尾 C棧頂 D棧底4設一組初始記錄關鍵字序列(4，2，3，7)，進行一趟簡單選擇排序的結果為（ ）A4，2，3，7 B4，2，7，3 C2，7，4，3 D2，4，3，75設先序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BCAD，則后序遍歷該二叉樹的序列為（ ）AABCD BBCA

2、D CCBDA DCDBA6深度為5的二叉樹（根結點層次為1）至多結點個數為（ ）A15 B31 C32 D637有7個頂點的無向連通圖最少邊數為（ ）A5 B6 C7 D88三元組表用于表示（ ）A線性表 B雙向鏈表 C稀疏矩陣 D棧9設無向圖G中有n個頂點，則該無向圖的最小生成樹上邊的數目為（ ）An-1 Bn C2n-1 D2n10有序表為3，5，7，9，30，當折半查找到3時，需要的比較次數為（ ）A1 B2 C3 D411設有一個10階的下三角矩陣A（包括對角線），按照以行為序進行順序存儲到連續的55個存儲單元中，每個元素占1個字節的存儲空間，如果A00存儲地址為100，則A43的存

3、儲地址為（ ）A111 B112 C113 D11412與&ai等價的是（ ）A*（a+i） Ba+i C*a+i D&（a+i）13完全二叉樹共有20個結點，按層次序列對每個結點編號（根結點編號為0），則編號為7的結點的右孩子編號為（ ）A13 B14 C15 D1614在一個無向圖中，邊的數目為8，則所有頂點的度數之和為（ ）A16 B8 C24 D3215下列不屬于算法的五個重要特性的是（ ）A有窮性 B確定性 C輸入 D描述性16. 操作系統的主要功能是（ ）。A提高系統的運行速度 B. 增強計算機系統的功能C. 合理組織系統的工作流程 D. 提高系統資源的利用率17.

4、關于程序的并發，下列敘述正確的是（ ）。A 并發是指若干事件在同一時刻發生 B. 并發是指若干事件在不同時刻發生C. 并發是指若干事件在同一時間間隔內發生 D. 并發是指若干事件在不同時間間隔內發生18.進程生存期中的狀態不包括下列哪一種（ ）。A 就緒 B. 執行C. 阻塞 D. 等待 19. 分時系統的響應時間（及時性）主要是根據下面哪一個來確定的？（ ）A 時間片 B. 用戶數目C. 用戶所能接受的等待時間 D. 控制對象所能接受的時延20. 下面關于臨界區的論述中，哪條是正確的？（ ）A. 臨界區是指進程中用于訪問臨界資源的那段代碼 B 臨界區是指進程中用于實現進程互斥的那段代碼 C.

5、 臨界區是指進程中用于實現進程同步的那段代碼D. 臨界區是指進程中用于實現進程共享的那段代碼21.下列算法中，哪一個是只能采用非搶占調度方式？（ ）A高優先級優先法 B. 時間片輪轉法C. FCFS調度算法 D. 短作業優先算法22. 磁盤屬于塊設備，磁盤的I/O控制方式主要利用（ ）A程序I/O方式 B. DMA方式C. 程序中斷方式 D.SPOOLing方式 23. 文件系統主要通過下面哪一種方式來實現文件的按名存取？（ ）A存儲空間管理 B. 文件的安全性管理C. 文件的讀寫管理 D. 目錄管理24. 操作系統向用戶提供多種接口，其中通過下面哪一種接口，用戶可從終端鍵入dir（或ls）來

6、顯示當前目錄的內容？（ ）A脫機用戶接口 B. 聯機命令接口 C. 圖形用戶接口 D. 系統調用接口25.一個計算機系統的虛擬存儲器的最大容量是由下面那一項確定的？（ ）A內存和硬盤容量之和 B. 內存容量C硬盤容量 D. 計算機的字長二簡答題(每題6分，共60分)26圖的定義是什么？圖中元素之間的關系是1對1，1對多，還是多對多？（6分）27 寫出下圖所示二叉樹的先序，中序和后序遍歷序列。（6分）ACEBDFG 28設給定權集W=1，2，3，8，20，試構造關于W的一棵赫夫曼樹，并求其加權路徑長度WPL。（6分）29什么是棧? 棧的特點是什么? 什么是隊列? 隊列的特點是什么?（6分）30

7、已知待散列的線性表為（7，15，23，54，26，20），散列用的一維地址空間為0.7，假定選用的散列函數是H（K）= K mod 8，若發生沖突采用線性探測法處理，計算出每一個元素的散列地址并在下圖中填寫出散列表，并求出平均查找長度ASL。（6分）0123456731.什么是進程？與程序有何不同？（6分）32.在設備管理中引入緩沖的主要原因是什么？一般有哪幾種常見的緩沖類型？（6分）33.說明操作系統與硬件、其它系統軟件以及用戶之間的關系。（6分）34.什么是目錄，目前廣泛采用的目錄結構是哪種？有什么優點？（6分）35.引起進程調度的因素有哪些？（6分）三綜合題(每題10分，共40分)36假

8、設二叉樹采用如下定義的存儲結構： typedef struct node int data; struct node *lchild,*rchild; PBinTree;其中，結點的lchild域和rchild域已分別填有指向其左、右孩子結點的指針。請編寫一個算法，實現用遞歸方法求二叉樹的葉子結點個數。（10分）void Leafcount(PBinTree *bt) 37編寫一個函數，實現對數組a中元素進行快速排序的算法，其中low為下界，high為上屆。（10分）void quickSort(int a, int low, int high)38. 有三個進程A，B，C，分別調用過程get、copy和put對緩沖區S和T進行操作，其中get負責將數據輸入緩沖區S，copy負責從緩沖區S中提取數據并復制到緩沖區T，put負責從緩沖區T取出數據打印，如圖所示，描述get、copy和put的操作過程。（10分）39. 解釋固定分區算法中的首次適應算法（First fit）、最佳適應算法（Best fit）、最差適應算法（Worst fit）的基本思想，假如某個系統有5個固定分區，其長度分別為100KB、500KB、200KB、300KB、600KB