数据结构和算法|集9

下面是在GATE CS考试中提出的问题。

1在包含n个元素的堆中，最小的元素位于根，第七个最小的元素可以及时找到（GATE CS 2003） a） Θ（n对数n） b） Θ（n） c） Θ（对数n） d） Θ（1）

答复（d） 第七小元素必须位于前7个级别。前7个级别的任何二进制堆中的节点总数最多为1+2+4+8+16+32+64，这是一个常量。因此，我们总能在Θ（1）时间内找到第七小元素。

2.假设数字7、5、1、8、3、6、0、9、4、2按该顺序插入到最初为空的二叉搜索树中。二叉搜索树使用自然数的常规排序。结果树的顺序遍历顺序是什么？（盖特CS 2003） a） 7510324689 b） 02431615987 c） 0123456789 d） 9864230157

答复（c） 按顺序，BST的遍历以递增的顺序给出元素。所以答案c毫无疑问是正确的。

3.让我们做一个大小为n>=1的堆栈。从空堆栈开始，假设我们按顺序推送前n个自然数，然后执行n个pop操作。假设Push和Pop操作各花费X秒，在一个这样的堆栈操作结束和下一个操作开始之间花费Y秒。对于m>=1，将m的堆栈寿命定义为从推送结束（m）到从S中移除m的pop操作开始所经过的时间。该堆栈元素的平均堆栈寿命为（GATE CS 2003） a） n（X+Y） b） 3Y+2X c） n（X+Y）-X d） Y+2X

答复（c） 通过举几个例子，我们很容易得出结果。

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

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