《數(shù)據(jù)結(jié)構(gòu)》各章練習(xí)題1

逵書破互卷___下筆力逵書破互卷___下筆力0有才電第一章練習(xí)一、選擇題1.算法的計算量的大小稱為計算的()。A效率復(fù)雜性現(xiàn)實(shí)性難度2.計算機(jī)算法指的是()，它必須具備()這三個特性。)計算方法排序方法解決問題的步驟序列調(diào)度方法)可執(zhí)行性、可移植性、可擴(kuò)充性可執(zhí)行性、確定性、有窮性確定性、有窮性、穩(wěn)定性易讀性、穩(wěn)定性、安全性3．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()兩大類。A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu).順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)線性結(jié)構(gòu)、非線性結(jié)構(gòu).初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)選擇題答案：1.B2.(1)C(2)B3.C二、判斷題1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。()2.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系；()TOC\o"1-5"\h\z3．算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機(jī)有關(guān)。()4．健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()5．程序一定是算法。()6．?dāng)?shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機(jī)內(nèi)的實(shí)際存儲形式。()7.數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。()判斷題答案：1.F2.F3.F4.T5.F6.T7.F三、填空對于給定的個元素可以構(gòu)造出的邏輯結(jié)構(gòu)有—,—,—,_四種。2數(shù)據(jù)的邏輯結(jié)構(gòu)是指。3一個數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中稱為存儲結(jié)構(gòu)。4數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是和數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的和，并對與這種結(jié)構(gòu)定義相應(yīng)的，設(shè)計出相應(yīng)的。6一個算法具有個特性、、，有零個或多個輸入、有一個或多個輸出。填空題答案：1.集合線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu).數(shù)據(jù)及相互之間的聯(lián)系.的存儲方式.時間復(fù)雜度空間復(fù)雜度.邏輯結(jié)構(gòu)存儲結(jié)構(gòu)運(yùn)算(操作)算法.有窮性確定性可行性第二章練習(xí)一選擇題1．下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)？（）A存儲密度大.插入運(yùn)算方便.刪除運(yùn)算方便.可方便地用于各種邏輯結(jié)構(gòu)的存儲表示2．下面關(guān)于線性表的敘述中，錯誤的是哪一個？（）A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。3線性表是具有jl）的有限序列（）OTOC\o"1-5"\h\zA表元素.字符.數(shù)據(jù)元素.數(shù)據(jù)項(xiàng).信息項(xiàng)4．若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲方式最節(jié)省時間。A順序表.雙鏈表.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表.單循環(huán)鏈表5．某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運(yùn)算時間。A單鏈表.僅有頭指針的單循環(huán)鏈表.雙鏈表.僅有尾指針的單循環(huán)鏈表6．設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用（最節(jié)省時間。單鏈表單循環(huán)鏈表帶尾指針的單循環(huán)鏈表帶頭結(jié)點(diǎn)的雙循環(huán)鏈表.靜態(tài)鏈表中指針表示的是（）.A內(nèi)存地址.數(shù)組下標(biāo).下一元素地址.左、右孩子地址.鏈表不具有的特點(diǎn)是（）A插入、刪除不需要移動元素.可隨機(jī)訪問任一元素不必事先估計存儲空間.所需空間與線性長度成正比.下面的敘述不正確的是（）A線性表在鏈?zhǔn)酱鎯r，查找第個元素的時間同的值成正比線性表在鏈?zhǔn)酱鎯r，查找第個元素的時間同的值無關(guān)線性表在順序存儲時，查找第個元素的時間同的值成正比線性表在順序存儲時，查找第個元素的時間同的值無關(guān).（靜1態(tài)）鏈表既有順序存儲的優(yōu)點(diǎn)，又有動態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第個元素的時間與無關(guān)。

（靜2態(tài)）鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。（靜3態(tài)）鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的是（）A．（1），（2）．（1）B．（1），（C2）,（3）（2）D若長度為的線性表采用順序存儲結(jié)構(gòu)，在其第個位置插入一個新元素的算法的時間復(fù)雜度為（）<12對若于順序存儲的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時間復(fù)雜度為（）。.線性表（…）以鏈接方式存儲時，訪問第位置元素的時間復(fù)雜性為（）A．O（i）．O（B1）．O（Cn）．O（iD-）1TOC\o"1-5"\h\z4非空的循環(huán)單鏈表的尾結(jié)點(diǎn)滿足（）。5在雙向鏈表指針的結(jié)點(diǎn)前插入一個指針的結(jié)點(diǎn)操作是（）.在單鏈表指針為的結(jié)點(diǎn)之后插入指針為的結(jié)點(diǎn)，正確的操作是：（）。7．對于一個頭指針為7．對于一個頭指針為（）的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是選擇題答案三、填空1.當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用存_儲_結(jié)_構(gòu)。2線性表（a。）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是。3設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為，為指針域，E知指針指向單鏈表中為的結(jié)點(diǎn)，指針指向?yàn)榈男陆Y(jié)點(diǎn)若將結(jié)點(diǎn)插入結(jié)點(diǎn)之后，則需要執(zhí)行以下語句;4在一個長度為的順序表中第個元素（）之前插入一個元素時，需向后移動個_元__素_。5．在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是。___6對于一個具有個結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為在給定值為的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為。7．根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點(diǎn)包含的指針個數(shù)，將線性鏈表分成和；_而_又_根據(jù)指針的連接方式，鏈表又可分成和_。8在雙向循環(huán)鏈表中向所指的結(jié)點(diǎn)之后插入指針?biāo)傅慕Y(jié)點(diǎn)，其操作是、、、。10．鏈接存儲的特點(diǎn)是利用來_表_示_數(shù)據(jù)元素之間的邏輯關(guān)系。11順.序存儲結(jié)構(gòu)是通過表_示_元_素_之間的關(guān)系的;鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過表_示_元_素_之間的關(guān)系的。12對.于雙向鏈表,在兩個結(jié)點(diǎn)之間插入一個新結(jié)點(diǎn)需修改的指針共___個_，單鏈表為個_。__13.循環(huán)單鏈表的最大優(yōu)點(diǎn)是：。E知指針指向單鏈表中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語句是：帶頭結(jié)點(diǎn)的雙循環(huán)鏈表中只有一個元素結(jié)點(diǎn)的條件是：在單鏈表中，指針?biāo)附Y(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是：填空答案：1．順序5．主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入元素和刪除第一個結(jié)點(diǎn)不必另作判斷。另外，不論鏈表是否為空，鏈表指針不變。6．O(1，)O(n)7．單鏈表，多重鏈表，(動態(tài))鏈表，靜態(tài)鏈表指針物理上相鄰指針TOC\o"1-5"\h\z42從任一結(jié)點(diǎn)出發(fā)都可訪問到鏈表中每一個元素。二、判斷1帶鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識的作用。()2帶順序存儲結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作。()3．線性表采用鏈表存儲時，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的。4．順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩?5.對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。()6．順序存儲方式只能用于存儲線性結(jié)構(gòu)。()7．集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。().所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。().線性表的特點(diǎn)是每個元素都有一個前驅(qū)和一個后繼。()取線性表的第個元素的時間同的大小有關(guān).循環(huán)鏈表不是線性表.().線性表只能用順序存儲結(jié)構(gòu)實(shí)現(xiàn)。().線性表就是順序存儲的表。()14．為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。()15順.序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。(16鏈.表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時，在鏈表中比在順序存儲結(jié)構(gòu)中效率高。()判斷題答案XJJ.XXXXXXXXXJXJ部分答案解釋0下。1、頭結(jié)點(diǎn)并不“僅起”標(biāo)識作用，并且使操作統(tǒng)一。另外，頭結(jié)點(diǎn)數(shù)據(jù)域可寫入鏈表長度，或作監(jiān)視哨。．兩種存儲結(jié)構(gòu)各有優(yōu)缺點(diǎn)，應(yīng)根據(jù)實(shí)際情況選用，不能籠統(tǒng)說哪一個好。．集合中元素?zé)o邏輯關(guān)系。．非空線性表第一個元素?zé)o前驅(qū)，最后一個元素?zé)o后繼。3．線性表是邏輯結(jié)構(gòu)，可以順序存儲，也可鏈?zhǔn)酱鎯Α５谌戮毩?xí)一選擇題TOC\o"1-5"\h\z1.有一個100*的9稀0疏矩陣，非0元素有10個，設(shè)每個整型數(shù)占2字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是()。A.60B.662.對稀疏矩陣進(jìn)行壓縮存儲目的是()。A便于進(jìn)行矩陣運(yùn)算.便于輸入和輸出.節(jié)省存儲空間.降低運(yùn)算的時間復(fù)雜度廣義表((A的表頭是()，表尾是()。O()()

廣義表（）的表頭為（）。設(shè)廣義表（（））,則的長度和深度分別為（）。和和和和面說法不正確的是（。廣義表的表頭總是一個廣義表廣義表難以用順序存儲結(jié)構(gòu)和2C.1和3D廣義表的表尾總是一個廣義廣義表可以是一個多層次的結(jié)構(gòu)選擇題答案三、填空TOC\o"1-5"\h\z.所謂稀疏矩陣指的是。___.當(dāng)廣義表中的每個元素都是原子時，廣義表便成了。___.廣義表的表尾是指除第一個元素之外，。___.廣義表簡稱表，是由零個或多個原子或子表組成的有限序列，原子與表的差別僅在于。為了區(qū)分原子和表，一般用表示表，用—表示原子。一個表的長度是指,而表的深度是指廣義表的定義為廣義表中括弧的重數(shù)。填空答案：非零元很少且分布沒有規(guī)律2.線性表3.其余元素組成的表.（1）原子（單元素）是結(jié)構(gòu)上不可再分的，可以是一個數(shù)或一個結(jié)構(gòu)；而表帶結(jié)構(gòu)，本質(zhì)就是廣義表，因作為廣義表的元素故稱為子表。（2）大寫字母（3）小寫字母（4）表中元素的個數(shù)（5）表展開后所含括號的層數(shù)5.深度二、判斷TOC\o"1-5"\h\z1.稀疏矩陣壓縮存儲后，必會失去隨機(jī)存取功能。（）一個稀疏矩陣采用三元組形式表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把和的值互換，則就完成了的轉(zhuǎn)置運(yùn)算。（）廣義表的取表尾運(yùn)算，其結(jié)果通常是個表，但有時也可是個單元素值。（）.若一個廣義表的表頭為空表，則此廣義表亦為空表。（）.廣義表中的元素或者是一個不可分割的原子，或者是一個非空的廣義表。（）.所謂取廣義表的表尾就是返回廣義表中最后一個元素。（）.廣義表的同級元素（直屬于同一個表中的各元素）具有線性關(guān)系。（）.對長度為無窮大的廣義表，由于存儲空間的限制，不能在計算機(jī)中實(shí)現(xiàn)。（）.一個廣義表可以為其它廣義表所共享。（）判斷題答案.*.......部分答案解釋0下。6.錯誤。稀疏矩陣轉(zhuǎn)置后，除行列下標(biāo)及行列數(shù)互換外，還必須確定該元素轉(zhuǎn)置后在新三元組中的位置。8.錯誤。廣義表的取表尾運(yùn)算，是非空廣義表除去表頭元素，剩余元素組成的表，不可能是原子。9.錯誤。廣義表的表頭就是廣義表的第一個元素。只有非空廣義表才能取表頭。10錯.誤。廣義表中元素可以是原子，也可以是表（包括空表和非空表）。11.錯誤。廣義表的表尾，指去掉表頭元素后，剩余元素所組成的表。第四章練習(xí)一、填空1．棧是的_線_性_表，其運(yùn)算遵循的_原_則_。．是_限_定_僅在表尾進(jìn)行插入或刪除操作的線性表。TOC\o"1-5"\h\z.一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是。___4用表示入棧操作，表示出棧操作，若元素入棧的順序?yàn)?為了得到出棧順序，相應(yīng)的和的操作串為_順序棧用存儲數(shù)據(jù)，棧頂指針是則,為的元素入棧的操作是6．表達(dá)式23+（（12*3-2）/4+的3后4綴*表5達(dá)/式7是）_+_1_0_。8_/_9_.循環(huán)隊(duì)列的引入，目的是為了克服。___．又__稱_作_先進(jìn)先出表。9．隊(duì)列是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表，其特點(diǎn)是。___0設(shè)循環(huán)隊(duì)列用數(shù)組表示，隊(duì)首、隊(duì)尾指針分別是和I判定隊(duì)滿的條件為。___11．表達(dá)式求值是應(yīng)_用_的_一個典型例子。.循環(huán)隊(duì)列用數(shù)組存放其元素值，已知其頭尾指針分別是和a則當(dāng)前隊(duì)列的元素個數(shù)是。___填空題答案：1、操作受限（或限定僅在表尾進(jìn)行插入和刪除操作）后進(jìn)先出2、棧3、312、義義義義、；、23.12.3*2-4/34.（5注*：7表/達(dá)+式+中1的08點(diǎn).（9.表/）示+將數(shù)隔開，023.1是2三.個3數(shù)）7、假溢出時大量移動數(shù)據(jù)元素。、8隊(duì)列、先進(jìn)9先出0）、棧、（）；二、判斷.棧是實(shí)現(xiàn)過程和函數(shù)等子程序所必需的結(jié)構(gòu)。（）.棧與隊(duì)列是一種特殊操作的線性表。（）.隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。（）.通常使用隊(duì)列來處理函數(shù)或過程的調(diào)用。（）.循環(huán)隊(duì)列也存在空間溢出問題。（）.棧和隊(duì)列的存儲方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?。（）判斷題答案：17,27,3.x,.x,5、,67第五、六章練習(xí)一、選擇題設(shè)樹的度為，其中度為，，和的結(jié)點(diǎn)個數(shù)分別為42，則中的葉子數(shù)為（）（提示：結(jié)點(diǎn)總數(shù)度總數(shù)）A．5．6B．7C．8DTOC\o"1-5"\h\z2.在下述結(jié)論中，正確的是（）①只有一個結(jié)點(diǎn)的二叉樹的度為②二叉樹的度為2③二叉樹的左右子樹可任意交換;④深度為的完全二叉樹的結(jié)點(diǎn)個數(shù)小于或等于深度相同的滿二叉樹。A①②③.②③④.②④.①④設(shè)森林對應(yīng)的二叉樹為，它有個結(jié)點(diǎn)，的根為的右子樹結(jié)點(diǎn)個數(shù)為森林中第一棵樹的結(jié)點(diǎn)個數(shù)是（）A..C條件不足，無法確定4．若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個數(shù)是（）A...不確定TOC\o"1-5"\h\z5設(shè)森林中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個數(shù)分別為1和3與森林對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個數(shù)是（）。A．M1．M1+M2B．M3C．M2+M3D6．一棵完全二叉樹上有100個1結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是（）A．250．5B01．254C．505D設(shè)給定權(quán)值總數(shù)有個，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為A不確定^^^有個葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）。A不確定^^^

9.有關(guān)二叉樹下列說法正確的是（）A二叉樹的度為.一棵二叉樹的度可以小于二叉樹中至少有一個結(jié)點(diǎn)的度為.二叉樹中任何一個結(jié)點(diǎn)的度都為2O二叉樹的第層上最多含有結(jié)點(diǎn)數(shù)為（）A．2I．I2--11B．I2-1C．2I-1D一個具有個結(jié)點(diǎn)的二叉樹的高為（）A,?至之間^至之間.一棵二叉樹高度為所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有結(jié)點(diǎn)A．2h．2hB-1．2h+1C．h+1DTOC\o"1-5"\h\z3對于有個結(jié)點(diǎn)的二叉樹其高度為（）..LJ.不確定一棵具有個結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（）A．LlongJ+1．long+B1．LlongJC．loDng-15深度為的滿叉樹的第層有（）j結(jié)點(diǎn)。A．mk-1．mk-1B．mh-1C．mh-D16在一棵高度為的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（）A．2k-1B．2kC．2k-1．LlogkJ+2D17高度為的二叉樹最大的結(jié)點(diǎn)數(shù)為（KA．2k．2k-B1．2k-1C．D2k--11一棵樹高為的完全二叉樹至少有（）個結(jié)點(diǎn)1．9對二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點(diǎn)的編號大于其左、右孩子的編號，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（次序的）遍歷實(shí)現(xiàn)編號。A先序中序后序從根開始按層次遍歷OE知一棵二叉樹的前序遍歷結(jié)果為中序遍歷結(jié)果為則后序TOC\o"1-5"\h\z遍歷的結(jié)果為（）。A．CBEFDA．FEDCBA．CBEDFCA．不定D1二叉樹的先序遍歷和中序遍歷如下：先序遍歷：I中序遍歷。該二叉樹根的右子樹的根是：、）哈夫曼樹.每個結(jié)點(diǎn)至、）哈夫曼樹.每個結(jié)點(diǎn)至.以上答案都不對22．在下列情況中，可稱為二叉樹的是（.每個結(jié)點(diǎn)至多有兩棵子樹的樹多有兩棵子樹的有序樹每個結(jié)點(diǎn)只有一棵右子樹．3由3個結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（）逵書破互卷___下筆力逵書破互卷___下筆力0有注電逵書破互卷___下筆力逵書破互卷___下筆力0有才電選擇題答案二、判斷題1.二叉樹是度為2的有序樹.2.完全二叉樹一定存在度為1的結(jié)點(diǎn)。對于有個結(jié)點(diǎn)的二叉樹，其高度為g4深度為的二叉樹中結(jié)點(diǎn)總數(shù)W。5．對一棵二叉樹進(jìn)行層次遍歷時，應(yīng)借助于一個棧。6．用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷。7．中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列8．完全二叉樹中，若一個結(jié)點(diǎn)沒有左孩子，則它必是樹葉。9.二叉樹只能用二叉鏈表表示。O在二叉樹的第層上至少有個結(jié)點(diǎn)。11．完全二叉樹的存儲結(jié)構(gòu)通常采用順序存儲結(jié)構(gòu)。12．度為二的樹就是二叉樹。13．霍夫曼樹的結(jié)點(diǎn)個數(shù)不能是偶數(shù)。14.一棵哈夫曼樹的帶權(quán)路徑長度等于其中所有分支結(jié)點(diǎn)的權(quán)值之和。15．哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。二、判斷題答案XXXJXXXXXXJXJXJ三、填空題1二叉樹由，，三個基本單元組成。2中綴式3）對應(yīng)的前綴式為,若====則后綴式的運(yùn)算結(jié)果為。3具有個結(jié)點(diǎn)的完全二叉樹的深度為。4已知一棵度為的樹有個度為的結(jié)點(diǎn)，個度為的結(jié)點(diǎn)，個度為的結(jié)點(diǎn)，則該樹有個葉子結(jié)點(diǎn)。.深度為的完全二叉樹至少有個結(jié)點(diǎn)，至多有個結(jié)點(diǎn)。.假設(shè)根結(jié)點(diǎn)的層數(shù)為1,具有n個結(jié)點(diǎn)的二叉樹的最大高度是07在一棵二叉樹中，度為零的結(jié)點(diǎn)的個數(shù)為度為的結(jié)點(diǎn)的個數(shù)為則有.高度為的完全二叉樹至少有個葉子結(jié)點(diǎn)。.已知二叉樹有個葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少是0完全二叉樹中，結(jié)點(diǎn)個數(shù)為，則編號最大的分支結(jié)點(diǎn)的編號為.具有個結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲，共有個空鏈域。.哈夫曼樹是。.若以4567作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是。4有一份電文中共使用個字符它們的出現(xiàn)頻率依次為,試,8一棵哈夫曼樹，則其加權(quán)路徑長度為,字符的編碼是。.設(shè)為哈夫曼樹的葉子結(jié)點(diǎn)數(shù)目,則該哈夫曼樹共有個結(jié)點(diǎn)。三.填空題答案1.（根1結(jié)）點(diǎn)（2左）子樹（3右）子樹L」.N+1帶.權(quán)路徑長度最小的二叉樹，又稱最優(yōu)二叉樹.6棵.（1）80（不（唯2一））001第七章練習(xí)一、選擇題i設(shè)無向圖的頂點(diǎn)個數(shù)為，則該圖最多有（）條邊。TOC\o"1-5"\h\zA．n-1．n（n-1B）/2．n（n+1）C/2．0．n22一個個頂點(diǎn)的連通無向圖，其邊的個數(shù)至少為（）。A．n-1．nB．n+1C．nlo；gn3要連通具有個頂點(diǎn)的有向圖，至少需要（）條邊。A．n-l．nB．n+lC．2n4個結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（）。B.（+1）/.（一）5一個有個結(jié)點(diǎn)的圖，最少有（）個連通分量，最多有（）個連通分量。A．0．1B．n-1C．n6．在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（）倍，在一個有

向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（）倍。A．1/2．2B．1C．4^無向圖其中：,對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）。A．a(chǎn),b,e,c,d,Bf．a(chǎn),c,f,e,b,dC．a(chǎn),e,b8已知有向圖V其中,1234567E={,<V>,<,V>,<,V>,<,V>,<,V>,<,V>,<,V>,<,V>,<,V>}121314253536465767的拓?fù)湫蛄惺牵ǎ?．一個有向無環(huán)圖的拓?fù)渑判蛐蛄校?．一個有向無環(huán)圖的拓?fù)渑判蛐蛄校ˋ一定.不一定在有向圖的拓?fù)湫蛄兄?，若頂點(diǎn)現(xiàn)的是（）。A中有弧V中沒有?。┦俏ㄒ坏?。B在頂點(diǎn)之前，則下列情形不可能出.中有一條從到的路徑.中有一條從到的路徑三、填空題判斷一個無向圖是一棵樹的條件是。.有向圖的強(qiáng)連通分量是指。3一個連通圖的是一個極小連通子圖。4具有個頂點(diǎn)的無向圖，邊的總數(shù)最多為。5若用表示圖中頂點(diǎn)數(shù)目，則有條邊的無向圖成為完全圖。在有個頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要條弧。7^在有個頂點(diǎn)的有向圖中，每個頂點(diǎn)的度最大可達(dá)。8設(shè)為具有個頂點(diǎn)的無向連通圖，則中至少有條邊。9個頂點(diǎn)的連通圖的生成樹含有條邊。.有個頂點(diǎn)的有向圖，至少需要量條弧才能保證是連通的。1.1右圖中的強(qiáng)連通分量的個數(shù)為（）個。.在圖的鄰接表表示中，每個頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對于無向圖來說等于該頂點(diǎn)的；對于有向圖來說等于該頂點(diǎn)的l。在有向圖的鄰接矩陣表示中，計算第個頂點(diǎn)入度的方法是。對于一個具有個頂點(diǎn)條邊的無向圖的鄰接表的表示，則表頭向量大小為，鄰接表的邊結(jié)點(diǎn)個數(shù)為。已知一無向圖（，），其中現(xiàn)用某一種圖遍歷方法從頂點(diǎn)開始遍歷圖，得到的序列為，則采用的是遍歷方法。一無向圖(V),其中()4()()),(2,)4，(2,)5，(3,)6，(3,)7，(6,)(75,)1},對該圖從頂點(diǎn)3開始進(jìn)行遍歷，去掉遍歷中未走過的邊，得一生成樹‘V‘)(’)()，(')(),(),(),(),(),()}則采用的遍歷方法是。為了實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除了一個標(biāo)志數(shù)組標(biāo)志已訪問的圖的結(jié)點(diǎn)外，還需存放被訪問的結(jié)點(diǎn)以實(shí)現(xiàn)遍歷。.構(gòu)造連通網(wǎng)最小生成樹的兩個典型算法是0有一個用于個頂點(diǎn)連通帶權(quán)無向圖的算法描述如下：().設(shè)集合與2初始均為空；().在連通圖上任選一點(diǎn)加入；().以下步驟重復(fù)次：在屬于1不屬于的邊中選最小權(quán)的邊；該邊加入。上述算法完成后，中共有條邊，該算法稱算法，中的邊構(gòu)成圖的遍0網(wǎng)中結(jié)點(diǎn)表示邊表示。當(dāng)一個網(wǎng)用鄰接表表示時，可按下列方法進(jìn)行拓?fù)渑判颉?).查鄰接表中入度為的頂點(diǎn)，并進(jìn)棧；().若棧不空，則①輸出棧頂元素，并退棧；②查的直接后繼，對入度處理，處理方法是:().若?？諘r，輸出