精編國(guó)家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)3作業(yè)及答案

《精編國(guó)家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)3作業(yè)及答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《精編國(guó)家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)3作業(yè)及答案（9頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、國(guó)家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡(luò)課形考任務(wù)3作業(yè)及答案 形考任務(wù)3 一、單項(xiàng)選擇題（每小題2分，共38分） 題目1 假定一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為30,則葉子結(jié)點(diǎn)數(shù)為（）o 選擇一項(xiàng)： A. 47 B. 16 C. 17 D. 15 題目2 二叉樹第k層上最多有（）個(gè)結(jié)點(diǎn)。 選擇一項(xiàng)： A. 2k-l B. 2k-l C. 2k-l D. 2k 題目3 將含有150個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)為 69的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（）o 選擇一項(xiàng)： A. 36 B. 35

2、 C. 34 D. 33 題目4 如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長(zhǎng)度最小，則該樹稱為（）o 選擇一項(xiàng)： A. 二叉樹 B. 哈夫曼樹 C. 完全二叉樹 D. 平衡二叉樹 在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（）o 選擇一項(xiàng)： A. 16 B. 32 C. 31 D. 33 題目6 一棵完全二叉樹共有6層，且第6層上有6個(gè)結(jié)點(diǎn)，該樹共有（）個(gè)結(jié)點(diǎn)。 選擇一項(xiàng)： A. 31 B. 37 C. 38 D. 72 題目7 利用3、6、8、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子結(jié)點(diǎn)中的最長(zhǎng)帶權(quán)路徑長(zhǎng)度

3、為（）。 選擇一項(xiàng)： A. 18 B. 16 C. 30 D. 12 題目8 在一棵樹中，（）沒有前驅(qū)結(jié)點(diǎn)。 選擇一項(xiàng)： A. 樹根結(jié)點(diǎn) B. 葉結(jié)點(diǎn) C. 空結(jié)點(diǎn) D. 分支結(jié)點(diǎn) 題目9 設(shè)一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2,該樹結(jié)點(diǎn)中共有20個(gè)指針域?yàn)榭?，則該樹有（ ） 個(gè)葉結(jié)點(diǎn)。 選擇一項(xiàng)： C. 21 D. 22 題目10 在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（）倍。 選擇一項(xiàng)： A. 2 B. 1 C. 4 D. 1/2 題目11 鄰接表是圖的一種（）o 選擇一項(xiàng)： A. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) B.

4、 順序存儲(chǔ)結(jié)構(gòu) C. 散列存儲(chǔ)結(jié)構(gòu) D. 索引存儲(chǔ)結(jié)構(gòu) 題目12 圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。 選擇一項(xiàng)： A. 先序 B. 后序 C. 層次 D. 中序 題目13 已知下圖所示的一個(gè)圖，若從頂點(diǎn)VI出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。 選擇一項(xiàng)： A. V1V2V4V5V8V3V6V7 B. V1V3V6V7V2V4V5V8 C. V1V2V4V8V3V5V6V7 D. V1V2V4V8V5V3V6V7 題目14 已知如下圖所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）o

5、 選擇一項(xiàng)： A. aedfcb B. abecdf C. aebcfd D. aecbdf 題目15 圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 選擇一項(xiàng)： A. 一對(duì)多 B. 多對(duì)多 C. 每一個(gè)元素都有一個(gè)且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼 D. 一對(duì)一 題目16 在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（ ）o 選擇一項(xiàng)： A. 2i+l B. 2i-l C. 2i D. 2i+2 題目17 一棵具有16個(gè)結(jié)點(diǎn)的完全二叉樹，共有（ ）層。（設(shè)根結(jié)點(diǎn)在第一層） 選擇一項(xiàng)： A. 7 B. 5 C. 6 D. 4

6、 題目18 對(duì)二叉排序樹進(jìn)行（ ）遍歷，可以使遍歷所得到的序列是有序序列。 選擇一項(xiàng): A. 按層次 B. 中序 C. 前序 D. 后序 )o 已知一個(gè)圖的邊數(shù)為m則該圖的所有頂點(diǎn)的度數(shù)之和為（ 選擇一項(xiàng)： A. m/2 B. m C. 2m D. 2m+l 二、判斷題（每小題1分，共10分） 題目20 一棵二叉樹的葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）數(shù)為5,單分支結(jié)點(diǎn)數(shù)為2,該樹共有11個(gè)結(jié)點(diǎn)。 選擇一項(xiàng)： 對(duì) 錯(cuò) 題目21 一棵有14個(gè)結(jié)點(diǎn)的完全二叉樹，則它的最高層上有7個(gè)結(jié)點(diǎn)。 選擇一項(xiàng)： 對(duì) 錯(cuò) 題目22 一棵二叉樹有6個(gè)葉結(jié)點(diǎn)，則該樹總共有1

7、1個(gè)結(jié)點(diǎn)。 選擇一項(xiàng)： 對(duì) 錯(cuò) 題目23 根據(jù)搜索方法的不同，圖的遍歷有.先序；中序；后序三種方法。 選擇一項(xiàng)： 對(duì) 錯(cuò) 題目24 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中共有n-1個(gè)指針域空。 選擇一項(xiàng)： 對(duì) 錯(cuò) 設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為10,該完全二叉樹 一共有21個(gè)結(jié)點(diǎn)。 選擇一項(xiàng)： 對(duì) 錯(cuò) 題目26 設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為偶數(shù)，該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為9,該完全二叉樹一 共有19個(gè)結(jié)點(diǎn)。 選擇一項(xiàng)： 對(duì) 錯(cuò) 題目27 按照二叉樹的遞歸定義，

8、對(duì)二叉樹遍歷的常用算法有深度優(yōu)先遍歷和深度優(yōu)先遍兩種方法。 選擇一項(xiàng)： 對(duì) 錯(cuò) 題目28 一棵有8個(gè)權(quán)重值構(gòu)造的哈夫曼數(shù)，共有17個(gè)結(jié)點(diǎn)。 選擇一項(xiàng)： 對(duì) 錯(cuò) 題目29 一棵有7個(gè)葉結(jié)點(diǎn)的二叉樹，其1度結(jié)點(diǎn)數(shù)的個(gè)數(shù)為2,則該樹共有15個(gè)結(jié)點(diǎn)。 選擇一項(xiàng)： 對(duì) 錯(cuò) 三、程序填空題（每空6分，共12分。請(qǐng)點(diǎn)擊正確選項(xiàng)，然后拖拽至相應(yīng)的方框上） 題目30 以下程序是后序遍歷二叉樹的遞歸算法的程序,完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right, 數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。完成程序中空格部分。 void inorder (str

9、uct BTreeNode *BT) ( if( BTI=NULL) ( lnarder(BT->left); lnorder(BT-> right) v printff,BT->data) v 利用上逑程序?qū)ψ髨D進(jìn)行后序遍歷，結(jié)果是 d.e.b.f.c.a 題目31 以下程序是中序遍歷二叉樹的遞歸算法的程序,完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right, 數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。 void Inorder (struct BTreeNode *BT) lnarder(BT->left)；｝ printf(,%cM,BT->dat

10、a) rlght) v . 利用上述程序?qū)τ覉D進(jìn)行中序遍歷，結(jié)果是 d.b.e.a.f.c 四、綜合應(yīng)用題（每小題8分，5題，共40分） 題目32 （1 ）以3,4/5,89,作為葉結(jié)點(diǎn)的權(quán),杓造F昭夫受利?正捌的帶枝路徑長(zhǎng)度為 B A.64 B.65 C. 62 D. 66 《2）權(quán)重為3的葉結(jié)點(diǎn)的哈夫曼漏碼為V . A.010 BD101 C.000 D.0111 題目33 (1 )以2 3 4 7 , 8 9作為口十結(jié)點(diǎn)的權(quán) 構(gòu)母一觸夫曼枸 該柯的希權(quán)路徑長(zhǎng)度為B € ? - A.66 B.80 C.62 D::07 ⑵權(quán)重值為

11、4的葉結(jié)點(diǎn)的哈夫曼編碼為C #八 A.0001 B. 1110 C.001 D.：110 題目34 (1)已知某二叉樹的后序遍歷序列是debc*中序遍歷序列是dbeac,該二叉樹的根結(jié)點(diǎn)是【， / Ae B c c； b D a 皿)先序遍用序列是C： ▼ / , A. e.0xc.d,a C. a.b.d.e.c D. a.c.b.d.e, 題目35 (1)已知某二叉樹的先序遍歷序列是沖曲，中序遍用序列是eadcb,該二叉樹的根結(jié)點(diǎn)是d S 5 i A/e: B-C IC.b Df.a (2 )后序遍歷序列為I A # 力. A, e.0,b.c,a B. c,a4bHd

12、,e C a.Dtd.8.c D. a.c.b.d.e； 題目36 (1)以結(jié)定權(quán)重值5,金17. 18< 25, 30,為葉結(jié)點(diǎn)，建立一禪哈夫曼樹，該樹的中序遍歷序列為B ? A.5, 11, 28, 6, 17, 58, 3。. 101, 18, 43, 25 4 3, 25 C.5, Ih 6, 28, 10I> 58, 30< 17. 18, 43. 25 lb 6, 28, 17, 58, 30, 10h 18f 25, 43. D. S, lb 6, 2& 17，5& 30, IDb (2)權(quán).重值為6的葉結(jié)點(diǎn)的哈夫曼為I)e ? A. 1DD1 B.D11 C.001 D.00D1