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