>>>>点击进入了解程序员培训视频

 >>>>点击进入了解程序员在线辅导

 >>>>点击进入了解程序员考试教材

       程序员考试是全国软考的初级考试，通过程序员考试的合格人员具有助理工程师（或技术员）的实际工作能力和业务水平。希赛软考网整理了一些程序员考试历年真题，供大家练习。

   试题三

   阅读以下说明、C函数和问题，将解答填入答题纸的对应栏内。

   【说明】

   二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：

   ●若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；

   ●若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；

   ●左、右子树本身就是二叉查找树。

   设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：

   typedefstructBiTnode{

   intkey_value;/*结点的键值，为非负整数*/

   structBiTnode*left,*right;/*结点的左、右子树指针*/

   }*BSTree;

   函数find_key（root,key）的功能是用递归方式在给定的二叉查找树（root指向根结点）中查找键值为key的结点并返回结点的指针；若找不到，则返回空指针。

   【函数】

   BSTreefind_key（BSTreeroot,intkey）

   {

   if（（1））

   returnNULL;

   else

   if（key==root->key_value）

   return（2）;

   elseif（keykey_value）

   return（3）;

   else

   return（4）;

   }

  【问题1】

   请将函数find_key中应填入（1）~（4）处的字句写在答题纸的对应栏内。

   【问题2】

   若某二叉查找树中有n个结点，则查找一个给定关键字时，需要比较的结点个数取决于（5）.

   试题三分析

   本题考查数据结构的应用、指针和递归程序设计。

   根据二叉查找树的定义，在一棵二叉查找树上进行查找时，首先用给定的关键字与树根结点的关键字比较，若相等，则查找成功；若给定的关键字小于树根结点的关键字，则接下来到左子树上进行查找，否则接下来到右子树上进行查找。如果在给定的二叉查找树上不存在与给定关键字相同的结点，则必然进入某结点的空的子树时结束查找。因此，空（1）处填入"!root"表明进入了空树；空（2）处填入"root"表明返回结点的指针；空（3）处填入"find_key（root→left,key）"表明下一步到左子树上继续查找；空（4）处填入"find_key（root→right,key）"表明下一步到右子树上继续查找。

   显然，在二叉排序树上进行查找时，若成功，则查找过程是走了一条从根结点到达所找结点的路径。例如，在下图所示的二叉排序树中查找62,则依次与46、54、101和62作了比较。因此，在树中查找一个关键字时，需要比较的结点个数取决于该关键字对应结点在该二叉查找树所在层次（数）或位置。

   试题三答案

   （1）！root,或root=0,或root==NULL

   （2）root

   （3）find_key（root→left,key）

   （4）find_key（root→right,key）

   （5）该关键字对应结点在该二叉查找树所在层次（数）或位置，或者该二叉树中从根结点到该关键字对应结点的路径长度

     希赛软考网，拥有十四年软考培训经验，希赛网一直坚持自主研发，将丰富的软考培训经验有效融入教程研发过程，自成体系的软考在线题库（软考历年真题）、软考培训教材和软考视频教程，多样的培训方式包括在线辅导、面授、和，使考生的学习更具系统性，辅导更具针对性。采用全程督学机制，，软考平均通过率在全国。

 相关推荐

 2016年希赛教材大放送 

   程序员教程

   程序员考试考前串讲

   程序员考试知识点分析与真题详解（第4版 ）