數(shù)據(jù)結構適用班級：軟件設計師主講：張紅網(wǎng)址：.bitpxEMail:bitpx@163分值說明：早上考36分,下午考15分比特培訓中心貴州·貴陽目錄TOC\o"13"\h\z\u第1節(jié)序論 11.1什么是數(shù)據(jù)? 11.2什么是數(shù)據(jù)元素? 11.3什么是數(shù)據(jù)結構及種類? 11.4數(shù)據(jù)的邏輯結構 11.5數(shù)據(jù)的物理結構 11.6算法和算法分析 11.7算法的五個特性 11.8算法設計的要求 21.9算法效率的度量 2第2節(jié)線性表 32.1線性表舉例 32.2線性表的存儲 42.3線性表棧 42.4隊列 42.5雙端隊列 6第3節(jié)樹和二叉樹 63.1樹 61.1.2樹的基本概念 61.1.3樹的常用存儲結構 61.1.4樹的遍歷 73.2二叉樹 73.3廣義表 133.4矩陣的壓縮存儲 143.4.1特殊矩陣 143.4.2壓縮存儲 14第4節(jié)歷年真題講解 15第5節(jié)圖 225.1圖的基本概念 225.2圖的存儲結構 235.3圖的遍歷 255.4最小生成樹 255.5最短路徑 265.6拓撲排序 275.7關鍵路徑 28第6節(jié)歷年真題講解 28第7節(jié)排序 327.1排序的功能 327.2排序的穩(wěn)定性 327.3排序的類別 327.4插入排序 337.4.1直接插入排序 337.4.2希爾排序 337.5選擇排序 337.5.1直接選擇排序 337.5.2堆排序 337.6交換排序 347.6.1冒泡排序 347.6.2快速排序 347.7歸并排序 347.8基數(shù)排序 357.8.1鏈式基數(shù)排序 357.9各種內部排序方法的比較 35第8節(jié)查找 358.18.1順序查找 358.2二分查找(有序表的查找) 368.3分塊查找 378.4散列表 388.4.1散列函數(shù)的構造方法 388.4.2沖突的解決 38第9節(jié)歷年真題講解 39序論什么是數(shù)據(jù)? 所有能輸入到計算機中并能夠被計算機程序處理的符號的總稱,它是計算機程序加工的原料。什么是數(shù)據(jù)元素?數(shù)據(jù)的基本單位,在計算機程序中通常作為一個整體來進行考慮和處理。如數(shù)組中一個存儲單元里面的數(shù)或者鏈表中一個結點。什么是數(shù)據(jù)結構及種類?數(shù)據(jù)元素相互之間存在的一種或多種特定關系的集合。主要研究數(shù)據(jù)邏輯結構和存儲結構及其運算的實現(xiàn)。數(shù)據(jù)結構的種類:集合：結構中的數(shù)據(jù)元素之間除了“同屬于一個集合”的關系外，別無其它關系，如REF_Ref462487010\h圖1.1所示。圖STYLEREF1\s1.SEQ圖\*ARABIC\s11集合線性結構：結構中的數(shù)據(jù)元素之間存在一個對一個的關系，如REF_Ref462487041\h圖1.2所示。圖STYLEREF1\s1.SEQ圖\*ARABIC\s12線性結構樹形結構：結構中的數(shù)據(jù)元素之間存在一個對多個的關系，如REF_Ref462487068\h圖1.3所示。圖STYLEREF1\s1.SEQ圖\*ARABIC\s13樹結構圖狀結構或網(wǎng)狀結構：結構中的數(shù)據(jù)元素之間存在多對多的關系，如REF_Ref462487087\h圖1.4所示。圖STYLEREF1\s1.SEQ圖\*ARABIC\s14圖數(shù)據(jù)的邏輯結構結構定義中的“關系”描述的是數(shù)據(jù)元素之間的邏輯關系,又稱為邏輯結構。比如平常教學中所畫的內存圖,數(shù)組等為數(shù)據(jù)的邏輯結構。數(shù)據(jù)的物理結構數(shù)據(jù)結構在計算機中的實際表示形式稱為數(shù)據(jù)的物理結構,又稱為物理存儲。算法和算法分析計算機算法是對特定問題求解步驟的描述，它是指令的有限序列。為解決某問題的算法與為該問題編寫的程序含義是相同的。常用的表示算法的語言有：自然語言、流程圖、盒圖、程序設計語言和偽代碼。算法的五個特性有限性：算法必須在執(zhí)行有限條指令之后結束，每條指令執(zhí)行的時間也必須是有限的。確定性：算法中每一條指令必須有確切的含義，讀者和計算機在理解時不會產生二義性，并且在相同條件下，相同的輸入只能得到相同的輸出?？尚行裕核惴馨褑栴}真正的解決。即不能是理論正確但無法在計算機上實現(xiàn)的算法。輸入：一個算法有零個或多個輸入。輸出：一個算法有一個或多個輸出?！?2004年下)下面的程序段違反了算法的(54)原則。voidsam(){intn=2；while(!odd(n))n+=2；printf(n)；}(54)A.有窮性B.確定性C.可行性D.健壯性解析:odd：判斷是否是奇數(shù)!算法設計的要求正確性：算法應當滿足具體問題的需求?？勺x性：算法應該能讓人讀懂，能被計算機運行。健壯性：算法應該具有容錯處理能力，不容易被擊垮。時間高效率與低存儲量要求：效率指程序的執(zhí)行時間(越短越好)，算法要占用計算機一定的存儲量(越小越好)。算法效率的度量時間復雜度根據(jù)不同的輸入，將算法的時間復雜度分為三種情況：最佳情況：使算法執(zhí)行時間最少的輸入。一般不進行算法在最佳情況下的時間復雜度分析。最壞情況：使算法執(zhí)行時間最多的輸入。一般會進行算法在最壞時間復雜度的分析，因為最壞情況是在任何輸入下運行時間的一個上限，而且對于某些算法來說，最壞情況是相當頻繁的。平均情況：算法的平均運行時間，可按三個步驟進行分析：將所有的輸入按其執(zhí)行時間分類；確定每類輸入發(fā)生的概率；確定每類輸入的執(zhí)行時間。時間復雜度的表示算法時間復雜度符號O、Ω、Θ的定義分別如下。O記號：給出一個函數(shù)的漸進上界。給定一個函數(shù)g(n)，O(g(n))表示為一個函數(shù)集合的{f(n)：存在正常數(shù)c和n0，使得對所有的n≥n0，有O≤f(n)≤c·g(n)}。Ω記號：給出一個函數(shù)的漸進下界。給定一個函數(shù)g(n),Ω(g(n))表示為一個函數(shù)集合的{f(n)：存在正常數(shù)c和n0，使得對所有的n≥n0，有O≤c·g(n)≤f(n)。Θ記號：給出一個函數(shù)的漸進上界和下界，即漸進確界。給定一個函數(shù)g(n)，Θ(g(n))表示為一個函數(shù)集合{f(n)：存在正常數(shù)c1、c2和n0，使得對所有的n≥n0，有O≤c1·g(n)≤f(n)≤c2·g(n)}。常見的時間復雜度如REF_Ref386800129\h圖1.5所示。圖STYLEREF1\s1.SEQ圖\*ARABIC\s15常見時間復雜度的比較●(2012年上)以下關于漸進符號的表示中，不正確的是(62)。A.n)A.n2=(n2)B.n2=O(n2)C.n2=O(n)D.n2=O(n3)解析：等號左邊為{f(n):…}中值,等號右邊為O(g(n))的理解方式?！?2004年下)下面函數(shù)中漸進時間最小的是(53)。(53)A.T1(n)=n+nlognB.T2(n)=2n+nlognC.T3(n)=n2lognD.T4(n)=n+100logn空間復雜度一個算法的空間復雜度是指程序運行從開始到結束所需的存儲量。主要包含算法自身實現(xiàn)所需要的輔助存儲空間，不包含程序中原存儲數(shù)據(jù)的空間。固定空間：在硬盤上的存儲空間?？勺兛臻g：程序運行時占用的內存空間?！?2007年下)關于算法與數(shù)據(jù)結構的關系，(64)是正確的。(64)A.算法的實現(xiàn)依賴于數(shù)據(jù)結構的設計B.算法的效率與數(shù)據(jù)結構無關C.數(shù)據(jù)結構越復雜，算法的效率越高D.數(shù)據(jù)結構越簡單，算法的效率越高●(2014年上)某個算法的時間復雜度遞歸式T(n)=T(nl)+n，其中n為問題的規(guī)模，則該算法的漸進時間復雜度為(62)，若問題的規(guī)模增加了16倍，則運行時間增加(63)倍。(62)A.Θ(n)B.Θ(nlgn)C.Θ(n2)D.Θ(n2lgn)(63)A.16B.64C.256D.1024●(2006年上)設某算法的計算時間可用遞推關系式T(n)=2T(n/2)+n表示，則該算法的時間復雜度為(59)。A．O(lgn)B．O(nlgn)C．O(n)D．O(n2)●(2008年下)設某算法的計算時間表示為遞推關系式T(n)=T(n1)+n(n>0)及T(0)=1，則該算法的時間復雜度為(65)。(65)A.O(lgn)B.O(nlgn)C.O(n)D.O(n2)●(2010年上)若某算法在問題規(guī)模為n時，其基本操作的重復次數(shù)可由下式表示，則該算法的時間復雜度為(64)。(64)A.O(n)B.O(n2)C.O(logn)D.O(nlogn)●(2009年下)某算法的時間復雜度表達式為T(n)=an2+bnlgn+cn+d，其中，n為問題規(guī)模，a、b、c和d為常數(shù)，用O表示其漸進意義時間復雜度為(63)。(63)A.O(n2)B.O(n)C.O(nlgn)D.O(1)●(2010年上)若對一個鏈表最常用的操作是在末尾插入結點和刪除結點，則采用僅設尾指針的單向循環(huán)鏈表(不含頭結點)時，(65)。(65)A.插入和刪除操作的時間復雜度都為O(1)B.插入和刪除操作的時間復雜度都為O(n)C.插入操作的時間復雜度為O(1)，刪除操作的時間復雜度為O(n)D.插入操作的時間復雜度為O(n)，刪除操作的時間復雜度為O(1)●(2011年下)對n個元素值分別為1、0或1的整列數(shù)組A進行升序排序的算法描述如下：統(tǒng)計A中1、0和1的個數(shù)，設分別為n1、n2和n3，然后將A中的前n1個元素賦值為1，第n1+1到n1+n2個元素賦值為0，最后n3個元素賦值為1。該算法的時間復雜度和空間復雜度分別為(64)。●(2012年上)現(xiàn)要對n個實數(shù)(僅包含正實數(shù)和負實數(shù))組成的數(shù)組A進行重新排列，使得其中所有的負實數(shù)都位于正實數(shù)之前。求解該問題的算法的偽代碼如下所示，則該算法的時間和空間復雜度分別為(65)。i=0；j=nl；whilei<jdowhileA[i]<0doi=i+l：whileA[j]>Odoj=jl；ifi<jdo交換A[i]和A[j](65)A.(n)和(n)B．(1)和(n)C.(n)和(1)D．(1)和(1)●(2013年上)采用順序表和單鏈表存儲長度為n的線性序列，根據(jù)序號查找元素，其時間復雜度分別為(51)。(51)A.0(l)、0(l)B.0(l)、0(n)C.0(n)、0(l)D.0(n)、0(n)●(2015年上)(53)算法采用模擬生物進化的三個基本過程“繁殖(選擇)→交叉(重組)→變異(突變)”。(53)A.粒子群B.人工神經(jīng)網(wǎng)絡C.遺傳D.蟻群線性表線性表舉例線性表是由相同數(shù)據(jù)類型的結點組成的有限序列，如數(shù)組、鏈表(單鏈表、雙鏈表、循環(huán)單鏈表，循環(huán)雙鏈表)、棧、隊列,雙端隊列等。數(shù)組inta[5]={1,2,3,4,5};a[0]a[1]a[2]a[3]a[4]12345單鏈表圖STYLEREF1\s2.SEQ圖\*ARABIC\s11只有頭指針的單鏈表圖STYLEREF1\s2.SEQ圖\*ARABIC\s12有頭指針及頭結點的非空鏈表及空鏈表單循環(huán)鏈表圖STYLEREF1\s2.SEQ圖\*ARABIC\s13非空表與空表雙向循環(huán)鏈表圖STYLEREF1\s2.SEQ圖\*ARABIC\s14雙向鏈表（a）結點結構（b）空的雙向循環(huán)鏈表（c）非空的雙向循環(huán)鏈表使用頭結點的好處:不管鏈表是否為空，頭結點都不為空，這使得對鏈表的各種操作(查找和修改)得到統(tǒng)一。線性表的存儲順序存儲用地址連續(xù)的數(shù)據(jù)結構如數(shù)組來存儲線性表。優(yōu)點：能隨機存取線性表中的任何結點。缺點：數(shù)組的大小通常是固定的，不利于任意增加或減少線性表的個數(shù)；插入和刪除線性表的結點時，要移動數(shù)組中的其他元素，操作復雜。鏈接存儲用鏈表存儲線性表(鏈表)，最簡單的是單向鏈表。優(yōu)點：表的每個結點的實際存儲位置是任意的，這給線性表的插入和刪除帶來方便，只要改變鏈表有關結點的后繼指針就能完成插入或刪除的操作，不需移動任何表元。缺點：每個結點增加了一個后繼指針成分，要花費更多的存儲空間；不方便隨機訪問線性表的任一結點。線性表棧棧是一種特殊的線性表，棧只允許在同一端進行插入和刪除運算。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。稱棧的結點插入為進棧，結點刪除為出棧。因為最后進棧的結點必定最先出棧，所以棧具有后進先出的特征。圖STYLEREF1\s2.SEQ圖\*ARABIC\s15(a)盞的示意圖(b)用鐵路調度站表示盞棧有順序存儲和鏈式存儲兩種存儲方式。主要應用在數(shù)制轉換、括號匹配的檢驗、行編輯程序、迷宮求解、表達式求值等?！袢魀ush、pop分別表示入棧、出棧操作，初始棧為空且元素1、2、3依次進棧，則經(jīng)過操作序列push、push、pop、pop、push、pop之后，得到的出棧序列為(29)。(29)A.321B.213●可以用棧來檢查算術表達式中的括號是否匹配。分析算術表達式時，初始棧為空，從左到右掃描字符，遇到字符“(”就將其入棧，遇到“)”就執(zhí)行出棧操作。對算術表達式“(a+b*(a+b))/c)+(a+b)”,檢查時，(33)；對算術表達式“((a+b/(a+b)c/a)/b”,檢查時，(34)。這兩種情況都表明所檢查的算術表達式括號不匹配。(33)A.棧為空卻要進行出棧操作B.棧已滿卻要進行入棧操作C.表達式處理已結束，棧中仍留下有字符“(”D.表達式處理已結束，棧中仍留下有字符“)”(34)A.棧為空卻要進行出棧操作B.棧已滿卻要進行入棧操作C.表達式處理已結束，棧中仍留下有字符“(”D.表達式處理已結束，棧中仍留下有字符“)”逆波蘭式：是一種算術表達式的另一種表示，也稱為后綴表示，定義為把運算符放在兩個運算對象的后面。中綴算術表達式（又名波蘭式）轉換成對應的后綴算術表達式：把每個運算符都移到運算對象的后面，然后去掉括號即可?！癖磉_式采用逆波蘭式表示時可以不用括號，而且可以用基于（1）的求值過程進行計算，與逆波蘭式ab+cd+*對應的中綴表達式為：（2）。1．A.棧B.隊列C.符號表D.散列表2．A．a+b+c*dB.(a+b)*c+dC.(a+b)*(c+d)D.a+b*c+d●表達式a*(b+c)d的后綴表達形式為____.(39)A.abcd*+B.abc+*dC.abc*+dD.+*abcd隊列隊列也是一種特殊的線性表，只允許在一端進行插入，另一端進行刪除運算。允許刪除運算的那一端稱為隊首，允許插入運算的一端稱為隊尾。稱隊列的結點插入為進隊，結點刪除為出隊。因最先進入隊列的結點將最先出隊，所以隊列具有先進先出的特征。順序存儲隊列可以用順序存儲線性表來表示隊列，為了指明當前執(zhí)行出隊運算的隊首位置，需要一個指針變量head(稱為隊頭指針)，為了指明當前執(zhí)行進隊運算的隊尾位置，也需要一個指針變量tail(稱為尾指針)，如REF_Ref462520420\h圖2.6所示。圖STYLEREF1\s2.SEQ圖\*ARABIC\s16順序存儲隊列若用有N個元素的數(shù)組表示隊列，隨著一系列進隊和出隊運算，隊列的結點移向存放隊列的數(shù)組的尾端，會出現(xiàn)數(shù)組的前端空著，而隊列空間已用完的情況。一種可行的解決辦法是當發(fā)生這樣的情況時，把隊列中的結點移到數(shù)組的前端，修改頭指針和尾指針。另一種更好的解決辦法是采用循環(huán)隊列。循環(huán)隊列就是將實現(xiàn)隊列的數(shù)組a的第一個元素a[0]與最后一個元素a[n1]連接起來。隊空的初態(tài)為head=tail=O。在循環(huán)隊列中，當tail趕上head時，隊列滿。反之，當head趕上tail時，隊列變?yōu)榭?。這樣隊空和隊滿的條件都同為head=tail，這會給程序判別隊空或隊滿帶來不便。因此，可采用當隊列只剩下一個空閑結點的空間時，就認為隊列已滿，用這種簡單辦法來區(qū)別隊空和隊滿。圖STYLEREF1\s2.SEQ圖\*ARABIC\s17循環(huán)隊列即隊空的判別條件是head=tail，隊滿的判別條件是head=(tail+1)modn。鏈接存儲隊列隊列也可以用鏈接存儲線性表實現(xiàn)，用鏈表實現(xiàn)的隊列稱為鏈接隊列。鏈表的第一個結點是隊列首結點，鏈表的末尾結點是隊列的隊尾結點，隊尾結點的鏈接指針值為NULL。隊列的頭指針font指向鏈表的首結點，隊列的尾指針rear指向鏈表的尾結點。當font==rear,隊列為空。圖STYLEREF1\s2.SEQ圖\*ARABIC\s18鏈式存儲隊列例題分析：●判斷“鏈式隊列為空”的條件是：____(front為頭指針，rear為尾指針)A．front＝NULLB.rear==NULLC.front==rearD.front!=rear●若in、out分別表示入、出隊操作，初始隊列為空且元素a、b、c依次入隊，則經(jīng)過操作序列in、in、out、out、in、out之后，得到的出隊序列為(30)。(30)A.cbaB.bacC.bcaD.abc雙端隊列限定插入和刪除操作在表的兩端進行的線性表(注意其與隊列的區(qū)別)。圖STYLEREF1\s2.SEQ圖\*ARABIC\s19雙端隊列●輸入受限的雙端隊列是指元素只能從隊列的一端輸入、但可以從隊列的兩端輸出，如下圖所示。若有8、1、4、2依次進入輸入受限的雙端隊列，則得不到輸出序列(57)。(57)A.2、8、4、1B.1、4、8、2C.4、2、1、8D.2、1、4、8樹和二叉樹樹樹的基本概念樹是由零個或多個結點組成的有限集合T。樹的幾個概念：樹的結點、結點的度(又叫次數(shù))、樹的度(又叫次數(shù))、葉子結點(終端結點)、非終端結點(分支結點)、孩子、雙親、兄弟、樹的深度等，如REF_Ref462522277\h圖3.1所示。圖STYLEREF1\s3.SEQ圖\*ARABIC\s11樹根結點的度數(shù)為3，結點2的度數(shù)為4，結點4的度數(shù)為1，結點9的成數(shù)為2，其他結點的度數(shù)為0，該樹的度數(shù)4，該樹的深度為4。定義一棵樹的根結點所在的層次為1(這里暫且定義1，也可以把它定義0層，考試時題目會有明確的規(guī)定)，其他結點所在的層次等于它的父結點所在的層次加1。樹中各結點的層次的最大值稱為樹的層次。樹的常用存儲結構標準存儲結構在樹的標準存儲結構中，樹中的結點內容可分成兩部分，分別為結點的數(shù)據(jù)和指向孩子結點的指針數(shù)組。對于N度樹，在其標準存儲結構中指針數(shù)組有N個元素。例如，設樹的次數(shù)為5，樹的結點數(shù)據(jù)僅限于字符，用c代碼描述樹結點的標準存儲結的數(shù)據(jù)類型如下：#defineN5typedefstructtnode{chardata；//樹結點的數(shù)據(jù)信息structtnode*child[N]；//樹結點的子結點指針}TNODE；//樹結點的數(shù)據(jù)類型帶逆存儲結構帶逆存儲結構在標準存儲結構的基礎上增加了一個指向其父結點的指針，用c代碼描述樹結點的帶逆存儲結構的數(shù)據(jù)類型如下：#defineN5typedefstructrtnode{chardata：//樹的結點數(shù)據(jù)信息strucrtnode*child[N]；//樹結點的子結點指針structrtnode*parent；//p父結點指引}RTNODE；//樹結點的數(shù)據(jù)類型樹的遍歷前序遍歷：首先訪問根結點，然后從左到右按前序遍歷根結點的各棵子樹。后序遍歷：首先從左到右按后序遍歷根結點的各棵子樹，然后訪問根結點。層次遍歷：首先訪問處于第1層上的根結點，然后從左到右依次訪問處于第2層上的結點，然后在從左到右依次訪問處于第3層上的結點等等，即自上而下從左到右逐層訪問樹各層上的結點。圖STYLEREF1\s3.SEQ圖\*ARABIC\s12樹上述各種遍歷結果如下：前序：1，2，5，6，7，8，3，4，9，a，b。后序：5，6，7，8，2，3，a，b，9，4，1。層次：1，2，3，4，5，6，7，8，9，a，b。注意：樹沒有中序遍歷。二叉樹二叉樹的基本概念二叉樹是一個有限的結點集合，該集合或者為空，或者是由一個根結點及其兩棵互不相交的左、右叉子樹所組成的。二叉樹的結點中有兩棵子二叉樹，分別稱為左子樹和右子樹。因二叉樹可以為空，所以二叉樹中的結點可能沒有孩子結點，也可能只有一個左子結點(或右子結點)，也可能同時有左右兩個了結點。如REF_Ref462603244\h圖3.3所示的是二叉樹的4種可能形態(tài)(如果把空樹計算在內，則共有5種狀態(tài))。圖STYLEREF1\s3.SEQ圖\*ARABIC\s13二叉樹的四種不同形態(tài)二叉樹與樹的區(qū)別二叉樹中，結點的子樹是有序的，分左右兩棵子樹。單就樹來說，一個結點可能擁有更多的孩子，所以沒有左右之分。問題：二叉樹是否為一種特殊的樹？答案：不是。樹及森林轉到二叉樹最左孩子結點變左孩子；兄弟結點變右孩子。樹轉成二叉樹圖STYLEREF1\s3.SEQ圖\*ARABIC\s14樹轉成二叉樹森林轉成二叉樹給各棵樹的根都定一個總雙親，讓各棵樹變成子樹，然后按照樹轉二叉樹的方法轉，最后去掉總雙親。二叉樹的性質性質1：在二叉樹的第i層上至多有2i-1個結點(i性質2：深度為k的二叉樹最多有2k-1個結點(k性質3：對任何一棵二叉樹，如果其葉子結點個數(shù)為n0,度為2的節(jié)點數(shù)為n2,則n0=補充:假設度為1的結點個數(shù)為n1,則二叉樹的結點個數(shù)n=n0+n1+n2,且n0滿二叉樹一棵深度為k且有2k-如REF_Ref462604765\h圖3.5所示就是一棵滿二叉樹，對結點進行順序編號。圖STYLEREF1\s3.SEQ圖\*ARABIC\s15滿二叉樹完全二叉樹如果深度為k，有n個結點的二叉樹中的結點能夠與深度為k的順序編號的滿二叉樹從1到n標號的結點相對應，則稱這樣的二叉樹為完全二叉樹。在一棵深度為k(k≥1)的完全二叉樹中，所有的葉子結點都出現(xiàn)在第k層或第k1層(最后兩層)。在完全二叉樹中，若一個結點沒有左子結點，則它必定沒有右子結點，所以一定是葉子結點。完全二叉樹中度為1的結點數(shù)只能為0或1。圖STYLEREF1\s3.SEQ圖\*ARABIC\s16完全二叉樹REF_Ref462604858\h圖3.6中，（a）是，（b）、（c）不是，根據(jù)完全二叉樹的定義。注意:滿二叉樹是完全二叉樹,但完全二叉樹不一定是滿二叉樹。完全二叉樹的性質性質4：具有n個結點的完全二叉樹的深度為log2n+1(其中為下取整)例子:在一棵完全二叉樹中，其根的序號為1，(33)可判定序號為p和q的兩個結點是否在同一層。(33)A．log2p=log2qB．log2p=log2qC．log2p性質5：如果對一棵n個結點的完全二叉樹的結點按層次編號(從第一層到第log2n+1層，每層從左到右)，則對任一結點i(1≤i≤如果i=1,則結點i無雙親，是二叉樹的根結點；如果i>1,則其雙親結點是i2如果2i〉n,則結點i為葉子結點，無左孩子，否則，其左孩子是2i;2i+1〉n,則結點i無右孩子；否則，其右孩子是結點2i+1。注意:性質1、性質2、性質3適用于所有類型的二叉樹，而性質4、性質5只適用于滿二叉樹和完全二叉樹。二叉樹的四種遍歷前序遍歷(先根遍歷、先序遍歷)：根左右根一定是遍歷序列的第一個元素。中序遍歷(中根遍歷)：左根右。后序遍歷(后根遍歷)：左右根根一定是遍歷序列的最后一個。層次遍歷：根一定是遍歷序列的第一個。圖STYLEREF1\s3.SEQ圖\*ARABIC\s17二叉樹遍歷先序：中序：后序：層次：注意：前序遍歷、中序遍歷、后續(xù)遍歷屬于深度優(yōu)先遍歷，層次遍歷屬于廣度優(yōu)先遍歷。都采用遞歸定義。性質：一棵二叉樹的前序序列與中序序列可以唯一地確定這棵樹。例：前序序列：ABHFDECKG；中序序列：HBDFAEKCG，則構造二叉樹的過程為：圖STYLEREF1\s3.SEQ圖\*ARABIC\s18已知前序序列和中序序列,求二叉樹的過程問題：什么情況下，二叉樹的前序遍歷序列與中序遍歷序列相同？答：只有根結點的二叉樹或只有右子樹的二叉樹。什么情況下，二叉樹的前序遍歷序列與后序遍歷序列相同？答：只有根結點的二叉樹?！?2003真題)結論“(7)”是正確的。(07)A．二叉樹的度為2 B．樹中結點的度可以小于2C．二叉樹中至少有一個結點的度為2 D．二叉樹中任何一個結點的度都為2二叉排序樹二叉排序樹也叫最優(yōu)查找樹(二叉查找樹)：或是一棵空樹，或者是具有下列性質(BST)的二叉樹：若它的左子樹非空，則左子樹上的所有結點的值均小于根結點；若它的右子樹非空,則右子樹上的所有結點均大于根結點;左、右子樹本身又各是一棵二叉排序樹。特點簡記：左小右大在二叉查找樹中，由根結點到所有其他結點的路徑長度總和稱為內部路徑長度。具有最小內部路徑長度的樹稱為豐滿樹，對豐滿查找樹進行插入或者刪除操作后，會產生一棵非豐滿樹,如REF_Ref462688912\h圖3.9所示：圖STYLEREF1\s3.SEQ圖\*ARABIC\s19二叉排序樹二叉排序樹的插入、刪除和查找時間復雜度均為：O(log2n●【2006年下半年】結點數(shù)目為n的二叉查找樹(二叉排序樹)的最小高度為(52)、最大高度為(53)。(52)A.nB.n2C.[log2n](53)A.nB.n2C.[log2n平衡二叉樹平衡二叉樹又稱AVL樹。它或者是一棵空樹，或者是具有下列性質的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。平衡二叉樹的的高度總為：log2n，基本操作的平均時間為O(log2n)，最壞情況下也為O二叉樹上結點的平衡因子BF：左子樹的深度減去它的右子樹的深度。平衡二叉樹上所有結點的平衡因子只可能是－1、0、1。只要二叉樹上有一個平衡因子的絕對值大于1，則該二叉樹就是不平衡的,如REF_Ref462690844\h圖3.10所示。圖STYLEREF1\s3.SEQ圖\*ARABIC\s110(a)平衡二叉樹(b)非平衡二叉樹●【2005年下半年】由元素序列(27,16,75,38,51)構造平衡二叉樹，則首次出現(xiàn)的最小不平衡子樹的根(即離插入結點最近且平衡因子的絕對值為2的結點)為(46)。(46)A.27B.38C.51D.75注意：構建以后的平衡二叉樹是二叉排序樹。m階B樹m階B樹是一種平衡的m叉樹，具有如下的性質：樹中每個結點至多有m棵子樹；除了根結點和葉子結點之外，每個結點的孩子個數(shù)大于等于m2)具有k個孩子的非葉結點含有k1個鍵值所有葉結點在同一層上，而且不附有信息。最優(yōu)二叉樹樹的(內部)路徑長度:從樹根到樹中每一個結點的路徑長度之和。在結點數(shù)相同的二叉樹中,豐滿樹的(內部)路徑長度最短。結點的權：可以賦予樹中結點一個有某種意義的實數(shù),這些數(shù)字稱為結點的權。結點的帶權路徑長度：結點到樹根之間的路徑長度與該結點上權的乘積,稱為結點的帶權路徑長度.樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和,稱為樹的帶權路徑長度(樹的代價),通過記為:WPL=k=1n帶權路徑長度最小(即代價最小)的二叉樹稱為最優(yōu)二叉樹或赫夫曼樹。構造一棵赫夫曼樹的過程如下:圖STYLEREF1\s3.SEQ圖\*ARABIC\s111赫夫曼樹的構造過程赫夫曼樹是嚴格的二叉樹，沒有度數(shù)為1的結點?！瘛?004年】若一棵赫夫曼樹共有9個結點，則其葉子結點為：______。A.4B.5C赫夫曼編碼：左分支表示’0’,右分支表示’1’在數(shù)據(jù)壓縮編碼的應用中，赫夫曼算法可以用來構造具有最優(yōu)前綴碼的二叉樹，這是一種貪心的算法?！裼蓹嘀禐?，2，5，7的四個葉子構造一棵哈夫曼樹，該樹的帶權路徑長度為________。(50)A.23B.37C.44二叉樹的存儲結構順序存儲用一組地址連續(xù)的存儲單元依次自上而下、自左而右存儲完全二叉樹上的結點元素，即將二叉樹上編號為i的節(jié)點元素存儲在一維數(shù)組中。對于一般的二叉樹，則將其每個結點與完全二叉樹上的結點相對照，存儲在一維數(shù)組的相應分量中。圖STYLEREF1\s3.SEQ圖\*ARABIC\s112二叉樹1REF_Ref462692199\h圖3.12所示的二叉樹順序存儲為：圖STYLEREF1\s3.SEQ圖\*ARABIC\s113二叉樹2REF_Ref462692270\h圖3.13所示的二叉樹順序存儲為：圖中以“0”表示不存在此結點。這種順序結構僅適用于完全二叉樹。因為，在最壞得情況下，一個深度為k且有k個結點的單支樹(樹中不存在度為2的結點)確需要長度為2k1鏈式存儲二叉樹常采用類似樹的存儲結構，其結點類型可以用C語言定義如下：typedefstructBtnode{chardata；//數(shù)據(jù)structBtnode*Ichild；//左孩子structBtnode*rchild；//右孩子}BYNODE；●【2005年下半年】在二叉樹的順序存儲中，每個結點的存儲位置與其父結點、左右子樹結點的位置都存在一個簡單的映射關系，因此可與三叉鏈表對應。若某二叉樹共有n個結點，采用三叉鏈表存儲時，每個結點的數(shù)據(jù)域需要d個字節(jié)，每個指針域占用4個字節(jié)，若采用順序存儲，則最后一個結點下標為k(起始下標為1),那么___(39)___時采用順序存儲更節(jié)省空間。(39)廣義表也稱為列表。廣義表通常用括號括起來，用逗號分隔廣義表中的元素，原定用小寫字母表示原子，用大寫字母表示廣義表：廣義表LS=(a1,a2,a3,…廣義表的長度：該廣義表中包含的元素(包括原子和子表)的個數(shù)。廣義表的深度：表展開后所含括號的層數(shù)。表頭和表尾：稱第一個元素a1為LS的表頭，稱其余元素組成的表(a2,a3,…,anA=():A是一個空廣義表，長度為0，深度為1B=(e):B只有一個原子e,長度為1，深度為1。C=(a，(b，c，d)):列表C長度為2，兩個元素分別是a和子表(b，c，d)，深度為2。D=(A,B,C):列表D的長度為3，三個元素都是列表。顯然，將子表的值帶入后，則有D＝(()，(e)，(a，(b，c，d)))，深度為3。E=(a,E):這是一個遞歸的表，它的長度為2。E相當于一個無限的列表E＝(a,(a,(a,…..)))，深度為∞。圖STYLEREF1\s3.SEQ圖\*ARABIC\s114列表D的圖GetHead(B)=eGetTail(B)=();GetHead(D)=AGetTail(B)=(B,C);G=(())：長度為1，深度為2，可分解得到其表頭、表尾均為空表()；●若廣義表L=((1,2,3))，則L的長度和深度分別為(36)。(36)A．1和1B．1和2C．1和3D．2和2矩陣的壓縮存儲特殊矩陣對稱矩陣若n階矩陣A中的元滿足aij=aji(1≤i,j≤n),則稱為對稱矩陣。對角矩陣REF_Ref462693977\h圖3.15所示的矩陣為對角矩陣。圖STYLEREF1\s3.SEQ圖\*ARABIC\s115對角矩陣上(下)三角矩陣圖STYLEREF1\s3.SEQ圖\*ARABIC\s116上（下）三角矩陣單位矩陣主對角線上的元素全為1，其余元素全為0的n階矩陣。圖STYLEREF1\s3.SEQ圖\*ARABIC\s117單位矩陣三對角矩陣圖STYLEREF1\s3.SEQ圖\*ARABIC\s118三對角矩陣壓縮存儲為多個值相同的元只分配一個存儲空間，對零元不分配空間。壓縮存儲的目的是節(jié)約存儲空間。特殊矩陣通?？梢圆捎脡嚎s存儲的方法，使用的是一維數(shù)組。1這個對陣矩陣可以壓縮到以下數(shù)組中(按行存儲)：a11a21a22a31a32a33等同于：212301歷年真題講解2009年上半年●下面關于二叉排序樹的敘述，錯誤的是(59)。(59)A.對二叉排序樹進行中序遍歷，必定得到結點關鍵字的有序列B.依據(jù)關鍵字無序的序列建立二叉排序樹，也可能構造出單支樹C.若構造二叉排序樹時進行平衡化處理，則根結點的左子樹高度與右子樹高度的差值一定不超過1。D.若構造二叉排序樹時進行平衡化處理，則根節(jié)點的左子樹高度與右子樹高度的差值一定不超過1.●下面關于棧和隊列的敘述，錯誤的是(60)。(60)A.棧和隊列都是操作受限的線性表B.隊列采用單循環(huán)鏈表存儲時，只需設置隊尾指針就可使入隊和出隊操作的時間復雜度都為O(1)C.若隊列的數(shù)據(jù)規(guī)模n可以確定，則采用順序存儲結構比鏈式存儲結構效率更高D.利用兩個?？梢阅M一個隊列的操作，反之亦可●下面關于二叉樹的敘述，正確的是(61)。(61)A.完全二叉樹的高度h與其結點數(shù)n之間存在確定的關系B.在二叉樹的順序存儲和鏈式存儲結構中，完全二叉樹更適合采用鏈式存儲結構C.完全二叉樹中一定不存在度為1的結點D.完全二叉樹中必定有偶數(shù)個葉子結點●設L為廣義表，將head(L)定義為取非空廣義表的第一個元素，tail(L)定義為取非空廣義表除第一個元素外剩余元素構成的廣義表。若廣義表定義為取L=((x,y,z),a,(u,t,w))，則從L中取出原子項y的運算是(62)。(62)A.head(tail(tail(L)))B.tail(head(head(L)))C.head(tail(head(L)))D.tail(tail(head(L)))2009年下半年●已知一個二叉樹的先序遍歷序列為①、②、③、④、⑤，中序遍歷序列為②、①、④、③、⑤，則該二叉樹的后序遍歷序列為(57)。對于任意一棵二叉樹，敘述錯誤的是(58)。(57)A②、③、①、⑤、④B.①、②、③、④、⑤C.②、④、⑤、③、①D.④、⑤、③、②、①(58)A.由其后序遍歷序列和中序遍歷序列可以構造該二叉樹的先序遍歷序列B.由其先序遍歷序列和后序遍歷序列可以構造該二叉樹的中序遍歷序列C.由其層序遍歷序列和中序遍歷序列可以構造該二叉樹的先序遍歷序列D.由其層序遍歷序列和中序遍歷序列不能構成該二叉樹的先序遍歷序列●單向鏈表中往往含有一個頭結點，該結點不存儲數(shù)據(jù)元素，一般令鏈表的頭指針指向該結點，而該結點指針域的值為第一個元素結點的指針。以下關于單鏈表頭結點的敘述中，錯誤的是(60)。(60)A.若在頭結點中存入鏈表長度值，則求鏈表長度運算的時間復雜度為O(1)B.在鏈表的任何一個元素前后進行插入和刪除操作可用一致的方式進行處理C.加入頭結點后，代表鏈表的頭指針不因為鏈表為空而改變D.加入頭結點后，在鏈表中進行查找運算的時間復雜度為O(1)●對于長度為m(m>1)的指定序列，通過初始為空的一個棧、一個隊列后，錯誤的敘述是(61)。(61)A.若入棧和入隊的序列相同，則出棧序列和出隊序列可能相同B.若入棧和入隊的序列相同，則出棧序列和出隊序列可以互為逆序C.入隊序列與出隊序列關系為1:1，而入棧序列與出棧序列關系是1:n(n≥1)D.入棧序列與出棧序列關系為1:1，而入隊序列與出隊序列關系是1:n(n≥1)●字符串采用鏈表存儲方式時，每個結點存儲多個字符有助于提高存儲密度。若采用結點大小相同的鏈表存儲串，則串比較、求子串、串連接、串替換等串的基本運算中，(62)。(62)A.進行串的比較運算最不方便B.進行求子串運算最不方便C.進行串連接最不方便D.進行串替換最不方便2010年上半年●設有如下所示的下三角矩陣A[0..8,0..8]，將該三角矩陣的非零元素(即行下標不小于列下標的所有元素)按行優(yōu)先壓縮存儲在數(shù)組M[1..m]中，則元素A[ij](o≤i≤8，j≤i)存儲在數(shù)組M的(58)中?！袢粲胣個權值構造一棵最優(yōu)二叉樹(哈夫曼樹)，則該二叉樹的結點總數(shù)為(59)。(59)A.2nB.2n-1C●棧是一種按“后進先出”原則進行插入和刪除操作的數(shù)據(jù)結構，因此，(60)必須用棧。(60)A.實現(xiàn)函數(shù)或過程的遞歸調用及返回處理時B.將一個元素序列進行逆置C.鏈表結點的申請和釋放D.可執(zhí)行程序的裝入和卸載●若對一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則采用僅設尾指針的單向循環(huán)鏈表(不含頭結點)時，(65)。(65)A.插入刪除操作的時間復雜度都為O(1)B.插入和刪除操作的時間復雜度都為O(n)C.插入操作的時間復雜度為O(1),刪除操作的時間復雜度為O(n)D.插入操作的時間復雜度為O(n),刪除操作的時間復雜度為O(1)2011年上半年●算術表達式采用逆波蘭式表示時不用括號，可以利用(20)進行求值，與逆波蘭式abcd+*對應的中綴表達式是(21)。(20)A.數(shù)組 B.棧 C.隊列 D.散列表(21)A.ab+c*d B.(ab)*c+d C.(ab)*(c+d) D.ab*c+d●設下三角矩陣(上三角部分的元素值都為0)A[0..n,0..n]如下所示，將該三角矩陣的所有非零元素(即行下標不小于列下標的元素)按行優(yōu)先壓縮存儲在容量足夠大的數(shù)組M[]中(下標從1開始)，則元素A[I,j](0≤i≤n,j≤i)存儲在數(shù)組M的(57)中。●在(59)中，任意一個結點的左、右子樹的高度之差的絕對值不超過1。(59)A.完全二叉樹B.二叉排序樹C.線索二叉樹D.最優(yōu)二叉樹2011年下半年●若二維數(shù)組arr[1..M,1..N]的首地址為base，數(shù)組元素按列存儲且每個元素占用K個存儲單元，則元素arr[I,j]在該數(shù)組空間的地址為(21)。(21)A.base+((i1)*M+j1)*K B.base+((i1)*N+j1)*KC.base+((j1)*M+i1)*K D.base+((j1)*N+i1)*K●對于線性表(由n個同類元素構成的線性序列)，采用單向循環(huán)鏈表存儲的特點之一是(58)。(58)A.從表中任意結點出發(fā)都能遍歷整個鏈表B.對表中的任意結點可以進行隨機訪問C.對于表中的任意一個結點，訪問其直接前驅和直接后繼結點所用時間相同D.第一個結點必須是頭結點●一棵滿二叉樹，其每一層結點個數(shù)都達到最大值，對其中的結點從1開始順序編號，即根結點編號為1，其左、右孩子結點編號分別為2和3，再下一層從左到右的編號為4、5、6、7，依此類推，每一層都從左到右依次編號，直到最后的葉子結點層為止，則用(60)可判定編號為m和n的兩個結點是否在同一層?！?61)是由權值集合{8，5，6，2}構造的哈夫曼樹(最優(yōu)二叉樹)。(61)A. B. C. D.2012年上半年●對于二維數(shù)組a[l．．N，l．．N】中的一個元素a[i,j](1≤i,j≤N)，存儲在a[i,j]之前的元素個數(shù)(21)。(21)A．與按行存儲或按列存儲方式無關B．在ij時與按行存儲或按列存儲方式無關C．在按行存儲方式下比按列存儲方式下要多D．在按行存儲方式下比按列存儲方式下要少●對于一個長度大于l且不存在重復元素的序列，令其所有元素依次通過一個初始為空的隊列后，再通過一個初始為空的棧。設隊列和棧的容量都足夠大，一個序列通過隊列(棧)的含義是序列的每個元素都入隊列(棧)且出隊列(棧)一次且僅一次。對于該序列在上述隊列和棧上的操作，正確的敘述是(57)。(57)A．出隊序列和出棧序列一定相同B．出隊序列和出棧序列一定互為逆序C．入隊序列與出隊序列一定相同，入棧序列與出棧序列不一定相同D．入棧序列與出棧序列一定互為逆序，入隊序列與出隊序列不一定互為逆序●若n2、n1、n0分別表示一個二叉樹中度為2、度為1和葉子結點的數(shù)目(結點的度定義為結點的子樹數(shù)目)，則對于任何一個非空的二叉樹，(59)。(59)A.n2一定大于n1B.n1定大于n0C.n2定大于n0D.n0定大于n22012年下半年●若某二叉樹的后序遍歷序列為KBFDCAE，中序遍歷序列為BKEFACD，則該二叉樹為(58)?！裣聢D所示為一棵M階B樹，M最有可能的值為(61)。(61)A．IB．2C．3D．4●霍夫曼編碼將頻繁出現(xiàn)的字符采用短編碼，出現(xiàn)頻率較低的字符采用長編碼。具體的操作過程為：i)以每個字符的出現(xiàn)頻率作為關鍵字構建最小優(yōu)先級隊列；ii)取出關鍵字最小的兩個結點生成子樹，根節(jié)點的關鍵字為孩子節(jié)點關鍵字之和，并將根節(jié)點插入到最小優(yōu)先級隊列中，直至得到一穎最優(yōu)編碼樹?；舴蚵幋a方案是基于(64)策略的。用該方案對包含a到f六個字符的文件進行編碼，文件包含100,000個字符，每個字符的出現(xiàn)頻率(用百分比表示)如下表所示，則與固定長度編碼相比，該編碼方案節(jié)省了(65)存儲空間。字符abcdef出現(xiàn)頻率1832481226(64)A．分治B．貪心C．動態(tài)規(guī)劃D．回溯(65)A．21%B．27%C．18%D．36%2013年上半年●設元素序列a、b、c、d、e、f經(jīng)過初始為空的棧S后，得到出棧序列cedfba，則棧S的最小容量為(52)。(52)A.3B.4C.5D.6●輸出受限的雙端隊列是指元素可以從隊列的兩端輸入、但只能從隊列的一端輸出，如下圖所示。若有el、e2、e3、e4依次進入輸出受限的雙端隊列，則得不到輸出序列(53)。(53)A.e4、e3、e2、elB.e4、e2、el、e3C.e4、e3、el、e2D.e4、e2、C3、C1●一個高度為h的滿二叉樹的結點總數(shù)為2h一1，從根結點開始，自上而下、同層次結點從左至右，對結點按照順序依次編號，即根結點編號為1，其左、右孩子結點編號分別為2和3，再下一層從左到右的編號為4、5、6、7，依此類推。那么，在一棵滿二叉樹中，對于編號為m和n的兩個結點，若n=2m+1，則(64)結點。(64)A.m是n的左孩子B.m是n的右孩子C.n是m的左孩子D.n是m的右孩子2013年下半年●算數(shù)表達式a+(bc)*d的后綴式是(22)(－、＋、*表示算數(shù)的減加乘運算，運算符的優(yōu)先級和結合性遵循慣例)。(22)A.bc－d*a＋ B.abc－d*+C.ab＋c－d* D.abcd－*＋●以下關于線性表存儲結構的敘述，正確的是(57)(57)A.線性表采用順序存儲結構時，訪問表中任意一個指定序號元素的時間復雜度為常量級B.線性表采用順序存儲結構時，在表中任意位置插入新元素的運算時間復雜度為常量級C.線性表采用鏈式存儲結構時，訪問表中任意一個指定序號元素的時間復雜度為常量級D.線性表采用鏈式存儲結構時，在表中任意位置插入新元素的運算時間復雜度為常量級●設循環(huán)隊列的定義中有front和size兩個域變量，其中front表示隊頭元素的指針，size表示隊列的長度，如下圖所示(隊列長度為3，對頭元素為X，隊尾元素為Z)，設隊列的存儲空間容量為M，則隊尾元素的指針為(58)(58)A.(Q.front+Q.size1)B.(Q.front+Q.size1+M)%MC.(Q.frontQ.size)D.(Q.frontQ.size+M)%M●以下關于哈夫曼樹的敘述，正確的是(60)(60)A.哈夫曼樹一定是滿二叉樹，其每層結點數(shù)都達到最大值B.哈夫曼樹一定是平衡二叉樹，其每個結點左右子樹的高度差為1,0,1C.哈夫曼樹中左孩子結點的權值小于父節(jié)點、右孩子結點的權值大于父節(jié)點D.哈夫曼樹中葉子結點的權值越小則距離樹根越遠、葉子結點的權值越大則距離樹根越近2014年上半年●若對線性表的最常用操作是訪問任意指定序號的元素，并在表尾加入和刪除元素，則適宜采用(57)存儲。(57)A．順序表B．單鏈表C．雙向鏈表D．哈希表●某二叉樹如圖所示，若進行順序存儲(即用一堆數(shù)組元素存儲該二叉樹中的結點且通過下標反映結點間的關系，例如，對于下標為i的結點，其左孩子的下標為2i、右孩子的下標為2i+1)，則該數(shù)組的大小至少為(58)；若采用三叉鏈表存儲該二叉樹(各個結點包括結點的數(shù)據(jù)、父結點指針、左孩子指針、右孩子指針)，則該鏈表的所有結點中空指針的數(shù)目為(59)。(58)A.6B.10C.12D.15(59)A.6B.8C.12D.14●某雙端隊列如下圖所示，要求元素進出隊列必須在同一端口，即從A端進入的元素必須從A端出、從B端進入的元素必須從B端出，則對于4個元素的序列el、e2、e3、e4，若要求前2個元素(el、e2)從A端口按次序全部進入隊列，后兩個元素(e3、e4)從B端口按次序全部進入隊列，則可能得到的出隊序列是(60)。(60)A.el、e2、e3、e4B.e2、e3、e4、elC.e3、e4、el、e2D.e4、e3、e2、el2014年下半年●對于線性表，相對于順序存儲：采用鏈表存儲的缺點是(57)。(57)A.數(shù)據(jù)元素之間的關系需要占用存儲空間，導致存儲密度不高B.表中結點必須占用地址連續(xù)的存儲單元，存儲密度不高C.插入新元素時需要遍歷整個鏈表，運算的時間效率不高D.刪除元素時需要遍歷整個鏈表，運算的時間效率不高(58)A.值為n的元素B.值為l的元素C.值為nk的元素D.不確定的●在某個二叉查找樹(即二叉排序樹)中進行查找時，效率最差的情形是該二叉查找樹是(59)。(59)A.完全二叉樹B.平衡二叉樹C.單枝樹D.滿二叉樹●已知一個文件中出現(xiàn)的各字符及其對應的頻率如下表所示。若采用定長編碼，則該文件中字符的碼長應為(64)。若采用Huffman編碼，則字符序列“face”的編碼應為(65)。字符abcdef頻率(%)4513121695(64)A.2B.3C.4D.5(65)A.110001001101B.C.101000010100D.2015年上半年●(2015年上半年)與算術表達式“(a+(bc))*d”對應的樹是(21)?！裨O某循環(huán)隊列Q的定義中有front和rear兩個域變量，其中，front指示隊頭元素的位置，rear指示隊尾元素之后的位置，如下圖所示。若該隊列的容量為M，則其長度為(57)。(57)A.(Q.rearQ.front+1)B.(Q.rearQ.front+M)C.(Q.rearQ.front+1)%MD.(Q.rearQ.front+M)%M●設棧S和隊列Q的初始狀態(tài)為空，元素abcdefg依次進入棧S。要求每個元素出棧后立即進入隊列Q，若7個元素出隊列的順序為bdfecag，則棧S的容量最小應該是(58)。(58)A.5B.4C.3D.2●某二叉樹的先序遍歷序列為cabfedg，中序遍歷序列為abcdefg，則該二叉樹是(59)。(59)A.完全二叉樹B.最優(yōu)二叉樹C.平衡二叉樹D.滿二叉樹●優(yōu)先隊列通常采用(62)數(shù)據(jù)結構實現(xiàn)，向優(yōu)先隊列中插入一個元素的時間復雜度為(63)。(62)A.堆B.棧C.隊列D.線性表(63)A.Θ(n)B.Θ(1)C.Θ(lgn)D.Θ(n2)2015年下半年●表達式采用逆波蘭式表示時，利用(22)進行求值。(22)A.棧B.隊列C.符號表D.散列表●對于一個長度為n(n>1)且元素互異的序列，令其所有元素依次通過一個初始為空的棧后，再通過一個初始為空的隊列。假設隊列和棧的容量都足夠大，且只要棧非空就可以進行出棧操作，只要隊列非空就可以進行出隊操作，那么以下敘述中，正確的是(57)。(57)A.出隊序列和出棧序列一定互為逆序B.出隊序列和出棧序列一定相同C.入棧序列與入隊序列一定相同D.入棧序列與入隊序列一定互為逆序●設某n階三對角矩陣An*n的示意圖如下圖所示。若將該三對角矩陣的非零元素按行存儲在一維數(shù)組B[k](1<=k<=3*n2)中，則k與i、j的對應關系是(58)。(58)A.k=2i+j2B.k=2ij+2C.k=3i+j1D.k=3ij+2●對于非空的二叉樹，設D代表根結點，L代表根結點的左子樹，R代表根結點的右子樹。若對下圖所示的二叉樹進行遍歷后的結點序列為,則遍歷方式是(59)。(59)A.LRDB.DRLC.RLDD.RDL2016年上半年●若元素以a、b，c、d、e的順序進入一個初始為空的棧中，每個元素進棧、出棧各1次，要求出棧的第一個元素為d，則合法的出棧序列共有(57)種。(57)A.4B.5C.6D.24●設有二叉排序樹(或二叉查找樹)如下圖所示，建立該二叉樹的關鍵碼序列不可能是(58)。(58)A.233117191127139061B.231719312790611113C.231727193113119061D.233190612717191113●若一棵二叉樹的高度(即層數(shù))為h，則該二叉樹(59)。(59)A.有2h個結點B.有2h1個結點C.最少有2h1個結點D.最多有2h1個結點2016年下半年●二維數(shù)組a[l..N,1..N]可以按行存儲或按列存儲。對于數(shù)組元素a[i,j](1≤i,j≤N),當(22)時，在按行和按列兩種存儲方式下，其偏移量相同。(22)A.i≠jB.i=jC.i>jD.i<j●設有一個包含n個元素的有序線性表。在等概率情況下刪除其中的一個元素，若采用順序存儲結構，則平均需要移動(58)個元素；若采用單鏈表存儲，則平均需要移動(59)個元素。(58)A.1B.(n1)/2C.lognD.n(59)A.0B.1C.(n1)/2D.n/2●具有3個結點的二又樹有_(60)_的種形態(tài)。(60)A.2B.3C.5D.7●以下關于二叉排序樹(或二叉查找樹、二叉檢索樹)的敘述中，正確的是_(61)_。(61)A.對二叉排序樹進行先序、中序和后序遍歷，都得到結點關鍵字的有序序列B.含有n個結點的二叉排序樹高度為log2nC.從根到任意一個葉子結點的路徑上，結點的關鍵字呈現(xiàn)有序排列的特點D.從左到右排列同層次的結點，其關鍵字呈現(xiàn)有序排列的特點●下表為某文件中字符的出現(xiàn)頻率，采用霍夫曼編碼對下列字符編碼，則字符序列“bee”的編碼為_(62)_；編碼“110001001101”對應的字符序列為_(63)_。字符abcdef頻率(%)4513121695(62)A.10111011101B.10111001100C.D.110011011(63)A.badB.beeC.faceD.bace2017年上半年●已知棧S初始為空，用1表示入棧、0表示出棧，若入棧序列為a1a2a3a4(58)A.11O11O1OOO B.1O1O1O1O1O C.1OO11O1O1O D.11OO1O1OOO●某二叉樹的先序遍歷序列為ABCDEF，中序遍歷序列為BADCFE，則該二叉樹的高度(即層數(shù))為(59)。(59)A.3 B.4 C.5 D.62017年下半年●設S是一個長度為n的非空字符串，其中的字符各不相同，則其互異的非平凡子串(非空且不同于S本身)個數(shù)為(57)。(57)A.2n1B.n2C.n(n+1)/2D.(n+2)(n●假設某消息中只包含7個字符{a，b，c，d，e，f，g}，這7個字符在消息中出現(xiàn)的次數(shù)為{5,24,8,17,34,4,13}，利用哈夫曼樹(最優(yōu)二叉樹)為該消息中的字符構造符合前綴編碼要求的不等長編碼。各字符的編碼長度分別為(58)。(58)A.a:4,b:2,c:3,d:3,e:2,f:4,g:3B.a:6,b:2,c:5,d:3,e:1,f:6,g:4C.a:3,b:3,c:3,d:3,e:3,f:2,g:3D.a:2,b:6,c:3,d:5,e:6,f:1,g:4●設某二叉樹采用二叉鏈表表示(即結點的兩個指針分別指示左、右孩子)。當該二叉樹包含k個結點時，其二叉鏈表結點中必有(59)個空的孩子指針。(59)Ak1B.kC.k+lD.2k2018年上半年●隊列的特點是先進先出，若用循環(huán)單鏈表表示隊列，則(57)。(57)A.入隊列和出隊列操作都不需要遍歷鏈表B.入隊列和出隊列操作都需要遍歷鏈表C.入隊列操作需要遍歷鏈表而出隊列操作不需要D.入隊列操作不需要遍歷鏈表而出隊列操作需要●設有n階三對角矩陣A，即非零元素都位于主對角線以及與主對角線平行且緊鄰的兩條對角線上，現(xiàn)對該矩陣進行按行壓縮存儲，若其壓儲空間用數(shù)組B表示，A的元素下標從0開始，B的元素下標從1開始。已知A[0,0]存儲在B[1],A[nl,nl]存儲在B[3n2],那么非零元素A[i,j](0≤i<n,0≤j<n,|ij|≤1)存儲在B[(58)]。(58)A.2i+ji B.2i+j C.2i+j+i D.3ij+i●對下面的二叉樹進行順序存儲(用數(shù)組MEM表示），已知結點A、B、C在MEM中對應元素的下標分別為1、2、3,那么結點D、E、F對應的數(shù)組元素下標為(59)。(59)A.4、5、6 B.4、7、10 C.6、7、8 D.6、7、142018年下半年●棧的特點是后進先出，若用單鏈表作為棧的存儲結構，并用頭指針作為棧頂指針，則(57)。(57)A.入棧和出棧操作都不需要遍歷鏈表B.入棧和出棧操作都需要遍歷鏈表C.入棧操作需要遍歷鏈表而出棧操作不需要D.入棧操作不需要遍歷鏈表而出棧操作需要●已知某二叉樹的先序遍歷序列為ABCDEF、中序遍歷序列為BADCFE，則可以確定該二叉樹(58)。(58)A.是單支樹(即非葉子結點都只有一個孩子)B.高度為4(即結點分布在4層上)C.根結點的左子樹為空D.根結點的右子樹為空●可以構造出下圖所示二叉排序樹(二叉檢索樹、二叉查找樹)的關鍵碼序列是(59)。(59)A.10131719232731406591B.23409117191031652713C.23194027171310916531D.273140659113101723192019年上半年●某n階的三對角矩陣A如下圖所示，按行將元素存儲在一維數(shù)組M中，設a1,1存儲在M[l],那么ai,j(l<=i,j<=n且ai,j位于三條對角線中)存儲在MA(57)A.i+2jB.2i+jC.i+2j2D.2i+j2●具有3個結點的二叉樹有5種，可推測出具有4個結點的二叉樹有(58)種。(58)A.10B.11C.14D.15●雙端隊列是指在隊列的兩個端口都可以加入和刪除元素，如下圖所示?，F(xiàn)在要求元素進隊列和出隊列必須在同一端口，即從A端進隊的元素必須從A端出、從B端進隊的元素必須從B端出，則對于4個元素的序列a、b、c、d,若要求前2個元素(a、b)從A端口按次序全部進入隊列，后兩個元素(c、d)從B端口按次序全部進入隊列，則不可能得到的出隊序列是(59)。(59)A.d、a、b、cB.d、c、b、aC.b、a、d、cD.b、d、c、a圖在線性結構(例如隊列和棧)中，除第一個結點沒有前驅，最后一個結點沒有后繼之外，每一個結點都有唯一的前驅和后繼。在樹形結構(例如樹和二叉樹)中，除根結點沒有前驅外，一個結點只有一個前驅結點，但可以有若干個后繼。在圖結構中，一個結點的前驅和后繼的個數(shù)是任意的。圖的基本概念圖的種類圖分為有向圖和無向圖兩種,如REF_Ref462765368\h圖5.1所示。圖STYLEREF1\s5.SEQ圖\*ARABIC\s11a是一個有向圖，b是一個無向圖圖的表示方法圖G由兩個集合V和E組成，記為G=(V，E)。通常，也將圖G的頂點集和邊集分別記為V(G)和E(G)。E(G)可以是空集。若E(G)為空，則圖G只有頂點而沒有邊。有向圖邊的表示方法在有向圖中，一條有向邊是由兩個頂點組成的有序對，有序對通常用尖括號表示。<Vi，Vj>表示一條有向邊，Vi是邊的始點(起點)，Vj是邊的終點，<Vi,Vj有向邊也稱為弧，邊的始點稱為弧尾，終點稱為弧頭。無向圖邊的表示方法無向圖中的邊均是頂點的無序對，無序對通常用圓括號表示。在無向圖G中，如果i≠j，i、j∈V，(i，j)∈E，即i和j是G的兩個不同的頂點，(i，j)是G中一條邊，頂點i和頂點j相鄰頂點，邊(i，j)是與頂點i和j相關聯(lián)的邊?；芈坊颦h(huán)第一個頂點和最后一個頂點相同的路徑稱為回路或環(huán)。無向完全圖如果限定任何一條邊的兩個頂點都不相同，則有n個頂點的無向圖至多有n(n1)／2條邊，這樣的無向圖稱為無向完全圖(圖中每兩個頂點之間都有無向邊)。有向完全圖一個有向圖至多有n(n1)條弧，這樣的有向圖稱為有向完全圖(圖中每兩個頂點之間都有有向邊)。頂點的度在無向圖中，一個頂點的度等于與其相鄰接的頂點個數(shù)。在有向圖中，一個頂點的入度等于鄰接到該頂點的頂點個數(shù)，其出度等于鄰接于該頂點的個數(shù)。路徑在圖G=(V，E)中，如果存在頂點序列(V0，V1……Vk-1Vk)其中V0=P，Vk=Q，且(V0，V1)，(V1，V2)，…，(Vk-1，Vk)都在E中，則稱頂點P到頂點Q有－條路徑，并用(連通圖在無向圖中，如果從頂點V1到頂點V2有路徑，稱V1和V2是連通的。如果對于圖中任意兩個頂點Vi、VjV,連通分量無向圖中的極大連通子圖(加入任何一個其它的結點便不連通的子圖),如REF_Ref462782256\h圖5.2所示為無向圖G3及其連同分量。圖STYLEREF1\s5.SEQ圖\*ARABIC\s12(a)無向圖G3，(b)G3的三個聯(lián)通分量強連通圖有向圖G中，若對于V(G)中任意兩個不同的頂點Vi和Vj，都存在從Vi到Vj及從Vj強連通分量有向圖中的極大強連通子圖稱為有向圖的強連通分量，如REF_Ref462782367\h圖5.3所示。圖STYLEREF1\s5.SEQ圖\*ARABIC\s13G1的兩個強連同分量圖的存儲結構最常用的圖的存儲結構有鄰接矩陣和鄰接表。鄰接矩陣鄰接矩陣反映頂點鄰接關系．設G=(V,E)是具有n(n≥1)個頂點的圖，G的鄰接矩陣M是一個n行n列的矩陣，并有若(i，j)或<i，j>∈E，則M[i][j]=1，否則，M[i][j]＝0。如REF_Ref462823256\h圖5.4所示的有向圖和無向圖對應的鄰接矩陣分別為Ma和Mb所示。圖STYLEREF1\s5.SEQ圖\*ARABIC\s14有向圖和無向圖無向圖的鄰接矩陣是對稱的，且非0元素的個數(shù)為邊數(shù)的2倍；有向圖的鄰接矩陣不一定對稱，且非0元素的個數(shù)等于邊數(shù)。對于無向圖，其鄰接矩陣第i行元素的之和即為頂點i的度。對于有向圖，其鄰接矩陣的第i行元素之和為頂點i的出度，而鄰接矩陣的第j列元素之和為頂點j的入度。若將圖的每條邊都賦上一個權，則稱這種帶權圖為網(wǎng)(絡)。如果圖G＝(V，E)是一個網(wǎng)，若(i，j)或<i,j>屬于E，則鄰接矩陣中的元素M[i][j]為(i,j)或<i，j>上的權。若(i，j)或<i,j>不屬于E，則M[i][j]為無窮大或為大于圖中任何權值的實數(shù)。圖STYLEREF1\s5.SEQ圖\*ARABIC\s15網(wǎng)及其鄰接矩陣(a)網(wǎng)N;(b)鄰接矩陣鄰接表在圖的鄰接表表示中，為圖的每個頂點建立一個鏈表，且第i個鏈表中的結點代表與頂點i相關聯(lián)的一條邊或由頂點i出發(fā)的一條弧。有n個頂點的圖，需用n個鏈表表示，這n個鏈表的頭指針通常由順序線性表存儲。如REF_Ref462782750\h圖5.6所示的圖對應的鄰接矩陣如REF_Ref462782758\h圖5.7所示。圖STYLEREF1\s5.SEQ圖\*ARABIC\s16圖的分類圖STYLEREF1\s5.SEQ圖\*ARABIC\s17圖的鄰接表表示在無向圖的鄰接表中，對應某結點的鏈表的結點個數(shù)就是該頂點的度。鏈表中結點數(shù)為邊數(shù)的2倍。在有向圖的鄰接表中，對應某結點的鏈表的結點個數(shù)就是該頂點的出度。圖的遍歷深度優(yōu)先遍歷圖的深度優(yōu)先遍歷類似于樹的前序遍歷。對于無向圖，如果圖是連通的，那么按深度優(yōu)先遍歷時，可遍歷全部頂點，得到全部頂點的一個遍歷序列。如果遍歷序列沒有包含所有頂點，那么該圖是不連通的。廣度優(yōu)先遍歷類似于樹的層次優(yōu)先遍歷。廣度優(yōu)先的遍歷過程是：首先訪問出發(fā)頂點V，然后訪問與頂點V鄰接的全部未被訪問過的頂點W0、W1、……Wk-1；接著再依次訪問與頂點W0、W1、……注意：圖的遍歷運算是按照某種策略訪問圖中的每一個頂點，是通過邊或狐找鄰接點的過程，不論廣度搜索還是深度搜索，時間復雜度都一樣。在鄰接矩陣中遍歷圖的時間為O(n2)，在鄰接表中遍歷的時間復雜度為O(n+e)最小生成樹如果連通圖G的一個子圖是一棵包含G的所有頂點的樹，則該子圖稱為G的生成樹。生成樹