數(shù)據(jù)結(jié)構(gòu)PPT的選擇

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)PPT的選擇1、將兩個各有n和m個元素的有序表（遞增）歸并成一個有序表，仍保持其遞增有序，則最少的比較次數(shù)是D，最多的比較次數(shù)是（其中，MIN表示求兩個數(shù)的最小數(shù)）。A.nB.m

C.m+n－1D.MIN(n,m)

例3.2設(shè)一個棧的輸入序列為A,B,C,D，則借助一個棧所得到的輸出序列不可能是。

(A)A,B,C,D(B)D,C,B,A

(C)A,C,D,B(D)D,A,B,C

解：可以簡單地推算，得簡單得出D,A,B,C是不可能的，由于D先出來，說明A,B,C,D均在棧中，依照入棧順序，在棧中順序應(yīng)為D,C,B,A，出棧的順序只能是D,C,B,A。所以此題答案為D。

例3.3已知一個棧的進(jìn)棧序列是1,2,3,?,n，其輸出序列是p1,p2,?,pn，若p1=n，則pi的值。(A)i(B)n-i(C)n-i+1(D)不確定

解：當(dāng)p1=n時，輸出序列必是n,n-1,?,3,2,1，則有:p2=n-1,p3=n-2,?,pn=1

推導(dǎo)出pi=n-i+1,所以此題答案為C。

例3.4設(shè)n個元素進(jìn)棧序列是1,2,3,?,n，其輸出序列是p1,p2,?,pn，若p1=3，則p2的值。

(A)一定是2(B)一定是1(C)不可能是1(D)以上都不對

解：當(dāng)p1=3時，說明1,2,3先進(jìn)棧，馬上出棧3，然后可能出棧，即為2，也可能4或后面的元素進(jìn)棧，再出棧。因此，p2可能是2，也可能是4,?,n，但一定不能是1。所以此題答案為C。

例3.9某隊列允許在兩端進(jìn)行入隊操作，但僅允許在一端進(jìn)行出隊操作，若a、b、c、d、e元素進(jìn)隊，則以下不可能得到的順序有哪些？（1）bacde（2）dbace（3）dbcae（4）ecbad解：此題的隊列實際上是一個輸出受限的雙端隊列。

（1）a后端進(jìn)，b前端進(jìn)，c后端進(jìn)，d后端進(jìn)，e后端進(jìn)，全出隊。（2）a后端進(jìn)，b前端進(jìn)，c后端進(jìn)，d前端進(jìn)，e后端進(jìn)，全出隊。

（3）a后端進(jìn)，b前端進(jìn)，因d未出，此時只能進(jìn)隊，c怎么進(jìn)都不可能在b、a之間。

（4）a后端進(jìn)，b前端進(jìn)，c前端進(jìn)，d后端進(jìn)，e前端進(jìn)，全出隊。所以不可能得到的順序為（3）。

例：一棵度為4的樹T中，若有20個度為4的節(jié)點，10個度為3的節(jié)點，1個度為2的節(jié)點，10個度為1的節(jié)點，則樹T的葉子節(jié)點個數(shù)是。A.41B.82C.113D.122

例7.2已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個葉節(jié)點，則該完全二叉樹的節(jié)點個數(shù)最多是。A.39B.52C.111D.119

考察完全二叉樹的特點。完全二叉樹比起滿二叉樹只是在最下面一層的右邊缺少了部分葉結(jié)點，而最終一層之上是個滿二叉樹，并且只有最終兩層上有葉結(jié)點。第6層有葉結(jié)點則完全二叉樹的高度可能為6或7，顯然樹高為7時結(jié)點更多。若第6層上有8個葉結(jié)點，則前六層為滿二叉樹，而第7層缺失了8×2＝16個葉結(jié)點，故完全二叉樹的結(jié)點個數(shù)最多為2^7-1-16=111個結(jié)點。

例：一棵滿二叉樹中共有n個節(jié)點，其中有m個葉子節(jié)點，高度為h，則。A.n=h+mB.h+m=2nC.m=h-1D.n=2^h-1

例7.3設(shè)森林F中有3棵樹，第一、其次和第三棵樹的節(jié)點個數(shù)分別為9、8和7，則與森林F對應(yīng)的二叉樹根節(jié)點的右子樹上的節(jié)點個數(shù)是。A.16B.15C.7D.17

例7.4設(shè)一棵二叉樹是由森林轉(zhuǎn)換而來的，若森林中有n個非終端節(jié)點，則二叉樹中無右孩子的節(jié)點個數(shù)為。

A.n-1B.nC.n+1D.n+2

例．一個無向連通圖中有16條邊，所有頂點的度均小于5，度為4的頂點有3個，度為3的頂點有4個，度為2的頂點有2個，則該圖有個頂點。A.10B.11C.12D.13

解：設(shè)該圖有n個頂點，圖中度為i的頂點數(shù)為ni（0≤i≤4），顯然n0=0，n=3+4+2+n1+n0=9+n1，而度之和=4×3+3×4+2×2+n1=28+n1，而度之和=2e=32，所以有28+n1=32，得n1=4，n=9+n1=13。此題答案為D。

例如，對于以下關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序

列是。

A.95,22,91,24,94,71B.92,20,91,34,88,35

C.21,89,77,29,36,38D.12,25,71,68,33,34

解：各選項對應(yīng)的查找過程如下圖所示，從中看到只有選項A對應(yīng)的查找樹不構(gòu)成一棵二叉排序樹，圖中虛線圓框內(nèi)部分表示違背二叉排序樹的性質(zhì)的子樹。此題答案為A。95922112

22208925

91917177

342468298894363335383471

（a）選項A對應(yīng)的查找過程（b）選項B對應(yīng)的查找過程（c）選項C對應(yīng)的查找過程（d）選項D對應(yīng)的查找過程

例如，對任意的7個關(guān)鍵字進(jìn)行基于比較的排序，至少要進(jìn)行次關(guān)鍵字之間的兩兩比較。

A.13B.14C.15D.16

解：基于“比較〞進(jìn)行排序的算法在最壞狀況下所需進(jìn)行的比較次數(shù)至少為?log2(n!)?。?log2(7!)?=13。此題答案為A。

例如，若數(shù)據(jù)元素序列{11,12,13,7,8,9,23,4,5}是采用以下排序方法之一得到的其次趟排序后的結(jié)果，則該排序算法只能是。A.起泡排序B.插入排序C.選擇排序D.二路歸并排序

例如，數(shù)據(jù)序列{8,9,10,4,5,6,20,1,2}只能是的兩趟排序后的結(jié)果。A.簡單項選擇擇排序B.起泡排序

C.直接插入排序D.堆排序

例如，已知關(guān)鍵字序列5,8,12,19,28,20,15,22是小根堆，插入關(guān)鍵字3，調(diào)整好后得到的小根堆是。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

點評：此題考察對堆調(diào)整算法--“篩選〞算法的應(yīng)用。篩選算法要求根的左右子樹必需是堆。把3插入后，關(guān)鍵序列變?yōu)?，8，12，19，28，20，15，22，3，以5為根的左右子樹的堆結(jié)構(gòu)可能被破壞，因此必需重建堆，從n/2個結(jié)點開始調(diào)用篩選算法，直到第一個結(jié)點，就可重建堆。答案為A。

例如，對一組數(shù)據(jù)(2,12,16,88,5,10)進(jìn)行排序，若前三趟的結(jié)果如下：第一趟：2,12,16,5,10,88其次趟：2,12,5,10,16,88第三趟：2,5,10,12,16,88則采用的排序方法可能是。

A.起泡排序B.希爾排序C.歸并排序D.基數(shù)排序

例如，采用遞歸方式對順序表進(jìn)行快速排序，以下關(guān)于遞歸次數(shù)的表達(dá)中，正確的是。

A.遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)

B.每次劃分后