數(shù)據(jù)結(jié)構(gòu)與算法分析六套期末復(fù)習(xí)題(含答案)-文庫吧資料
2025-06-25 23:18本頁面
【正文】 logn)，快速排序是O(n2)，所以，可見快速排序時間復(fù)雜度最差。六、（本題8分）請說明對一棵二叉樹進(jìn)行前序、中序和后序遍歷，其葉結(jié)點(diǎn)的相對次序是否會發(fā)生改變？為什么？七、（本題9分）已知一棵二叉樹的先序序列與中序序列分別如下，試畫出此二叉樹。三、（本題8分）給定一個關(guān)鍵字序列｛24，19，32，43，38，6，13，22｝，請寫出快速排序第一趟的結(jié)果；堆排序時所建的初始堆；然后回答上述兩種排序方法中哪一種方法使用的輔助空間最小，在最壞情況下哪種方法的時間復(fù)雜度最差？四、（本題8分）設(shè)二維數(shù)組A[0:10,5:0]，按行優(yōu)先順序存儲，每個元素占4個單元，A[0][5]的存儲地址為1000，則A[9][2]的存儲地址為多少？五、（本題8分）用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL。（10）設(shè)有關(guān)鍵碼序列(q,g,m,z,a)，（ ）序列是從上述序列出發(fā)建的小根堆的結(jié)果。A）3 B）2 C）5 D）4（8）該二叉樹的按層遍歷的序列為（ ）。（6）則該二叉樹結(jié)點(diǎn)的前序遍歷的序列為（ ）。A）在隊(duì)列第i個元素之后插入一個元素 B）從隊(duì)頭刪除一個元素C）判斷一個隊(duì)列是否為空 D）讀取隊(duì)頭元素的值（4）字符A、B、C、D依次進(jìn)入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成（ ）個不同的字符串？A）15 B）14 C）16 D）21（5）由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ）。 }}試題四一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？（ ?。〢）有向圖 B）棧 C）二叉樹 D）B樹（2）若某鏈表最常用的操作是在最后一個結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)和刪除最后一個結(jié)點(diǎn)，則采用（ ?。┐鎯Ψ绞阶罟?jié)省時間。 //左子樹的深度 d_rsub=BiTreeDepth(Trchild)。 //空二叉樹的深度為0 else { int d_lsub,d_rsub。本題最簡單算法是遞歸算法。歸并段3：2,14,17,20,30.五、（本題9分）構(gòu)造二叉排序樹的過程如下圖所示。然而交換后一定減少的是“逆序?qū)Α钡膫€數(shù)，例如上例中｛l｝的逆序?qū)Φ膫€數(shù)是 7，交換第二個 3和2后，｛1｝的逆序?qū)Φ膫€數(shù)是6?！敬鸢浮?=================================一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）B （2）A （3）B （4）C （5）B （6）B （7）D （8）A （9）D （10）C二、（本題8分）采用樹形選擇排序方法所需的關(guān)鍵字比較次數(shù)最少，最多比較次數(shù)=999999+=1000019次。五、（本題9分）已知關(guān)鍵字序列{23，13，5，28，14，25}，試構(gòu)造二叉排序樹。若在一個無序序列中有一對元素aiaj(ij)，試問，當(dāng)ai與aj相互交換后，該序列中逆序元素的個數(shù)一定不會增加，這句話對不對？如果對，請說明為什么？如果不對，請舉一例說明。A）O(log2n) B）O(nlog2n) C）O(n) D）O(n2)（10）從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為（ ?。）值 B）函數(shù) C）指針 D）引用（8）在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點(diǎn)都具有相同的（ ）。A）冒泡排序 B）簡單選擇排序C）希爾排序 D）直接插入排序（6）采用開放定址法處理散列表的沖突時，其平均查找長度（ ?。?。 pnext=HL（3）對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（ ）A）經(jīng)常需要隨機(jī)地存取元素 B）經(jīng)常需要進(jìn)行插入和刪除操作C）表中元素需要占據(jù)一片連續(xù)的存儲空間 D）表中元素的個數(shù)不變（4）一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是（ ?。?。 HL=pC）pnext=HL。A）pnext=HLnext。 }試題三一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）對一個算法的評價，不包括如下（ ）方面的內(nèi)容。Trchild==NULL) return 1。 //空樹返回0 else if(Tlchild==NULLamp。五、（本題8分）六、（本題15分）本題只要在遍歷二叉樹的過程序中對葉子結(jié)點(diǎn)進(jìn)行記數(shù)即可。三、（本題8分）樹的遍歷方法有先根序遍歷和后根序遍歷，它們分別對應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄浜蟮南刃虮闅v與中序遍歷方法。六、（本題15分）以二叉鏈表作存儲結(jié)構(gòu)，試編寫計(jì)算二叉樹中葉子結(jié)點(diǎn)數(shù)目的遞歸算法。三、（本題8分）樹有哪些遍歷方法？它們分別對應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄涞哪男┍闅v方法？四、（本題8分）設(shè)有數(shù)組A[1:3,0:6,2:3]，按行為主序存放在2000開始的連續(xù)空間中，如元素的長度是5，試計(jì)算出A[1,1,1]的存儲位置。A）1 B）2 C）3 D）4（10）下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（ ）。A）線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序 B）線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序C）線性表以順序方式存儲，并且按關(guān)鍵碼值排好序D）線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序（8）對n個記錄進(jìn)行堆排序，所需要的輔助存儲空間為（ ）。A）若一個葉子是某二叉樹的中序遍歷的最后一個結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷最后一個結(jié)點(diǎn)B）若一個結(jié)點(diǎn)是某二叉樹的前序遍歷最后一個結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷的最后一個結(jié)點(diǎn)C）若一個結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個結(jié)點(diǎn)，則它必是該二叉樹的前序最后一個結(jié)點(diǎn)D）若一個樹葉是某二叉樹的前序最后一個結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后一個結(jié)點(diǎn)（6）k層二叉樹的結(jié)點(diǎn)總數(shù)最多為（ ?。?。A）n B）n1 C）n+1 D）不確定（3）下述哪一條是順序存儲方式的優(yōu)點(diǎn)？（ ?。〢）存儲密度大 B）插入和刪除運(yùn)算方便 C）獲取符合某種條件的元素方便 D）查找運(yùn)算速度快（4）設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每個元素占一個空間，問A[2][3](10)存放在什么位置？（腳注(10)表示用10進(jìn)制表示，m3）（ ）。 //顯示左子樹 }}=========================================================================試題二一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）設(shè)Huffman樹的葉子結(jié)點(diǎn)數(shù)為m，則結(jié)點(diǎn)總數(shù)為（?。? //確保在第le
外語相關(guān)推薦
鄂ICP備17016276號-1