数据结构与算法.doc

文档介绍：存储结构:顺序、链式、索引P11
数据结构: 逻辑结构: 线性结构:栈(先进后出)、队列(先进先出)带链的栈带链的队列
非线性结构:树:二叉树满二叉树
完全二叉树
树的遍历:二叉树是非线性结构,树的遍历指树中各结点的访问顺序。在先左后右的原则下,根据访问根结点的次序,二叉树的遍历分为:前中后序遍历。P38
树:结点,根结点,叶子结点。结点的度(结点拥有的后件个数),树的度(结点中最大的度)树的深度(树的最大层次)P27
二叉树基本性质:1、在二叉树的第K层上,最多有2K-1 个结点
2、深度为M的二叉树,最多有2M-1个结点
3、具有N个结点的二叉树,其深度至少为【log2n】+1
4、在任意一个二叉树中,叶子结点总是比度为2的结点多一个
查找技术:有序表顺序存储二分法查找最多log2n次
有序表链式存储顺序查找 n次
无序表顺序查找
排序技术:交换类:n(n-1)/2 冒泡排序法、快速排序法
插入类:简单插入排序n(n-1)/2;希尔排序O()
选择类:简单选择排序n(n-1)/2;堆排序法O(nlog2n)
算法:解题方案的准确而完整的描述。
控制结构:顺序、选择、循环
时间复杂度:执行算法的运算次数
空间复杂度:执行算法所需内存空间
下列关于栈叙述正确的是;(p17)
A) 栈顶元素最先能被删除
B)栈顶元素最后才能被删除
C)栈底元素永远不能被删除
D)以上三种说法都不对
(2)下列叙述中正确的是
A)有一个以上根结点的数据结构不一定是非线性结构
B)只有一个根结点的数据结构不一定是线性结构
C)循环链表是非线性结构
D)双向链表是非线性结构
(3)某二叉树共有7个结点,其中叶子结点只有1个,则该二叉树的深度为(假设根结点在第1层)
A)3
B)4
C)6
D)7
(1)下列叙述中正确的是
A)对长度为n的有序链表进行查找,最坏情况下需要的比较次数为n
B)对长度为n的有序链表进行对分查找,最坏情况下需要的比较次数为(n/2)
C)对长度为n的有序链表进行对分查找,最坏情况下需要的比较次数为(log2n)
D)对长度为n的有序链表进行对分查找,最坏情况下需要的比较次数为