满二叉树---除最后一层外,其余层的结点都有两个子结点
完全二叉树---除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边
的若干结点,叶子结点只可能在层次最大的两层上出现。
满二叉树是完全二叉树,而完全二叉树不是满二叉树。完
全二叉树有两个性质:(1)具有 n 个结点的完全二叉树的
深度为[Log
2
n]+1(2)
二叉树遍历---不重复地访问各个结点。分为前序遍历(DLR-根左右)、中序遍历(LDR-左根
右)和后序遍历(LRD-左右根)
查找技术---顺序查找——对于长度为 n 的有序线性表,查找时需要比较 n 次
二分法查找——对于长度为 n 的有序线性表,查找时需要比较 log
2
n 次
排序技术---假设线性表的长度为 n,则冒泡排序和简单插入排序的比较次数(时间复杂
度)为 n(n-1)/2;希尔排序的比较次数为 O(n
1.5
);简单选择排
序的比较次数为 n(n-1)/2;堆排序的比较次数为 O(nlog
2
n).
习题 1
算法的时间复杂度是指( ),算法的空间复杂度是指( );
线性表、栈、队列、线性链表是(线性结构),树是(非线性结构);数据的存储结构是
指( );
队列是(先进先出),栈是(先进后出);
下列二叉树的遍历结果:前序遍历(ABDECF)、中序遍历( DBEAFC)、后续遍历
(DEBFCA)
在深 度 为 5 的满 二 叉 树 中 ,叶 子 结 点 的 个 数 为( 16 ) ; 设 树 T 的度为 4 , 其 中 度 为
1,2,3,4 的结点的个数分别为 4,2,1,1。则 T 中的叶子结点的个数为(8);对于长度
为 n 的有序线性表,顺序查找次数为(n),二分法查找次数为(log
2
n);一棵完全二叉树共
有 700 个结点,则在该二叉树中有(350)个叶子结点;一棵二叉树的中序遍历结果为
DBEAFC,前序遍历结果为 ABDECF,则后续遍历结果为(DEBFCA);冒泡排序的时间复
杂度为(n(n-1)/2);在一个容量为 15 的循环队列中,若头指针 front=6,尾指针 rear=9,则该循
环队列中共有(3)元素;
第二章 程序设计基础
结构化程序设计的三种结构---是顺序、选择和循环
对象---表示客观世界的任何实体
类---是具有共同属性和方法的对象的集合
实例---任何一个对象都是其对应类的实例
消息---一个实例和另一个实例之间传递的信息
继承---是指直接获得已有的性质和特征,而不必重复定义它们。例如子类继承父类
评论0
最新资源