数据结构（山东联盟-青岛大学）章节测试课后答案2024春

第八章测试

1.顺序查找算法适用于（      ）结构。
A:查找网            B:线性表            C:查找树            D:连通图
答案:B
2.在顺序存储的线性表R[30]上进行顺序查找的平均查找长度为（        ）。
A:16 B:15.5 C:20 D:15 3.对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找到表中任一元素的平均查找长度为（ ）。
A:39/8 B:5 C:19/4 D:5.5 4.如果有5个关键字{a,b,c,d,e}放在顺序表中，它们的查找概率分别为{0.35,0.25，0.20,0.15,0.05}，按照（   ）顺序存放可使平均查找长度达到最小。
A:e,d,c,b,a B:a,c,e,d,b C:d,a,b,c,e D:a,b,c,d,e 5.对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平均查找长度为（    ）。
A:(n-1)/2 B:(n+1)/2 C:n/4 D:n/2 6.对线性表进行折半查找时，要求线性表必须（      ）。
A:以链接方式存储 B:以顺序方式存储 C:以顺序方式存储，且结点按关键字有序排序 D:以链接方式存储，且结点按关键字有序排序 7.采用折半查找方式查找一个长度为n的有序顺序表时，其平均查找长度为（ ）。
A:O(log2n) B:O(n^2) C:O(nlog2n) D:O(n) 8.采用折半查找法查找长度为n的有序顺序表，查找每个元素的数据比较次数（  ）对应二叉判定树的高度（设高度≥2）。
A:大于 B:小于等于 C:等于 D:小于 9.折半查找和二叉排序树的时间性能（      ）。
A:有时不相同 B:不定 C:相同 D:完全不同 10.在常用的描述二叉排序树的存储结构中，关键字值最大的结点（     ）。
A:右指针一定为空 B:左右指针均为空            C:左右指针均不为空 D:左指针一定为空            11.m阶B-树是一棵（           ）。
A:m-1叉高度平衡查找树 B:m叉高度平衡查找树 C:m+1叉高度平衡查找树 D:m叉查找树                          12.下列关于m阶B-树的说法中错误的是（              ）。
A:根结点至多有m棵子树 B:根结点中的数据是有序的 C:非失败结点至少有m/2（m为偶数）或m/2+1（m为奇数）棵子树 D:所有叶结点都在同一层次上 13.下面关于B-树和B+树的叙述中错误的是（  ）。
A:B-树和B+树都是平衡的多叉查找树 B:B-树和B+树都能有效地支持顺序查找 C:B-树和B+树都可用于文件的索引结构 D:B-树和B+树都能有效地支持随机查找 14.散列法存储的基本思想是根据（    ）来决定元素的存储地址。
A:关键字值        B:元素的序号     C:元素个数        D:非码属性 15.设一个散列表中有n个元素，用散列法进行查找，理想情况下的平均查找长度是（   ）。
A:O(1)  B:O(log2n)  C:O(n)  D:O(n^2)  16.使用散列函数将元素的关键字值映射为散列地址时，常会产生冲突。此时的冲突是指（    ）。
A:两个元素的关键字值不同，而非关键字值相同 B:两个元素具有相同的序号 C:装填因子过大，数据元素过多 D:不同关键字值对应到相同的存储地址 17.以下关于散列函数选择原则的叙述中，不正确的是（        ）。
A:装填因子必须限制在0.8以下 B:散列函数应是简单的，能在较短的时间内计算出结果 C:散列函数的定义域应包括全部关键字值,值域必须在表范围之内 D:散列函数计算出来的地址应能均匀分布在整个地址空间中 18.计算出的地址分布最均匀的散列函数是（     ）。
A:折叠法 B:平方取中法            C:除留余数法            D:数字分析法            19.除留余数法的基本思路是：设散列表的地址空间为0～m-1，元素的关键字值为k，用p去除k，将余数作为元素的散列地址，即h(k)=k%p，为了减少发生冲突的可能性，一般取p为（      ）。
A:小于或等于m的最大合数 B:m C:小于或等于m的最大素数 D:大于m的最小素数 20.解决散列法中出现的冲突问题常采用的方法是（        ）。
A:数字分析法、除留余数法、平方取中法 B:数字分析法、除留余数法、线性探测法 C:数字分析法、线性探测法、双散列法 D:线性探测法、二次探测散列法、链地址法 21.在用开放定址法构造出的散列表中，散列到同一个地址而引起的“二次聚集”问题是由于（  ）引起的。
A:同义词之间或非同义词之间发生冲突 B:散列表“溢出” C:非同义词之间发生冲突 D:同义词之间发生冲突 22.散列表的平均查找长度（        ）。
A:与处理冲突方法无关而与表的长度有关 B:与处理冲突方法有关而与表的长度无关 C:与处理冲突方法有关且与表的长度有关 D:与处理冲突方法无关且与表的长度无关 23.在由n个元素组成的有序表上进行折半查找时，对任一个元素进行查找的长度都不会大于。
A:错 B:对 24.对于两棵具有相同关键码集合而形状不同的二叉查找树，按中序遍历它们得到的序列的各元素的顺序是一样的。
A:对 B:错 25.在一棵AVL树中删除一个结点后，失去平衡的结点多于一个。
A:错 B:对