问答题
(1)设二叉排序树中关键字由1至1000的整数组成，现要检索关键字为363的结点，下述关键字序列中哪些可能是二叉排序树上搜索到的序列，哪些不可能是二叉排序树上搜索到的序列?a.2，252，401，398，330，344，397，363b.924，220，911，244，898，258，362，363c.925，202，911，240，912，245，363d.2，399，387，219，266，382，381，278，363(2)通过对(1)的分析，写一个算法判定给定的关键字序列(假定关键字互不相同)是否可能是二叉排序树的搜索序列。若可能是返回真，否则返回假。可假定被判定的序列已存入数组中。【中国科学技术大学1998】
【正确答案】正确答案：(1)A、B、D有可能是二叉排序树的查找序列。C不可能是。 (2)二叉排序树的查找走了一条从根结点到子孙结点的路径。查找开始时首先和根结点的值比较，若根结点的值大于待查结点的值，则到左子树中查找，否则到右子树中查找。子树根结点的值和待查结点值的比较，也遵循如上规律。在查找过程中逐渐缩小查找范围。我们用high表示查找的上界，用low表示查找的下界，若low>high，则不是二叉排序树的查找序列。算法的核心语句段如下： low=preLow=一maxint，high=preHigh=maxint；／／max是机器最大数 while(low
low＆＆icn) ／／相当于沿右子女方向走，在某结点左转时退出 {preLow=low；low=a[i++]) if(i
【答案解析】