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

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

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

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

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

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