1.对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?
2.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：
(1)查找不成功，即表中无关键字等于给定值K的记录；
(2)查找成功，即表中有关键字等于给定值K的记录。
3.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。
4.为什么有序的单链表不能进行折半查找?
5.设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。
6.将(for, case, while, class, protected, virtual, public, private, do, template, const ,if, int)中的关键字依次插入初态为空的二叉排序树中，请画出所得到的树T。然后画出删去for之后的二叉排序树T',若再将for 插入T'中得到的二叉排序树T''是否与T相同?最后给出T"的先序、中序和后序序列。
7.对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同一棵二叉排序树?
8.将二叉排序树T的先序序列中的关键字依次插入一空树中，所得和二叉排序树T'与T否相同?为什么?
9.设二叉排序树中关键字由1至1000的整数构成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树上查找到的序列?
(a) 2，252，401，398，330, 344，397，363；
(b) 924, 220, 911, 244, 898, 258, 362, 363;
(c) 925, 202, 911, 240, 912, 245, 363;
(d) 2, 399, 387, 219, 266, 382, 381, 278, 363.
10.设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗?
11.在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字?若删去某结点中的一个关键字，而导致结点合并时，该结点中原有几个关键字?
12.在一棵B-树中，空指针数总是比关键字数多一个，此说法是否正确?请问包含8个关键字的3阶B-树(即2-3树)最多有几个结点?最少有几个结点?画出这两种情况的B-树。
13.从空树开始，依次输入20，30，50，52，60，68，70，画出建立2-3树的过程。并画出删除50和68后的B-树状态。
14.画出依次插入z,v,o,p,w,y到图9.12(h)所示的5阶B-树的过程。
15.在含有n个关键字的m阶B-树中进行查找，至多读盘多少次?完全平衡的二叉排序树的读盘次数大约比它大多少倍?
16.为什么在内存中使用的B-树通常是3阶的，而不使用更高阶的B-树?
17.为什么二叉排序树长高时，新结点总是一个叶子，而B-树长高时，新结点总是根?哪一种长高能保证树平衡?
18.已知关键字序列为(PAL,LAP,PAM,MAP,PAT,PET,SET,SAT,TAT,BAT)试为它们设计一个散列函数，将其映射到区间[0..n-1]上，要求碰撞尽可能的少。这里n=11,13,17,19.
19.对于一组给定的、固定不变的关键字序列，有可能设计出无冲突的散列函数H，此时称H为完备的散列函数(perfect hashing function)，若H能无冲突地将关键字完全填满散列表，则称H是最小完备(minimal perfect)的散列函数。通常找完备的散列函数非常困难，找最小完备的散列函数就更困难。请问：
(1)若h是已知关键字集合K的完备的散列函数，若要增加一个新的关键字到集合K，一般情况下H还是完备的吗?
(2)已知关键字集合为(81，129，301，38，434，216，412，487，234)，散列函数为H(x)=(x+18)/63,请问H是完备的吗?它是最小完备的吗?
(3)考虑由字符串构成的关键字集合(Bret,Jane,Shirley,Bryce,Michelle,Heather)，试为散列表[0..6] 设计一个完备的散列函数。(提示：考虑每个字符串的第3个字符，即s[2])
20.设散列函数为h(key)=key%101,解决冲突的方法为线性探查，表中用"-1"表示空单元。若删去散列表HT中的304(即令HT[1]=-1)之后，在表HT中查找707将会发生什么?若将删去的表项标记为"-2",查找时探查到-2继续向前搜索，探查到-1时终止搜索。请问用这种方法删304后能否正确地查找到707?
0 1 2 3 100
┌──┬──┬──┬──┬───────────┬─┐
HT│202 │304 │507 │707 │ ...... │ │
└──┴──┴──┴──┴───────────┴─┘