工學(xué)期末復(fù)習(xí)題ppt課件-文庫(kù)吧資料
2025-01-23 07:46本頁(yè)面
【正文】 6. 對(duì)下圖分別進(jìn)行深度，廣度優(yōu)先遍歷的結(jié)果 遍歷二叉樹和線索二叉樹 a c d e f ／ b * ＋ + 中序遍歷結(jié)果 : a+b*cde/f 遍歷二叉樹和線索二叉樹 a c d e f ／ b * ＋ + 后序遍歷結(jié)果 : abcd*+ef/ 遍歷二叉樹和線索二叉樹 a c d e f ／ b * ＋ + 先序遍歷結(jié)果 : +a*bcd/ef 例： 已知結(jié)點(diǎn)的先序序列和中序序列，求整棵二叉樹。 3. 將下面的森林變換成二叉樹 4. 某子系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn) 8種字符，其出現(xiàn)的概率分別為 ， ， ………… 試設(shè)計(jì)赫夫曼編碼。 ，要求從頂點(diǎn) 1出發(fā)。 解：先構(gòu)造哈夫曼樹，得到各葉子的路徑長(zhǎng)度之后便可求出 WPL＝（ 4＋ 5＋ 3） 2＋（ 1＋ 2） 3=33 7. 圖有 鄰接矩陣 、 領(lǐng)接表 等存儲(chǔ)結(jié)構(gòu)，遍歷圖有 廣度優(yōu)先 、 深度優(yōu)先 等方法。 5．由３個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有 5 種形態(tài)。不允許插入和刪除運(yùn)算的一端稱為 棧底 。 ，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由 前一個(gè)節(jié)點(diǎn)的指針域 指示。（ t ） 。 （ f） ，如果不存在非空左子樹，則不存在非空右子樹。（ t ） 6. 一個(gè)棧的輸入序列是 12345，則棧的輸出序列不可能是 12345。（ f ） 4. 棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。 （ f） 2. 鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。 A． n1 B． n(n1)/2 C． n(n+1)/2 D． 0 12．已知有向圖 G=(V,E)，其中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ù)湫蛄惺牵? a ）。 A．表元素 B．字符 C．?dāng)?shù)據(jù)元素 D．?dāng)?shù)據(jù)項(xiàng) 7．若一棵二叉樹具有 10個(gè)度為 2的結(jié)點(diǎn)， 5個(gè)度為 1的結(jié)點(diǎn)，則度為 0的結(jié)點(diǎn)個(gè)數(shù)是（ b） A． 9 B． 11 C． 15 D．不確定 8．在一棵高度為 k的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（ a ） A． 2^k1 B． 2k C． 2k1 D． ?log2k?+1 9．已知一棵二叉樹的前序遍歷結(jié)果為 ABCDEF,中序遍歷結(jié)果為 CBAEDF,則后序遍歷的結(jié)果為（ a ）。 D．線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。 B．線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。 i =f(f(1))。 A. 1， 2， 4， 3， B. 2， 1， 3， 4， C. 1， 4， 3， 2， D. 4， 3， 1， 2， 4. 執(zhí)行完下列語(yǔ)句段后， i值為：（ b ） int f(int x) { return ((x0) ? x* f(x1):2)。 A. 先進(jìn)先出 B. 后進(jìn)先出 C. 后進(jìn)后出 D. 不分順序 2. 一個(gè)棧的輸入序列為 123…n ，若輸出序列的第一個(gè)元素是 n，輸出第 i（ 1=i=n）個(gè)元素是（ b ）。 n個(gè)結(jié)點(diǎn)的二叉樹中 ,一共有 _2n_______個(gè)指針域 ,其中只有 _n1_______個(gè)用來(lái)指向結(jié)點(diǎn)的左右孩子，其余的 ___n+1_____個(gè)指針域?yàn)镹ULL。 4．將一棵有 100個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，則編號(hào)為 49的結(jié)點(diǎn) X，其雙親 PARENT（ X）的編號(hào)為＿＿ 24＿＿＿＿＿。 ( t ) 10．對(duì)任意一個(gè)圖，從它的某個(gè)頂點(diǎn)出發(fā)，進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個(gè)頂點(diǎn) .（ f ） lian tong tu 1．在帶有頭結(jié)點(diǎn)的單鏈表 L中，若要?jiǎng)h除第一個(gè)結(jié)點(diǎn)，則需執(zhí)行下列三條語(yǔ)句：＿＿＿ u=l next＿＿＿＿＿； Lnext=Unext； free(U)； 2． G為無(wú)向圖，如果從 G的某個(gè)頂點(diǎn)出發(fā)，進(jìn)行一次廣度優(yōu)先搜索，即可訪問圖的每個(gè)頂點(diǎn)，則該圖一定是＿＿完全＿連通＿＿圖。 （ f ） 8．在順序表中取出第 i個(gè)元素所花費(fèi)的時(shí)間與 i成正比。 ( t ) i個(gè)元素的時(shí)間同 i的大小有關(guān) . (f ) 6．如果兩個(gè)串含有相同的字符，則這兩個(gè)串相等。 ( f ) 2．?dāng)?shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。 A． n1 B． n C． n+1 D．
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1