计算机考研专业课复习科目包括数据结构、操作系统、计算机组成原理、计算机网络四门课程。其中数据结构这一科目兼具理论与实践，要求同学们在复习过程中不仅要对教材的基本概念进行记忆，同时还要结合知识点掌握相应的实际操作知识。为帮助同学们在计算机专业课复习上卓有成效，中公考研将为同学们整理全面的考点梳理，今天为大家带来的是数据结构的相关内容，请同学们适当参考，结合自身实际在全面复习的基础上进行重点理解记忆。

　　证明：采用数学归纳法，先证(2)和(3)。

　　设n个结点的完全二叉树如图所示。

　　i=1时,显然 i 结点的左子编号为2，i的右子编号为2+1=3，除非2>n , 3>n 。

　　设对i结点，命题(2)、(3)成立，即Lchild(i)=2i，Rchild(i)=2i+1。根据按层编号规则，i+1时有：

　　Lchild(i+1)=(2i+1)+1=2(i+1)，除非2(i+1)>n,

　　Rchild(i+1)=(2i+1)+1+1=2(i+1)+1，除非2(i+1)+1>n，

　　故(2)、(3)得证。

　　再证(1)，它可看作是(2)、(3)的推广。

　　因Lchild(j)=2j，所以Parent(2j)=j,令2j=i，有 Parent(i)=i/2= (i/2为正整数);

　　又：Rchild(j)=2j+1，所以Parent(2j+1)=j，令2j+1=i (i=3,5,7…)，有:

　　Parent(i)=(i-1)/2= ，证毕。

　　n

　　2i

　　2i+1

　　1

　　2

　　3

　　2i+1+1

　　2i+1+2

　　i

　　i+1

　　例题：一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )【西安交通大学 1996 三、2 (3分)】

　　A. 250 B. 500 C.254 D.505 E.以上答案都不对 501

　　例题1：由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。

　　例题2：高度为K的完全二叉树至少有_ __个叶子结点。(刚好第K上只有一个叶子时，高度为K，N= -1+1= 例题3：在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是

　　用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条件是ëlog2sû=ëlog2tû。