数据结构大题
- 格式：docx
- 大小：872.56 KB
- 文档页数：12
1 / 12
数据结构
简答：二叉树前四个性质的证明 4选1
性质1 在二叉树的第 i 层上至多有 2i －1个结点。(i 1) [证明用归纳法]
证明：当i=1时，只有根结点，2 i-1=2 0=1。
假设对所有j，i>j1，命题成立，即第j层上至多有2 j-1 个结点。
由归纳假设第i-1 层上至多有 2i －2个结点。
由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2* 2i －2= 2 i-1。
性质2 深度为 k 的二叉树至多有 2k -1个结点(k 1)。
证明：由性质1可见，深度为k的二叉树的最大结点数为
＝=＝20 + 21
+ … + 2k-1 = 2k -1
性质3 对任何一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0＝n2＋1.
证明：若度为1的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义，
n = n0 + n1 + n2 e = 2n2 + n1 = n - 1
因此，有 2n2 + n1 = n0 + n1 + n2 - 1
n2 = n0 - 1 n0 = n2 + 1
性质4 具有 n (n 0) 个结点的完全二叉树的深度为log2(n) ＋1
证明：
设完全二叉树的深度为 h，则根据性质2和完全二叉树的定义有
2h－1 - 1 < n 2h - 1或 2h－1 n < 2h
取对数 h－1 < log2n h，又h是整数，
因此有 h = log2(n) ＋1
性质5考计算
性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0, 1,
2, …, n-1，则有以下关系：
若i = 0, 则 i 无双亲
若i > 0, 则 i 的双亲为(i -1)/2
若2*i+1 < n, 则 i 的左子女为 2*i+1，若2*i+2 < n, 则 i 的右子女为2*i+2
若结点编号i为偶数，且i!=0,则左兄弟结点i-1.
若结点编号i为奇数，且i!=n-1,则右兄弟结点为i+1.
结点i 所在层次为log2(i+1) kii1(层上的最大结点数）第kii112 2 / 12
会画线索二叉树
二叉树的计数：
前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下：
求霍夫曼树：
举例霍夫曼树的构造过程 3 / 12
图、会转换表和矩阵
四个算法、
1， 求最小生成树
2， 求拓补排序结果
3， 为了简化算法, 假定在求关键路径之前已经对各顶点实现了拓扑排序, 并按拓扑有序的顺序对各顶点重新进行了编号。 4 / 12
4， 最短路径
边上权值非负情形的单源最短路径问题 5 / 12
折半查找的比较次数
折半查找算法实现
1.设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。
2.初始时，令 low=1,high=n,mid=(low+high)/2
让k与mid指向的记录比较
若k==r[mid].key，查找成功
若k 若k>r[mid].key，则low=mid+1 3.重复上述操作，直至low>high时，查找失败。 4. 构造二叉平衡（查找）树的方法： 在插入过程中，采用平衡旋转技术。 例如:依次插入的关键字为5, 4, 3, 8, 19,1,2，25，23 （1） 由于插入节点3使得树不再平衡，而3是插入在失去平衡的最小子树根节点5的左子树根节点4的左子树上。定义失去平衡的最小子树根节点为a，则该类不平衡可归纳为，在a的左子树根节点的左子树上插入导致的不平衡可使用单向右旋平衡处理，可以记为左左->右 6 / 12 7 / 12 8 / 12 B-树创建、删除 哈希表 9 / 12 希尔、快速、堆排序过程 实际上排序过程中不用每次交换枢轴记录和指针所指记录，当一趟排序算法结束时（即low=high）的位置是枢轴记录的最后位置。故先将枢轴记录保存在r[0]位置上，排序过程中只作r[low]或r[high]记录的移动，待一趟排序结束后再将枢轴记录移至正确位置上 堆排序( Heap sort ) 堆 ( Heap )设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从 1开始连续编号。若满足 Ki K2i && Ki K2i+1 或 Ki K2i && Ki K2i+1, 则称该关键字集合构成一个堆。 前者成为最小堆，后者称为最大堆。 10 / 12 堆排序 (Heap Sort) 利用堆及其运算, 可以很容易地实现选择排序的思路。 堆排序分为两个步骤 ① 根据初始输入数据，利用堆的调整算法 HeapAdjust( ) 形成初始堆; ② 通过一系列的对象交换和重新调整堆进行排序。 11 / 12 12 / 12
