计算机学科专业基础2026 真题档案

（1）算法的基本设计思想

按照在二叉搜索树中查找目标 k 的方法，从根开始沿着某条向下的路径进行查找。若当前结点中的关键字值与 k 相等，则结果只包含一个结点，差值的绝对值为 0，不相等时，结果最多包含两个结点，差值的绝对值大于 0。

对于不相等的情况，若当前结点中的关键字值大于 k，则结果只可能是当前结点或/及左子树中的结点，此时沿 left 指针继续查找。若当前结点中的关键字值小于 k，则结果只可能是当前结点或/及右子树中的结点，此时沿 right 指针继续查找。直到遇到空指针时为止。

（2）算法实现

void searchX( BTree root, int k )
{   BTree p = root, pmin1, pmin2;
    int min = MAX;                          //MAX 为能表示的整型最大值
    if ( p == NULL ) return;                //若为空树，则返回
    while( p != NULL )
    {   if ( p->data == k )                 //结果只包含一个结点
        {   min = 0;
            printf ( "差值绝对值 = %d 结点 = %d\n", min, p->data );
            return;
        }
        else if ( abs( p->data-k ) < min )  //出现差值绝对值更小的结点
        {   min = abs( p->data-k );
            pmin1 = pmin2 = p;
        }
        else if ( abs( p->data-k ) == min ) //出现另一个差值绝对值为 min 的结点
            pmin2 = p;
        if ( p->data > k )
            p = p->left;    //若当前结点的 data>k，则结果还可能在左子树中
        else
            p = p->right;   //若当前结点的 data<k，则结果还可能在右子树中
    }
    if ( pmin1->data != pmin2->data )
        printf ( "差值绝对值 = %d 结点 1 = %d 结点 2 = %d\n",
        min, pmin1->data, pmin2->data );
    else
        printf ( "差值绝对值 = %d 结点 = %d\n", min, pmin1->data );
    return;
}