数据结构-2014-2-期末-2（补充）1

数据结构知识点总结 本文旨在总结数据结构相关知识点，涵盖图论、树、堆、排序算法、散列表、红黑树、左式堆、K-选取等方面。 一、图论和树 1. BFS、DFS的复杂度可能不是O(N+E)，因为 BFS、DFS 在遍历图或树时需要考虑图或树的结构，可能需要更多的时间。 2. PFS 每次调用 priorUpdata()，总复杂度 O(n)，因为 PFS 需要对所有节点进行更新。 3. Floyd 建堆，每次同层之间下滤顺序打乱，不影响复杂度和正确性，因为 Floyd 算法可以handle 打乱的顺序。 二、堆和排序算法 1. 将 0..2^d-1 插入 AVL树一定高度为 d，因为 AVL树是一种自平衡的二叉搜索树，高度与插入元素个数有关。 2. 两棵 key 值顺序一样的 BBST 经过 O(logN) 次 zig、zag 就能互相转化，因为 BBST 是一种自平衡的二叉搜索树，可以通过旋转来维持平衡。 3. 将 2014 个数插入 splay，第一次访问经过 2013 次旋转，则是单调插入的，因为 splay.Tree 是一种自适应的二叉搜索树，可以根据访问频率来调整结构。 4. 跳转表期望高度 O(logN)，因为跳转表是一种基于概率的查找结构，高度与插入元素个数有关。 5. 多叉堆比二叉堆插入慢，删除快，因为多叉堆需要更多的比较和交换操作。 6. 字符集变大，概率平均，则 bc 表比 next 表好，因为 bc 表是一种基于概率的查找结构，可以更好地适应大规模数据。 7. shell 排序若将插入排序改成归并排序，效率变快，因为 shell 排序可以通过分治策略来提高效率。 三、散列表 1. 有若干数字，遵循模 13、双向平方、懒惰删除，填写每一次操作后的散列表，散列表是一种基于哈希函数的查找结构，可以用于快速查找和插入元素。 2. 最后问询问一个数字会发生什么情况，因为所有可用的都满了会产生死循环，散列表需要避免这种情况。 四、红黑树 1. 依次插入 [0,N)，写出 N=9 的红黑树，红黑树是一种自平衡的二叉搜索树，可以维持平衡状态。 2. 写出树高 H 和 N 的通项公式，红黑树的高度与插入元素个数有关，可以通过公式来计算高度。 五、左式堆 1. 0..2014，问左子树至少有几个节点，右子树最高多高，左式堆是一种特殊的堆结构，可以用于快速查找和插入元素。 2. 画出示意图，左式堆可以通过分治策略来构建。 3. 按什么顺序插入 0..2014，能成为画的样子，左式堆可以通过特定的插入顺序来维持结构。 六、K-选取 1. 将 1983 个数字取前三大，最少比较多少次，K-选取可以通过锦标赛模型来解决问题。 2.锦标赛模型可以减少比较次数，提高效率。 七、shell 排序 1. 因为取 1,2,4,8,...,2^n 会产生最坏情况，因此每次取到偶数就 -1 或 +1，问能不能避免最坏情况，shell 排序可以通过取不同的步长来避免最坏情况。 2. 每次遇偶数 -1 或 +1 都可以避免最坏情况，因为 shell 排序可以通过动态调整步长来适应不同的数据分布。