文档介绍：数据结构基础知识
第1页，本讲稿共33页
什么是数据结构？
数据元素相互之间的关系称为数据结构。其中数据元素是个广义概念，是所有能输入到计算机中并被计算机程序处理的符号的总称。
第2页，本讲稿共33页
四大类基本数据结 B. b, c, a, e, d
C. a, e, c, b, d D. d, c, e, b, a
(NOIP2010)元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的可能是(    )。                           
C
ACD
第14页，本讲稿共33页
树
树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如下图的树，其度为3。
树的深度——组成该树各结点的最大层次，如下图的树，其深度为4。
第15页，本讲稿共33页
二叉树
二叉树是树的一种重要形态，只有左、右子树且顺序不能颠倒。逻辑上二叉树有五种基本形态：
(1)空二叉树——(a)；
(2)只有一个根结点的二叉树——(b)；
(3)右子树为空的二叉树——(c)；
(4)左子树为空的二叉树——(d)；
(5)完全二叉树——(e)
第16页，本讲稿共33页
关于二叉树的两个重要概念
满二叉树，一棵深度为K的二叉树有2K-1个结点，则称为满二叉树。
第17页，本讲稿共33页
关于二叉树的两个重要概念
和满二叉树对照，只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树，称为完全二叉树。
结论：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
第18页，本讲稿共33页
历届试题
（NOIp2005）.完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为（ ）。
A. 2 * N B. 2 * N - 1 C. 2 * N + 1
D. 2 * N - 2 E. 2 * N + 2
（NOIp2008）．完全二叉树共有2*N-1个结点，则它的叶节点数是（ ）。
A. N-1 B. 2*N C. N
D. 2N-1 E. N/2
（NOIp2006）．高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为 n-1 的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有 2381 个结点， 则该树的树高为（ ）。
A. 10 B. 11 C. 12 D. 13 E. 210 – 1
E
C
B
第19页，本讲稿共33页
历届试题
(NOIP2009)一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：( )
A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+1
(NOIP2010)完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（   ）号位置。          +1                      D.(k+1)/2
D
C
第20页，本讲稿共33页
树的遍历（访问）
先序遍历
中序遍历
后序遍历
第21页，本讲稿共33页
历届试题
（NOIp2005）.二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知E的父结点可能是（ ）。
A. A B. B C. C D. D E. F
（NOIp2006）. 已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ ）
A. 3 2 1 4 6 5 B. 3 2 1 5 4 6
C. 2 3 1 5 4 6 D. 2 3 1 4 6 5
(NOIP2010)一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（   ）。 A．0