B树与Hash查找

2023-05-25 21:05:09 hash 查找

2-3



       解析 ： 有可能会发生冲突，所以没法求平均查找长度。



2-10



       解析 ：参考点击打开链接。



2-14



       解析 : 最少为ceil(m / 2)。








2-1

在散列表中，所谓同义词就是： (1分)

  1. 两个意义相近的单词

  2. 具有相同散列地址的两个元素

  3. 被映射到不同散列地址的一个元素

  4. 被不同散列函数映射到同一地址的两个元素



作者: DS课程组



单位: 浙江大学



2-2

在下列查找的方法中，平均查找长度与结点个数无关的查找方法是： (1分)

  1. 顺序查找

  2. 二分法

  3. 利用哈希（散列）表

  4. 利用二叉搜索树



作者: DS课程组



单位: 浙江大学



2-3

对包含N个元素的散列表进行查找，平均查找长度为： (1分） A

  1. 不确定



作者: DS课程组



单位: 浙江大学



2-4

将M个元素存入用长度为S的数组表示的散列表，则该表的装填因子为： (2分)

  1. S+M

  2. M−S

  3. M×S

  4. M/S



作者: DS课程组



单位: 浙江大学



2-5

散列冲突可以被描述为： (1分)

  1. 两个元素除了有不同键值，其它都相同

  2. 两个有不同数据的元素具有相同的键值

  3. 两个有不同键值的元素具有相同的散列地址

  4. 两个有相同键值的元素具有不同的散列地址



作者: DS课程组



单位: 浙江大学



2-6

将10个元素散列到100000个单元的哈希表中，是否一定产生冲突？ (1分)

  1. 一定会

  2. 可能会

  3. 一定不会

  4. 有万分之一的可能会



作者: DS课程组



单位: 浙江大学



2-7

设散列表的地址区间为[0,16]，散列函数为H(Key)=Key%17。采用线性探测法处理冲突，并将关键字序列{ 26，25，72，38，8，18，59 }依次存储到散列表中。元素59存放在散列表中的地址是： (2分)

  1. 8

  2. 9

  3. 10

  4. 11



作者: DS课程组



单位: 浙江大学



2-8

采用线性探测法解决冲突时所产生的一系列后继散列地址： (1分)

  1. 必须大于等于原散列地址

  2. 必须小于等于原散列地址

  3. 可以大于或小于但不等于原散列地址

  4. 对地址在何处没有限制



作者: DS课程组



单位: 浙江大学



2-9

将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个初始为空的、大小为11的散列表中。散列函数为：H(Key)=Key%11，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？ (3分)

  1. 0.27

  2. 0.45

  3. 0.64

  4. 0.73



作者: DS课程组



单位: 浙江大学



2-10

给定散列表大小为11，散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的4个元素。问：此时该散列表的平均不成功查找次数是多少？ (2分)

  1. 1

  2. 4/11

  3. 21/11

  4. 不确定



作者: DS课程组



单位: 浙江大学



2-11

从一个具有N个结点的单链表中查找其值等于X的结点时，在查找成功的情况下，需平均比较多少个结点？ (2分)

  1. N/2

  2. N

  3. (N−1)/2

  4. (N+1)/2



作者: DS课程组



单位: 浙江大学



2-12

设数字 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 在大小为10的散列表中根据散列函数 h(X)=X%10得到的下标对应为 {1, 3, 4, 9, 5, 0, 2}。那么继续用散列函数 “h(X)=X%表长”实施再散列并用线性探测法解决冲突后，它们的下标变为：(3分)

  1. 11, 3, 13, 19, 4, 0, 9

  2. 1, 3, 4, 9, 5, 0, 2

  3. 1, 12, 9, 13, 20, 19, 11

  4. 1, 12, 17, 0, 13, 8, 14



作者: DS课程组



单位: 浙江大学



2-13

下列叙述中，不符合m阶B树定义要求的是： (1分)

  1. 叶结点之间通过指针链接

  2. 根结点最多有m棵子树

  3. 所有叶结点都在同一层上

  4. 各结点内关键字均升序或降序排列



作者: DS课程组



单位: 浙江大学



2-14

127阶B-树中除根结点外所有非终端结点至少有多少棵子树？ (2分)

  1. 64



作者: DS课程组



单位: 浙江大学



2-15

B+树不同于B树的特点之一是：(1分)

  1. 能支持顺序查找



作者: DS课程组



单位: 浙江大学



2-17

下列关于M阶B+树的说法，哪一句是对的？(1分)

  1. 根结点一定有2到M个孩子

  2. 不是所有的叶结点都有同样的深度

  3. 叶结点和非叶结点中存的有一些键值是一样的

  4. 所有非叶结点都有⌈M/2⌉到M个孩子



作者: 陈越



单位: 浙江大学

相关文章