數據結構考研分類復習真題 第九章 集合[43]

　　 設記錄RR…Rn按關鍵字值從小到大順序存儲在數組r[n]中在r[n+]處設立一個監督哨其關鍵字值為+∞; 試寫一查找給定關鍵字k 的算法;並畫出此查找過程的判定樹求出在等概率情況下查找成功時的平均查找長度【武漢交通科技大學 四 (分)】

　　．試編寫算法在根結點指針為t的m階B樹上查找關鍵字k返回記錄(ptitag)若查找成功則特征位tag=等於k的關鍵字即為指針pt所指結點中的第i個關鍵字;若查找不成功則特征位tag=等於k的關鍵字應插入到指針pt所指結點中第i個和第i+個關鍵字之間簡化B樹存儲結構如下所示

　　type  mblink=↑mbnode
　　mbnode=record
　　keynum:integer;
　　parent:mblink;
　　key:array[m]  of  keytp  {關鍵字}
　　ptr:array [m]  of  mblink
　　end;
　　result=record
　　pt:mblink;
　　i:integer;
　　tag:()
　　end;

　　(注所用語言C PASCAL等都可使用編制算法若算法不用類PASCAL描述要給出相應語言的結構描述題目中給出的結構說明可供參考也可自行給出)【北京輕工業學院   八 (分)】

　　元素集合已存入整型數組A[n]中試寫出依次取A中各值A[i](<=i<=n)構造一棵二叉排序樹T的非遞歸算法CSBT(TA) 【北京科技大學   八】

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []