2. 计算机
  3. 阅读下列说明和流程图，将应填入(n)的语句写在对应栏内。 【流程图说明】 下面的流程(如图1所示)用N-S盒图形式描述了在一棵二叉树排序中查找元素的过程，节点有3个成员：data, left和right。其查找的方法是：首先与树的根节点的元素值

阅读下列说明和流程图，将应填入(n)的语句写在对应栏内。 【流程图说明】 下面的流程(如图1所示)用N-S盒图形式描述了在一棵二叉树排序中查找元素的过程，节点有3个成员：data, left和right。其查找的方法是：首先与树的根节点的元素值

admin2009-02-15  89
问题 阅读下列说明和流程图，将应填入(n)的语句写在对应栏内。
   【流程图说明】
   下面的流程(如图1所示)用N-S盒图形式描述了在一棵二叉树排序中查找元素的过程，节点有3个成员：data, left和right。其查找的方法是：首先与树的根节点的元素值进行比较：若相等则找到，返回此结点的地址；若要查找的元素小于根节点的元素值，则指针指向此结点的左子树，继续查找；若要查找的元素大于根节点的元素值，则指针指向此结点的右子树，继续查找。直到指针为空，表示此树中不存在所要查找的元素。
  【算法说明】
  【流程图】
   将上题的排序二叉树中查找元素的过程用递归的方法实现。其中NODE是自定义类型：

typedef struct node {
       int data;
       struct node * left;
       struct node * right;
   }NODE;
  【算法】
   NODE * SearchSortTree(NODE * tree, int e)
   {
       if(tree!=NULL)
       {
           if(tree-＞data＜e)
                 (4);     //小于查找左子树
           else if(tree-＞data＜e)
                 (5);    　//大于查找左子树
           else return tree;
       }
      return tree;
   }
选项
答案(1)p=p-＞left (2)ptr=p-＞right (3)return P (4) return SearchSortTree(tree-＞left ) (5)return SearchSortTree(tree-＞right)
解析 所谓二叉排序树，指的是一棵为空的二叉树，或者是一棵具有如下特性的非空二叉树：
   ①若它的左子树非空，则左子树上所有结点的值均小于根结点的值。②若它的右子树非空，则右子树上所有结点的值均大干根结点的值。③左、右子树本身又各是一棵二叉排序树。
   先来分析流程图。在流程图中只使用一个变量p，并作为循环变量来控制循环，所以循环体中必须修改这个值。当进入循环时，首先判断p是不是为空和该结点是不是要找的结点，如果这两个条件有一个满足就退出循环，返回prt，(如果是空，则返回NULL，说明查询失败；否则返回键值所在结点的指针。)因此(3)空处应当填写“return p”。如果两个条件都不满足，就用查找键值e与当前结点的关键字进行比较，小的话，将指针p指向左子树继续查找，大的话将指针P指向右子树继续查找。于是，(1)空处应当填写“p=p-＞left”，(2)空处应当填写“p=p-＞right”。
   再来分析程序。虽然是递归算法，但实现思路和非递归是一样。首先用查找键值e与树根结点的关键字比较，如果值小的话，就在左子树中查找(即返回在左子树中查找结果)；如果值大的话在右子树中查找(即返回在右子树中查找结果)；如果相等的活就返回树根指针。因此(4)、(5)空分别应填写“return SearehSortTree(tree-＞left)”和“return SearehSoaTree(tree-＞right)”。
转载请注明原文地址:https://kaotiyun.com/show/lbjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)