2. 计算机
  3. 一棵查找二叉树，其结点A，B，C，D，E，F依次存放在一个起始地址为n(假定地址以字节为单位顺序编号)的连续区域中，每个结点占4个字节：前2个字节存放结点值，后2个字节依次放左指针、右指针。若该查找二叉树的根结点为万，则它的一种可能的前序遍历为(54)，相

一棵查找二叉树，其结点A，B，C，D，E，F依次存放在一个起始地址为n(假定地址以字节为单位顺序编号)的连续区域中，每个结点占4个字节：前2个字节存放结点值，后2个字节依次放左指针、右指针。若该查找二叉树的根结点为万，则它的一种可能的前序遍历为(54)，相

admin2019-03-04  39
问题 一棵查找二叉树，其结点A，B，C，D，E，F依次存放在一个起始地址为n(假定地址以字节为单位顺序编号)的连续区域中，每个结点占4个字节：前2个字节存放结点值，后2个字节依次放左指针、右指针。若该查找二叉树的根结点为万，则它的一种可能的前序遍历为(54)，相应的层次遍历为(55)。在以上两种遍历情况下，结点C的左指针LC的存放地址为(56)，　LC的内容为(57)。结点A的右指针凡的内容为(58)。
选项 A、n+4
B、n+8
C、n+12
D、n+16
答案B
解析 本题的出题方式比较新颖，很多考生在求第一空时就不知如何动手，因为他们都只看到了条件：“根结点为E”。但未挖掘“查找二叉树”给出的隐含条件。实际上此题最主要的条件就是“查找二叉树”。查找二叉树中每一个结点的左子树结点关键值小于结点本身，而右子树结点大于结点本身。题目中又给出条件“根结点为召”，所以比E小的结点：A，B，C，D都是E的左子树结点，而F是右子树结点，又因为前序遍历顺序为：根、左、右，所以前序遍历的第一个结点是E，最后一个结点是F。在(41)的　4个选项中，只有D才满足此条件。既然已经知道前序遍历序列为EACBDF，且知道二叉树的左子树是ACBD，再根据前序遍历的性质和A是左子树的根结点，可知C，召，D均是　A结点下的右子树(A的左子树为空)。同理，B和D分别是　C的左子树和右子树。最后所得的二叉树如图4-22所示。

根据图4-22，我们立即可得该二叉树的层次遍历序列为　EAFCBD。根据试题条件，结点A，B，C，D，E，F依次存放，且每个结点占4个字节(前2个字节存放结点值，后2个字节依次放左指针、右指针)，所以C的起始地址为n+8，LC的地址为n+10。根据图4-23所示，LC中应存放B的地址，由于起始地址为n，因此B的地址为n+4，LC的内容是n+4。结点A的右指针Ra中应存放C的地址，而C的地址为n+8，即Ra的内容是n+8。另外，我们也可以参考练习5的分析，来解答这道试题。
转载请注明原文地址:https://kaotiyun.com/show/sXTZ777K
本试题收录于： 数据库系统工程师上午基础知识考试题库软考中级分类
0

数据库系统工程师上午基础知识考试

软考中级

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