2021數(shù)據(jù)結(jié)構(gòu)考研數(shù)據(jù)結(jié)構(gòu)與C語言考研名?？佳姓骖}

2021數(shù)據(jù)結(jié)構(gòu)考研數(shù)據(jù)結(jié)構(gòu)與C語言考研名校考研真題一、名校考研真題解析為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是( )。［2009年聯(lián)考真題］A.棧B.隊(duì)歹I」C.樹D.圖【答案】B!~【解析】這類問題一般都先分析題目中的數(shù)據(jù)具有什么操作特性或是結(jié)構(gòu)特性比如“先進(jìn)后出”、“先進(jìn)先出”等再判斷其邏輯結(jié)構(gòu)。棧和隊(duì)列是操作受限的線性表，棧具有先進(jìn)后出的特性而隊(duì)列具有先進(jìn)先出的特性。由于本題中先進(jìn)入打印數(shù)據(jù)緩沖區(qū)的文件先被打印，因此打印數(shù)據(jù)緩沖區(qū)具有先進(jìn)先出性，則它的邏輯結(jié)構(gòu)應(yīng)該是隊(duì)列。100.設(shè)哈希表長M=14，哈希函數(shù)H(KEY)=KEYMOD11。表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4,ADDR(38)=5,ADDR(61)=6,ADDR(84)=7,其余地址為空，如用二次探測(cè)再哈希法解決沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是( )。［東華大學(xué)考研真題］A.8C.5D.9【答案】D!~【解析】15,38,61,84用哈希函數(shù)H(key)=key%11計(jì)算后得地址:4,5,6,749計(jì)算后為5,發(fā)生沖突.用二次探測(cè)再散列法解決沖突:1:(key+1八2)%11=(49+1)%11=6，仍然發(fā)生沖突.2:(key-1-2)%11=(49-1)%11=4，仍然發(fā)生沖突.3:(key+2八2)%11=(49+4)%11=9，不再發(fā)生沖突.101.設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素2,b,c,d,e,f,g依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q,且7個(gè)元素出隊(duì)的順序是b,d,c,f,e,a,g,則棧S的容量至少是()。［2009年聯(lián)考真題］A.1B.2C.3D.4【答案】C!~【解析】由于棧具有先進(jìn)后出的特性，隊(duì)列具有先進(jìn)先出的特性，出隊(duì)順序即為人隊(duì)順序。在本題中，每個(gè)元素出棧S后立即進(jìn)入隊(duì)列Q,出棧順序即為入隊(duì)順序，所以本題中隊(duì)列的作用形同虛設(shè)，根據(jù)題意出隊(duì)順序即為出棧順序。根據(jù)出棧順序可以分析各個(gè)元素進(jìn)出棧的過程：第一個(gè)出棧元素為b，表明棧內(nèi)還有元素a,b出棧前的深度為2;第二個(gè)出棧元素為d，棧內(nèi)元素為a和c,d出棧前的深度為3；c出棧后，剩余元素為a,c出棧前的深度為2;f出棧后，剩余元素為a和e,f出棧前的深度為3；e出棧后，剩余元素為a,e出棧前的深度為2;a出棧后，無剩余元素，a出棧前的深度為1;g出棧后，無剩余元素，g出棧前的深度為1。所以棧容量至少是3。102.給定二叉樹如下圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3,1,7,5,6,2,4,則其遍歷方式是（）。［2009年聯(lián)考真題］A.LRNB.NRLC.RLND.RNL【答案】D!~【解析】對(duì)“二叉樹”而言，一般有三條搜索路徑：①先上后下的按層次遍歷；②先左（子樹）后右（子樹）的遍歷；③先右（子樹）后左（子樹）的遍歷。其中第1種搜索路徑方式就是常見的層次遍歷，第2種搜索路徑方式包括常見的先序遍歷NLR、中序遍歷LNR、后序遍歷LRN,第3種搜索路徑方式則是不常使用的NRL、RNL、RLN。本題考查的是第3種搜索路徑方式的一種情況。根據(jù)遍歷的序列以及樹的結(jié)構(gòu)圖，可以分析出該遍歷的順序是先右子樹再跟結(jié)點(diǎn)最后左子樹，故答案為D。103.排序算法的穩(wěn)定性是指（ ）。［北京理工大學(xué)考研真題］A.經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的相對(duì)位置不變B.經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的絕對(duì)位置不變C.算法的排序性能與被排序元素的數(shù)量關(guān)系不大D.算法的排序性能與被排序元素的數(shù)量關(guān)系密切【答案】A!~【解析】假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對(duì)次序保持不變，即在原序列中，ri=rj,且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。104.下列二叉排序樹中，滿足平衡二叉樹定義的是（ ）。［2009年聯(lián)考真題］【答案】B【解析】平衡二叉樹是指左右子樹高度差（平衡因子）的絕對(duì)值不超過1的二叉樹。A項(xiàng)中根結(jié)點(diǎn)的平衡因子是2;B項(xiàng)中每個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值均不超過1；C項(xiàng)中根結(jié)點(diǎn)的平衡因子是-2；D項(xiàng)中根結(jié)點(diǎn)的平衡因子是3。105.已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是（ ）。［2009年聯(lián)考真題］A.39B.52C.111D.119【答案】C!~【解析】完全二叉樹的一個(gè)特點(diǎn)是：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層。題目中沒有說明完全二叉樹的高度，首先由完全二叉樹的特點(diǎn)確定題目中樹的高度。根據(jù)題意，一棵完全二叉樹的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，可知此二叉樹的高度是6或7。題目中求二叉樹的結(jié)點(diǎn)數(shù)最多的情況，因此此完全二叉樹的高度為7。由于高度為7的完全二叉樹的前6層是一棵滿二叉樹，根據(jù)二叉樹的性質(zhì)2可知，高度為6的滿二叉樹的結(jié)點(diǎn)數(shù)是26-1=63。又根據(jù)二叉樹的性質(zhì)1可知，題目中二叉樹的第6層結(jié)點(diǎn)數(shù)是25=32個(gè)結(jié)點(diǎn)，已知有8個(gè)葉子結(jié)點(diǎn)，那么其余32-8=24個(gè)結(jié)點(diǎn)均為分支結(jié)點(diǎn)，這些結(jié)點(diǎn)在第7層上最多有48個(gè)子結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）。所以此二叉樹的結(jié)點(diǎn)數(shù)最多可達(dá)26-1+（25-8）x2=111o106.下面給出的四種排序方法中，排序過程中的比較次數(shù)與排序方法無關(guān)的是（ ）。［北京航空航天大學(xué)考研真題］A.選擇排序法B.插入排序法C.快速排序法D.堆排序法【答案】A!~【解析】選擇排序的基本思想是：第i趟排序開始時(shí)，當(dāng)前有序區(qū)和無序區(qū)分別為R[0..i-1]和R[i..n-1](0<i<n-1)，該趟排序則是從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄R[k],將它與無序區(qū)的第1個(gè)記錄R[i]交換，使R[0..i]和R[i+1..n-1]分別變?yōu)樾碌挠行騾^(qū)和新的無序區(qū)。107.將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹，若在二叉樹中，結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來的森林中，u和v可能具有的關(guān)系是( )。[2009年聯(lián)考真題]I.父子關(guān)系口.兄弟關(guān)系m.u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)系A(chǔ).只有IB.I和口C.I和田D.I、口和田【答案】B!~【解析】首先，在二叉樹中，若結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，那接下來根據(jù)森林與二叉樹的轉(zhuǎn)換規(guī)則，將這4種情況還原成森林中結(jié)點(diǎn)的關(guān)系。其中:情況（1），在原來的森林中情況（1），在原來的森林中u是v的父結(jié)點(diǎn)的父結(jié)點(diǎn);情況（2），在森林中u是v的父結(jié)點(diǎn);，在森林中u是v的父結(jié)點(diǎn)的兄弟;，在森林中u與v是兄弟關(guān)系。由此可知，題目中的I、口是正確的。108.下列關(guān)于無向連通圖特性的敘述中，正確的是（ ）。［2009年聯(lián)考真題］I.所有的頂點(diǎn)的度之和為偶數(shù)口.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1田.至少有一個(gè)頂點(diǎn)的度為1A.只有IB.只有口C.I和口D.工和田【答案】A!~【解析】在圖中，頂點(diǎn)的度TD()之和與邊的數(shù)目滿足關(guān)系式： 二2e(n為圖的總結(jié)點(diǎn)數(shù)，e為總邊數(shù))，因此，1項(xiàng)正確。對(duì)于口、田項(xiàng)中的特性不是一般無向連通圖的特性，可以輕松地舉出反例?！爸辽儆幸粋€(gè)頂點(diǎn)的度為1”的反例如下圖(1)所示，“邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1”的反例如下圖(2)所示。

CM?109.設(shè)被排序的結(jié)點(diǎn)序列共有N個(gè)結(jié)點(diǎn)，在該序列中的結(jié)點(diǎn)已十分接近排序的情況下，用直接插入法、歸并法和一般的快速排序法對(duì)其排序，這些算法的時(shí)間復(fù)雜性應(yīng)為()。［上海交通大學(xué)考研真題］A.O(N),O(N),O(N)B.O(N),O(N*log2N),0(N*log2N)C.O(N),O(N*log2N),0(N2)D.O(N2),O(N*log2N),0(N2)【答案】C!~【解析】因?yàn)樵撔蛄兄械慕Y(jié)點(diǎn)已經(jīng)十分接近排序的情況，對(duì)于直接插入法，大部分結(jié)點(diǎn)只需要直接插入后面即可，因此時(shí)間復(fù)雜度為0(N)。對(duì)于采用歸并法，它是一種穩(wěn)定的排序方法，它的時(shí)間復(fù)雜度為O（Nlog2N）。對(duì)于一般的快速排序法，序列越接近有序，所需要的比較次數(shù)越多，此時(shí)的時(shí)間復(fù)雜度為O（N2）。110.下列敘述中，不符合m階B樹定義要求的是（ ）。［2009年聯(lián)考真題］A.根結(jié)點(diǎn)最多有m棵子樹B.所有葉結(jié)點(diǎn)都在同一層上C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D.葉結(jié)點(diǎn)之間通過指針鏈接【答案】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)之間通過指針鏈接，是B+樹的定義，而B-樹中沒有。因此，D項(xiàng)是錯(cuò)誤的。111.已知關(guān)鍵字序列5,8,12,19字8,20,15,22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后的小根堆是（ ）。［2009年聯(lián)考真題］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)整剩余元素。具體過程如圖（1）~（5）所示，（1）為原堆，（2）為插入3后，（3）、（4）為調(diào)整過程，（5）為調(diào)整后的小根堆。<5>20112.有些排序算法在每趟排序過程中，都會(huì)有一個(gè)元素被放置在其最終的位置上，下列算法不會(huì)出現(xiàn)此情況的是（ ）。［北京交通大學(xué)考研真題］A.希爾排序B.堆排序C.起泡排序D.快速排序【答案】A!~【解析】選擇排序、起泡排序和堆排序一趟排序后，在序列首部或尾部應(yīng)該有最大或最小值。113.若數(shù)據(jù)元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是（）。［2009年聯(lián)考真題］A.起泡排序B.插入排序C.選擇排序D.二路歸并排序【答案】B!~【解析】經(jīng)過兩趟排序后，A項(xiàng)起泡排序的結(jié)果是兩個(gè)最小或最大的元素放到了序列的最終位置；B項(xiàng)插入排序的結(jié)果是前三個(gè)數(shù)有序即可；C項(xiàng)選擇排序結(jié)果是兩個(gè)最小的元素在最前面按順序排好；D項(xiàng)二路歸并排序的結(jié)果是長度為4的子序列有序，即前4個(gè)數(shù)排好序，接下來的4個(gè)數(shù)排好序。顯然題目中的元素序列只能是插入排序第二趟排序后的結(jié)果，因此，B項(xiàng)正確。在有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)中，頂點(diǎn)V在鏈表中出現(xiàn)的次數(shù)是（ ）。［北京理工大學(xué)考研真題］A.頂點(diǎn)v的度B.頂點(diǎn)v的出度C.頂點(diǎn)v的入度D.依附于頂點(diǎn)v的邊數(shù)【答案】B!~【解析】在有向圖中，第j個(gè)鏈表中的結(jié)點(diǎn)個(gè)數(shù)只是頂點(diǎn)vi的出度，為求入度，必須遍歷整個(gè)鄰接表。因此頂點(diǎn)v在鏈表中出現(xiàn)的次數(shù)是頂點(diǎn)v的入度。83.若元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許連續(xù)三次進(jìn)行退棧操作，則不可能得到的出棧序列是（）。［2010年聯(lián)考真題］A.d,c,e,b,f,aB.c,b,d,a,e,fC.b,c,a,e,f,dD.a,f,e,d,c,b【答案】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)行退棧操作，所以D項(xiàng)所給序列為不可能得到的出棧順序。.某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，元素a,b,c,d,e依次入此隊(duì)列后再進(jìn)行出隊(duì)操作，則不可能得到的出隊(duì)序列是（）。[2010年聯(lián)考真題]A.b,a,c,d,eB.d,b,a,c,eC.d,b,c,a,eD.e,c,b,a,d【答案】C!~【解析】根據(jù)題意，隊(duì)列兩端都可以輸入數(shù)據(jù)元素，但是只能在一端輸出數(shù)據(jù)元素，這種隊(duì)列為輸出受限的雙端隊(duì)列。本題解題方法分別判斷每個(gè)選項(xiàng)如何入隊(duì)和出隊(duì)，從而得出不可能的情況。假設(shè)L代表從左端入隊(duì)，R代表從右端入隊(duì)，出隊(duì)都是從左端L出。四個(gè)選項(xiàng)所給序列的進(jìn)隊(duì)操作序列分別為：選項(xiàng)A.aL（或aR）,bL,cR,dR,eR選項(xiàng)B.aL（或aR）,bL,cR,dL,eR選項(xiàng)C.不可能出現(xiàn)選項(xiàng)D.aL（或aR）,bL,cL,dR,eL.已知有向圖6=（丫〃），其中V={V1,V2,V3,V4,V5,V6,V7},E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>，<V3，V5>，<V3，V6>，<V4,V6>,<V5,V7>,<V6,V7>},G的拓?fù)湫蛄惺牵ǎ?。［北京航空航天大學(xué)考研真題］A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.%、匕，峰，%，％，乂，叫【答案】A!~【解析】設(shè)G=（V，E）是一個(gè)具有n個(gè)頂點(diǎn)的有向圖，V中頂點(diǎn)序列v1，v2，…，vn，能被稱為拓?fù)湫蛄械臈l件：若<vi，于是圖中的邊（即從頂點(diǎn)vi到3有一條路徑），則在序列中頂點(diǎn)vi必須排在頂點(diǎn)七之前。根據(jù)上面拓?fù)湫蛄械亩x，就可以得出G的拓?fù)湫蛄惺荲1，V3，V4，V5，V2，V5.V7。.下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（ ）。［2010年聯(lián)考真題］【答案】D!~【解析】線索二叉樹利用二叉鏈表的空鏈域來存放結(jié)點(diǎn)的前驅(qū)和后繼信息、，解題思路較簡單。題中所給二叉樹的后序序列為dbca。結(jié)點(diǎn)d無前驅(qū)和左子樹，左鏈域空，無右子樹，右鏈域指向其后繼結(jié)點(diǎn)b；結(jié)點(diǎn)b無左子樹，左鏈域指向其前驅(qū)結(jié)點(diǎn)d；結(jié)點(diǎn)c無左子樹，左鏈域指向其前驅(qū)結(jié)點(diǎn)b，無右子樹，右鏈域指向其后繼結(jié)點(diǎn)a。所以正確選項(xiàng)為D。.在下圖所示的平衡二叉樹中，插入關(guān)鍵字48后得到一棵新平衡二叉樹。在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是( )。［2010年聯(lián)考真題］379037A.13、48B.24、48C.24、53D.24、90【答案】C!~【解析】題目中，插入48以后，樹根結(jié)點(diǎn)的平衡因子由-1變?yōu)?2，失去平衡。這屬于RL（先右后左）型平衡旋轉(zhuǎn)，需做兩次（先右旋后左旋轉(zhuǎn)）旋轉(zhuǎn)操作。過程如下圖所示：0）插入的后,調(diào)整前 0）先右旋轉(zhuǎn) 0）再左旋轉(zhuǎn)顯然，在調(diào)整后的新平衡二叉樹中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是24,53。.在有向圖G的拓?fù)湫蛄兄校繇旤c(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（ ）。［南京理工大學(xué)考研真題］A.G中有弧＜Vi,Vj＞B.G中有一條從Vi到Vj的路徑C.G中沒有?。糣i,VJD.G中有一條從Vj到Vi的路徑【答案】D【解析】若想實(shí)現(xiàn)圖的一個(gè)拓?fù)渑判?，需要滿足的一個(gè)條件為：若頂點(diǎn)A在序列中排在頂點(diǎn)B的前面，則在圖中不存在從頂點(diǎn)B到頂點(diǎn)A的路徑。又因?yàn)槿鬐中有一條從Vj到Vi的路徑，則在拓?fù)湫蛄兄蠽i不可能在Vj前。89.在一棵度為4的樹T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹T的葉結(jié)點(diǎn)個(gè)數(shù)是（ ）。［2010年聯(lián)考真題］A.41B.82C.113D.122【答案】B!~【解析】根據(jù)二叉樹的性質(zhì)3的推廣公式：N0=l+N2+2N3+...+（m-1）Nm可直接在將數(shù)據(jù)帶入公式，即No=l+N2+2N3+3N4=l+1x1+2x10+3x20=82o樹T的葉子結(jié)點(diǎn)的個(gè)數(shù)是82。如果考生不能熟練掌握二叉樹的性質(zhì)3的推廣公式，得到本題的正確答案將費(fèi)時(shí)費(fèi)力。因此，需要熟練掌握二叉樹的性質(zhì)及推廣。69.已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組A［0…n-1］中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時(shí)隊(duì)列為空，且要求第1個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A［0］處，則初始時(shí)front和rear的值分別是（ ）。［2011年聯(lián)考真題］A.0,0B.0,n-1C.n-1,0D.n-1,n-1【答案】B!~【解析】題目要求隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元素，若初始時(shí)隊(duì)列為空，且要求第1個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A［0］處，則此時(shí)front和rear的值都為0。由于進(jìn)隊(duì)操作要執(zhí)行（rear+1）%n，則初始時(shí)front的值為0、rear的值為n-1。70.設(shè)F是一個(gè)森林，B是由F變換得到的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（ ）個(gè)。［西安電子科技大學(xué)考研真題］A.n-1B.nC.n+1D.n+2【答案】C!~【解析】B中右指針為空的點(diǎn)，就是森林中的每棵樹中的每個(gè)非終端結(jié)點(diǎn)最右邊那個(gè)子樹的根結(jié)點(diǎn)，也可以說是每棵樹的每一棵子樹的每一層的最后一個(gè)結(jié)點(diǎn)。每個(gè)非終端結(jié)點(diǎn)都有一個(gè)最右邊的結(jié)點(diǎn)（X）,轉(zhuǎn)化成二叉樹的時(shí)候，X就是那個(gè)右指針為空的點(diǎn)，所以F中N個(gè)非終端結(jié)點(diǎn)就對(duì)應(yīng)著N個(gè)B中右指針為空的結(jié)點(diǎn)。還有一個(gè)結(jié)點(diǎn)，就是森林中最右邊那個(gè)樹的根結(jié)點(diǎn)（T）,如果這個(gè)森林只有一棵樹，這個(gè)結(jié)點(diǎn)就是這棵樹的根結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)不是任何結(jié)點(diǎn)的最右邊的孩子，但是轉(zhuǎn)化成二叉樹B的時(shí)候，他的右指針可以是為空。所以答案的n+L71.若一棵完全二叉樹有768個(gè)結(jié)點(diǎn)，則該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)是（ ）。［2011年聯(lián)考真題］A.257B.258C.384D.385【答案】C!~【解析】由n=n0+n1+n2和n0=n2+1可知,n=2n0-1+n1,即2n0-1+n1二768,顯然n1=1,2no=768，則n0=384，所以二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)是384。還可以根據(jù)完全二叉樹的另一個(gè)性質(zhì)：最后一個(gè)分支結(jié)點(diǎn)的序號(hào)為［768/2］,故非葉子結(jié)點(diǎn)數(shù)為384，而葉子結(jié)點(diǎn)的個(gè)數(shù)為768-384=384。（［乂］表示不大于x的最大整數(shù)，比如［3.14］=3）。72.若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為l,2,3,4和4,3,2,1,則該二叉樹的中序遍歷序列不會(huì)是（ ）。［2011年聯(lián)考真題］A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4