数据结构练习3答案

《数据结构练习3答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构练习（三）参考一、选择题1.顺序查找法适合于存储结构为的线性表A）哈希存储B）顺序存储或链式存储C）压缩存储D）索引存储2.一个长度为100的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较________次。A）9B）8C）7D）63.采用顺序查找方法查找长度为n的线性表时，平均比较次数为。A）nB）n/2C）（n+1）/2D）（n-1）/24.对线性表进行折半查找时，要求线性表必须。A）以顺序方式存储B）以顺序方式存储，且结点按关键字有序排列C）以链表方式存储D）以链表方式存储，且结点按关键字有序排列5.采用二分查

2、找法查找长度为n的线性表时，每个元素的平均查找长度为。A）O（n2）B）O（nlog2n）C）O（n）D）O（log2n）6.有一个长度为12的有序表R[0…11]，按折半查找法对该表进行查找，在表内各元素等概率查找情况下查找成功所需的平均比较次数为。A）35/12B）37/12C）39/12D）43/127.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，99}，当采用折半查找法查找关键字为82的元素时，次比较后查找成功。A）1B.2C）4D）88.当采用分块查找时，数据的组织方式为。A）数据分成若干

3、块，每块内存数据有序B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C）数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D）数据分成若干块，每块（出最后一块外）中的数据个数需相同9.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应有个结点最佳。11A）10B）25C）6D）62510.不能生成右图所示二叉排序树的关键字序列是_____。A）45312B）42531C）45213D）4231511.按____遍历

4、二叉排序树，可以得到按值递增或递减次序的关键码序列。A）先序B）中序C）后序D）层序12.在一棵平衡二叉树中，每个结点的平衡因子的取值范围是。A）-1—1B）-2—2C）1—2D）0—113.具有5层结点的AVL树至少有个结点A）10B）12C）15D）1714.在含有15个结点的平衡二叉树上，查找关键字为28的结点，则依次比较的关键字可能是。A）30，36B）38，48，28C）48，18，38，28D）60，30，50，40，38，3615.一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有个结点。A）2k-1-

5、1B）2k-1C）2k-1+1D）2k-116.查找效率最高的二叉排序树是。A．所有结点的左子树都为空的二叉排序树B．所有节点的右子树都为空的二叉排序树C．平衡二叉树D．没有左子树的二叉排序树17.下面关于B-树和B+树的叙述中，不正确的结论是。A）B-树和B+树都能有效地支持顺序查找B）B-树和B+树都能有效地支持随机查找C）B-树和B+树都是平衡的多分支树D）B-树和B+树都可用于文件索引结构18.设有n个关键字，哈希查找法的平均查找长度是。A）O（1）B）O（n）C）O（log2n）D）O（n2）19.将10个元素散列到10000

6、0个单元的哈希表，则产生冲突。A）一定会B）一定不会C）仍可能会D）以上都不对20.设哈希表长m=14，哈希函数H（key）=keyMod1111.表中已有4个结点H（15）=4，H（38）=5，H（61）=6，H（84）=7，其余地址为空，如用二次探测再散列法处理冲突，则关键字为49的结点的地址是。A）8B）3C）5D）921.假设有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入哈希表中，至少要进行次探查。A）k-1B）kC）k+1D）k（k+1）/222.若采用链地执法构造哈希表，哈希函数为H（key）=keyMod1

7、7，则需（1）个链表，这些链表的首指针构成一个指针数组，该数组的下标范围为（2）。（1）A）17B）13C）16D）任意（2）A）0—17B）1—17C）0—16D）1—1623.直接插入排序在最好情况下的时间复杂度为。A）O（n）B）O（nlog2n）C）O（log2n）D）O（n2）24.稳定的排序算法是。A）直接插入排序B）直接选择排序C）堆排序D）快速排序25.数据序列{8，9，10，4，5，6，20，1，2}只能是算法的两趟排序后的结果。A）直接选择排序B）冒泡排序C）直接插入排序D）堆排序26.对数据序列{15，9，7，8，

8、20，-1，4}进行排序，进行一趟后数据的排序变为{9，15，7，8，20，-1，4}，则采用的是算法。A）直接选择排序B）冒泡排序C）直接插入排序D）堆排序27.以下排序方法中，在初始序列已基本有序的情况