數(shù)據(jù)結(jié)構(gòu)與算法分析六套期末復(fù)習(xí)題(含答案)(編輯修改稿)
2025-07-16 23:18 本頁面
【文章內(nèi)容簡介】 9）D （10）C二、（本題8分）采用樹形選擇排序方法所需的關(guān)鍵字比較次數(shù)最少，最多比較次數(shù)=999999+=1000019次。三、（本題8分）不對，例如序列｛l｝的“逆序元素”個數(shù)是2，2和1是“逆序元素”；但是將第二個3和2交換后，成為｛l｝，此時“逆序元素”個數(shù)是3，3和1是“逆序元素”。然而交換后一定減少的是“逆序?qū)Α钡膫€數(shù)，例如上例中｛l｝的逆序?qū)Φ膫€數(shù)是 7，交換第二個 3和2后，｛1｝的逆序?qū)Φ膫€數(shù)是6。四、（每小題4分，共8分）（1）用內(nèi)排序求出初始?xì)w并段為：歸并段1：29,33,38,50,60,70:歸并段2：9,25,28,31,36,43歸并段3：2,18,57,65,80,100:歸并段4：14,17,20,30,78,99.（2）用置換一選擇排序求初始?xì)w并段為：歸并段1：29,33,38,50,60,70,80,100歸并段2：9,18,25,28,31,36,57,65,78,99。歸并段3：2,14,17,20,30.五、（本題9分）構(gòu)造二叉排序樹的過程如下圖所示。構(gòu)造的二叉排序樹如下圖所示：六、（本題15分）若二叉樹為空，深度為0；若二叉樹不空，則二叉樹的深度為左右子樹深度的最大值加1。本題最簡單算法是遞歸算法。C語言版測試程序見exam3\10c，具體算當(dāng)如下：int BiTreeDepth(BiTree T)// 求二叉樹的深度{ if(T==NULL) return 0。 //空二叉樹的深度為0 else { int d_lsub,d_rsub。 d_lsub=BiTreeDepth(Tlchild)。 //左子樹的深度 d_rsub=BiTreeDepth(Trchild)。 //右子樹的深度 //返回左右子樹的深度最大值加1 return ((d_lsubd_rsub)?d_lsub:d_rsub)+1。 }}試題四一、單項選擇題（每小題 2 分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？（ ）A）有向圖 B）棧 C）二叉樹 D）B樹（2）若某鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用（ ?。┐鎯Ψ绞阶罟?jié)省時間。A）單鏈表 B）雙鏈表 C）帶頭結(jié)點的雙循環(huán)鏈表 D）單循環(huán)鏈表（3）（ ）不是隊列的基本運算。A）在隊列第i個元素之后插入一個元素 B）從隊頭刪除一個元素C）判斷一個隊列是否為空 D）讀取隊頭元素的值（4）字符A、B、C、D依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成（ ?。﹤€不同的字符串？A）15 B）14 C）16 D）21（5）由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ?。?。A）11 B）37 C）19 D）53以下68題基于下面的敘述：若某二叉樹結(jié)點的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。（6）則該二叉樹結(jié)點的前序遍歷的序列為（ ?。?。A）E、G、F、A、C、D、B B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）E、G、A、C、D、F、B（7）該二叉樹有（ ?。﹤€葉子。A）3 B）2 C）5 D）4（8）該二叉樹的按層遍歷的序列為（ ?。）E、G、F、A、C、D、B B）E、A、C、B、D、G、FC）E、A、G、C、F、B、D D）E、G、A、C、D、F、B（9）下面的二叉樹中，（ C ）不是完全二叉樹。（10）設(shè)有關(guān)鍵碼序列(q,g,m,z,a)，（ ?。┬蛄惺菑纳鲜鲂蛄谐霭l(fā)建的小根堆的結(jié)果。A）a,g ,m,q,z B）a,g,m,z,q C）g,m,q,a,z D）g, m, a,q,z二、（本題8分）設(shè)有一個輸入數(shù)據(jù)的序列是{ 46, 25, 78, 62, 12, 80 }，試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。三、（本題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。請寫出后序遍歷該二叉樹的訪問結(jié)點序列。六、（本題8分）請說明對一棵二叉樹進行前序、中序和后序遍歷，其葉結(jié)點的相對次序是否會發(fā)生改變？為什么？七、（本題9分）已知一棵二叉樹的先序序列與中序序列分別如下，試畫出此二叉樹。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI八、（本題15分）已知二叉排序樹采用二叉鏈表存儲結(jié)構(gòu)，根結(jié)點的指針為T，請寫出遞歸算法，從小到大輸出該二叉排序樹中所有關(guān)鍵字值≥K的結(jié)點的關(guān)鍵字的值?！敬鸢浮?=================================一、單項選擇題（每小題 2 分，共20分）（1）B （2）C （3）A （4）B （5）B （6）C （7）A （8）C （9）C （10）B二、（本題8分）如下圖所示：三、（本題8分）快速排序的第一趟結(jié)果為｛22,19,13,6,24,38,43,12｝；堆排序時所建立的初始大頂堆如所圖所示：兩種排序方法所需輔助空間：堆是O(1)，快速排序是O(logn)，可見堆排序所需輔助空間較少；在最壞情況下兩種排序方法所需時間：堆是O(nlogn)，快速排序是O(n2)，所以，可見快速排序時間復(fù)雜度最差。注意：快速排序的平均時排序速度最快，但在最壞情況下不一定比其他排序方法快。四、（本題8分）依題意A的起始地址為1000，則有：Loc(9,2)=1000+[(90)*(0(5)+1)+(2(5))]*4=1228。五、（本題8分）先畫出該二叉樹的樹形結(jié)構(gòu)。對其進行后序遍歷得到后序序列為：HIDJKEBLFGCA。六、（本題8分）二叉樹任兩個中葉結(jié)點必在某結(jié)點的左/右子樹中，三種遍歷方法對左右子樹的遍歷都是按左子樹在前、右子樹在后的順序進行遍歷的。所以在三種遍歷序列中葉結(jié)點的相對次序是不會發(fā)生改變的。七、（本題9分）先由先序序列的第一個結(jié)點確定二叉樹的根結(jié)點，再由根結(jié)點在中序序列中左側(cè)部分為左子樹結(jié)點，在右側(cè)部分為右子樹結(jié)點，再由先序序列的第一個結(jié)點確定根結(jié)點的左右孩子結(jié)點，由類似的方法可確定其他結(jié)點，如下圖所示。八、（本題15分）由于二叉排序樹是中序有序的，因此對二叉排序樹采用中序遍歷依次輸出大于等于K的結(jié)
外語相關(guān)推薦
鄂ICP備17016276號-1