Skip to content
22考研征询 | 码哥（jnumagekaoyan）
对有序表和无序表的次序查找成功的均匀查找长度相同，都为：
而无序表的查找失利的均匀查找长度为n+1（要查找到最终一个元素），有序表的查找失利的均匀查找长度为：
查找失利：asl失利=［log2n］+1（减半查找断定树的树高）
次序表次序查找、减半查找、分块查找的3种查找办法比照：
?就均匀查找长度而言，减半查找的均匀查找长度取小，分块查找次之，次序查找最大。
?就表的规划而言，次序查找对有序表、无序表均适用，减半查找仅适用于有序表，而分块查找需求表中元素至少是分块有序的。
?就表的存储规划而言，次序查找和分块查找可以适用于次序表和链表两种存储规划,而减半查找只适用于以次序表作为存储规划的表。
?分块查找归纳了次序查找和减半查找的利益，既能较快速地查找，又能习气动态改变的需求。
对长度为2k-1的有序表进行减半查找，在成功查找时，最少需要多少次要害词比照?最多需要多少次要害词比照?查找失利时的均匀比照次数是多少?
当查找的记载正优点于中心方位时，要害词比照次数最少，所以减半查找在成功查找时最少需要1次要害词比照。
减半查找在成功查找时最多要害词比照次数为断定树的高度，即?log2(2k-1+1) = k。减半查找在不成功查找时比照进程都落在外部节点中，将断定树当作是一棵满二叉树，一切外部节点的高度为k+1，其要害词比照次数为k，所以查找失利时的均匀比照次数是k 次。
查找失利：查找失利时的比照次数/（mod后的数字）
?散列表饱满的程度，即装填因子的巨细。（装填因子是指散列表中已存入的记载数ｎ与散列表长度ｍ的比值，单独凭n或m不构成影响asl的要素）
?在b+树中，具有n个要害词的结点只富含n棵子树，即每个要害词对应一棵子树;而在b树中，具有n个要害词的结点富含n+1棵子树。
?在b+树中，每个结点(非根内部结点)的要害词个数n的规模是［m/2］≤n≤m (根结点:1≤n≤m);在b树中，每个结点(非根内部结点)的要害词个数n的规模是［m/2］ -1≤n≤m-1 (根结点: l≤n≤m-1)。
?在b+树中，叶结点包括信息，一切非叶结点仅起索引作用，非叶结点中的每个索引项只
富含对应子树的最大体害词和指向该子树的指针，不富含该要害词对应记载的存储地址。
?在b+树中，叶结点包括了悉数要害词，即在非叶结点中呈现的要害词也会呈如今叶结点中;而在b树中，叶结点包括的要害词和其他结点包括的要害词是不重复的。
?b+树查找时是从上到下查找；b-树则是从下往上查找（中序遍历）。
简述平衡二叉树中刺进新节点致使不平衡进行调整的4种形状。
在平衡二叉树中刺进新节点可致使使不平衡，调整成平衡二叉树的4种形状如下。
ll型调整:在节点的左子树的左子树上刺进新节点致使不平衡。
rr型调整:在节点的右子树的右子树上刺进新节点致使不平衡。
lr型调整:在节点的左子树的右子树上刺进新节点致使不平衡。
rl型调整:在节点的右子树的左子树上刺进新节点致使不平衡。
时刻凌乱度为o(nlogn)的办法有：快速排序、堆排序和归并排序?
时刻凌乱度为o(n2)的有：直接刺进排序、起泡排序和简略选择排序?
时刻凌乱度为o(d(n+r))的排序办法只需基数排序。
当待排记载序列按要害词次序有序时，直接刺进排序和起泡排序能抵达o(n)的时刻杂度;而关于快速排序而言，这是最不好的情况，此时的时刻功能蜕化为o(n2)，因而 是大约尽量避免的情况。?
另外，简略选择排序、堆排序和归并排序的时刻功能不随记载序列中要害词的分布而改动。
?一切的简略排序办法(包括：直接刺进、起泡和简略选择)和堆排序的空间凌乱度为o(1)；
?归并排序所需辅佐空间最多，其空间凌乱度为o(n);
?平稳的排序办法指的是，关于两个要害词相等的记载，它们在序列中的相对方位，在排序之前和经过排序之后，没有改动。
?关于不平稳的排序办法，只需能举出一个实例阐明即可。
?快速排序、简略选择排序、堆排序和希尔排序是不平稳的排序办法。
直接刺进排序算法是平稳的，更合适于初始元素根柢有序的情况。若选用减半查找而不是次序查找待刺进元素的刺进方位时，可削减元素比照的次数，但移动元素的次数没有削减;在选用次序查找待刺进元素的刺进方位时也适用于链式存储规划。
希尔排序算法是不平稳的;元素的总比照次数和移动次数都比直接刺进排序时要少，n越大时，作用越显着;增量序列d可以有不一样的取法，但有两个一起的特征，即最终一个增量有必要是1，增量序列中的值没有除1之外的公因子;希尔排序不适用于链式存储规划。
以小根堆为例，堆的特征是双亲节点的要害词必定小于等于孩子节点的要害词，而两个孩子节点的要害词没有次序规则。而二叉排序树中，每个双亲节点的要害词均大于左子树节点的要害词，每个双亲节点的要害词均小于右子树节点的要害词，也就是说，每个双亲节点的左、右孩子的要害词有次序联络。
堆排序是一种不平稳的排序办法。因为在堆的调整进程中，要害词进行比照和交流所走的是该节点到叶子节点的一条途径，因而对相同的要害词而言，就可以呈现排在后边的要害词被交流到前面来的情况。
将快速排序算法改为非递归算法时一般运用一个栈，若把栈换为行列会对究竟排序成果有啥影响?
在实施快速排序算法时，用栈保存每趟快速排序区别后左、右子区段的首、尾地址，其意图是为了在处置子区段未排序子序列时可以晓得其规模，这样才干对该子序列进行排序(排序进程中可以发生新的左、右区段)，但这与处置子序列的先后次序没啥联络，而只是起存储作用。因而，用行列相同可以存储子区段的首、尾地址，即可以替代栈的作用。在实施快速排序算法时，把栈换为行列对究竟排序成果不会发生任何影响。
Categories : Categories : 艺术考研资讯
|京ICP备18012533号-384