資源簡介

粵教版 選修1 第四章 抽象數(shù)據類型 單元練習
學校:___________姓名：___________班級：___________考號：___________
一、選擇題
1．以下數(shù)據結構中不屬于線性結構的是（ ）
A．數(shù)組 B．鏈表 C．隊列 D．樹
2．如圖a為一棵二叉樹，其數(shù)組實現(xiàn)示意圖(部分)如圖b 所示
圖 a
0 1 2 3 4 5 …
A B C D E
圖b
下列說法正確的是（ ）
A．該二叉樹的前序遍歷為ABCDEFG B．該二叉樹的高度為 3
C．該二叉樹是完全二叉樹 D．節(jié)點 G 存儲在數(shù)組下標為 11 的位置
3．設一棵二叉樹的中序遍歷序列：becfad，后序遍歷序列：efcbda，則二叉樹前序遍歷序列為（ ）
A．abcdef B．bdaefc C．abcefd D．abcfed
4．已知一棵完全二叉樹，其第 4 層有3個葉子節(jié)點，這棵二叉樹的節(jié)點數(shù)量不可能是( )
A．25 B．24 C．11 D．10
5．已知7個結點的二叉樹的前序遍歷是 A B D E F C G（字母為結點的編號，以下同），中序遍歷是D B F E A G C，則該二叉樹的后序遍歷是（ ）
A．D F E B G C A B．D F E B A C G C．F B C G E D A D．D F E C A G B
6．一棵度為3，深度為4的樹，最多有（ ）個節(jié)點。
A．31 B．32 C．40 D．42
7．已知一棵二叉樹的前序遍歷為ABDECFG，中序遍歷為DBEAFCG，則該二叉樹的后序遍歷序列為(　　)
A．DEBAFGC B．DEBFGCA C．DBEGFCA D．DEBFGCA
8．已知一棵二叉樹的前序遍歷序列為：A-B-D-C-E，后序遍歷序列為：D-B-E-C-A，則該二叉樹是否 能唯一確定？中序遍歷序列是？（ ）
A．能唯一確定，中序遍歷序列為：B-D-A-E-C
B．不能唯一確定， 中序遍歷序列可能為： B-D-A-E-C
C．能唯一確定，中序遍歷序列為：D-C-B-A-E
D．不能唯一確定， 中序遍歷序列可能為： D-C-B-A-E
9．一棵二叉樹的前序遍歷結果為JFDECBHAIG，中序遍歷結果為DFEJAHBICG，則該二叉樹的深度為（ ）
A．6 B．5 C．4 D．3
10．有一棵二叉樹如圖所示，該二叉樹的后序遍歷結果正確的是（ ）
A．XBCDAYEF B．FEYADCBX C．DBEAFXCY D．DEFABYCX
試卷第1頁，共3頁
試卷第1頁，共3頁
參考答案：
1．D
【詳解】本題主要考查數(shù)據結構的描述。線性結構是一個有序數(shù)據元素的集合，如數(shù)組、鏈表和隊列。樹結構屬于非線性結構，故本題選D選項。
2．D
【詳解】本題主要考查二叉樹的描述。由圖可知，該二叉樹的前序遍歷為ABDCEGF；該二叉樹的高度為 4；該二叉樹是不完全二叉樹；按照數(shù)組示意圖，可知是逐層自左向右依次存儲，沒有的元素為空，可推得節(jié)點 G 存儲在數(shù)組下標為 11 的位置，故本題選D選項。
3．C
【詳解】本題主要考查二叉樹的遍歷。從后序遍歷中，我們確定了根結點為a，在從中序遍歷中得出 b-c-e-f 在根結點的左邊，d在根結點的右邊，那么我們就可以構建我們的二叉樹的雛形。之后就是新根節(jié)點b，cef在根右。在之后就是新根c，e根左，f根右，如圖所示： ，則二叉樹前序遍歷序列為abcefd，故本題選C選項。
4．C
【詳解】本題主要考查二叉樹。完全二叉樹除了最后一層，是一棵滿二叉樹，其節(jié)點數(shù)為2^k- 1, k是層數(shù)，所以為2^3- 1 =7，然后加上第四層最少3個葉子為7+3=10 ,故最少給10個節(jié)點，由于是完成二叉樹，每增加一個根節(jié)點則下面增加兩個子節(jié)點，所以不可能是11個節(jié)點，故本題選C選項。
5．A
【詳解】本題主要考查二叉樹遍歷。前序遍歷是 A B D E F C G（即先遍歷：根左右），中序遍歷是D B F E A G C（左根右的方式），則可以畫出該二叉樹如下，則該二叉樹的后序遍歷是（即左右根的方式）：D F E B G C A，故本題選A選項。
6．C
【詳解】本題主要考查數(shù)據結構。一棵度為3，深度為4的樹，則第一層有1個根節(jié)點，第二層最多有3個子節(jié)點，第三層最多有3*3=9個子節(jié)點，第四層最多有3*9=27個子節(jié)點，則最多有1+3+9+27=40個節(jié)點，故本題選C選項。
7．B
【詳解】本題主要考查二叉樹的遍歷。根據前序遍歷為ABDECFG，中序遍歷為DBEAFGC可畫出該二叉樹如下： ，則該二叉樹的后序遍歷序列為DEBFGCA，故本題選B選項。
8．B
【詳解】本題主要考查二叉樹的遍歷。已知一棵二叉樹的前序遍歷序列為：A- B- D- C - E可以確定根節(jié)點為A，已知后序遍歷序列為:D- B- E-C- A可以確定左子樹的起點為B，無法確定左子樹到哪里結束，同樣無法確定右子樹的開始節(jié)點。所以無法確定唯一性，中序遍歷序列可能為:B- D- A- E- C，故本題選B選項。
9．B
【詳解】本題主要考查二叉樹的遍歷。前序遍歷是“根左右”，中序遍歷是“左根右”，一棵二叉樹的前序遍歷結果為JFDECBHAIG，中序遍歷結果為DFEJAHBICG，則該二叉樹如下： 由圖可知，該二叉樹的深度為5，故本題選B選項。
10．D
【詳解】本題主要考查二叉樹的遍歷。二叉樹的后序遍歷：即先左子樹、再右子樹、最后根，故該二叉樹的后序遍歷結果正確的是DEFABYCX，故本題選D選項。
答案第1頁，共2頁
答案第1頁，共2頁

展開更多......

收起↑