数据结构单元练习9

《数据结构单元练习9》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、单元练习9一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）二分查找法要求待查表的关键字值必须有序。（ㄨ）（2）对有序表而言采用二分查找总比采用顺序查找法速度快。（ㄨ）（3）在二叉排序树中，根结点的值都小于孩子结点的值。（√）（4）散列存储法的基本思想是由关键字的值决定数据的存储地址。（√）（5）哈希表是一种将关键字转换为存储地址的存储方法。（ㄨ）（6）选择好的哈希函数就可以避免冲突的发生。（ㄨ）（7）在有序的顺序表和有序的链表上，均可以采用二分查找来提高查找速度。（√）（8）采用分块查找，既能实现线性表所希望的查找速度，又能适应动态变化的需要。（√）（9）哈希

2、法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。（ㄨ）（10）在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。二．填空题（1）顺序查找法，表中元素可以任意存放。（2）在分块查找方法中，首先查找索引，然后再查找相应的块。（3）顺序查找、二分查找、分块查找都属于静态查找。（4）静态查找表所含元素个数在查找阶段是固定不变的。（5）对于长度为n的线性表，若进行顺序查找，则时间复杂度为O（n）。（6）对于长度为n的线性表，若采用二分查找，则时间复杂度为：O（log2n）。（7）理想情况下，在散列表中查找一个元素的时间复杂度为：O（1）

3、。（8）在关键字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找关键字92，要比较4次才找到。（9）设有100个元素，用二分查找时，最大的比较次数是7次。（10）对二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较，若比根结点小，则继续在左子树中查找。（11）二叉排序树是一种动态查找表。（12）哈希表是按散列存储方式构造的存储结构（13）哈希法既是一种存储方法，又是一种查找方法。（14）散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。（15）设散列函数H和键值k1，k2，若k1≠k2，且H（k1）=H（k2），则称这种现象为冲突。（

4、16）处理冲突的两类主要方法是开放定址法和拉链法（或链地址法）。（17）散列表（或散列）查找法的平均查找长度与元素个数n无关。（18）在哈希函数H(key)=key%P中，P一般应取质数。（19）在查找过程中有插入元素或删除元素操作的，称为动态查找。（20）各结点左右子树深度之差的绝对值至多为1的二叉树称谓平衡二叉树。三．选择题（1）查找表是以（A）为查找结构。A．集合B．图C．树D．文件（2）顺序查找法适合于存储结构为（B）的线性表。A．散列存储B．顺序存储或链接存储C．压缩存储D．索引存储（3）在表长为ｎ的链表中进行线性查找，它的平均查找长度为（B）。Ａ.ASL＝ｎ;Ｂ.ASL＝(

5、n+1)/２;Ｃ.ASL＝＋１;Ｄ.ASL≈log2ｎ（4）对线性表进行二分查找时，要求线性表必须（D）。A．以顺序方式存储B．以链接方式存储，且结点按关键字有序排序C．以链接方式存储D．以顺序方式存储，且结点按关键字有序排序（5）衡量查找算法效率的主要标准是（B）。A．元素个数B.平均查找长度C．所需的存储量D．算法难易程度（6）如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（A）查找方法。A．分块B．顺序C．二分D．散列（7）链表适用于（A）查找。A．顺序B．二分C．随机D．顺序或二分（8）一个有序表为{1，3，9，12，32，41，45，62，75，77，82

6、，95，100}，当二分查找值为82的结点时，(C)次比较后查找成功。A．2B．3C．4D．5（9）二分查找有序表{4，6，10，12，20，30，50，70，88，100},若查找表中元素58，则它将依次与表中（B）比较大小，查找结果是失败。A．30，88，70，50B．20，70，30，50C．20，50D．30，88，50（10）对有14个元素的有序表A[1..14]作二分查找，查找元素A[4]时的被比较元素依次为（C）。A．A[1]，A[2]，A[3]，A[4]B．A[1]，A[14]，A[7]，A[4]C．A[7]，A[3]，A[5]，A[4]D．A[7]，A[5]，A[3]

7、，A[4]（11）有一个长度为12的有序表，按二分查找法对其进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（B）。A．35／12B．37／12C．39／12D．43／12（12）采用分块查找时，若线性表共有625个元素，查找每个元素的概率相等，假设采用顺序查找来确定结点所在的块时，每块分（C）个结点最佳。A．6B．10C．25D．625（13）下列（C）不是利用查找表中数据元素的关系进行查找的方法。A．平衡二叉树B．有序表的查找