首页 > 试题广场 >

设欲做一个实验来验证由随机InsertDelete操作对可

[问答题]
设欲做一个实验来验证由随机Insert/Delete操作对可能引起的问题。这里有一个策略,它不是完全随机的,但却是足够封闭的。通过插入从1到之间随机选出的N个元素来建立一棵具有N个元素的树。然后执行N2对先插入后删除的操作。假设存在例程RandomInteger(A,B),它返回一个在A和B之间(包括A,B)的均匀随机整数。
a. 解释如何生成在1和M之间的一个随机整数,该整数不在这棵树上(从而随机插入可以进行)。用N和来表示这个操作的运行时间。
b. 解释如何生成在1和M之间的一个随机整数,该整数已经存在与这棵树上,(从而删除可以随机进行)。这个操作的运行时间是多少?
c. 的最佳选择值是多少?为什么?

这道题你会答吗?花几分钟告诉大家答案吧!