算法设计⑴设计顺序查找算法，将哨兵设在下标高端。【解答】将哨兵设置在下标高端，表示从数组的低端开始查找，在查找不成功的情况下，算法自动在哨兵 处终止。具体算法如下：咂序查找算法Search|ini Search(intr[ ]tintn,mt k)(i-l;r[nFl]=k;while(r[i]l=k)i++;return i%(n+1),⑵编写算法求给定结点在二叉排序树中所在的层数。【解答】根据题目要求采用递归方法，从根结点开始查找结点p,若待查结点是根结点，则深度为到左子树(或右子树)上去找，查找深度加1。具体算法如下：结点疫二又排序材的层數算法Levelint L-e^l (BiNode *root. BiNode *p)帕iNode谙筆见二查排序树的结点结构{if(Ip)returnQ;if (p=p口Dt)return UelseifCp->data<r□olr>data)return Level (root->lchildTp) +1;elsereturnLewd(rool-^child,p)+l;}⑶编写算法，在二叉排序树上找岀任意两个不同结点的最近公共祖先。【解答】设两个结点分别为A和B,根据题目要求分下面情况讨论：⑴ 若A为根结点，则A为公共祖先；⑵若A->datadata且root->datadata，root为公共祖先；⑶ 若A->datadata且B->datadata，则到左子树查找；⑷若A->data>root->data且B->data>root->data，则到右子树查找。具体算法如下：求公共祖先算法AncestorBiNode ^Ancestor®iNode*A,BiNode半B,BiNode *root){if(Irool)return NULL;else if((A->data<root~>data) && (root~>data<B~>data) ||(A~>data==root->data))return root;else if((A->data>ro>data) &&(B'>data>root->data))return Ancestor(A,B,root->rchdd);else returnAncestor(A,Bproot™>lchild)P}⑷设计算法判定一棵二叉树是否为二叉排序树。【解答】对二叉排序树来讲，其中序遍历序列为一个递增序列。因此，对给定二叉树进行中序遍历，如果始终能够保证前一个值比后一个值小，则说明该二叉树是二叉排序树。具体算法如下：判断是否为二又排序树算法SortBiTree|________intSortBiTreetBiNode+roo0快记录当前结点的前驰结点值 >祕值为■間(if('root)return1;else (bl= SortBiTree(root^Mchild);if (Ibl [ |pre>=root->datajreturn0;pr&=root->date;b2=S orLBiTr ee (ro ot->r child);returnb2;}}I学习自测及答案