假设有k个关键字互为同义词，若用线性探测再散列法将这k个关键字存入哈希表中，至少要进行 次定址。A．k-1B．kC．k+1D．k(k+1)/2

题目

假设有k个关键字互为同义词，若用线性探测再散列法将这k个关键字存入哈希表中，至少要进行 次定址。

A．k-1

B．k

C．k+1

D．k(k+1)/2

相似考题

1.●假定有K个关键字互为同义词，若用线性探查法把这些同义词存入散列表中，至少要进行 (48) 次探查。(48) A．k(k+1)/2B．k(k+1)C．2k(k+1)D．不确定

2.假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测?()A、k-1次B、k次C、k+1次D、k(k+1)/2次

3.设有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表,至少要进行()次探测。A、k-1B、kC、k+1D、k(k-1)/2

4.假定有n个关键字，它们具有相同的散列函数值，用线性探查方法把这n个关键字存入到哈希地址空间中要做【 】次探查。

更多“假设有k个关键字互为同义词，若用线性探测再散列法将这k个关键字存入哈希表中，至少要进行 次定址。”相关问题

  • 第1题：

    哈希函数可以减少冲突，但仍不可避免，通常处理冲突的方法有再哈希法，建立公共溢出区和( )。

    A．链地址法和直接定址法

    B．线性探测再散列法和二次探测再散列法

    C．开方定址法和链地址

    D．除留余数法和数字分析法


    正确答案：C
    解析：用哈希函数处理冲突的方法通常有开方定址法、再哈希法、链地址法以及建立公共溢出区。

  • 第2题：

    假定有K个关键字互为同义词，若用线性探测再散列法把这K个关键字存入散列表中，至少要进行(42)次探测。

    A．K-1

    B．K

    C．K(K-1)/2

    D．K(K+1)/2


    正确答案：D
    解析：哈希涉及到构造哈希函数和处理)中突。解决冲突就是为出现冲突的关键字找到另一个”空”的哈希地址。开放地址法是常用的一种方法。开放地址法：Hi=(H(key)+di)%mi=1，2，...k(km-1)，其中H(key)为哈希函数；m为哈希表表长；di为增量序列，当di1，2，3，...，m-1时，称为线性探测再散列。用线性探测再散列法把这K个关键字存入散列表中，第1个关键字最少需进行1次探测，第2个关键字最少需进行2次探测，...第A个关键字最少需进行七次探测，所以最少要进行K(K+1)/2次探测。

  • 第3题：

    设哈希表长m=14，哈希函数H(key)=key%ll，表中已经有4个结点： addr(13)=4； addr(28)=5 addr(51)=6； addr(77)=7 如果用线性探测再与散列法处理冲突，关键字为49的结点地址为( )。

    A．8

    B．5

    C．9

    D．3


    正确答案：A

  • 第4题：

    在长度为11的哈希表中已经填有关键字28、49、40，现有关键字为38的记录，若采用线性探测再散列，应该填入的地址为( )。

    A．8

    B．4

    C．6

    D．3


    正确答案：A
    解析：线性探测再散列的增量序列分别为1，2，3，4……，哈希表中已经填有的关键字所占用的地址分别为6，5，7，38，本来应该占用地址5，由于已经被占用，根据散列的增量序列，移到地址6，发现也被占用，于是移动到7，发现被占用，继续移动到8，空闲着，于是占用地址8。

  • 第5题：

    假定有k个关键字互为同义词，若用线性探查法把这些同义词存人散列表中，至少要进行(48)次探查。

    A．L(k+1)/2

    B．k(k+1)

    C．2k(k+1)

    D．不确定


    正确答案：A
    解析：存入第1个，需要探查一次；存入第2个，需要探查两次j....；存人第k个需要探查k次；因此至少要进行1+2+3+……+k=k(k+1)/2次探查。

  • 第6题：

    设哈希表长为14，哈希函数是H(key)=key%ll，表中已有数据的关键字为15，28，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()。

    A.8
    B.3
    C.5
    D.9

    答案：D
    解析：

  • 第7题：

    数据结构与算法里，以下属于哈希函数的构造方法的是（）。

    • A、直接定址法
    • B、哈希再散列法
    • C、线性探测再散列法
    • D、二次探测再散列法

    正确答案:A

  • 第8题：

    设散列表的长度为16，散列函数为H（k）=k%13，用线性探测法处理冲突，依次插入关键字：19，01，13，23，24，55，20，84，27，68，11，10，77。请回答：查找关键字98（失败）时，需要依次与哪些关键字比较。


    正确答案:分别于关键字20,84比较。

  • 第9题：

    数据结构与算法中，设哈希表长为14，哈希函数是H（key）=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）。

    • A、8
    • B、9
    • C、5
    • D、3

    正确答案:B

  • 第10题：

    问答题
    设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：若查找关键字63，需要依次与哪些关键字进行比较？

    正确答案： 查找63,首先要与H(63)=63%16=15号单元内容比较，即63与31比较 ,不匹配; 然后顺移，与46,47,32,17,63相比，一共比较了6次！
    解析： 暂无解析

  • 第11题：

    单选题
    假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？（）
    A

    k-1次

    B

    k次

    C

    k+1次

    D

    k（k+1）/2次


    正确答案： A
    解析： 暂无解析

  • 第12题：

    单选题
    数据结构与算法里，以下属于哈希函数的构造方法的是（）。
    A

    直接定址法

    B

    哈希再散列法

    C

    线性探测再散列法

    D

    二次探测再散列法


    正确答案： C
    解析： 暂无解析

  • 第13题：

    在长度为9，序号为从0-8的哈希表中已填有关键字分别为13、23、51的记录，现在有一个记录为40，若用二次探测再散列，则该填入序号为 ______ 的位置。


    正确答案：3
    3 解析：对二次探测再散列的增量序列di=12，-12，22，-22...，对长度为9的哈希表，哈希函数H(key)=key MOD 9，关键字13、23、51分别已填入地址为4、5、6的位置，对记录 40，通过哈希函数求出其位置为4，由于已经有13在该位置，根据增量序列找位置5，发现23在该位置，又找位置3，没有元素，就填入到3的位置。

  • 第14题：

    设哈希函数h (k) =k mod 7,哈希表的地址空间为0～6,对关键字序列（32，13，49， 55，22，38，12）按线性探测法解决冲突，关键字12应存放在散列表中的地址是 【】 ，

    查找关键字12需比较的次数为 【】


    正确答案：

    5         6次


    h(k)=k mod 7,所以地址为：12 mod 7=5. 分别于关键字进行比较，从而得出比较次数为6.

  • 第15题：

    已知一个线性表(38，25，74，63，52，48)，假定采用h(k)=k%6计算散列地址进行散列存储，若用线性探测的开放定址法处理冲突，则在该散列表上进行查找的平均查找长度为(44)。

    A．1.5

    B．1.7

    C．2

    D．2.3


    正确答案：A
    解析：用散列函数n(k)=k%6计算得到散列地址见表2。表2散列地址关键字散列地址用线性探测的开放定址法处理冲突所构造得到的散列表见表3。表3散列表该散查找次数列表的平均查找长度为(1×3+2×3)/6=1.5。

  • 第16题：

    在长度为11的哈希表中已经填有关键字28、49、40，现有关键字为38的记录，若采用二次探测再散列，应该填入的地址为( )。

    A．8

    B．4

    C．5

    D．3


    正确答案：B
    解析：二次探测再散列的增量序列分别为12，-12，22，-22，32，-32...，±k2，已经填有的关键字所占用的地址分别为6、5、7，38本来应该占用地址5，由于已经被占用，根据散列的增量序列，移到地址6，发现也被占用，于是占用地址4。

  • 第17题：

    假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，至少要进行的探查次数是()。

    A.k-1
    B.k
    C.k+1
    D.k(k+1)/2

    答案：D
    解析：
    假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，探查次数最少的情况是第1个关键字通过1次比较后插入，第2个关键字通过2次比较后插入，…，第k个关键字通过k次比较后插入。总的比较次数=1+2+…+k=k(k+1)/2。

  • 第18题：

    假设n个关键字互为同义词，若采用线性探测再散列法处理冲突，把这些关键字散列到一个散列表中，则进行的探测次数是（）。

    • A、n-1
    • B、n
    • C、n+1
    • D、n（n-1）/2

    正确答案:D

  • 第19题：

    设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：若查找关键字63，需要依次与哪些关键字进行比较？


    正确答案:查找63,首先要与H(63)=63%16=15号单元内容比较，即63与31比较 ,不匹配; 然后顺移，与46,47,32,17,63相比，一共比较了6次！

  • 第20题：

    假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？（）

    • A、k-1次
    • B、k次
    • C、k+1次
    • D、k（k+1）/2次

    正确答案:D

  • 第21题：

    已知哈希表地址空间为A[0..8]，哈希函数为H（k）=k mod 7，采用线性探测再散列处理冲突。若依次将数据序列：76，45，88，21，94，77，17存入该散列表中则元素17存储的下标为（）。

    • A、0
    • B、1
    • C、2
    • D、3
    • E、4
    • F、5
    • G、6
    • H、7

    正确答案:F

  • 第22题：

    单选题
    已知哈希表地址空间为A[0..8]，哈希函数为H（k）=k mod 7，采用线性探测再散列处理冲突。若依次将数据序列：76，45，88，21，94，77，17存入该散列表中在等概率情况下查找成功的平均查找长度为（）。
    A

    0

    B

    1

    C

    2

    D

    3

    E

    4

    F

    5

    G

    6

    H

    7


    正确答案： E
    解析： 暂无解析

  • 第23题：

    单选题
    已知哈希表地址空间为A[0..8]，哈希函数为H（k）=k mod 7，采用线性探测再散列处理冲突。若依次将数据序列：76，45，88，21，94，77，17存入该散列表中则元素17存储的下标为（）。
    A

    0

    B

    1

    C

    2

    D

    3

    E

    4

    F

    5

    G

    6

    H

    7


    正确答案： E
    解析： 暂无解析

  • 第24题：

    单选题
    假设n个关键字互为同义词，若采用线性探测再散列法处理冲突，把这些关键字散列到一个散列表中，则进行的探测次数是（）。
    A

    n-1

    B

    n

    C

    n+1

    D

    n（n-1）/2


    正确答案： D
    解析： 暂无解析

相关内容