數(shù)據(jù)結(jié)構(gòu)第九章《集合》算法設(shè)計題_跨考網(wǎng)

???????? 1．請編寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)二叉樹用llink-rlink法存儲?！?a target="_blank">北京大學(xué) 1998 三、2 （5分）】

　　類似本題的另外敘述有：

　?。?）試寫一個判別給定二叉樹是否為二叉排序樹的算法?！?a target="_blank">中山大學(xué) 1994 五 (12分)】

　?。?）某二叉樹采用鏈接存儲，其結(jié)點結(jié)構(gòu)是：（lc,data,rc）。 lc和rc分別是指向左子樹根和右子樹根的指針域。data為結(jié)點數(shù)據(jù)域。試寫出判斷該二叉樹是否為二叉排序樹的算法（不許另設(shè)空間，但可以設(shè)一些輔助指針）。設(shè)二叉排序樹左子樹每個結(jié)點值<根結(jié)點值，右子樹每個結(jié)點的值≥根結(jié)點的值。二叉樹是遞歸定義的。按此定義寫出判斷某二叉樹是否為二叉排序樹的算法?！?a target="_blank">北京郵電大學(xué) 1993 四 （20分）】

　　（3）編寫判定給定的二叉樹是否是二叉排序樹的函數(shù)?！?a target="_blank">南京大學(xué) 2000】
　　
　　2．某個任務(wù)的數(shù)據(jù)模型可以抽象為給定的K個集合：S1，S2，…，Sk。其中Si(1<=i<=k)中的元素個數(shù)不定。在處理數(shù)據(jù)過程中將會涉及到元素的查找和新元素的插入兩種操作，查找和插入時用一個二元組（i,x）來規(guī)定一個元素，i是集合的序號，x是元素值。設(shè)計一種恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)來存儲這k個集合的元素，并能高效的實現(xiàn)所要求的查找和插入操作。
　?。?）借助Pascal的數(shù)據(jù)類型來構(gòu)造和描述你所選定的數(shù)據(jù)結(jié)構(gòu)，并且說明選擇的理由；

　?。?） 若一組數(shù)據(jù)模型為S1={10.2, 1.7, 4.8, 16.2 }, S2={1.7, 8.4, 0.5 }, S3={4.8, 4.2, 3.6, 2.7, 5.1, 3.9 }, 待插入的元素二元組為(2, 11.2 )和(1, 5.3 ), 按你的設(shè)計思想畫出插入元素前后的數(shù)據(jù)結(jié)構(gòu)狀態(tài)?！?a target="_blank">北京工業(yè)大學(xué) 1995 七 (20分)】
　　
　　3．假設(shè)K1，…，Kn是n個關(guān)鍵詞，試解答：

　　(1) 試用二叉查找樹的插入算法建立一棵二叉查找樹，即當(dāng)關(guān)鍵詞的插入次序為K1，K2，…，Kn時，用算法建立一棵以LLINK / RLINK 鏈接表示的二叉查找樹。

　　(2) 設(shè)計一個算法，打印出該二叉查找樹的嵌套括號表示結(jié)構(gòu)。例如，K1=B，K2=A，K3=D，K4=C，K5=E，則用二叉查找樹的插入算法建立的二叉查找樹為：

　　該二叉查找樹的嵌套括號表示結(jié)構(gòu)為：B（A，D（C，E）） 【吉林大學(xué) 1995 六 (14分)】