查找习题.pptVIP

习题 以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为 ，时间复杂度为 。 在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是 。 法构造的哈希函数肯定不会发生冲突。 在分块查找方法中,首先查找 ，然后再查找相应的 。 判断题 用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。 有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。 已知10个元素{54,28,16,73,62,95,60,26,43,79}，按照依次插入的方法生成一棵二叉排序树。查找值为62的结点所需比较次数为_______。 (A) 2 (B) 3 (C) 4 (D) 5 散列技术中的冲突是指_______。 (A) 两个元素具有相同的序号 (B) 两个元素的键值不同，而其他属性相同 (C) 数据元素过多 (D) 不同键值的元素对应于相同的存储地址 假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[11]，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。 设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H（key）= key % 13，采用开放地址法的线性探测再散列方法解决冲突，试在0~18的散列地址空间中对该关键字序列构造哈希表。 设计顺序查找算法，将哨兵设在下标高端。 以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为 (n+1)/2 ，时间复杂度为O(n) 。 在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是1,3,6,8,11,13,16,19 。 直接定址 法构造的哈希函数肯定不会发生冲突。 在分块查找方法中,首先查找索引 ，然后再查找相应的块。 判断题 用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 (x) 对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。 (x) 有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。 (x) 已知10个元素{54,28,16,73,62,95,60,26,43,79}，按照依次插入的方法生成一棵二叉排序树。查找值为62的结点所需比较次数为_______。 (A) 2 (B) 3 (C) 4 (D) 5 散列技术中的冲突是指_______。 (A) 两个元素具有相同的序号 (B) 两个元素的键值不同，而其他属性相同 (C) 数据元素过多 (D) 不同键值的元素对应于相同的存储地址 假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[11]，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。 散列函数：H(K) = k % m 其中依题意得 m = 11 H( 32 ) = 32 % 11 = 10 H( 75 ) = 75 % 11 = 9 H( 29 ) = 29 % 11 = 7 H( 63 ) = 63 % 11 = 8 H( 48 ) = 48 % 11 = 4 H( 94 ) = 94 % 11 = 6 H( 25 ) = 25 % 11 = 3 H( 46 ) = 46 % 11 = 2 H( 18 ) = 18 % 11 = 7 H( 70 ) = 70 % 11 = 4 ASL = ( 8*1+2*2 )/10 = 1.2 设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H（key）= key % 13，采用开放地址法的线性探测再散列方法解决冲突，试在0~18的散列地址空间中对该关键字序列构造哈希表。 依题意，m=19，线性探测再散列的下一地址计算公式为： d1=H（key） dj+1=（dj+1）% m；j=1，2，… 其计算函数如下： H（19）=19 % 13 = 6 H（01）=01 % 13 = 1 H（23）=23 % 13 =10 H（14）=14 % 13 =1（冲突） H（14）=（1+1）% 19 =