計(jì)算機(jī)專業(yè)基礎(chǔ)綜合華東理工考研真題集

計(jì)算機(jī)專業(yè)基礎(chǔ)綜合華東理工考研真題集一、華東理工大學(xué)815計(jì)算機(jī)專業(yè)基礎(chǔ)綜合考試大綱815計(jì)算機(jī)專業(yè)基礎(chǔ)綜合碩士研究生招生考試包括數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)組成原理、操作系統(tǒng)三大塊內(nèi)容，各占1/3。考試大綱：一、數(shù)據(jù)結(jié)構(gòu)1數(shù)據(jù)結(jié)構(gòu)的基本概念，算法及其特征，算法的簡(jiǎn)單分析與時(shí)間/空間復(fù)雜度。2線性表的概念特征及的實(shí)現(xiàn)。3棧和隊(duì)列的概念特征及實(shí)現(xiàn)，遞歸。4多維數(shù)組與存儲(chǔ)，特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)。5二叉樹的性質(zhì)及實(shí)現(xiàn)，線索二叉樹，二叉排序樹，平衡二叉樹，哈夫曼樹，堆的建立，插入和刪除算法的實(shí)現(xiàn)。6樹與森林的概念，存儲(chǔ)及操作算法，B樹，B+樹的定義及操作的實(shí)現(xiàn)。7圖的概念，存儲(chǔ)表示，操作及應(yīng)用的實(shí)現(xiàn)。8查找的概念及典型查找算法的實(shí)現(xiàn)，哈希表。9排序的概念及典型排序算法的實(shí)現(xiàn)。二、計(jì)算機(jī)組成原理1計(jì)算機(jī)概要與技術(shù)：程序概念入門；硬件概念入門；性能和功耗；性能的測(cè)試方法，Amdahl定律。2指令：計(jì)算機(jī)的語(yǔ)言；計(jì)算機(jī)的操作數(shù)，不同的尋址方式；各種指令的基本格式以及原理，計(jì)算機(jī)硬件對(duì)過(guò)程的支持；基本的MIPS指令集體系結(jié)構(gòu)。3計(jì)算機(jī)的算術(shù)運(yùn)算：計(jì)算機(jī)加減乘除法運(yùn)算。浮點(diǎn)數(shù)表示，正￡￡754標(biāo)準(zhǔn)，浮點(diǎn)運(yùn)算。4處理器：數(shù)據(jù)通路的概念以及建立數(shù)據(jù)通路的思想；流水線概述；流水線數(shù)據(jù)通路及其控制；結(jié)構(gòu)冒險(xiǎn)、數(shù)據(jù)冒險(xiǎn)、控制冒險(xiǎn)；數(shù)據(jù)冒險(xiǎn)的轉(zhuǎn)發(fā)與阻塞；控制冒險(xiǎn)中假設(shè)分支不發(fā)生、縮短分支的延遲、動(dòng)態(tài)分支預(yù)測(cè)的思想與實(shí)現(xiàn)方法。5存儲(chǔ)器的層次結(jié)構(gòu)：大容量存儲(chǔ)器的層次結(jié)構(gòu)；cache的基本原理；cache的性能評(píng)估與改進(jìn)。虛擬存儲(chǔ)器；集成虛擬存儲(chǔ)器、快表和cache。虛擬存儲(chǔ)器、cache、內(nèi)存數(shù)據(jù)一致性問題。6存儲(chǔ)系統(tǒng)和其他I/O主題：可信度、可靠性和可用性；磁盤存儲(chǔ)器；flash；處理器、內(nèi)存及I/O設(shè)備的連接；廉價(jià)磁盤冗余陣列。三、操作系統(tǒng)1操作系統(tǒng)的概念、特征、功能和提供的服務(wù)。2進(jìn)程與線程，處理機(jī)調(diào)度，進(jìn)程同步與互斥（信息、量，經(jīng)典同步問題），死鎖（系統(tǒng)安全狀態(tài)，銀行家算法）。3內(nèi)存管理（分頁(yè)管理方式，分段管理方式），虛擬內(nèi)存管理（請(qǐng)求分頁(yè)管理方式，頁(yè)面置換算法）。4文件管理，設(shè)備管理，磁盤組織與管理（磁盤調(diào)度算法）。二、配套數(shù)據(jù)結(jié)構(gòu)考研真題解析第一部分考研真題精選一、單項(xiàng)選擇題1若元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許連續(xù)三次進(jìn)行退棧操作，則不可能得到的出棧序列是（ ）。［計(jì)算機(jī)統(tǒng)考（408）2010年研］【答案】D@@【解析】4個(gè)選項(xiàng)所給序列的進(jìn)、出棧操作序列分別為：選項(xiàng)A:Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop選項(xiàng)B：Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop選項(xiàng)C：Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop選項(xiàng)D:Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop按照題目要求，不允許連續(xù)三次進(jìn)行退棧操作，所以選項(xiàng)D所給序列為不可能得到的出棧順序。2若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（ ）。［計(jì)算機(jī)統(tǒng)考（408）2012年研］A.只有eB.有e、bC.有e、cD.無(wú)法確定【答案】A@@【解析】由題目可知，若一棵二叉樹的前序遍歷序列為a,e,b,d,c,后序遍歷序列為5,。~,6〃，其中a為這棵二叉樹的根結(jié)點(diǎn)，接下來(lái)，在前序遍歷的第二個(gè)結(jié)點(diǎn)為e，而后序遍歷的倒數(shù)第二個(gè)結(jié)點(diǎn)為e，說(shuō)明a的孩子^結(jié)點(diǎn)只有e。3循環(huán)隊(duì)列放在一維數(shù)組A［0..M-1］中，endl指向隊(duì)頭元素，end2指向隊(duì)尾元素的后一個(gè)位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容納M-1個(gè)元素。初始時(shí)為空，下列判斷隊(duì)空和隊(duì)滿的條件中，正確的是( )。［計(jì)算機(jī)統(tǒng)考(408)2014年研］A.隊(duì)空：endl==end2;隊(duì)滿：endl==(end2+1)modMB.隊(duì)空：end1==end2;隊(duì)滿：end2==(end1+1)mod(M-1)C.隊(duì)空：end2==(end1+1)modM;隊(duì)滿：end1==(end2+1)modMD.隊(duì)空：end1==(end2+1)modM;隊(duì)滿：end2==(end1+1)mod(M-1)【答案】A@@【解析】在循環(huán)隊(duì)列中，在少用一個(gè)元素空間的前提下，可約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等，則隊(duì)滿。而隊(duì)空的條件還是首尾指針是否相等。

4已知關(guān)鍵字序列5,8,12,19,28,20,15,22是小根堆（最小堆），插入關(guān)鍵字3入關(guān)鍵字3，調(diào)整后的小根堆是（）。［計(jì)算機(jī)統(tǒng)考（408）2009年研］A.3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,19【答案】A@@【解析】在堆中插入一個(gè)元素后，將不再滿足堆的性質(zhì)。為了使其成為新堆，需要重新調(diào)整剩余元素的位置。具體過(guò)程如圖（1）~（5）所示，（1）為原堆，（2）為插入3后，（3）、（4）為調(diào)整過(guò)程，（5）為調(diào)整后的小根堆。

5下列選項(xiàng)中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是（ ）。［計(jì)算機(jī)統(tǒng)考（408）2015年研］A.500,200,450,180B.500,450,200,180C.180,500,200,450D.180,200,500,450【答案】A@@【解析】折半查找也稱二分查找（BinarySearch），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。折半查找的過(guò)程是：先確定待查找記錄所在的范圍，然后逐步縮小范圍直到找到或找不到該記錄為止。折半查找的關(guān)鍵字序列滿足：對(duì)每一個(gè)關(guān)鍵字，其后面的所有關(guān)鍵字序列或者都小于等于該關(guān)鍵字或者都大于等于該關(guān)鍵字。A項(xiàng)錯(cuò)誤，第三次上比較的關(guān)鍵字為450，說(shuō)明待查關(guān)鍵字位于200~450間，所以第四次比較時(shí)不會(huì)遇到關(guān)鍵字180。6已知字符串S為"abaabaabacacaabaabcc"，模式串t為"abaabc"，采用KMP算法進(jìn)行匹配，第一次出現(xiàn)“失配"（s[i]!=t[i]）時(shí)，閆二5,則下次開始匹配時(shí)，i和j的值分別是（ ）。[計(jì)算機(jī)統(tǒng)考（408）2015年研]A.i=1,j=0B.i=5,j=0C.i=5,j=2D.i=6,j=2【答案】C@@【解析】模式匹配（KMP）算法對(duì)普通的暴力匹配的改進(jìn)在于：每當(dāng)匹配過(guò)程中匹配失敗時(shí)，主串（本題為S）的指針（i）不需要回溯，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式串（t）向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。模式串“滑動(dòng)”的距離是由模式串（t）本身決定的，即t的子串t[0...j-1]中前綴串和后綴串相等的最長(zhǎng)長(zhǎng)度。本題中第一次失配i=5,字串為匕522匕’，其相等且最長(zhǎng)的前后綴為“ab”，一次下一個(gè)）二2。7下列關(guān)于無(wú)向連通圖特性的敘述中，正確的是（ ）。［計(jì)算機(jī)統(tǒng)考（408）2009年研］I.所有的頂點(diǎn)的度之和為偶數(shù)口.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1田.至少有一個(gè)頂點(diǎn)的度為1A.只有IB.只有口C.I和口D.I和田【答案】A@@【解析】在圖中，頂點(diǎn)的度TD（Vi）之和與邊的數(shù)目滿足關(guān)系式：2=1其中，n為圖的總結(jié)點(diǎn)數(shù)，e為總邊數(shù)。因此，1項(xiàng)正確。對(duì)于口、皿頁(yè)中的特性不是一般無(wú)向連通圖的特性，可以輕松地舉出反例?！爸辽儆幸粋€(gè)頂點(diǎn)的度為1”的反例如下圖（1）所示，“邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1”的反例如下圖（2）所示。8下列敘述中，不符合m階B樹定義要求的是（ ）。［計(jì)算機(jī)統(tǒng)考（408）2009年研］A.根結(jié)點(diǎn)最多有m棵子樹B.所有葉結(jié)點(diǎn)都在同一層上C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D.葉結(jié)點(diǎn)之間通過(guò)指針鏈接【答案】D@@【解析】B樹就是指B-樹。根據(jù)B-樹的定義，m階B-樹中每個(gè)結(jié)點(diǎn)最多有m個(gè)分支，因此，根結(jié)點(diǎn)最多有m棵子樹，A項(xiàng)正確；B-樹中所有葉結(jié)點(diǎn)都在最底層，位于同一層，B項(xiàng)正確；結(jié)點(diǎn)內(nèi)各關(guān)鍵字互不相等且有序排列，C項(xiàng)正確。但是，所有葉子結(jié)點(diǎn)之間通過(guò)指針鏈接，是B+樹的定義，而B-樹中沒有。因此，D項(xiàng)是錯(cuò)誤的。9排序過(guò)程中，對(duì)尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束時(shí)都至少能夠確定一個(gè)元素最終位置的方法是（ ）。［計(jì)算機(jī)統(tǒng)考（408）