數(shù)據(jù)結(jié)構(gòu)自測題及解答-全文預(yù)覽
【正文】 ose data fields are single characters. When the data fields of the nodes are output in inorder, the output is ABCDEFGHIJ, and when they are output in preorder, the output is ADBCJGFEHI. Draw the binary tree showing the data in each node and the pointers between nodes. 參考答案一、概念題（，共28分） 分支層次、根、直接前趨 5 31 32 9 2i1 2 k1 n2+1 最大值、完全 350 （[n/2]＝350） 500 499 1 0 n 21 L R N F E G H D C B1 O(n)1 順序、鏈式1 根、左孩子、右孩子、2i、右孩子、2i+11 根1 指向該結(jié)點的一個孩子、空指針NULL1 2n、nn+11 二叉鏈表、三叉鏈表1 第一 左子樹、右子樹、左子樹、右子樹2 02 先根遍歷、后根遍歷、層次遍歷2 樹2 最短、較近2 332 n+12 父節(jié)點；子節(jié)點、……、二、選擇題（每空1分，共15分）1. C 2. C 3. C 4. A 5. A=① B=① C=③ 6. A=② B=① C=① D=③ 8. B 9. D 10. D 三、綜合題（19每題3分，1012每題10分,共57分）1．解：方法是：由前序先確定root，由中序可確定root的左、右子樹。對于上述實例，比較兩種方案的優(yōu)缺點。 7. 編寫遞歸算法，求二叉樹中以元素值為x的結(jié)點為根的子樹的深度。3．試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結(jié)點序列。由樹轉(zhuǎn)換成的二叉樹里，一個結(jié)點N的左子女是N在原樹里對應(yīng)結(jié)點的 C ，而N的右子女是它在原樹里對應(yīng)結(jié)點的 D 。一個結(jié)點的子結(jié)點個數(shù)為該結(jié)點的 C 。log2(n)+1249。 log2(n) （Ｄ）順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都不能使用 （ ）3. 具有n(n0)個結(jié)點的完全二叉樹的深度為 。 （Ｄ）既不是樹也不是二叉樹（ ）2．二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。二、 選擇題（每空1分，共15分）（ ）1． 不含任何結(jié)點的空樹 。（Huffman）樹是帶權(quán)路徑長度________的樹，通常權(quán)值較大的結(jié)點離根________。：二叉樹中各結(jié)點的子樹要區(qū)分為________和________，即使在結(jié)點只有一棵子樹的情況下，也要明確指出該子樹是________還是________。，這個值或者是____________的指針，或者是______。，則對任一編號為i(1=i=n)的結(jié)點X有：（1） 若i=1,則結(jié)點X是______；若i〉1,則X的雙親PARENT(X)的編號為______。這三種方法相互
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1