开放教育数据结构历年真题 09年自考《数据结构》各章要点二[9]

09年自考《数据结构》各章要点二[9]  

　　第九章 查找

　　查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表 否则称之为静态查找表

　　衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL)

　　线性表查找的方法

　　·顺序查找 逐个查找 ASL=(n+ )/

　　·二分查找 取中点int(n/ )比较 若小就比左区间 大就比右区间 用二叉判定树表示 ASL=(∑(每层结点数*层数))/N

　　·分块查找 要求 分块有序 将表分成若干块内部不一定有序 并抽取各块中的最大关键字及其位置建立有序索引表

　　二叉排序树(BST)定义是二叉排序树是空树或者满足如下性质的二叉树

　　 ·若它的左子树非空 则左子树上所有结点的值均小于根结点的值

　　·若它的右子树非空 则右子树上所有结点的值均大于根结点的值

　　·左 右子树本身又是一棵二叉排序树

　　二叉排序树的插入 建立 删除的算法平均时间性能是O(nlog n)

　　二叉排序树的删除操作可分三种情况进行处理

　　·*P是叶子 则直接删除*P 即将*P的双亲*parent中指向*P的指针域置空即可

　　·*P只有一个孩子*child 此时只需将*child和*p的双亲直接连接就可删去*p

　　·*p有两个孩子 则先将*p结点的中序后继结点的数据到*p 删除中序后继结点

　　关于B 树(多路平衡查找树) 它适合在磁盘等直接存取设备上组织动态的查找表 是一种外查找算法 建立的方式是从下向上拱起