数据结构考研分类复习真题 第九章 集合[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) 【北京科技大学 八】

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