2001年度程序员级上午试题详解

"2001年度程序员级上午试题" 本节试题涵盖了树的转换、二叉树、数组的存储和语法分析等多个方面的知识点。 首先，在树的转换部分，试题中提到任一棵树均可唯一地转换成与它对应的二叉树。在树转换成的二叉树中，结点N的左子女是N在原树里对应结点的最左子结点，而N的右子女是原树里对应结点的最右兄弟。 在二叉树的识别部分，试题中给出了三种不同的二叉树，分别是查找树、满二叉树和平衡树但不是满二叉树。查找树是一种特殊的二叉树，其中每个结点的关键字都大于其左子树的关键字，小于其右子树的关键字。满二叉树是一种特殊的二叉树，其中每个结点都有两个子女，且所有叶子结点都在同一层次上。平衡树但不是满二叉树是一种特殊的二叉树，其中每个结点的左子树和右子树的高度之差不超过一。 在数组的存储部分，试题中给出了一个二维数组X的存储方法。数组X的行下标范围是0～5，列下标范围是1～8，每个数组元素占六个字节。因此，该数组的体积为288个字节。若已知X的最后一个元素的起始字节地址为382，则X的首地址（即第一个元素的起始字节地址）为94。 在语法分析部分，试题中提到了自底向上分析和自顶向下分析两种方法。自底向上分析方法自左向右扫描输入符号串，通过归约分析其语法是否正确。例如，算符优先分析法就是一种自底向上的分析方法，通过对输入符号串的分析来判断其语法是否正确。自顶向下分析方法从文法的开始符号出发，判断其能否派生出输入符号串。采用自顶向下分析方法时，要求文法不含有左递归。 本节试题涵盖了树的转换、二叉树、数组的存储和语法分析等多个方面的知识点，对于程序员来说非常重要。