數(shù)據(jù)結(jié)構(gòu)綜合練習(xí)

1、軟件技術(shù)基礎(chǔ)（二）數(shù)據(jù)結(jié)構(gòu)（二）一、選擇題只允許在一端進行插入刪除的線性表稱為.棧頂 B.隊列 C.堆棧 D.隊尾向順序棧中壓入元素時，A.先移動棧頂指針，后存入元素B.先存入元素，后移動棧頂指針C.誰先誰后無關(guān)緊要D.同時進行對鏈?zhǔn)酱鎯Φ木€性表。A.可采用順序查找，但不可采用二分查找B.可采用二分查找，但不可采用順序查找C.順序查找和二分查找均可采用D.順序查找和二分查找均不可采用線性表L在下列 情況下，適合使用鏈接結(jié)構(gòu)實現(xiàn)。A.L中含有大量結(jié)點B.需經(jīng)常對L表進行刪除與插入C.需經(jīng)常修改L的結(jié)點值 D.L表結(jié)點結(jié)構(gòu)復(fù)雜設(shè)f和r分別是一個鏈表的隊頭和隊尾，那么從該隊列中刪除一個結(jié)點的運算是。

2、A.r=f-next B.r=r-next C.f=f-next D.f=r-next設(shè)f和r分別是一個鏈表的隊頭和隊尾，那么從該隊列中插入一個結(jié)點的運算是。 A.r=f-next B.r=r-next C.f=f-next D.f=r-next在有n單元的順序存儲的堆棧中，假定以地址低端（即下標(biāo)為1的單元）作為棧底，以top作為棧頂指針， 則當(dāng)做入棧處理時,top的變化為：.A.top 不變 B. top=top+1 C. top=n D.top=top-1若進棧序列為1，2, 3, 4,假定進棧和出?？梢源┎暹M行，則不可能出棧的序列是.A. 1,4,3,2 B. 2,3,4,1 C. 3,

3、1,4,2 D. 3,4,2,1設(shè)棧初始為空，輸入序列為：a，b，c，d。經(jīng)過入棧、入棧、出棧、入棧、出棧、入棧操作之后，棧 中的元素（從棧底到棧頂）依次為。A. a，dB.a,c C. b， c D. d,a對于任何一棵二叉樹，若葉子結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則n0=.A.n2-1B.n2C.n2+1D.2*n2一棵二叉樹中共有70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為A.219B.221C.229D.231深度為6的二叉樹上共有 個葉子結(jié)點。A. 31B.32C.63D.64將有三棵樹的森林轉(zhuǎn)換成一棵二叉樹，則第二棵樹的根結(jié)點是該二叉樹根結(jié)點的 的根結(jié)點。A

4、.左子樹 B.左子女的右子樹C.右子樹 D.右子女的右子樹將有三棵樹的森林轉(zhuǎn)換成一棵二叉樹，則第三樹的根結(jié)點是該二叉樹根結(jié)點的 的根結(jié)點。A.左子樹 B.左子樹的右子樹C.右子樹D.右子樹的右子樹 假定一棵二叉樹的結(jié)點數(shù)為18,則它的最小深度為.A.18B.9C.5D.3在具有size單元的順序存儲的循環(huán)隊列中，假定front和rear分別指示隊列中第一個元素和最后一 個元素的下一個位置，則判斷隊空的條件是： .A.front+1= rear B.front=0 C. front= rear D.front=rear+1在由m個單元組成的循環(huán)隊列中，隊首指針F指示隊列中首元素的前一個位置，隊尾

5、指針R指示隊列 中最后一個元素，則判斷隊滿的條件是。A.F=(R+1)%mB.F=RC.(F+1)%m=RD.R%m+1=F鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是A-插入操作更加方便B.通常不會出現(xiàn)棧滿的情況C.不會出現(xiàn)?？盏那闆rD.刪除操作更加方便如果n1和n2是二叉樹T中兩個不同結(jié)點，n2是n1的后代，那么按 遍歷二叉樹T時，結(jié)點n2 一定比結(jié)點n1先被訪問。A.先序 B.中序 C.后序 D.逆中序一棵二叉樹具有9個葉子結(jié)點。且非葉子結(jié)點都是度為2的結(jié)點，則這棵二叉樹共有 結(jié)點。A.17B.18C.19D.20具有三個結(jié)點的二叉樹的基本形態(tài)有 種。A.5B.4C.3D.2以下 不是隊列的

6、基本操作。A.從隊尾插入一個新元素B.從隊列中刪除第i個元素C.判斷一個隊列是否為空D。讀取隊頭元素的值。在樹結(jié)構(gòu)中，如果結(jié)點A有3個兄弟，而且B是A的雙親，則B的度是。A.3 B.1C.4 D5.線性表是A. 一個有限序列，可以為空B. 一個有限序列，不能為空C. 一個無限序列，可以為空D. 一個無限序列，不能為空線性表采用鏈?zhǔn)酱鎯r，其地址A.必須是連續(xù)的B。部分地址必須是連續(xù)的C. 一定是不連續(xù)的D.連續(xù)與否均可以一維數(shù)組和線性表的區(qū)別是。A.前者長度固定，后者長度可變B。后者長度固定，前者長度可變C.兩者長度均固定D.兩者長度均可變數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu).A.

7、存儲 B.物理 C.物理和存儲D.邏輯 鏈表不具有的特點是。A.隨機訪問B.不必事先估計存儲空間（1插入刪除時不需移動元素D.所需空間與線性表成正比二叉樹有多種形式，若深度為K,且有2K-1個結(jié)點的二叉樹稱為。A.完全二叉樹B.滿二叉樹C.順序二叉樹D.排序樹已知某二叉樹的前序序列是ABDC，中序序列是DBAC，問它的后序序列是。A. ADBC B. DBCA C. CABD D.DCBA上溢現(xiàn)象通常出現(xiàn)在.A.順序棧的入棧操作過程中B.順序棧的出棧操作過程中C.鏈棧的入棧操作過程中D.鏈棧的出棧操作過程中引起循環(huán)隊列隊頭位置發(fā)生變化的操作是.A.出隊 B.入隊 C.取隊頭元素D.取隊尾元素除

8、第一層外，滿二叉樹中每一層結(jié)點個數(shù)是上一層結(jié)點個數(shù)的.A.1/2 倍 B. 1 倍 C. 2 倍 D. 3 倍在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系.A.不一定相同 B.都相同 C.都不相同 D.互為逆序一棵二叉樹中共有10個葉子結(jié)點與20個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為A.30B.31C.39D.40棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是A.順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)B.鏈表存儲結(jié)構(gòu)和數(shù)組C.線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)D.散列方式和索引方式 鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間。分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針只有一部分，存放結(jié)點值只有一部分

9、，存儲表示結(jié)點間關(guān)系的指針分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)只允許在二端進行插入刪除的線性表稱為.A.棧頂 B.隊列 C.堆棧 D.隊尾堆棧結(jié)構(gòu)的特點是。A.同時進出 B.先進先出C.后進后出D.后進先出網(wǎng)狀數(shù)據(jù)模型.A.允許有一個以上的結(jié)點無雙親B有且只有一個結(jié)點無雙親C .除了一個根結(jié)點，其他結(jié)點只有一個雙親 D.每一個結(jié)點的子女不能多于一個學(xué)校中學(xué)生作為一個實體與他的學(xué)習(xí)課程（另一個實體）之間的聯(lián)系是.A.一對一B.多對多 C一對多0.多對一 鏈表中進行 操作的效率比順序表中高。A.二分查找和刪除B.插入和刪除C.二分查找和插入 D.快速查找當(dāng)棧中的元素為n個，作進棧

10、運算時發(fā)生上溢，則說明該棧的最大容量為.A.n-1B.n C.n+1D.n/2棧和隊列.A.的共同點都是先進后出B.的共同點都是先進先出C.的共同點是只允許在端點處插入和刪除元素D.沒有共同點二.填空題有一棵順序二叉樹，有編號為22結(jié)點的雙親，其左孩子在 編號位置上。在深度為7的滿二叉樹中，度為2的結(jié)點個數(shù)為。按“先進后出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是。需要對線性表進行插入和刪除運算，則最好采用 存儲結(jié)構(gòu)。若一個棧的輸入序列是1，2, 3.，n，輸出序列的第一個元素是n，則第I個輸出元素是。允許在一端進行插入，而在一端進行刪除的線性表稱為.對于任一棵二叉樹，若葉子結(jié)點個數(shù)為n0,度為2的結(jié)點數(shù)為n

11、2，則n2=.一個具有22個葉子結(jié)點的二叉樹，其度數(shù)為2的結(jié)點數(shù)是。在二叉樹上的第3層上至多有 個結(jié)點.采用二叉鏈表存儲二叉樹時，具有10個結(jié)點的二叉樹，則有 個指針域為空。一棵二叉樹其終端結(jié)點為10，則度為2的結(jié)點數(shù)有 個。深度為K的滿二叉樹有 個結(jié)點.（K=1）順序表是一種隨機存取的存儲結(jié)構(gòu)，而單鏈表是一種 的存儲結(jié)構(gòu).需要對線性表經(jīng)常進行插入和刪除運算，則最好采用 存儲結(jié)構(gòu)。為了最快的存取某元素，宜用順序結(jié)構(gòu)；為了方便地插入一個元素，宜用.設(shè)有n個節(jié)點的完全二叉樹，順序存放在數(shù)組A1.n中，對任一個節(jié)點Ai，若Ai有左子女， 則左子女是數(shù)組A的 .設(shè)有n個節(jié)點的完全二叉樹，順序存放在數(shù)組

12、A1.n中，對任一個節(jié)點Ai，若Ai有父母，則 父母是數(shù)組A的 . 鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是借助 來表示數(shù)據(jù)元素之間的邏輯關(guān)系。樹形結(jié)構(gòu)中節(jié)點a有4個兄弟，b是a的雙親，則b的度為二元組（D，R）來表示數(shù)據(jù)結(jié)構(gòu)，那么D指數(shù)據(jù)元素，R指。二叉排序樹進行中序遍歷時，得到的結(jié)點序列是一個.在樹中，一個結(jié)點的直接子結(jié)點的個數(shù)稱為該結(jié)點的.數(shù)據(jù)庫的層次模型有且僅有一個結(jié)點無雙親，而網(wǎng)狀模型一定會有 結(jié)點無雙親，這是與層次模型的重要區(qū)別。三改錯題如果一棵二叉樹中的結(jié)點的度只有0或2,則稱此樹為滿二叉樹。（）棧是操作受限的線性表，它的運算僅能在線性表的二端進行。（） TOC o 1-5 h z 在順序表中插入和

13、刪除元素時，移動元素的個數(shù)僅與該元素的位置有關(guān)。（）順序存儲方式的優(yōu)點是存儲密度大，且插入和刪除運算效率高.（）用樹的前序遍歷和后序遍歷可以導(dǎo)出樹的中序遍歷。（）如果一棵二叉樹中的結(jié)點的度只有0或2,則稱此樹為順序二叉樹。（）棧是操作受限的線性表，它的運算僅能在線性表的二端進行。（）用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷。二叉樹是樹的特殊情況。在哈夫曼樹中，權(quán)重的結(jié)點離樹根愈遠。將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點沒有左子樹。二叉樹中每個結(jié)點有二個子結(jié)點，而一般的樹則無此限制，因此二叉樹是樹的特殊情況。鏈接存儲方式的優(yōu)點是存儲密度大，但是插入和刪除運算效率差。每個結(jié)點的度都小于等于2的樹是二叉

14、樹。不使用遞歸，也可以實現(xiàn)二叉樹的前序、中序、后序遍歷。完全二叉樹中，若一個結(jié)點沒有左孩子，則它必然是葉子。圖結(jié)構(gòu)是一種線性數(shù)據(jù)結(jié)構(gòu).二叉樹中結(jié)點只有一個孩子時無左右之分.堆棧結(jié)構(gòu)是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)二叉樹中必有度為 2 的結(jié)點簡答題（每題5分，共15分）什么是數(shù)據(jù)的邏輯結(jié)構(gòu)?什么是數(shù)據(jù)的物理結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)有幾種類型？各有什么特點？請分別寫出棧和隊的定義，并寫出它們的簡單應(yīng)用例。試畫出具有三個結(jié)點的二叉樹的所有不同形態(tài)。棧與隊列是兩種特殊的線性表，棧的特點是什么？隊的特點是什么？二叉樹和樹有什么不同？綜合應(yīng)用題（共3*7=21分）若a，b，c，d，e，f的權(quán)重分別為11,2,16,3,22,18，試構(gòu)造關(guān)于w的一棵哈夫曼樹，并求出其 wpl和各字符的編碼（結(jié)點的排列為左小右大）。95.設(shè)二叉樹的存儲結(jié)構(gòu)如下:12345678910Lchild00237580101JHFDBACEGI0009400000DataRchild其中根結(jié)點的指針值為6 , Lchild、Rchild分別為結(jié)點的左、右孩子指針域，Data為數(shù)據(jù)域。畫出該二叉樹的邏輯結(jié)構(gòu)。寫出該二叉樹的前序、中序和后序遍歷的序列。有一棵二叉樹如5圖所示，試寫出該二叉樹的中序遍歷和后序遍歷序列。假設(shè)一棵二叉樹的先序遍歷序列為FAMBXCR，中序遍歷序列為AFXBMCR，請畫出該二叉樹和求出二叉 樹的后序遍歷序列。98