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

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

　　類(lèi)似本題的另外敘述有：

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

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

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

　?。?） 若一組數(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è)計(jì)思想畫(huà)出插入元素前后的數(shù)據(jù)結(jié)構(gòu)狀態(tài)?！?a target="_blank">北京工業(yè)大學(xué) 1995 七 (20分)】
　　
　　3．假設(shè)K1，…，Kn是n個(gè)關(guān)鍵詞，試解答：

　　(1) 試用二叉查找樹(shù)的插入算法建立一棵二叉查找樹(shù)，即當(dāng)關(guān)鍵詞的插入次序?yàn)镵1，K2，…，Kn時(shí)，用算法建立一棵以L(fǎng)LINK / RLINK 鏈接表示的二叉查找樹(shù)。

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

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