Access疑难知识点.ppt

二叉树性质
4
2
3
1
6
7
8
9
10
11
12
13
14
15
5
性质1:二叉树的第i层上至多有2 i-1(i 1)个结点,满二叉树的第k层上有2 k-1个结点;
性质2:深度为h的二叉树中至多有2 h-1个结点,深度为h的满二叉树共有2 h-1个结点;
性质3:若在任意一棵二叉树中,有n0个叶子结点,有n2个度为2的结点,则:n0=n2+1;
性质4:具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分;
第1页/共18页
性质5:具有n个结点的完全二叉树的深度为[log2n]+1;
若完全二叉树有n个结点,那该二叉树有n-[n/2]个叶子结点,其中[n/2]表示对n/2取不大于n/2的最大整数。
第2页/共18页
真题
[]在深度为7的满二叉树中,度为2的结点个数为。
依据:
性质2:深度为h的二叉树中至多有2 h-1个结点,深度为h的满二叉树共有2 h-1个结点;
若完全二叉树有n个结点,那该二叉树有n-[n/2]个叶子结点,其中[n/2]表示对n/2取不大于n/2的最大整数。
性质3:若在任意一棵二叉树中,有n0个叶子结点,有n2个度为2的结点,则:n0=n2+1;
计算:
2 7-1=127 127-[127/2]=64 64-1
63
第3页/共18页
[]一棵二叉树第六层(根结点为第一层)的结点数最多为_____ 个。
依据:
性质1:二叉树的第i层上至多有2 i-1(i >=1)个结点,满二叉树的第k层上有2 k-1个结点;
计算:
2 6-1=32
32
第4页/共18页
[]某二叉树中度为2的结点有18个,则该二叉树中有____ 个叶子结点。
[]一棵二叉树中共有70个叶子结点与80个度为1的结点,则该二叉树中的总结点数为___。
A)219 B)221 C)229 D)231
依据:
性质3:若在任意一棵二叉树中,有n0个叶子结点,有n2个度为2的结点,则:n0=n2+1;
19
A
第5页/共18页
设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为______。
性质2:深度为h的二叉树中至多有2 h-1个结点,深度为h的满二叉树共有2 h-1个结点;
由于(2^9)-1=511 (2^10)-1=1023,推断出h=10
性质3:若在任意一棵二叉树中,有n0个叶子结点,有n2个度为2的结点,则:n0=n2+1;
设度为1的结点数为x1(1或者0),度为2的结点数x2,则度为0的结点数为x2+1,由此得到公式
1+x2+x2+1=699 2x2=697 (结点个数应为整数)
或者 0+x2+x2+1=699 2x2=698 x2=349
-> x0=350
350
第6页/共18页
[]某二叉树有5个度为2的结点,则该二叉树中的叶子结点数是( )
(A)10 (B)8 (C)6 (D)4
[]深度为5的满二叉树有叶子结点.
性质1:二叉树的第i层上至多有2 i-1(i >=1)个结点,满二叉树的第k层上有2 k-1个结点;
√
16
第7页/共18页
排序方法
插入排序
选择排序
交换排序
简单插入排序
希尔排序
简单选择排序
堆排序
冒泡排序
快速排序
排序
第8页/共18页
几种排序方法的效率比较(讨论最坏情况下的比较次数)
交换类排序:
冒泡排序 n(n-1)/2
快速排序 n(n-1)/2
插入类排序:
简单插入排序: n(n-1)/2
希尔排序:与增量序列有关
选择类排序:
简单选择排序:n(n-1)/2
堆排序:nlog2n
第9页/共18页
窗体上控件的事件顺序
焦点
一种接受通过鼠标或键盘操作或 SetFocus 方法进行的用户输入的能力。
获得焦点
将焦点移动到窗体上的控件上时(例如,通过打开包含一个或多个活动控件的窗体,或通过将焦点移至同一窗体上的另一控件上),Enter 和 GotFocus 事件会按以下顺序发生:
EnterGotFocus
打开窗体时,Enter 和 GotFocus 事件会在与打开窗体相关联的事件(如 Open、Activate 和 Current)之后发生,如下所示:
Open(窗体)  Activate(窗体)  Current(窗体)  Enter(控件) GotFocus(控件)
失去焦点
当焦点离开窗体上的控件时(例如,当关闭包含一个或多个活动控件的窗体时,或者当移至同一窗体上的另一控件时),Exit 和 LostFocus 事件会按以下顺序发生:
Exit