数据结构和算法|集23

在2005门CS考试中提出了以下问题。

1.在索引数据库关系时，与二叉搜索树相比，以下哪一项是首选B-树的关键因素？ （a） 数据库关系有大量记录 （b） 数据库关系按主键排序 （c） B-树比二进制搜索树需要更少的内存 （d） 磁盘的数据传输是以块为单位的。

答复（d） 磁盘块包含相当多的密钥。与每个节点只包含一个键的BST不同，B-Tree被设计为包含大量键，因此树的高度很小。

2.从4个不同的键中可以创建多少个不同的二进制搜索树？ （a） 五, （b） 14 （c） 24 （d） 42

答复（b）

以下是列举这些BST的系统方法。考虑所有可能的二叉搜索树，其中每个元素在根上。如果有n个节点，那么对于每个根节点的选择，都有n–1个非根节点，这些非根节点必须划分为小于所选根的节点和大于所选根的节点。

假设节点i被选为根。然后是比i小的i–1节点和比i大的n–i节点。对于这两组节点中的每一组，都有一定数量的可能子树。

设t（n）为具有n个节点的BST总数。根为i的BST总数为t（i–1）t（n–i）。这两项相乘是因为左右子树中的排列是独立的。也就是说，对于左树中的每个排列和右树中的每个排列，都会得到一个BST，其中i是根。

求和i给出了具有n个节点的二叉搜索树的总数。

基本情况是t（0）=1和t（1）=1，即有一个空BST，有一个BST和一个节点。

3.在一个完整的k元树中，每个内部节点都有k个子节点。这样一棵内部有n个节点的树的叶子数是： （a） nk （b） （n-1）k+1 （c） n（k-1）+1 （d） n（k-1）

答复（c）

4） 假设T（n）=2T（n/2）+n，T（0）=T（1）=1 以下哪一项是错误的。 a） T（n）=O（n^2） b） T（n）=Θ（nLogn） c） T（n）=&欧姆；（n） ^2. ) d） T（n）=O（nLogn）

答复（c） 给定的递推关系可以用 主定理 它位于主定理的情况2。或者，如果你还记得合并排序或最佳情况快速排序的递归关系，你可以猜测T（n）的值。

T（n）=Θ（nLogn）

根据定义 大O符号 我们可以说。 Θ（nLogn）=O（nLogn）=O（n^2）

Θ（nLogn）可以等于欧姆；（n） 或&欧姆；（nLogn），但不是&ohm；（n^2）

请看 门角 所有上一年的论文/解决方案/解释、教学大纲、重要日期、笔记等。

如果您发现任何答案/解释不正确，或者您想分享有关上述主题的更多信息，请发表评论。