|
对含有n个互不相同元素的集合同时找最大元和最小元至少需进行多少次比较? 若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找试在下述两种情况下分别讨论两者在等概率时的平均查找长度 ()查找不成功即表中无关键字等于给定值K的记录 ()查找成功即表中有关键字等于给定值K的记录 画出对长度为的有序的顺序表进行二分查找的判定树并指出在等概率时查找成功的平均查找长度以及查找失败时所需的最多的关键字比较次数 为什么有序的单链表不能进行折半查找? 设有序表为(abcefgijkpq)请分别画出对给定值bg和n进行折半查找的过程 将(for case while class protected virtual public private do template const if int)中的关键字依次插入初态为空的二叉排序树中请画出所得到的树T然后画出删去for之后的二叉排序树T若再将for 插入T中得到的二叉排序树T是否与T相同?最后给出T的先序中序和后序序列 对给定的关键字集合以不同的次序插入初始为空的树中是否有可能得到同一棵二叉排序树? 将二叉排序树T的先序序列中的关键字依次插入一空树中所得和二叉排序树T与T否相同?为什么? 设二叉排序树中关键字由至的整数构成现要查找关键字为的结点下述关键字序列哪一个不可能是在二叉排序树上查找到的序列? (a) (b) ; (c) ; (d) 设二叉排序树中关键字互不相同则其中最小元必无左孩子最大元必无右孩子此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗? 在一棵m阶的B树中当将一关键字插入某结点而引起该结点的分裂时此结点原有多少个关键字?若删去某结点中的一个关键字而导致结点合并时该结点中原有几个关键字? 在一棵B树中空指针数总是比关键字数多一个此说法是否正确?请问包含个关键字的阶B树(即树)最多有几个结点?最少有几个结点?画出这两种情况的B树 从空树开始依次输入画出建立树的过程并画出删除和后的B树状态 画出依次插入zvopwy到图(h)所示的阶B树的过程 在含有n个关键字的m阶B树中进行查找至多读盘多少次?完全平衡的二叉排序树的读盘次数大约比它大多少倍? 为什么在内存中使用的B树通常是阶的而不使用更高阶的B树? 为什么二叉排序树长高时新结点总是一个叶子而B树长高时新结点总是根?哪一种长高能保证树平衡? 已知关键字序列为(PALLAPPAMMAPPATPETSETSATTATBAT)试为它们设计一个散列函数将其映射到区间[n]上要求碰撞尽可能的少这里n= 对于一组给定的固定不变的关键字序列有可能设计出无沖突的散列函数H此时称H为完备的散列函数(perfect hashing function)若H能无沖突地将关键字完全填满散列表则称H是最小完备(minimal perfect)的散列函数通常找完备的散列函数非常困难找最小完备的散列函数就更困难请问 ()若h是已知关键字集合K的完备的散列函数若要增加一个新的关键字到集合K一般情况下H还是完备的吗? ()已知关键字集合为()散列函数为H(x)=(x+)/请问H是完备的吗?它是最小完备的吗? ()考虑由字符串构成的关键字集合(BretJaneShirleyBryceMichelleHeather)试为散列表[]设计一个完备的散列函数(提示考虑每个字符串的第个字符即s[]) 设散列函数为h(key)=key%解决沖突的方法为线性探查表中用表示空单元若删去散列表HT中的(即令HT[]=)之后在表HT中查找将会发生什么?若将删去的表项标记为查找时探查到继续向前搜索探查到时终止搜索请问用这种方法删后能否正确地查找到? ┌──┬──┬──┬──┬───────────┬─┐ HT│ │ │ │ │ ││ └──┴──┴──┴──┴───────────┴─┘ |
