沈陽(yáng)農(nóng)業(yè)大學(xué)信息與電氣工程學(xué)院計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)歷考研真題匯編附答案

1、沈陽(yáng)師范大學(xué)教育技術(shù)學(xué)院862計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基 礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）歷年考研真題匯編附答案最新資料，WORD式，可編輯修改！目錄第一部分沈陽(yáng)師范大學(xué)教育技術(shù)學(xué)院 862計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作 系統(tǒng)）歷年考研真題匯編 2014年沈陽(yáng)師范大學(xué)教育技術(shù)學(xué)院 867計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合 （數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）考研真題2013年沈陽(yáng)師范大學(xué)教育技術(shù)學(xué)院 867計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合 （數(shù)據(jù)結(jié)構(gòu)、操作 系統(tǒng)）考研真題第二部分全國(guó)碩士研究生入學(xué)統(tǒng)一考試 408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合歷年真題及詳解2012年全國(guó)碩士研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題 2012年全國(guó)碩士

2、研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題及詳解2011年全國(guó)攸士研究生入學(xué)統(tǒng)受試408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題 2011年全國(guó)攸士研究生入學(xué)統(tǒng)受試408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題及詳解2010年全國(guó)秋十研究生入學(xué)統(tǒng)支試408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題 2010年全國(guó)攸士研究生入學(xué)統(tǒng)受試408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題及詳解2009年全國(guó)攸士研究生入學(xué)統(tǒng)受試408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題 2009年全國(guó)攸士研究生入學(xué)統(tǒng)受試408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題及詳解說(shuō)明：沈陽(yáng)師范大學(xué)2012年之前參加全國(guó)統(tǒng)考 408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合，2013 年開(kāi)始自主命題，科目改為867計(jì)算機(jī)學(xué)

3、科專(zhuān)業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)），2015 年科目代碼改為862。為幫助考生全面復(fù)習(xí)， 特提供20092012年408計(jì)算機(jī)學(xué)科專(zhuān)業(yè) 基礎(chǔ)綜合真題及詳解。第一部分沈陽(yáng)師范大學(xué)教育技術(shù)學(xué)院 862計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、 操作系統(tǒng)）歷年考研真題匯編2014年沈陽(yáng)師范大學(xué)教育技術(shù)學(xué)院867計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）考研真題科目代碼：867科目名稱：計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）適用專(zhuān)業(yè)名稱：計(jì)算機(jī)應(yīng)用技術(shù)考生注意：請(qǐng)將答案寫(xiě)在答題紙上，寫(xiě)在本題簽及草紙上無(wú)效?？荚嚭蟊绢}簽同答題紙一并交回。一、單項(xiàng)選擇題（共10題，每題2分，合計(jì)20分）1.某算法的時(shí)間

4、復(fù)雜度為 O（n2）,表明該算法（）oA問(wèn)題規(guī)模是n2B.執(zhí)行時(shí)間等于n2C.執(zhí)行時(shí)間與n2成正比D.問(wèn)題規(guī)模與n2成正比2設(shè)線性表有n個(gè)元素，以下操作中，（）在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更 局。A輸出第i （1i next= p-next ； p-next=s;t=p-data; p-data= s-data;s-data= t;B. p-next=s ; s-next= p-next；t=p-data； p-data= s-data;s-data= t;C. s-next= p-next ； p-next=s;p-data= s-data ; t=p-data;s-data= t;D.

5、 p-next=s ; s-next= p-next；t= s-data; s-data p-data;p-data= t;4 .已知一個(gè)棧的進(jìn)棧序列是1, 2, 3, ,n,其輸出序列是p1,p2,，p%若p1=n,則pi的值（）。A iB. n-iC. n-i+1D.不確定5.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，常用的兩種方法是（）。A二元組和散列表B.三元組和十字鏈表C.三角矩陣和對(duì)角矩陣D.對(duì)角矩陣和十字鏈表6 .廣義表（a） , a）的表頭和表尾分別是（）。A. （ a）和（a）B. a和（a）C. （a）和 aD. （ （ a）和（a）7 .已知二叉樹(shù)的先序序列為 ABDEGCF中序序列為DB

6、GEACF則后序序列為（）,A. GEDBFCAB. DGEBFCAC. DGEBAFCD. EBFDGCA8 . 一棵完全二叉樹(shù)上有1000個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）。A 250B. 500C. 505D. 5019 .線索二叉樹(shù)是一種（）結(jié)構(gòu)。A.邏輯10 邏輯和存儲(chǔ)C.物理D.線性11 .以數(shù)據(jù)集2 , 5, 7, 9, 13為權(quán)值構(gòu)造一棵哈夫曼樹(shù)，則其帶權(quán)路徑長(zhǎng)為（）A 78B. 80C. 81D. 7911.一個(gè)有向圖的鄰接表存儲(chǔ)如圖1所示，現(xiàn)按深度優(yōu)先搜索遍歷，從頂點(diǎn) 必出發(fā),所得到的頂點(diǎn)序列是（）?？赡懿淮嬖贒.13 .若一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?，則可斷定該有

7、向圖（）。A是個(gè)有根有向圖B.是個(gè)強(qiáng)連通圖C.含有多個(gè)入度為0的頂點(diǎn)D.含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量14 .順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（）的線性表。A哈希存儲(chǔ)B.索引存儲(chǔ)C.壓縮存儲(chǔ)D.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)15.在含有27個(gè)結(jié)點(diǎn)的二叉樹(shù)排序樹(shù)上，查找關(guān)鍵字為35的結(jié)點(diǎn)，則依次比較的關(guān)鍵字有可能是（）A. 28, 36, 18, 46, 35B. 18, 36, 28, 46, 35C. 46, 28, 18, 36, 35D. 46, 36, 18, 28, 3516.在有序表a 1.20中，采用二分查找算法查找元素值等于 a12的元素，所 比較過(guò)元素的次數(shù)為（）。A. 4B. 5C. 3D.

8、 617.數(shù)據(jù)序列 8, 9, 10, 4, 5, 6, 20, 1, 2 只能是下列排序算法中的（）的兩趟排序后的結(jié)果。A選擇排序B.冒泡排序C.插入排序D.堆排序18.就平均性能而言，目前最好的內(nèi)部排序方法是（）排序法。A.冒泡排序B.希爾排序C.插入排序D.快速排序19.有一組數(shù)據(jù) 15, 9, 7, 8, 20,-1 , 7, 4,用堆排序的篩選方法建立的初 始堆為（）。A. -1,4,5, 9, 20,7, 15,7B. -1,7,15, 7, 4,8, 20,9C. -1,4,7, 8, 20,15, 7,9D. A, B, C都不對(duì)20 .下面說(shuō)法不正確的是（）。A.關(guān)鍵活動(dòng)不按

9、期完成就會(huì)影響整個(gè)工程的完成時(shí)間B.任何一個(gè)關(guān)鍵活動(dòng)提前完成，將使整個(gè)工程提前完成C.所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程提前完成D.某些關(guān)鍵活動(dòng)若提前完成，將使整個(gè)工程提前完成21 .下列選項(xiàng)中，（）不是操作系統(tǒng)關(guān)心的主要問(wèn)題。A.管理計(jì)算機(jī)裸機(jī)B.設(shè)計(jì)、提供用戶程序與計(jì)算機(jī)硬件系統(tǒng)的界面C.管理計(jì)算機(jī)系統(tǒng)資源D.高級(jí)程序設(shè)計(jì)語(yǔ)言的編譯器22 .系統(tǒng)功能調(diào)用是（）。A.用戶編寫(xiě)的一個(gè)子程序B.高級(jí)語(yǔ)言中的庫(kù)程序C.操作系統(tǒng)中的一條命令D.操作系統(tǒng)向用戶程序提供的接口23 .在處理機(jī)管理中，當(dāng)（）時(shí)，進(jìn)程從阻塞狀態(tài)變?yōu)榫途w狀態(tài)。A.進(jìn)程被調(diào)度程序選中B.等待某一事件發(fā)生C.等待的事件發(fā)生D.時(shí)間

10、片用完24 .高級(jí)調(diào)度是（）。A進(jìn)程調(diào)度B.作業(yè)調(diào)度C.程序調(diào)度D.設(shè)備調(diào)度25 .臨界區(qū)是（）。A 一個(gè)緩沖區(qū)B. 一段共享數(shù)據(jù)區(qū)C. 一段程序D. 一個(gè)互斥資源26 .產(chǎn)生死鎖的根本原因是（）。A資源共享B.并發(fā)執(zhí)行的進(jìn)程太多C.進(jìn)程推進(jìn)順序非法D.以上3個(gè)因素全是27 .在下述存儲(chǔ)管理方案中，（）管理方式要求作業(yè)占用連續(xù)的存儲(chǔ)空間。A分區(qū)B.分頁(yè)C.分段D.段頁(yè)式28 .操作系統(tǒng)中對(duì)數(shù)據(jù)進(jìn)行管理的部分叫做（）。A數(shù)據(jù)庫(kù)系統(tǒng)B.文件系統(tǒng)C.檢索系統(tǒng)D.數(shù)據(jù)存儲(chǔ)系統(tǒng)29 .下列文件中屬于邏輯結(jié)構(gòu)的文件是（）。A連續(xù)文件B.系統(tǒng)文件C.散列文件D.流式文件30 .在磁盤(pán)文件系統(tǒng)中，對(duì)于下列文件

11、物理結(jié)構(gòu)，（）不具有直接讀寫(xiě)文件任意一個(gè)記錄的能力。A.順序結(jié)構(gòu)B.鏈接結(jié)構(gòu)C.索引結(jié)構(gòu)D.散列結(jié)構(gòu)二、算法設(shè)計(jì)題（共2題，每題10分，合計(jì)20分）31 .設(shè)C=a1,b1,a2,b2,an, bn 為一線性表，采用帶頭結(jié)點(diǎn)的 hc單鏈表存放， 設(shè)計(jì)一個(gè)就地算法，將其拆分為兩個(gè)線性表，使得： A= a1,a2,，an,B= b1, b2, bn32 .冒泡排序的算法是把大的元素向上移動(dòng)（氣泡的上升）也可以把最小的元素向 下移動(dòng)（氣泡的下沉）。請(qǐng)給出上浮和下沉過(guò)程交替的冒泡排序算法。三、綜合應(yīng)用題（共6題，合計(jì)70分）33 .寫(xiě)出用Prim算法構(gòu)造圖2最小生成樹(shù)的過(guò)程。（10分） 圖2無(wú)向網(wǎng)34

12、 .關(guān)鍵字序列 A=（36,27,68,33,97,40,81,24,23,90,32,14） 共 12 個(gè)數(shù)據(jù)，哈希表 長(zhǎng)為13,采用的哈希函數(shù)為：h（key尸key %13如果采用開(kāi)放定址的線性探測(cè)再散列方 法解決沖突，請(qǐng)構(gòu)造哈希表并求其查找成功時(shí)的平均查找長(zhǎng)度。（10分）35 .在如圖3所示的AOEW,求：（10分）（1）完成此工程最少需要的多少天（設(shè)邊上權(quán)值為天數(shù)）。（2）是否存在某項(xiàng)活動(dòng)，當(dāng)其提高速度后能使整個(gè)工程縮短工期。a12=4a1=a8=1圖3 AOE網(wǎng)79需9=4 SJ584136.若有以下四個(gè)作業(yè)同2寸到達(dá)鈾并怔作業(yè)名作業(yè)作業(yè)作業(yè)作業(yè)1234cpuH間（分鐘）a6=312

13、=683_假設(shè)系統(tǒng)中沒(méi)有其他作業(yè)，現(xiàn)a宛fl(15給出作業(yè)調(diào)度順序并求出平均作業(yè)周轉(zhuǎn)時(shí)間T,平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W分）37 .在一個(gè)請(qǐng)求式頁(yè)式管理系統(tǒng)中，某程序在內(nèi)存中分配三個(gè)頁(yè)面，初始為空 .頁(yè) 面走向?yàn)椋? ,3,2, 1,4,3,5,4,3,2,1,5。用學(xué)過(guò)的頁(yè)面值換算法FIFO算出缺頁(yè)次數(shù)。給出執(zhí)行過(guò)程中內(nèi)存頁(yè)面的變化情況。（15分）38 .在4*100m接力賽中，4個(gè)運(yùn)動(dòng)員之間存在如下關(guān)系圖 4,運(yùn)動(dòng)員1跑到終點(diǎn)把 接力棒交給運(yùn)動(dòng)員2,，運(yùn)動(dòng)員4接到棒后跑完全程。試用信號(hào)量機(jī)制進(jìn)行描述。 試寫(xiě)出這四個(gè)并發(fā)進(jìn)程能正確執(zhí)行的程序。（10分）關(guān)系圖第二部分全國(guó)碩士研究生入學(xué)統(tǒng)一考試408

14、計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合歷年真題及詳解2012年全國(guó)碩士研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題一、單項(xiàng)選擇題：l40小題。每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中， 只有一個(gè)選項(xiàng)是最符合題目要求的。1 .求整數(shù)n (n0)階乘的算法如下，其時(shí)間復(fù)雜度是()。A. O (log2n)B. 0 (n)C. O (nlog2n) 一， 2、D. O ( n )2 .已知操作符包括+、 -、 *、 /、(和)。將中綴表達(dá) 式a+b-a* ( (c+d) /e-f ) +g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式 ab+acd+e/f-*-g+時(shí)，用棧來(lái) 存放暫時(shí)還不能確定運(yùn)算次序的操作符。若棧初始時(shí)為空

15、，則轉(zhuǎn)換過(guò)程中同時(shí)保存在棧 中的操作符的最大個(gè)數(shù)是()。A. 5B. 7C. 8D. 113.若一棵二叉樹(shù)的前序遍歷序列為a, e, b, d, c,后序遍歷序列為b, c, d, e,a,則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)()。A只有eB.有 e、bC.有 e、cD.無(wú)法確定4 .若平衡二叉樹(shù)的高度為 6,且所有非葉結(jié)點(diǎn)的平衡因子均為1,則該平衡二叉樹(shù)的結(jié)點(diǎn)總數(shù)為()。A. 12B. 20C. 32D. 335 .對(duì)有2個(gè)頂點(diǎn)e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí) 間復(fù)雜度是()。A. 0 (n)B. 0 (e)C. O (n+e)D. O (nXe)6 .若用鄰接矩陣存儲(chǔ)有向圖，矩陣中主

16、對(duì)角線以下的元素均為零，則關(guān)于該圖拓 撲序列的結(jié)論是()。A.存在，且唯一8 .存在，且不唯一不唯一C.存在，可能不唯一D.無(wú)法確定是否存在7 .有向帶權(quán)圖如題7圖所示，若采用迪杰斯特拉（Dijkstra ）算法求從源點(diǎn)a到 其他各頂點(diǎn)的最短路徑，則得到的第一條最短路徑的目標(biāo)頂點(diǎn)是b,第二條最短路徑的目標(biāo)頂點(diǎn)是c,后續(xù)得到的其余各最短路徑的目標(biāo)頂點(diǎn)依次是（）。題7圖有向帶權(quán)圖A. d, e, fB. e, d, fC. f, d, eD. f, e, d8 .下列關(guān)于最小生成樹(shù)的敘述中，正確的是（）。I.最小生成樹(shù)的代價(jià)唯一n.所有權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹(shù)中 m.使用普里姆（P

17、rim）算法從不同頂點(diǎn)開(kāi)始得到的最小生成樹(shù)一定相同IV.使用普里姆算法和克魯斯卡爾（Kruskal ）算法得到的最小生成樹(shù)總不相同A僅IB.僅nC.僅 I、mD.僅 n、iv9 .設(shè)有一棵3階B樹(shù)，如題9圖所示。刪除關(guān)鍵字78得到一棵新B樹(shù)，其最右葉 結(jié)點(diǎn)所含的關(guān)鍵字是（）。題9圖3二叉樹(shù)圖A. 60B. 60, 62C. 62, 65D. 6510 .排序過(guò)程中，對(duì)尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下 列排序方法中，每一趟排序結(jié)束時(shí)都至少能夠確定一個(gè)元素最終位置的方法是（）。I.簡(jiǎn)單選擇排序 n .希爾排序田.快速排序iv.堆排V.二路歸并排序A.僅 I、m、IVB.僅 I

18、、n、mC.僅n、m、ivD.僅田、IV、V11 .對(duì)同一待排序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同 之處是（）。A.排序的總趟數(shù)B.元素的移動(dòng)次數(shù)C.使用輔助空間的數(shù)量D.元素之間的比較次數(shù)12 .假定基準(zhǔn)程序A在某計(jì)算機(jī)上的運(yùn)行時(shí)間為l00秒，其中90秒為CPU時(shí)間， 其余為I/O時(shí)間。若CPU1度提高50%, I/O速度不變，則運(yùn)行基準(zhǔn)程序 A所耗費(fèi)的時(shí) 同是（）。A. 55 秒B. 60 秒C. 65 秒D. 70 秒13.假定編譯器規(guī)定語(yǔ)句：unsigned short XC語(yǔ)百）。A.B.C.D.00007FFAH 0000FFFAH FFFF7FFAH FFF

19、FFFFAH14. float類(lèi)型（即IEEE754單精度浮點(diǎn)數(shù)格式）能表示的最大正整數(shù)是（A.B.C.D.2126-22127-22127-22128-2103104103104int和short類(lèi)型長(zhǎng)度分別為32位和16位，執(zhí)行下列= 65530; unsigned int y=X：得到 y 的機(jī)器數(shù)為（15 .某計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址，采用小端方式存放數(shù)據(jù)。假定編譯器規(guī)定int和short型長(zhǎng)度分別為32位和16位，并且數(shù)據(jù)按邊界對(duì)齊存儲(chǔ)。某C語(yǔ)言程序段如下：若record變量的首地址為 0xC008,則地址0xC008中內(nèi)容及record.c 的地址分別 為（）。A. 0x00、0xC

20、00DB. 0x00、0xCOOEC. 0x11、0xC00DD. 0x11、0xC00E16 .下列關(guān)于閃存（FlashMemory）的敘述中，錯(cuò)誤的是（）。A.信息可讀可寫(xiě)，并且讀、寫(xiě)速度一樣快17 存儲(chǔ)元由MOST組成，是一種半導(dǎo)體存儲(chǔ)器C.掉電后信息不丟失，是一種非易失性存儲(chǔ)器D.采用隨機(jī)訪問(wèn)方式，可替代計(jì)算機(jī)外部存儲(chǔ)器17.假設(shè)某計(jì)算機(jī)按字編址，Cache有4個(gè)行，Cache和主存之間交換的塊大小為l個(gè)字。若Cache的內(nèi)容初始為空，采用 2路組相聯(lián)映射方式和 LRU替換算法，當(dāng)訪問(wèn)的 主存地址依次為 0, 4, 8, 2, 0, 6, 8, 6, 4, 8時(shí)，命中Cache的次數(shù)是

21、（）。A. 1B. 2C. 3D. 418 .某計(jì)算機(jī)的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直 接編碼法，共有33個(gè)微命令，構(gòu)成5個(gè)互斥類(lèi)，分別包含7、3、12、5和6個(gè)微命令, 則操作控制字段至少有（）。A. 5位B. 6位C. 15 位D. 33 位19 .某同步總線的時(shí)鐘頻率為100MHz,寬度為32位，地址/數(shù)據(jù)線復(fù)用，每傳輸 一個(gè)地址或數(shù)據(jù)占用一個(gè)時(shí)鐘周期。若該總線支持突發(fā)（猝發(fā)）傳輸方式，則一次“主 存寫(xiě)”總線事務(wù)傳輸128位數(shù)據(jù)所需要的時(shí)間至少是（）。）。A. 20nsB. 40nsC. 50nsD. 80ns20 .下列關(guān)于USB總線特性的描述中，錯(cuò)誤的是（

22、）。A.可實(shí)現(xiàn)外設(shè)的即插即用和熱插拔B.可通過(guò)級(jí)聯(lián)方式連接多臺(tái)外設(shè)C.是一種通信總線，可連接不同外設(shè)D.同時(shí)可傳輸2位數(shù)據(jù)，數(shù)據(jù)傳輸率高21 .下列選項(xiàng)中，在I/O總線的數(shù)據(jù)線上傳輸?shù)男畔ǎǎ?。I. I/O接口中的命令字n. I/O接口中的狀態(tài)字 m.中斷類(lèi)型號(hào)A.僅 I、nB.僅 I、mC.僅n、田d. I 、 n 、田22.響應(yīng)外部中斷的過(guò)程中，中斷隱指令完成的操作，除保護(hù)斷點(diǎn)外，還包括（）I.開(kāi)關(guān)中斷 n.保存通用寄存器的內(nèi)容田.形成中斷服務(wù)程序入口地址并送PCA.僅 I、nB.僅 i、mC.僅n、田d. i 、 n 、田23.下列選項(xiàng)中，不可能在用戶態(tài)發(fā)生的事件是（）。A系統(tǒng)調(diào)用B

23、.外部中斷C.進(jìn)程切換D.缺頁(yè)24.中斷處理和子程序調(diào)用都需要壓棧以保護(hù)現(xiàn)場(chǎng)，中斷處理一定會(huì)保存而子程序 調(diào)用不需要保存其內(nèi)容的是（）。A.程序計(jì)數(shù)器B.程序狀態(tài)字寄存器C.通用數(shù)據(jù)寄存器D.通用地址寄存器25.下列關(guān)于虛擬存儲(chǔ)的敘述中，正確的是（）。A.虛擬存儲(chǔ)只能基于連續(xù)分配技術(shù)B.虛擬存儲(chǔ)只能基于非連續(xù)分配技術(shù)C.虛擬存儲(chǔ)容量只受外存容量的限制D.虛擬存儲(chǔ)容量只受內(nèi)存容量的限制26.操作系統(tǒng)的I/O子系統(tǒng)通常由四個(gè)層次組成，每一層明確定義了與鄰近層次 的接口。其合理的層次組織排列順序是（）。A.用戶級(jí)I /O軟件、設(shè)備無(wú)關(guān)軟件、設(shè)備驅(qū)動(dòng)程序、中斷處理程序B.用戶級(jí)I /O軟件、設(shè)備無(wú)關(guān)軟

24、件、中斷處理程序、設(shè)備驅(qū)動(dòng)程序C.用戶級(jí)I /O軟件、設(shè)備驅(qū)動(dòng)程序、設(shè)備無(wú)關(guān)軟件、中斷處理程序D.用戶級(jí)I /O軟件、中斷處理程序、設(shè)備無(wú)關(guān)軟件、設(shè)備驅(qū)動(dòng)程序27.假設(shè)5個(gè)進(jìn)程P0、Pl、P2、P3、P4共享三類(lèi)資源 Rl、R2 R3,這些資源總數(shù) 分別為18、6、22 o T0時(shí)刻的資源分配情況如題 27表所示，此時(shí)存在的一個(gè)安全序列是 （ ）。題27表資源分配情況表已分配資源資源最大需求進(jìn)程R1R2R3R1R2R3PO3235510P14O3536P24O54O11P32O4425P4314424A. P0, P2, P4, Pl , P3B. Pl, P0, P3, P4, P2C. P

25、2, Pl , P0, P3, P4D. P3, P4, P2, Pl , P0P028.若一個(gè)用戶進(jìn)程通過(guò)read系統(tǒng)調(diào)用讀取一個(gè)磁盤(pán)文件中的數(shù)據(jù)，則下列關(guān)于 此過(guò)程的敘述中，正確的是（）。I .若該文件的數(shù)據(jù)不在內(nèi)存，則該進(jìn)程進(jìn)入睡眠等待狀態(tài)；n .請(qǐng)求 read系統(tǒng) 調(diào)用會(huì)導(dǎo)致CPU從用戶態(tài)切換到核心態(tài)；m. read系統(tǒng)調(diào)用的參數(shù)應(yīng)包含文件的名稱A.僅 I、nB.僅 I、mC.僅n、田d. I、 n和田29. 一個(gè)多道批處理系統(tǒng)中僅有 Pl和P2兩個(gè)作業(yè)，P2比Pl晚5ms到達(dá)。它們的 計(jì)算和I/0操作順序如下：P1:計(jì)算60ms, I/O 80ms,計(jì)算20ms； P2:計(jì)算120m

26、s, I/O 40ms ，計(jì)算40ms若不考慮調(diào)度和切換時(shí)間，則完成兩個(gè)作業(yè)需要的時(shí)間最 少是（）。A. 240msB. 260msC. 340msD. 360ms30 .若某單處理器多進(jìn)程系統(tǒng)中有多個(gè)就緒態(tài)進(jìn)程，則下列關(guān)于處理機(jī)調(diào)度的敘述 中，錯(cuò)誤的是（）。A.在進(jìn)程結(jié)束時(shí)能進(jìn)行處理機(jī)調(diào)度B.創(chuàng)建新進(jìn)程后能進(jìn)行處理機(jī)調(diào)度C.在進(jìn)程處于臨界區(qū)時(shí)不能進(jìn)行處理機(jī)調(diào)度D.在系統(tǒng)調(diào)用完成并返回用戶態(tài)時(shí)能進(jìn)行處理機(jī)調(diào)度31 .下列關(guān)于進(jìn)程和線程的敘述中，正確的是（）。A.不管系統(tǒng)是否支持線程，進(jìn)程都是資源分配的基本單位B.線程是資源分配的基本單位，進(jìn)程是調(diào)度的基本單位C.系統(tǒng)級(jí)線程和用戶級(jí)線程的切換都需

27、要內(nèi)核的支持D.同一進(jìn)程中的各個(gè)線程擁有各自不同的地址空間32 .下列選項(xiàng)中，不能改善磁盤(pán)設(shè)備I/O性能的是（）。A.重排I/0請(qǐng)求次序B.在一個(gè)磁盤(pán)上設(shè)置多個(gè)分區(qū)C.預(yù)讀和滯后寫(xiě)D.優(yōu)化文件物理塊的分布33 .在TC% IP體系結(jié)構(gòu)中，直接為ICMP提供服務(wù)的協(xié)議是（）。A. PPP B. IP C. UDP D. TCP34 .在物理層接口特性中，用于描述完成每種功能的事件發(fā)生順序的是（）。A.機(jī)械特性 B.功能特性 C.過(guò)程特性 D.電氣特性 35.以太網(wǎng)的MAO議提供的是（）。A無(wú)連接不可靠服務(wù)B.無(wú)連接可靠服務(wù)C.有連接不可靠服務(wù)D.有連接可靠服務(wù)36.兩臺(tái)主機(jī)之間的數(shù)據(jù)鏈路層采用后

28、退N幀協(xié)議（GBN傳輸數(shù)據(jù)，數(shù)據(jù)傳輸速率為16kbps ,單向傳播時(shí)延為270ms數(shù)據(jù)幀長(zhǎng)度范圍是128512字節(jié)，接收方總是 以與數(shù)據(jù)幀等長(zhǎng)的幀進(jìn)行確認(rèn)。為使信道利用率達(dá)到最高，幀序號(hào)的比特?cái)?shù)至少為 （ ）。A. 5B. 4C. 3 D. 237 37.下列關(guān)于IP路由器功能的描述中，正確的是（）。I.運(yùn)行路由協(xié)議，設(shè)置路由表；n.監(jiān)測(cè)到擁塞時(shí)，合理丟棄IP分組；田.對(duì)收到的IP分組頭進(jìn)行差錯(cuò)校驗(yàn)，確保傳輸?shù)?IP分組不丟失；IV.根據(jù)收到的IP分組 的目的IP地址，將其轉(zhuǎn)發(fā)到合適的輸出線路上。A.僅田、IVB.僅 I、n、mC.僅 i、n、iv d. i、n、m、iv 38. ARP協(xié)議的

29、功能是（）。A.根據(jù)IP地址查詢MAC4址B.根據(jù)MAO址查詢IP地址C.根據(jù)域名查詢IP地址D.根據(jù)IP地址查詢域名39 .某主機(jī)的IP地址為180.80.77.55 ,子網(wǎng)掩碼為 255.255.252.0。若該主機(jī)向 其所在子網(wǎng)發(fā)送廣播分組，則目的地址可以是（）。A. 180.80.76.0B. 180.80.76.255C. 180.80.77.255D. 180.80.79.25540 .若用戶l與用戶2之間發(fā)送和接收電子郵件的過(guò)程如題40圖所示，則圖中、階段分別使用的應(yīng)用層協(xié)議可以是()。題40圖電子郵件發(fā)送接收示意圖A. SMTP SMTP SMTPB. POP3 SMTP PO

30、P3C. POP3 SMTP SMTPD. SMTP SMTP POP3二、綜合應(yīng)用題：41-47 小題。共70分。41 . (10分)設(shè)有6個(gè)有序表 A B、C、R E、F,分別含有10、35、40、50、60 和200個(gè)數(shù)據(jù)元素，各表中元素按升序排列。要求通過(guò) 5次兩兩合并，將6個(gè)表最終合 并成1個(gè)升序表，并在最壞情況下比較的總次數(shù)達(dá)到最小。請(qǐng)回答下列問(wèn)題。(1)給出完整的合并過(guò)程，并求出最壞情況下比較的總次數(shù)。(2)根據(jù)你的合并過(guò)程，描述n (n2)個(gè)不等長(zhǎng)升序表的合并策略，并說(shuō)明理由。42 . (13分)假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個(gè)單詞有相同的后綴時(shí)， 則可共享相同的后綴存

31、儲(chǔ)空間。例如，“ loading ”和“ being ”的存儲(chǔ)映像如題42圖所示。題42圖存儲(chǔ)映像示意圖設(shè)strl和str2分別指向兩個(gè)單詞所在單鏈表的頭結(jié)點(diǎn)，鏈表結(jié)點(diǎn)結(jié)構(gòu)為data ,next,請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間上盡可能高效的算法，找出由 strl和str2所指的兩個(gè)鏈表共 同后綴的起始位置(如圖中字符 i所在結(jié)點(diǎn)的位置p)。要求：(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用 C或C+堿JAVA語(yǔ)言描述算法，關(guān)鍵之處給出注釋。(3)說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度。43. (11分)假定某計(jì)算機(jī)的 CPUfe頻為80MHz CPI為4,并且平均每條指令訪 存1.5次，主存與Cache之間交

32、換的塊大小為 168, Cache的命中率為99%,存儲(chǔ)器總 線寬度為32位。請(qǐng)回答下列問(wèn)題。(1)該計(jì)算機(jī)的 MIPS數(shù)是多少？平均每秒Cache缺失的次數(shù)是多少？在不考慮DMA 傳送的情況下，主存帶寬至少達(dá)到多少才能滿足CPU勺訪存要求？(2)假定在Cache缺失的情況下訪問(wèn)主存時(shí)，存在 0.0005 %的缺頁(yè)率，則CPUff 均每秒產(chǎn)生多少次缺頁(yè)異常？若頁(yè)面大小為4KB,每次缺頁(yè)都需要訪問(wèn)磁盤(pán)，訪問(wèn)磁盤(pán)時(shí) DMA專(zhuān)送采用周期挪用方式， 磁盤(pán)I/O接口的數(shù)據(jù)緩沖寄存器為 32位，則磁盤(pán)I/O接 口平均每秒發(fā)出的DMA 青求次數(shù)至少是多少？(3) CPUffl DMA空制器同時(shí)要求使用存儲(chǔ)器

33、總線時(shí)，哪個(gè)優(yōu)先級(jí)更高？為什么？(4)為了提高性能，主存采用 4體交叉存儲(chǔ)模式，工作時(shí)每l/4個(gè)存儲(chǔ)周期啟動(dòng) 一個(gè)體。若每個(gè)體的存儲(chǔ)周期為50ns,則該主存能提供的最大帶寬是多少 ？44. (12分)某16位計(jì)算機(jī)中，帶符號(hào)整數(shù)用補(bǔ)碼表示， 數(shù)據(jù)Cache和指令Cache 分離。題44表給出了指令系統(tǒng)中部分指令格式，其中 Rs和Rd表示寄存器，memi示存 儲(chǔ)單元地址，(X)表示寄存器X或存儲(chǔ)單元X的內(nèi)容。表指令系統(tǒng)中部分指令格式名稱指令的匯編格式指令功能 1加法指令A(yù)DD R Rd(Rs) + (Rd) f Rd算術(shù)/邏輯左移SHLR d2* (Rd) f Rd 算術(shù)右移SHRR d(Rd)

34、 /2f Rd取數(shù)指令LOAD RD mem(merm f Rd存數(shù)指令STORE Rs mem(Rs) f mem該計(jì)算機(jī)采用5段流水方式執(zhí)行指令，各流水段分別是取指(IF)、譯碼/讀寄存 器(ID)、執(zhí)行/計(jì)算有效地址(EX)、訪問(wèn)存儲(chǔ)器(M)和結(jié)果寫(xiě)回寄存器(WB , 流水線采用“按序發(fā)射，按序完成”方式，沒(méi)有采用轉(zhuǎn)發(fā)技術(shù)處理數(shù)據(jù)相關(guān)，并且同一 個(gè)寄存器的讀和寫(xiě)操作不能在同一個(gè)時(shí)鐘周期內(nèi)進(jìn)行。請(qǐng)回答下列問(wèn)題。(1)若int型變量x的值為-513,存放在寄存器Rl中，則執(zhí)行指令 SHRRl”后, Rl的內(nèi)容是多少？(用十六進(jìn)制表示)(2)若某個(gè)時(shí)間段中，有連續(xù)的 4條指令進(jìn)入流水線，在其執(zhí)

35、行過(guò)程中沒(méi)有發(fā)生任何阻塞，則執(zhí)行這4條指令所需的時(shí)鐘周期數(shù)為多少 ？(3)若高級(jí)語(yǔ)言程序中某賦值語(yǔ)句為x = a+b, x、a和b均為int型變量，它們的存儲(chǔ)單元地址分別表示為x、聞和回。該語(yǔ)句對(duì)應(yīng)的指令序列及其在指令流水線中 的執(zhí)行過(guò)程如題44圖所示。則這4條指令執(zhí)行過(guò)程中，I 3的ID段和14的IF段被阻塞 的原因各是什么？(4)若高級(jí)語(yǔ)言程序中某賦值語(yǔ)句為x = 2*x+a, x和a均為unsigned int 類(lèi)型變量，它們的存儲(chǔ)單元地址分別表示為x、聞，則執(zhí)行這條語(yǔ)句至少需要多少個(gè)時(shí)鐘周期？要求模仿題44圖畫(huà)出這條語(yǔ)句對(duì)應(yīng)的指令序列及其在流水線中的執(zhí)行過(guò)程示意圖。45. (7分)某請(qǐng)

36、求分頁(yè)系統(tǒng)的局部頁(yè)面置換策略如下：系統(tǒng)從0時(shí)刻開(kāi)始掃描，每隔5個(gè)時(shí)間單位掃描一輪駐留集(掃描時(shí)間忽略不計(jì))，本輪沒(méi)有被訪問(wèn)過(guò)的頁(yè)框?qū)?被系統(tǒng)回收，并放入到空閑頁(yè)框鏈尾，其中內(nèi)容在下一次被分配之前不被清空。當(dāng)發(fā)生 缺頁(yè)時(shí)，如果該頁(yè)曾被使用過(guò)且還在空閑頁(yè)框鏈表中，則重新放回進(jìn)程的駐留集中；否 則，從空閑頁(yè)框鏈表頭部取出一個(gè)頁(yè)框。假設(shè)不考慮其他進(jìn)程的影響和系統(tǒng)開(kāi)銷(xiāo)，初始 時(shí)進(jìn)程駐留集為空。目前系統(tǒng)空閑頁(yè)框鏈表中頁(yè)框號(hào)依次為32、15、21、41。進(jìn)程P依次訪問(wèn)的 虛擬頁(yè)號(hào)，訪問(wèn)時(shí)刻 是：1, 1、3, 2、0, 4、0, 6、1, 11、0, 13、2, 14。請(qǐng)回答下列問(wèn)題。(1)訪問(wèn)0, 4時(shí)，

37、對(duì)應(yīng)的頁(yè)框號(hào)是什么？(2)訪問(wèn)1, 11時(shí)，對(duì)應(yīng)的頁(yè)框號(hào)是什么？說(shuō)明理由。(3)訪問(wèn)2, 14時(shí)，對(duì)應(yīng)的頁(yè)框號(hào)是什么？說(shuō)明理由。(4)該策略是否適合于時(shí)間局部性好的程序 ？說(shuō)明理由。46. (8分)某文件系統(tǒng)空間的最大容量為 4TB (1T= 24),以磁盤(pán)塊為基本分配單位，磁盤(pán)塊大小為lKBo文件控制塊(FCB包含一個(gè)512B的索引表區(qū)。請(qǐng)回答下列 問(wèn)題。(1)假設(shè)索引表區(qū)僅采用直接索引結(jié)構(gòu)，索引表區(qū)存放文件占用的磁盤(pán)塊號(hào)。索引表項(xiàng)中塊號(hào)最少占多少字節(jié) ？可支持的單個(gè)文件最大長(zhǎng)度是多少字節(jié) ？(2)假設(shè)索引表區(qū)采用如下結(jié)構(gòu)：第 07字節(jié)采用 起始?jí)K號(hào)，塊數(shù) 格式表示文 件創(chuàng)建時(shí)預(yù)分配的連續(xù)存

38、儲(chǔ)空間，其中起始?jí)K號(hào)占 6B,塊數(shù)占2B;剩余504字節(jié)采用 直接索引結(jié)構(gòu)，一個(gè)索引項(xiàng)占 6B,則可支持的單個(gè)文件最大長(zhǎng)度是多少字節(jié) ？為了使單 個(gè)文件的長(zhǎng)度達(dá)到最大，請(qǐng)指出起始?jí)K號(hào)和塊數(shù)分別所占字節(jié)數(shù)的合理值并說(shuō)明理由。47. （9分）主機(jī)H通過(guò)快速以太網(wǎng)連接Internet , IP地址為192.168.0.8 ,服務(wù) 器S的IP地址為211.68.71.80 。H與S使用TCP信時(shí)，在 H上捕獲的其中5個(gè)IP分 組如題47-a表所示。題47-a表Sfflj七IP分組的前40字節(jié)內(nèi)容（十六進(jìn)制）1019b4000 8006lde8 coa80008 d3444750 0bd91388 84

39、6b41c5 000000005db00000200004000 31066e83 3d3444750 cOa8000813880bd9 e0599fef 846b41c6 6701216d037e100003019c4000 8006ldef cOa80008 d3444750 bd913888 46b41c6e 0599ff05 01043802 b3200004019d4000 80061dde cOa80008 d34447500bd91388 846b4lc6 e0599ff0c655000053106067a d3444750 cOa8000813880bd9 e0599ff0 8

40、46b41d6 501016d057d20000請(qǐng)回答下列問(wèn)題。（1）題47-a表中的IP分組中，哪幾個(gè)是由H發(fā)送的？哪幾個(gè)完成了 TCP連接建立 過(guò)程？哪幾個(gè)在通過(guò)快速以太網(wǎng)傳輸時(shí)進(jìn)行了填充？（2）根據(jù)題47-a表中的IP分組，分析S已經(jīng)收到的應(yīng)用層數(shù)據(jù)字節(jié)數(shù)是多少？（3）若題47-a表中的某個(gè)IP分組在S發(fā)出時(shí)的前40字節(jié)如題47-b表所列，則 該IP分組到達(dá)H時(shí)經(jīng)過(guò)了多少個(gè)路由器？題47-b表來(lái)自S發(fā)出的上組4006eCad d3444750 ca760106 1388a108 e0599ff0 846b41d6 501016dO b7d60000注：IP分組頭和TCP段頭結(jié)構(gòu)分別如題4

41、7-a圖、題47-b圖所示:版本頭部長(zhǎng) 度服務(wù)類(lèi)型 （8-15）總長(zhǎng)度(16-31 )標(biāo)識(shí)標(biāo)志片偏移生存時(shí)（TTL）協(xié)議頭部校驗(yàn)和源IP地址目的IP地址題47-a圖IP分組頭結(jié)構(gòu)源端口（ 0-15）目的端口 （ 16-31 ）序號(hào)（seq)確認(rèn)號(hào)（ack）UAPRSF數(shù)據(jù)偏移保留RCSSYI窗口GKHTNN校驗(yàn)和1緊急指針選項(xiàng)（長(zhǎng)度可艾）填充題47-b圖TCP段頭結(jié)構(gòu)2012年全國(guó)碩士研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題及詳解一、單項(xiàng)選擇題：l40小題。每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中， 只有一個(gè)選項(xiàng)是最符合題目要求的。1 .求整數(shù)n (n0)階乘的算法如下，其時(shí)間

42、復(fù)雜度是()。A. O (log2n)B. 0 (n)C. O (nlog2n)一， 2、D. O ( n )【答案】Bo【解析】設(shè)fact (n)的運(yùn)行時(shí)間函數(shù)是 T (n)。該函數(shù)中語(yǔ)句的運(yùn)行時(shí)間是 0 (1),語(yǔ)句的運(yùn)行時(shí)間是 T (n-1) +O (1),其 中O (1)為乘法運(yùn)算的時(shí)間。因此，當(dāng) n1 時(shí)，T (n) =T (n-1 ) +O (1)。則，T (n) = O (1) +T (n-1 )= 2XO (1) +T (n-2) = (n-1) x O (1) +T (1) =nx O (1)=O (n)即fact (n)的時(shí)間復(fù)雜度為 O (n)。2 .已知操作符包括+、

43、-、 *、 /、(和)。將中綴表達(dá) 式a+b-a* ( (c+d) /e-f ) +g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式 ab+acd+e/f-*-g+時(shí)，用棧來(lái) 存放暫時(shí)還不能確定運(yùn)算次序的操作符。若棧初始時(shí)為空，則轉(zhuǎn)換過(guò)程中同時(shí)保存在棧 中的操作符的最大個(gè)數(shù)是()。A. 5B. 7C. 8D. 11【答案】Ao【解析】基本思想是：采用運(yùn)算符棧是為了比較運(yùn)算符的優(yōu)先級(jí)，所有運(yùn)算符必須 進(jìn)棧。只將大于棧頂元素優(yōu)先級(jí)的運(yùn)算符直接進(jìn)棧，否則需要退棧棧頂運(yùn)算符(先出棧 的運(yùn)算符先計(jì)算，同優(yōu)先級(jí)的運(yùn)算符在棧中的先計(jì)算)。表達(dá)式a+b-a* ( (c+d) /e-f )+g產(chǎn)生后綴表達(dá)式的過(guò)程如下表所列：當(dāng)前字符運(yùn)

44、算符棧內(nèi) 容后綴表達(dá)式說(shuō)明a+“+”進(jìn)棧b+ab-ab+“-”與棧頂兀素“ +”的優(yōu)先級(jí) 相同，則“ +”出棧，“-”進(jìn)棧a-ab+a*-*ab+a“* ”的優(yōu)先級(jí)大于棧頂兀素“-”， 則“進(jìn)棧(-* (ab+a“(”對(duì)它之前后的運(yùn)算符起隔 離作用(-* (ab+a“（”對(duì)它之前后的運(yùn)算符起隔 離作用-* (ab+ac+-* ( ( +ab+ac“+”進(jìn)棧d-* ( ( +ab+acd)-* (ab+acd+與其配對(duì)的左括號(hào)及其前所有運(yùn) 算符出棧/-* (/ab+acd+進(jìn)棧e-* (/ab+acd+e-* (-ab+acd+e/“-”的優(yōu)先級(jí)小于棧頂兀素“/”，則出棧，“-”進(jìn) 棧f-* (

45、-ab+acd+e/f)-*ab+acd+e/f-與其配對(duì)的左括號(hào)及其前所有運(yùn) 算符出棧+-ab+acd+e/ f-*“+”的優(yōu)先級(jí)小于棧頂兀素“*”， 則“出棧+ab+acd+e/ f-*-“ +”與棧頂兀素“-”的優(yōu)先級(jí) 相同，則“-”出棧，“ +”進(jìn)棧g+ab+acd+e/ f-*-gab+acd+e/ f-*-g+全部出棧通過(guò)上表可以看出，顯然轉(zhuǎn)換過(guò)程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是5。3 .若一棵二叉樹(shù)的前序遍歷序列為 a, e, b, d, c,后序遍歷序列為b, c, d, e, a,則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）。A.只有e8 .有 e、bC.有 e、cD.無(wú)法確定【答案】Ao【解析】由題目可知，若一棵二叉樹(shù)的前序遍歷序列為a, e, b, d, c,后序遍歷序列為b, c, d, e, a,其中a為這棵二叉樹(shù)的根結(jié)點(diǎn)，接下來(lái)，在前序遍歷的第二個(gè) 結(jié)點(diǎn)為e,而后序遍歷的倒數(shù)第二個(gè)結(jié)點(diǎn)為 e,說(shuō)明a的孩子結(jié)點(diǎn)只有e。4 .若平衡二叉樹(shù)的高度為 6,且所有非葉結(jié)點(diǎn)的平衡因子均為 1,則該平衡二叉樹(shù) 的結(jié)點(diǎn)總數(shù)為（）。A. 12B. 20C. 32D. 33【答案】Bo【解析】本題題目的實(shí)際問(wèn)題是，具有 6層結(jié)點(diǎn)的平衡二叉樹(shù)含有最少的結(jié)點(diǎn)數(shù)是 多少。Nh表示深度為h的平衡二叉樹(shù)中含有的最少結(jié)點(diǎn)數(shù)，有 N=0, N = 1, Nb = 2 N=N-i+N-2+1由此可