2、二叉树的性质:度为0的结点(即叶子结点)总是比度为2的结点多一个。
3、循环链表采用链式存储结构。线性表链式存储结构的特点是,用一组不连续的存储单元存储线性表中的各个元素。线性链表的存储单元是任意的,即各数据结点的存储序号可以连续、也可不连续。
4、若循环队列的存储空间为(1:m),在循环队列运转起来后,如果front<rear,则队列中的元素个数为rear-front;如果front>rear,则队列中的元素个数为rear-front+m。
5、设循环队列的存储空间为Q(1:m),当front=rear=m时,循环队列为空;当front=rear且不等于m时,循环队列可能为空,也可能为满。
6、二分查找:在最坏情况下,二分法查找需要比较log2n次。
7、双向链表有两个指针域,但属于线性结构。二叉树属于非线性结构,循环队列是队列的一种顺序存储结构。所有的线性结构都可以采用顺序存储结构。
8、当top=boton=NULL时,为栈空;当top=bottom且不等于NULL时,栈中存在一个元素,其他情况无法判断。
9、当front=rear=NULL时,为队空;当front=rear且不等于NULL时,队列中存在一个元素,其他情况无法判断。
10、最坏情况下时间复杂度:有序表的对分查找为O(log2n),寻找最大项为0(n-1),顺序查找为o(n),堆排序为O(nlog2n)。
11、一个非空线性结构应满足两个条件:①有且只有一个根节点;②每个节点最多有一个前件,也最多有一个后件。
12、多重链表具有两个及两个以上的指针域,但多重链表既可以表示线性结构,也可以表示非线性结构。
13、数据的存储结构直接决定数据的输入,而这会影响算法所执行的基本运算次数,影响算法的效率。
14、算法的有穷性指算法中的操作步骤为有限个,且每个步骤都能在有限时间内完成,即算法能在有限的时间内运行结束。
15、算法的时间复杂度是指执行算法所需要的计算工作量,算法空间复杂度指执行这个算法所需要的内存空间,算法的时间复杂度与空间复杂度没有直接关系。
16、如果额外空间量相对于问题规模(即输入数据所占的存储空间)来说是常数,即额外空间量不随问题规模的变化而变化,则称该算法是原地(in place)工作的。
17、带链栈的栈底指针在栈空时值为null,在栈不为空时指向栈底结点,值为其的地址,有可能改变。
18、线性表的链式存储结构与顺序存储结构相比,链式存储结构的优点:插入与删除运算效率高。