查找与排序练习题

《查找与排序练习题》由会员分享，可在线阅读，更多相关《查找与排序练习题（3页珍藏版）》请在金锄头文库上搜索。

1、查找和排序练习题查找和排序练习题选择题选择题1静态查找表与动态查找表的根本区别在于（ ） A它们的逻辑结构不一样 B施加在其上的操作不一样 C所包含的数据元素不一样 D存储实现不一样 2在表长为 n 的顺序表上实现顺序查找，在查找不成功时与关键字比较的次数为（ ） An B1 Cn+1 Dn1 3顺序查找适用于存储结构为（ ）线性表 A散列存储 B压缩存储C顺序存储或链式存储D索引存储 4用顺序表查找法对具有 n 个结点的线性表查找一个结点的时间复杂度为（ ） AO(log2n2) BO(nlog2n) CO(n) DO(log2n) 5适用于折半查找的表的存储方式及元素排列要求为（ ） A链

2、接方式存储，元素无序 B链接方式存储，元素有序 C顺序方式存储，元素无序 D顺序方式存储，元素有序 6有一个长度为 12 的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况 下查找成功所需的平均比较次数为（ ） A35/12 B37/12 C39/12 D43/12 7在有序表1，3，9，12，32，41，62，75，77，82，95，100上进行折半查找关键字 为 82 的数据元素需要比较（）次 A1 B2 C4 D5 8设散列长度为 14，散列函数为 H（key）=key%11。当前表中有 4 个结点，addr（15） =4，addr(38)=5，addr(61)=6，addr(

3、84)=7。如用二次探测在散列处理冲突，则关键字为 49 的结点的地址是（ ） A8 B3 C5 D9 9散列函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。 A最大概率 B最小概率 C平均概率 D同等概率 10假定有 k 个关键字互为同义词，若用线性探测法把这 k 个关键字存入散列表中，至少 要进行多少次探测（） Ak-1 次 Bk 次 Ck+1 次 Dk(k+1)/2 次 11在散列函数 H(k)=k%m 中，一般来讲，m 应取（ ） A奇数 B偶数 C素数 D充分大的数 12在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查 找成功的情况下，所探测到的

4、这些位置上的键值（） A一定是同义词B一定不是同义词C都相同D不一定是同义词 13采用分块查找时，若线性表中有 625 个元素，查找每个元素的概率相同，假设采用顺 序法查找来确定结点所在的块，每块应分（）结点最佳 A10 B25 C6 D625 14下列关于 m 阶 B 树的说法错误的是（） A根结点至多有 m 棵子树 B所有叶子上都在同一层次上 C非叶结点至少有 m/2(m 为偶数)或 m/2+1(m 为奇数)棵子树 D根结点中的数据是有序的15m 阶 B 树是一棵（） Am 叉排序树Bm 叉平衡排序树 Cm1 叉平衡排序树 Dm+1 叉平衡排序树判断题判断题1顺序查找可以在顺序表上进行不能

5、在单链表上进行。 （ ） 2折半查找只能在有序的顺序上进行。 （） 3对于给定的关键字集合，以不同的次序插入到初始为空的二叉排序树中，得到的二叉排 序树是相同的。 （ ） 4若二叉排序树中关键字互不相同，那么最小值结点必定无左孩子，最大值结点必定无右 孩子。 （ ） 5在二叉排序树中，最大值结点和最小值结点一定是叶子结点。 （ ） 6在二叉排序树 T1的先序遍历序列依次插入初始为空的树中，所得到的二叉排序树 T2和 T1的形态完全相同。 （ ） 7对二叉排序树进行中序遍历得到的序列是由小到大有序的。 （ ） 8二叉树为二叉树排序树的充分必要条件是任一非终端结点的值大于其左孩子的值，小于 右孩子

6、的值。 （ ） 9二叉排序树的查找和折半查找的时间复杂度都是 O（log2n） ，时间性能相同。 （ ） 10采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。 （ ） 11采用线性探测法处理冲突时，当从散列表中删除一个记录时，不应将这个记录的所在 位置为空，因为这将会影响今后的查找。 （ ） 12m 阶 B 树每一个结点的子树个数都小于或等于 m。 （ ） 13散列表的查找效率主要取决于构造散列表时选取的散列函数和处理冲突的方法。 （ ） 14散列法存储的基本思想是由关键码的值决定数据的存储地址。 （ ） 15当负载因子 a 小于 1 时，则向散列表中插入元素时不会引起冲突。

7、 （ ） 16查找表中数据元素的任何数据项都可以作为关键字。 （ ） 17m 阶 B 树任何一个结点的所有子树的高度都相等。 （ ） 18在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点相应的指针域置 空即可。 （ ） 19在散列存储方式中，负载因子的值越大，存取元素时发生冲突的可能性就越大。 （ ） 20对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历他们得到的序列的 顺序是一样的。 （ ）选择题选择题1在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ） A插入排序 B选择排序 C快速排序 D归并排序 2设有 1000 个无序的元素，希望用最快的速度挑选出其

8、中前 10 个最大的元素，最好选用 哪种排序法？（ ） A冒泡排序 B快速排序 C堆排序 D基数排序 3具有 12 个记录的序列，采用冒泡排序最少的比较次数是（ ） A1 B144 C11 D66 4下列 4 种排序方法中，要求内存容量最大的是（ ） A插入排序 B选择排序 C快速排序 D归并排序 5初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为（ ）An Bnlog2n Clog2n Dn1 6有四种排序方法，在排序过程中，关键码比较的次数与记录的初始排序顺序无关的是 （） A直接插入排序和快速排序 B快速排序和归并排序 C直接选择排序和归并排序 D直接插入排序和归并排序

9、 7一组记录的排序码为（46，79，56，38，40，84） ，则利用堆排序的方法建立的初始堆 为（ ） A79，46，56，38，40，84B84，79，56，38，40，46 C84，79，56，46，40，38D84，56，79，40，46，38 8一组记录的排序码为（46，79，56，38，40，84） ，则利用快速排序的方法，以第 1 个 记录为基准得到的一次划分的结果为（ ） A38，40，46，56，79，84B40，38，46，79，56，84 C40，38，46，56，79，84D40，38，46，84，56，79 9用某种排序方法对线性表（25，84，21，47，15，27

10、，68，35，20）进行排序时，元素 序列的变化情况如下 25，84，21，47，15，27，68，35，20 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则采用排序方法是（ ） A选择排序 B希尔排序 C归并排序 D快速排序 10快速排序方法在（ ）情况下最不利于发挥其长处 A要排序的数据量太大B要排序的数据中含有多个的相同值 C要排序的数据已基本有序D要排序的数据个数为奇数判断题判断题1插入排序是稳定的，选择排序是不稳定的。 （） 2不稳定的排序算法是没有实用价值的。 （）

11、 3当待排序的元素很多时，为了交换元素的位置，移动元素要占较多的时间，这是影响时 间复杂度的主要原因。 （） 4对有 n 个记录的集合进行归并排序，所需要的辅助空间数与初始记录的排列状况有关。 （） 5对有 n 个记录的集合进行快速排序，所需要的附加空间数是 O(n)。 （） 6堆排序所需要的附加空间数与待排序的记录个数无关。 （） 7对有 n 个记录的集合进行冒泡排序，所需时间决定于初始记录的排列情况，在初始记录 无序的情况下最好。 （ ） 8对有 n 个记录的集合进行快速排序，所需时间决定于初始记录的排列情况，在初始记录 无序的情况下最好。 （ ） 9对不稳定的排序算法，不论采用任何描述方法，总能举出一个说明它不稳定的实例来。 （） 10选择排序的比较次数不会随待排序记录的关键字的分布情况而变化。 （ ）