9.3练习题及参考答案
9.3.1练习题
一、选择题
1．顺序查一个共有n个元素的线性表，其时间复杂度为（        ），折半查一个具有n个元素的有序表，其时间复杂度为（        ）。
  A.O(n)          B.O(log2n)            C.O(n2)          D.(n log2n)
2.在对长度为n的顺序存储的有序表进行折半查，对应的折半查判定树的高度为（      ）。
  A.n              B.          C.  D.   
3.采用折半查方式查长度为n 的线性表时，平均查长度为（          ）。
  A. O(n2)          B. (n log2n)          C. O(n)          D. O(log2n)
4.采用顺序查方式查长度为n的线性表时，平均查长度为（          ）。
  A.n              B.n/2                C.(n+1)/2        D.(n-1)/2
5.采用折半查方法检索长度为n的有序表，检索每个元素的平均比较次数（        ）对应判定树的高度（设高度＞＝2）。
  A.小于          B.大于              C.等于          D.大于等于
6.已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查值为90的元素时，查成功的比较次数为（        ）。
  A．1            B. 2                C. 3            D. 4
7.对有序表｛1，3，9，12，32，41，45，62，排序题75，77，82，95，100｝，当折半查值为82的结点时（        ）次比较后查成功。
  A．1            B. 2                  C. 3          D. 8
8.对线性表进行折半查时，要求线性必须（          ）。
  A．以顺序方式存储
  B．以链接方式存储
  C．以顺序方式存储，且结点按关键字有序排序
  D．以链接方式存储，且结点按关键字有序排序
9.顺序查法适合于存储结构为（        ）的线性表。
  A．散列存储                B. 顺序存储或链接存储
  C．压缩存储                D. 索引存储
10.采用分块查时，若线性表中共有625个元素。查每个元素的概率相同，假设采用顺序查来确定结点所在的块时，每块应分（          ）个结点最佳。
  A．10          B. 25                C. 6              D. 625
11.在顺序存储的线性表（R[0]~R[29]）上进行顺序查的平均查长度为（          ），进行折半查的平均查长度为（          ），进行分块查（设等分为5块）的平均查长度为（          ）。
  （1）A．15        B. 15.5          C. 16            D. 20
  （2）A．4        B. 62/15        C. 64/15        D. 25/6
  （3）A．6        B. 11            C. 5            D. 6.5
12.从键盘依次输入关键字的值：t,u,r,b,o,p,a,s,c,l.建立二叉排序树，则其先序遍历序列为（      ），中序遍序列为（        ）。 
  A．abcloprstu      B.alcpobsrut    C.trbaoclpsu        D.trusaocpl
13.折半查和二叉排序树的时间能（          ）。
  A．相同            B. 不相同
14.一棵浓度为k的平衡树，其每个非终端结点的平衡因子均为0,则该树共有（        ）个结点。
  A．2K-1－1      B. 2K-1                C. 2K-1+1          D.2 k-1
  E.  2 k              F. 2 k+1
15.利用逐点插入法建立序列｛50，72，43，85，75，20，35，45，65，30｝对应的二叉树以后，查元素35的进行（          ）元素间的比较。
  A．4次        B. 5次          C. 7次          D. 10次
16.在关键字随机分布的情况下，用二叉排序树的方法进行查，其查长度与（        ）
量级相同。
  A．顺序查    B。折半查      C。前两者都不正确
17.最优二叉树（哈夫曼树），最优查树均为平均查路径长度最小的树，其中对最优二叉树，n表示（          ），对最优查树，n表示（        ），构造这两种树均（      ）。
  A．结点数      B. 叶结点数      C. 非叶结点树      D. 度为2的结点数
  E．需要一张n个关键字的表        F. 需要对n个关键字进行动态插入
  G．需要n个关键字的查概率      H. 不需要任何前提
18.如果要求一个线性表既能较快发检索，又能适应动态变化的要求，则宜采用的检索方法为（        ）。
  A．分块检索      B. 顺序检索      C. 折半检索        D. 基于属性检索
19.散列函数有一个共同性质即函数值应按（          ）取其会晤域的每一个会晤。
  A．最大概率      B. 最小概率      C. 同等概率        D. 平均概率
20.对于一个线性表，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（        ）。
  A．以顺序方式存储                B. 以链接方式存储
  C．以散列方式存储                D. 以上均可
21.设Hash地址空间为0~~(m-1),哈希函数为：h(k)=k%p,为了减少发生冲突的可能性，一般取p为（        ）。
  A．小于m的最大奇数              B. 小于m的最大素数
  C．小于m的最大偶数              D. 小于m的最大合数
22.设Hash表长m=14，哈希函数H（key）=key%11.表中已有4个结点，地址分别为：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点地址是（          ）。
  A．8          B. 3              C. 5            D. 9
23.已知一个线性表（38，25，74，63，52，48），假定采用h(k)=k%7计算Hash地址进行散列存储，若采用线性探测的开放定址法解决冲突，则在该Hash表上进行查的平均查长度为（        ）；恐龙啊利用链地址法处理冲突，则在该Hash表上进行查的平均查长度为（        ）。
  （1）A．1.5      B. 1.7          C. 2            D. 2.3
  （2）A．1.0      ｂ. 7/6        C. 4/3          D. 3/2
24.在非空m阶B－树上，除根结点以外的所有其他非终端结点（        ）。
A．至少有棵子树          B. 至多有棵子树
    C．至少有棵子树          D. 至多有棵子树
25.当向一棵m阶的B－树做插入操作时，若一个结点中的关键字个数等于（      ），则必须分裂成两个结点；当向一棵m阶的B－树做删除操作时，若一个结点的关键字个数等于（      ），则可能需要用它的左兄弟或右兄弟结点合并成一个结点。
  （1）A.m        B.m-1        C.m+1        D.m+1
  (2) A.m/2      B.m/2-1      C.m/2+1      D.m/2-2
26.在一个3阶的B－树上，每个结点包含的子树相同，最多为（        ）个结点，最少为（        ）个结点。
A．1          B. 2              C. 3              D. 4
27．下列结论正确的有（          ）。
A．最佳二叉树是AVL树（平衡二叉树）。
B．二叉树中，具有两个子女的结点的中序后继结点最多只能有一个子女。
C．若散列表的负载（装载）因子a<1,则可避免冲突的发生。
D．有n个数存放在一维数组A[n]中，在进行顺序查时，这n个数的排列有序或无序                    其平均查长度不同。
28.下面关于B－树和B＋树的叙述中，不正确的是（          ）
A．B－树和B＋树都是平衡的多叉树
B．B－树和B＋树都可用于文件的索引结构
C．B－树和B＋树都能有效地支持随机检索
D．B－树和B＋树都能有效地支持顺序检索
29.m 路B＋树是一棵（        ），其结点中关键字最多为（          ）个，最少为（        ）个。
A．m路平衡查树      B. m路平衡查树      C. m路trie树
D．m路键树            E. m-1                F. m
G.m/2-1                H.m/2                I.m/2+1