《数据结构单元练习9》由会员分享，可在线阅读，更多相关《数据结构单元练习9（14页珍藏版）》请在金锄头文库上搜索。
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，若k1k2，且H（k1）=
4、H（k2），则称这种现象为 冲突 。（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）在表长为的链表中进行
5、线性查找，它的平均查找长度为（ B ）。. ASL; . ASL(n+1)/; . ASL; . ASLlog2（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）一个
6、有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值为82的结点时，( C )次比较后查找成功。A2 B3 C4 D5（9）二分查找有序表4，6，10，12，20，30，50，70，88，100,若查找表中元素58，则它将依次与表中（ B ）比较大小，查找结果是失败。A30，88，70，50 B 20，70，30，50 C20，50 D30，88，50（10）对有14个元素的有序表A1.14作二分查找，查找元素A4时的被比较元素依次为（ C ）。AA1，A2，A3，A4BA1，A14，A7，A4CA7，A3，A5，A4DA7，A5，A3，A4（11）有
7、一个长度为12的有序表，按二分查找法对其进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（ B ）。A3512 B3712 C3912 D4312（12）采用分块查找时，若线性表共有625个元素，查找每个元素的概率相等，假设采用顺序查找来确定结点所在的块时，每块分（ C ）个结点最佳。A6 B10 C25 D625（13）下列（ C ）不是利用查找表中数据元素的关系进行查找的方法。A平衡二叉树 B有序表的查找 C. 散列查找 D二叉排序树的查找（14）设哈希表长m=14，哈希函数H（key）=key11。表中已有4个结点： addr(15)=4 addr(38)=5 addr(6
8、1)=6 addr(84)=7 其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是（ D ）。A8 B3 C5 D9（15）对包含n个元素的散列表进行查找，平均查找长度为（ D ）。AO(n2) BO(log2n) C. O(n) D不直接依赖于n（16）冲突指的是（ C ）。A两个元素具有相同序号 B. 两个元素的键值不同C不同键值对应相同的存储地址 D两个元素的键值相同（17）在查找过程中，不做增加、删除或修改的查找称为（ A ）。A静态查找 B. 内创造 C动态查找 D外查找（18）已知8个元素为34，76，45，18，26，54，92，65，按照依次插入结点的方法生成
9、一棵二叉树，最后两层上结点的总数为（ B ）。A1 B2 C. 3 D4（19）不可能生成下图二叉排序树的关键字的序列是（ A ）。A4 5 3 1 2B4 2 5 3 1C4 5 2 1 3D4 2 3 1 542A135（20）动态查找包括（ B ）查找。A顺序表 B. 二叉排序树 C有序表 D索引顺序表四应用题1 对于给定结点的关键字集合K=5，7，3，1，9，6，4，8，2，10，（1）试构造一棵二叉排序树；（2）求等概率情况下的平均查找长度ASL。解：（1）构造二叉排序树 ： （2）ASL=(1*1+2*2+3*4+4*3)/10=2.974312596108D2 对于给定结点的关键
10、字集合K=10，18，3，5，19，2，4，9，7，15，（1）试构造一棵二叉排序树；（2）求等概率情况下的平均查找长度ASL。1853D2410191579解：（1）构造二叉排序树 ：（2）ASL=(1*1+2*2+3*4+4*2+5*1)/10=33 将数据序列：25，73，62，191，325，138，依次插入下图所示的二叉排序树，并画出最后结果。10008013150906213819110000732580D90150解：3254 对于给定结点的关键字集合K=1，12，5，8，3，10，7，13，9，1385D37129110（1）试构造一棵二叉排序树；（2）在二叉树排序BT中删除“
11、12”后的树结构：85D371391101385D371019 或5 对于给定结点的关键字集合K=34，76，45，18，26，54，92，38，（1）试构造一棵二叉排序树；（2）求等概率情况下的平均查找长度ASL。解：18269245D76543438（1）构造二叉排序树（2）ASL=（1*1+2*2+3*3+4*2）/ 8 =2.75 （或=11/4）6 对于给定结点的关键字集合K=4，8，2，9，1，3，6，7，5， （1）试构造一棵二叉排序树；（2）求等概率情况下的平均查找长度ASL。解：（1）构造二叉排序树2396D87415（2）ASL=（1*1+2*2+3*4+4*2）/ 9 =2.78 （或=25/9）7 画出对长
