●设顺序存储的某线性表共有108个元素，按分块查找的要求等分为4块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为(79)。
(79)A.14
B.17
C.23
D.54
答案：(79)B
解析：分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。二分查找表由”分块有序”的线性表和索弓l表组成。表R[1…n]均分为b块。前b-1块中结点个数为s=[n/ b]，第b块的结点数允许小于等于s;每一块中的关键字不一定有序。但前一块中的最大关键字必须小于后一块中的最小关键字，即表是”分块有序”的。抽取各块中的最大关键字及其起始位置构成一个索引表ID[1…b]。即：ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的。所以索引表是一个递增有序表。分块查找的基本思想是：(1)首先查找索引表：索引表是有序表。可采用二分查找或顺序查找，以确定待查的结点在哪一块。(2)然后在已确定的块中进行顺序查找，由于块内无序，只能用顺序查找。
平均查找长度ASL：分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。
①以二分查找来确定块，分块查找成功时的平均查找长度
ASL1=ASLbn+ASLsq≈log2(b+1)-1+(S+1)/2≈log2(n/s+1)+s/2
②以顺序查找确定块，分块查找成功时的平均查找长度
ASL2=(b+1)/2+(s+1)/2=(S2+2s+n)/(2s)
本题中。n=108，b=4，s=27，计算得平均查找长度为17。
●将一维数组A[0，m*n-1]存放到m行、n列的矩阵中，则下面的对应关系(80)可将元素 A[k](0≤k
(80)A.i=k/n，i=k%m
B.i=k/n，j=k%n
C.i=k/m，j=k%m
D.i=k/m，j=k%n
答案：(80)B
解析：把A数组的前n个元素放到B数组的第一行中，A数组的第n个元素放到B数组的第二行中。依此类推，A数组的最后n个元素放到B数组的最后一行。求A[k]在B数组中的位置，应先确定行，应该是k/n行，然后再确定列。显然是k%n。
●设f表示某个二元逻辑运算符，XfY的真值表见表1，则XfY等价于(81)。
(81) A.X∧┑Y
B.┑X∧Y
C.┑X∧┑Y
D.┑X∨┑Y
答案：(81)B
解析：将真值表的各项代入可得只有B正确。
