数据结构查找与排序练习题——查找排序练习题

一、单选题1．下列查找方法中，不属于动态的查找方法是( )。

A ．二叉排序树法B ．平衡树法C ．散列法D ．二分查找法2．适用于静态的查找方法为( )。

A ．二分查找、二叉排序树查找B ．二分查找、索引顺序表查找C ．二叉排序树查找、索引顺序表查找D ．二叉排序树查找、散列法查找3．静态查找表与动态查找表二者的根本差别在于( )。

A ．它们的逻辑结构不一样B ．施加在其上的操作不同C ．所包含的数据元素的类型不一样D ．存储实现不一样4．对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为( )。

A ．5.5B ．5C ．39/8D ．19/45．( )存储方式适用于折半查找。

A ．键值有序的单链表B ．键值有序的顺序表C ．键值有序的双链表D ．键值无序的顺序表6．对线性表进行二分查找时，要求线性表必须( )。

A ．以顺序方式存储B ．以链接方式存储C ．顺序存储，且结点按关键字有序排序D ．链式存储，且结点按关键字有序排序7．在索引顺序表中查找一个元素，可用的且最快的方法是( )。

A ．用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找B ．用顺序查找法确定元素所在块，再用二分查找法在相应块中查找C ．用二分查找法确定元素所在块，再用顺序查找法在相应块中查找D ．用二分查找法确定元素所在块，再用二分查找法在相应块中查找8．在索引查找中，若主表长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。

A ．13B ．24C ．12D ．799．由同一关键字集合构造的各棵二叉排序树( )。

A ．形态和平均查找长度都不一定相同B ．形态不一定相同，但平均查找长度相同C ．形态和平均查找长度都相同D ．形态相同，但平均查找长度不一定相同10．对二叉排序树进行( )，可以得到各结点键值的递增序列。

1、静态查找表和动态查找表的区别是( )。

A.所包含的数据元素的类型不同B.施加其上的操作不同C.它们的逻辑结构相同D.以上都不对正确答案：B解析：B、若在查找的同时对表做修改操作(如插入和删除)，则相应的查找表称之为动态查找表。

若在查找中不涉及表的修改操作，则相应的查找表称之为静态查找表。

2、顺序查找法适合于存储结构为( )的线性表。

A.索引存储B.压缩存储C.顺序存储或者链式存储D.哈希存储正确答案：C解析：C、顺序查找可以从前向后或者从后向前挨次查找，既适合于顺序存储结构也适合于链式存储结构。

3、采用顺序查找方法查找长度为n 的顺序表时，在等概率时成功查找的平均查找长度为( )。

A.(n-1)/2B.nC.n/2D.(n+1)/2正确答案：D解析：D、顺序查找时，元素ai 需i 次比较，成功查找的平均查找长度=(1+2+ …+n)/n=(n+1)/2。

4、采用顺序查找方法查找长度为n 的顺序表时，在等概率时不成功查找的平均查找长度为( )。

A.(n-1)/2B.nC.n/2D.(n+1)/2正确答案：B解析：B、当查找的元素不在线性表中时，均需要n 次元素之间的比较。

5、适合于折半查找的数据组织方式是( )。

A.以链表存储的有序线性表B.以顺序表存储的有序线性表C.以链表存储的线性表D.以顺序表存储的线性表正确答案：B解析：B、折半查找的数据必须是有序的。

此外，折半查找中需要确定查找区间，这要求存储结构最好具有随机存取特性，而顺序表满足这个特性。

6、采用折半查找方法查找长度为n 的线性表，当n 很大时，在等概率时不成功查找的平均查找长度为( )。

n)A. O(nlog2B. O(n2)C. O(n)n)D. O(log2正确答案：D解析：D、采用折半查找时，若n 很大，对应的判定树可以看成是一棵满二叉树，失败节点(外部节点)集中在最下一层，落在每一个失败节点时比较的次都均为log n。

27、设有100 个元素的有序表，采用折半查找方法，在等概率时成功时最大的比较次数是( )。

数据结构查找排序经典试题一、填空1、针对有n条记录的顺序表做顺序查找，假定各记录的查找机会均等，则平均查找长度ASL=_______。

2、在二叉平衡树中，平衡因子hl-hr的所有可能取值有____________。

3、在排序操作中，待排序的记录有n条，若采用直接插入排序法，则需进行_________趟的插入才能完成排序。

4、在排序操作中，待排序的记录有n条，若采用冒泡排序法，则至多需进行_________趟的排序。

5、直接插入排序算法的时间复杂度为________________。

6、按（）遍历二叉排序树，可以得到按值递增的关键字序列，在下图所示的二叉排序树中，查找关键字85的过程中，需和85进行比较的关键字序列为（）。

509520557010 30 85二、判断1、平衡二叉树中子树的深度不能大于1。

（）2、快速排序法是稳定的排序方法。

（）3、任何一种排序方法都必须根据关键字值比较的结果来将记录从一个地方移动到另一个地方。

（）4、冒泡排序法是稳定的排序方法。

（）5、折半插入排序法是稳定的排序方法。

（）三、选择1、在排序操作中，待排序的记录有n条，若采用直接插入排序法，则需进行_________趟的插入才能完成排序。

A、nB、(n-1)/2C、n+1D、n-12、采用顺序查找法查找长度为n的线性表时，平均查找长度为（）A、nB、(n-1)/2C、n/2D、(n+1)/23、用折半查找法在{11,33,55,77,99,110,155,166,233}中查找155需要进行（）次比较。

A、1B、2C、3D、44、请指出在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用折半查找法查找12需做（）次比较。

A、5B、4C、3D、25、如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

（）就是不稳定的排序方法。

A、起泡排序B、归并排序C、直接插入排序D、简单选择排序四、综合题1、给定一组数{6，7，9，4，3，5，8}，要求（a）构造一棵平衡的二叉排序树；（b）先根遍历该树；（c）从该树中删除结点6，并保持其特性。

查找与排序部分习题一、选择题1.设有100个元素，用折半查找法进行查找时，最大比较次数是______。

Ａ、25 B、8 C、10 D、72.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查找值82的结点时，______次比较后查找成功。

（注：计算中间位置时取下整）A、1B、2C、4D、83.顺序查找法适合于存储结构为______的线性表。

A、散列存储B、顺序存储或链接存储C、压缩存储D、索引存储4.某顺序存储的表格中有90000个元素，以按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同，用顺序查找法查找时，平均比较次数约为______；最大比较次数约为______。

A、25000B、30000C、45000D、900005.设散列地址空间为0到m-1，k为关键字，用p去除k，将所得的余数作为k的散列地址，即H（k）=k%p。

为了减少发生冲突的频率，一般取p为______。

A、小于m的最大奇数B、小于m的最大偶数C、小于m的最大素数D、大于m的最大素数6.设有9个数据记录组成的线性表，它们的排序关键字的取值分别是（11，15，20，27，30，35，46，88，120），已将它们按照排序关键字递增有序的方式存放在一维结构数组a[0..8]中从下标0开始到下标8结束的位置，则当采用折半查找算法查找关键字值等于20的数据记录时，所需比较的元素下标依次是：______。

（注：计算中间位置时取下整）A、0，1，2B、4，1，2C、4，2D、4，3，27.顺序查找一个共有n个元素的线性表，其时间复杂度为______。

A、O(n)B、O(log2n)C、O(n2)D、O(nlog2n)8.设有100个元素，用折半查找法进行查找时，最小比较次数是______。

A、7B、4C、2D、19.哈希法中，除了考虑构造“均匀”的哈希函数外，还要解决冲突的问题，以下选项中______不是解决冲突的办法。

第九章查找一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A． (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 下面关于二分查找的叙述正确的是 ( )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储3. 用二分（对半）查找表的元素的速度比用顺序法( )A．必然快 B. 必然慢 C. 相等 D. 不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度（）A. 3.1B. 4C. 2.5D. 55．当采用分块查找时，数据的组织方式为 ( )A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同6. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案:A. 相同的B.不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130）D. (100，80， 60， 90， 120，130，110)10. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。

习题——查找与排序篇1、在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为（）A）63 B）64 C）6 D）72、在长度为N的有序线性表中进行二分法查找,最坏情况下需要比较的次数是（）A）O(N) B）O(N2) C）O(㏒2N) D）O(N㏒2N)3、下列数据结构中，能用二分法进行查找的是（）A）顺序存储的有序线性表B）线性链表C）二叉链表D）有序线性链表4、请写出用二分查找法在有序顺序表(1,2,3,4,6,8,9,11)中查找3的比较序列：5、下列叙述中正确的是（）A）对长度为n的有序链表进行查找，最坏情况下需要的比较次数为nB）对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2)C）对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)D）对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n)6、在长度为n的线性表中，寻找最大项至少要比较_ __次7、下列排序方法中，最坏情况下比较次数最少的是（）A）冒泡排序B）简单选择排序C）直接插入排序D）堆排序8、支持子程序调用的数据结构是（）A）栈B）树C）队列D）二叉树9、对长度N的线性表排序,在最坏情况下,比较次数不是N(N-1)/2的排序方法是（）A）快速排序B）冒泡排序C）直接插入排序D）堆排序10、冒泡排序在最坏情况下的比较次数是（）A）N(N+1)/2 B）N㏒2N C）N(N-1)/2 D）N/211、通过相邻数据元素的交换逐步将线性表变成有序的排序方法是（）A）冒泡排序法B）简单选择排序法C）简单插入排序法D）希尔排序法12、对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为_ _13、序列(5,1,7,3,1,6,9,3,2,7,6)从大到小排列，冒泡排序第一遍扫描后结果__ ____14、如果一个算法P显式地调用自己称为__ ___，如果算法P调用另一个算法Q，而算法Q又调用算法P，则称为__ ____15、以下排序技术中属于交换类排序法的有________，属于插入类排序法的有___________，属于选择类排序法的有__________1.希尔排序2.堆排序3.冒泡排序4.简单选择排序5.简单插入排序6.快速排序16、下列排序方法中，最坏情况下比较次数最少的是（）A）冒泡排序B）简单选择排序C）直接插入排序D）堆排序。

Python数据结构与算法50排序与查找编程练习题1快速排序主元注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。

本文阅读时间约为5分钟。

著名的快速排序算法里有一个经典的划分过程：我们通常采用其中一种方法取一个元素作为主元（中值），通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。

给定划分后的N个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？例如给定的排列是[1, 3, 2, 4, 5]。

则：• 1 的左边没有元素，右边的元素都比它大，所以它可能是主元；•尽管 3 的左边元素都比它小，但其右边的 2 比它小，所以它不能是主元；•尽管 2 的右边元素都比它大，但其左边的 3 比它大，所以它不能是主元；•类似原因，4 和 5 都可能是主元。

因此，有 3 个元素可能是主元。

输入格式:一行数个整数的排列，由空格分隔。

输出格式：在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：1 32 4 5输出样例：3 14 5解答：判断一组数是否符合要求，把这组数分三类来分别判断：•第一类，去掉头尾的中间所有的数，判断条件是，大于其左边所有数中最大的，同时也要小于右边所有数中最小的。

•第二类，第一个数，即头部的数，判断条件是，小于右边所有数中最小的。

但是，基于第一类数的判断条件，只需要小于第二个数即可。

•第三类，最后一个数，即尾部的数，判断条件是，大于左边所有数中最大的。

但是，基于第一类数的判断条件，只需要大于倒数第二个数即可。

最后，因题意明确说了一组不相等的整数，故不用考虑等于的情况，直接用大于或小于即可。

参考代码如下：# 排序与查找编程练习题1：快速排序主元。

s = input( l = list(map(int, s.split(' '))) l1 = [] # 第一类数的判断。

第９章查找一、单选题1.对一棵二叉搜索树按（）遍历,可得到结点值从小到大得排列序列。

A、先序ﻩB、中序ﻩC、后序ﻩD、层次2.从具有n个结点得二叉搜索树中查找一个元素时,在平均情况下得时间复杂度大致为(）。

A、O（n) ﻩB、O（1）ﻩC、O(loｇn) ﻩD、Ｏ（ｎ2）3.从具有n个结点得二叉搜索树中查找一个元素时，在最坏情况下得时间复杂度为(）.A、O（ｎ) ﻩB、Ｏ(1) ﻩC、O（logｎ) ﻩﻩD、O（n２)4.在二叉搜索树中插入一个结点得时间复杂度为(）。

A、O（1）ﻩﻩﻩB、O（ｎ)ﻩC、O(logn)ﻩﻩD、O（n２)5.分别以下列序列构造二叉搜索树,与用其它三个序列所构造得结果不同得就是()。

Ａ。

（1００，80，90，6０，１20,１１0，130）B、(10０，120,110,130，80，6０, 90）C、(１0０,60, 8０, 9０,120，１１0,1３0)Ｄ、（10０，８0，６0，90，１20，１３0，110）6.在一棵AVＬ树中，每个结点得平衡因子得取值范围就是(）。

A、—1~１B、—2～２Ｃ、1～2 ﻩD、０~17.根据一组关键字（56,42，５0,64，４８)依次插入结点生成一棵ＡVL树,当插入到值为(）得结点时需要进行旋转调整。

A、4２ﻩﻩB、５0ﻩﻩC、６4ﻩﻩD、488.深度为４得ＡVL树至少有（)个结点。

A。

9 B、8ﻩﻩC、7ﻩﻩD、69.一棵深度为k得A VL树，其每个分支结点得平衡因子均为０,则该平衡二叉树共有（)个结点。

A、2k—1—１ﻩﻩB、2k-1+1ﻩC、2k－1 ﻩD、２k10.在A VL树中插入一个结点后造成了不平衡,设最低得不平衡结点为A，并已知A得左孩子得平衡因子为0,右孩子得平衡因子为1，则应作( ）型调整以使其平衡。

A、LLB、ＬR Ｃ、RL D、RR二、判断题1.二叉搜索树得任意一棵子树中，关键字最小得结点必无左孩子，关键字最大得结点必无右孩子。

数据结构查找与排序练习题一、选择题1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/22.适用于折半查找的表的存储方式及元素排列要求为( )A．链接方式存储，元素无序 B．链接方式存储，元素有序C．顺序方式存储，元素无序 D．顺序方式存储，元素有序3.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减4．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。

A．35/12 B.37/12 C.39/12 D.43/125.折半查找的时间复杂性为（）A. O（n2）B. O（n）C. O（nlogn）D. O（logn）6.对有18个元素的有序表作折半查找，则查找A[3]的比较序列的下标为（）A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，37.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。

A.2B. 3C. 4D.128.用n个键值构造一棵二叉排序树，最低高度为（）A.n/2B.、nC.lognD.logn+19．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130）B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130）D.(100，80， 60， 90， 120，130，110)10.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key% 13,散列地址为1的链中有（）个记录。

第9章查找一、单选题1.对一棵二叉搜索树按〔〕遍历，可得到结点值从小到大的排列序列。

A. 先序B. 中序C. 后序D. 层次2.从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂度大致为〔〕。

A. O(n)B. O(1)C. O(logn)D. O(n2)3.从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂度为〔〕。

A. O(n)B. O(1)C. O(logn)D. O(n2)4.在二叉搜索树中插入一个结点的时间复杂度为〔〕。

A. O(1)B. O(n)C. O(logn)D. O(n2)5.分别以下列序列构造二叉搜索树，与用其它三个序列所构造的结果不同的是〔〕。

A．〔100，80，90，60，120，110，130〕B.〔100，120，110，130，80，60，90〕C.〔100，60，80，90，120，110，130〕D.〔100，80，60，90，120，130，110〕6.在一棵AVL树中，每个结点的平衡因子的取值X围是〔〕。

A. -1~1B. -2~2C. 1~2D. 0~17.根据一组关键字〔56，42，50，64，48〕依次插入结点生成一棵A VL树，当插入到值为〔〕的结点时需要进行旋转调整。

A. 42B. 50C. 64D. 488.深度为4的A VL树至少有〔〕个结点。

A．9 B.8C.7D.69.一棵深度为k的A VL树，其每个分支结点的平衡因子均为0，则该平衡二叉树共有〔〕个结点。

A.2k-1-1B.2k-1+1C.2k-1D.2k10.在A VL树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作〔〕型调整以使其平衡。

A. LLB. LRC. RLD. RR二、判断题1.二叉搜索树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。

2.二叉搜索树中每个结点的关键字值大于其左非空子树〔若存在的话〕所有结点的关键字值，且小于其右非空子树〔若存在的话〕所有结点的关键字值。

查找和排序练习题选择题1．静态查找表与动态查找表的根本区别在于（）A．它们的逻辑结构不一样B．施加在其上的操作不一样C．所包含的数据元素不一样D．存储实现不一样2．在表长为n的顺序表上实现顺序查找，在查找不成功时与关键字比较的次数为（）A．n B．1 C．n+1 D．n－13．顺序查找适用于存储结构为（）线性表A．散列存储B．压缩存储C．顺序存储或链式存储D．索引存储4．用顺序表查找法对具有n个结点的线性表查找一个结点的时间复杂度为（）A．O(log2n2) B．O(nlog2n) C．O(n) D．O(log2n)5．适用于折半查找的表的存储方式及元素排列要求为（）A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序6．有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）A．35/12 B．37/12 C．39/12 D．43/127．在有序表｛1，3，9，12，32，41，62，75，77，82，95，100｝上进行折半查找关键字为82的数据元素需要比较（）次A．1 B．2 C．4 D．58．设散列长度为14，散列函数为H（key）=key%11。

当前表中有4个结点，addr（15）=4，addr(38)=5，addr(61)=6，addr(84)=7。

如用二次探测在散列处理冲突，则关键字为49的结点的地址是（）A．8 B．3 C．5 D．99．散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。

A．最大概率B．最小概率C．平均概率D．同等概率10．假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测（）A．k-1次B．k次C．k+1次D．k(k+1)/2次11．在散列函数H(k)=k%m中，一般来讲，m应取（）A．奇数B．偶数C．素数D．充分大的数12．在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测到的这些位置上的键值（）A．一定是同义词B．一定不是同义词C．都相同D．不一定是同义词13．采用分块查找时，若线性表中有625个元素，查找每个元素的概率相同，假设采用顺序法查找来确定结点所在的块，每块应分（）结点最佳A．10 B．25 C．6 D．62514．下列关于m阶B树的说法错误的是（）A．根结点至多有m棵子树B．所有叶子上都在同一层次上C．非叶结点至少有m/2(m为偶数)或m/2+1(m为奇数)棵子树D．根结点中的数据是有序的15．m阶B树是一棵（）A．m叉排序树B．m叉平衡排序树C．m－1叉平衡排序树D．m+1叉平衡排序树判断题1．顺序查找可以在顺序表上进行不能在单链表上进行。

第九章查找一、选择题1。

若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A． (n—1)/2 B. n/2 C。

（n+1）/2 D。

n2. 下面关于二分查找的叙述正确的是（ )A。

表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B。

表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储3. 用二分(对半）查找表的元素的速度比用顺序法（ )A．必然快 B. 必然慢 C. 相等 D. 不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度( ）A. 3。

1 B。

4 C. 2。

5 D. 55．当采用分块查找时,数据的组织方式为 ( ）A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序,但块间必须有序，每块内最大(或最小）的数据组成索引块C。

数据分成若干块，每块内数据有序，每块内最大(或最小）的数据组成索引块D. 数据分成若干块,每块（除最后一块外)中数据个数需相同6。

二叉查找树的查找效率与二叉树的( （1）)有关, 在（（2）)时其查找效率最低（1）: A。

高度 B。

结点的多少 C. 树型 D. 结点的位置(2）: A。

结点太多 B. 完全二叉树 C。

呈单枝树 D. 结点太复杂。

7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败，它们的平均查找长度是((1）） ,对于查找成功，他们的平均查找长度是（（2））供选择的答案：A。

相同的 B。

不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）A．(100,80， 90， 60， 120，110，130） B。

（100，120，110,130，80， 60, 90) C。

（100，60, 80， 90, 120，110，130） D。

数据结构练习第⼋章查找数据结构练习第⼋章查找1.若有18个元素的有序表存放在⼀维数组A[19]中，第⼀个元素放A[1]中，现进⾏⼆分查找，则查找A［3］的⽐较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，32．设⼆叉排序树中有n个结点，则在⼆叉排序树的平均平均查找长度为（）。

A. O(1)B. O(log2n)C. O(n)D. O(n2)3．在⼆叉排序树中插⼊⼀个结点的时间复杂度为（）。

A. O(1)B. O(n)C. O(log2n)D. O(n2)4．设有序顺序表中有n个数据元素，则利⽤⼆分查找法查找数据元素X的最多⽐较次数不超过（）。

A. log2n+1B. log2n-1C. log2nD. log2(n+1) 5．设有序表中有1000个元素，则⽤⼆分查找查找元素X最多需要⽐较（）次。

A. 25B. 10C. 7D. 16．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。

A. O(n)B. O(n2)C. O(n1/2)D. O(1og2n) 7．设⼆叉排序树上有n个结点，则在⼆叉排序树上查找结点的平均时间复杂度为（）。

A. O(n)B. O(n2)C. O(nlog2n)D. O(1og2n) 8．（）⼆叉排序树可以得到⼀个从⼩到⼤的有序序列。

A. 先序遍历B.中序遍历C. 后序遍历D. 层次遍历9．设⼀组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利⽤⼆分法查找关键字90需要⽐较的关键字个数为（）。

A. 1B. 2C. 3D. 410．设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。

A. 99B. 97C. 91D. 9311．在⼆叉排序树中插⼊⼀个关键字值的平均时间复杂度为（）。

A. O(n)B. O(1og2n)C. O(nlog2n)D. O(n2)12．设⼀个顺序有序表A[1:14]中有14个元素，则采⽤⼆分法查找元素A[4]的过程中⽐较元素的顺序为( )。

数据结构查找与排序练习题答案一、选择题1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/22.适用于折半查找的表的存储方式及元素排列要求为( )A．链接方式存储，元素无序 B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序3.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减4．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。

A．35/12 B.37/12 C.39/12 D.43/125.折半查找的时间复杂性为（）A. O（n2）B. O（n）C. O（nlogn）D. O（logn）6.对有18个元素的有序表作折半查找，则查找A[3]的比较序列的下标为（）A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，37.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。

A.2B. 3C. 4D.128.用n个键值构造一棵二叉排序树，最低高度为（）A.n/2B.、nC.lognD.logn+19．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130）B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130）D.(100，80， 60， 90， 120，130，110)10.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key% 13,散列地址为1的链中有（）个记录。

一、单选题1、关于折半查找，以下说法正确的是 ( ) 。

A.待查找表必须有序，可以顺序方式存储，也可以链表方式存储B.待查找表必须有序，且只能以顺序方式存储C.待查找表必须有序，而且必须从小到大排列D.待查找表必须有序且表中数据必须是整型正确答案：B2、具有12个关键字的有序表，折半查找的平均查找长度（）。

A.2.5B.37/12C.10/12D.25/12正确答案：B3、以下适合用分块查的数据集是 ( ) 。

A.数据分成大小相等的若干块，块内数据有序B.数据分成若干块，每块（除最后一块外）中数据个数需相同C.数据分成若干块，块内数据必须有序，块间不必有序D.数据分成若干块，块内数据不必有序，但块间必须有序正确答案：D4、分别以下列序列构造二叉排序树，以下哪一个和其他三个不同( ) 。

A.（90,65,25,110,100,107,87,85）B.(90,65,110,100,107,87,85,25)C. (90,110,65,25,87,100,107,85）D.（90,100,65,25,87,85,110,107）正确答案：D5、关于哈希查找，以下说法不正确的是( ) 。

A.哈希查找中，记录的存储地址是计算出来的，因而不需要比较B.链地址法和线性探测再散列都是解决冲突的方法C.装填因子越大，越容易产生冲突D.哈希查找有两个关键问题：哈希函数和处理冲突的方法正确答案：A6、对长度为4的顺序表进行查找，查找顺序从前向后。

若查找前面2个元素的概率均为1/8，查找后2个元素的概率均为3/8，则查找任一元素的平均查找长度为( )。

A.19/4B.39/8C.5.5D.3正确答案：D7、由同一关键字集合构造的各棵二叉排序树( )。

A.形态相同，但平均查找长度不一定相同B.形态和平均查找长度都相同C.形态不一定相同，但平均查找长度相同D.形态和平均查找长度都不一定相同正确答案：D8、100个元素进行折半查找，查找成功时最大的比较次数是（）。

数据结构图,查找,内排序的练习及答案数据结构课后练习习题要求：此次练习不要求上交，只是帮助⼤家掌握知识点，便于复习。

第⼋章图⼀．单项选择题（20分）1. 带权有向图G ⽤邻接矩阵A 存储，则Vi 的⼊度等于A 中___D______A. 第i ⾏⾮∞的元素只和B. 第i 列⾮∞的元素之和C. 第i ⾏⾮∞且⾮0的元素之和D. 第i 列⾮∞且⾮0的元素个数2. ⽆向图的邻接矩阵是⼀个___A____A. 对称矩阵B. 零矩阵C. 上三⾓阵D. 对⾓矩阵3. 在⼀个⽆向图中，所有顶点的度之和等于边数的__C____倍A. 1/2B. 1C. 2D. 44. ⼀个有n 个顶点的⽆向图最多有___C____条边。

A. nB. n(n-1)C. n(n-1)/2D.2n5. 对于⼀个具有n 个顶点的⽆向图，若采⽤邻接矩阵表⽰，则该矩阵⼤⼩是__D_____A. nB. 2)1(?nC. n-1D. 2n6. ⼀个有向图G 的邻接表存储如右图所⽰，现按深度优先搜索遍历，从V1出发，所得到的顶点序列是___B_____。

A. 1，2，3，4，5B. 1，2，3，5，4C. 1，2，4，5，3D. 1，2，5，3，47. 对右图所⽰的⽆向图，从顶点V1开始进⾏深度优先遍历，可得到顶点访问序列__A______（提⽰：可先画出邻居表图再遍历）A. 1 2 4 3 5 7 6B. 1 2 4 3 5 6 7C. 1 2 4 5 6 3 7D. 1 2 3 4 5 6 78. 如果从⽆向图的任⼀顶点出发进⾏⼀次深度优先搜索即可访问所有顶点，则该图⼀定是__B_____A. 完全图B. 连通图C.有回路D. ⼀棵树9. 任何⼀个⽆向连通图___B___最⼩⽣成树（提⽰：注意最⼩⽣成树的定义，此题易错）A. 只有⼀棵B. ⼀棵或多棵C. ⼀定有多棵D.可能不存在11. 若图的邻接矩阵中主对⾓线上的元素全是0，其余元素全是1，则可以断定该图⼀定是_D_____。

一、单选题1、对于查找表(13,27,38,49,50 ,65,76,97)采用顺序查找，在等概率情况下查找成功的平均查找长度是( )。

A.4.5B.9C.4D.8正确答案：A2、在关键字序列( 10,20,30,40,50)中采用折半查找20 ，挨次与( )关键字进行了比较。

A.30,10,20B.20C.30,20D.40,20正确答案：A3、在关键字序列(8,12,20,25,33)中，采用二分查找25 ，关键字之间比较需要( ) 次。

A.2B.1C.3D.4正确答案：A4、对于长度为11 的有序表，按折半查找，在等概率情况下查找成功时，其平均查找长度是( )。

A.3B.4C.1D.2正确答案：A5、对于长度为11 的有序表，按折半查找，在查找失败时，待查找值域表中关键字比较的次数是( )。

A.3 次或者4 次B.2 次或者3 次C.4 次或者5 次D.1 次或者2 次正确答案：A6、对于长度为n 的有序表，按折半查找，在等概率情况下查找成功平均时间复杂度是( )。

A.O(㏒n)B.O(n)C.O(1)D.O(n ㏒n)正确答案：A7、索引顺序查找也叫分块查找，其查找过程分为是( )个步骤。

A.1B.3C.4D.2正确答案：D8、对于长度为n 的关键字序列创建一颗二叉排序树，该树可能的最大高度是( )。

A.n+1B.n-1C.㏒nD.n正确答案：D9、对于关键字序列(30,25,40,35,45) ，按序列次序创建一颗二叉排序树，在等概率情况下查找成功时，其平均查找长度是( )。

A.8/3B.11/5C.8D.11正确答案：B10、影响散列查找时间效率的主要因素( )。

A.仅与散列表中实际元素个数相关B.仅与散列表长相关C.与散列表长和散列表中实际元素个数均相关D.与散列表长和散列表中实际元素个数均不相关正确答案：C11、一组关键字序列为(27，17，9，19，16，43，53，8，63) ，用哈希函数H(key)=key MOD 8 和链地址法处理冲突，查找关键字43 ，与散列表中关键字进行了( )次比较。

一、单选题12．设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用( )法。

A．冒泡排序B．快速排序C．堆排序D．归并排序1．已知持排序的n个元素可分为n/k个组，每个组包含k个元素，各组间分块有序，若采用基于比较的排序，其时间下界应为：( )A．O(nlog2n) B．O(nlog2k) C．O(klog2n) D．O(klog2k))且稳定的排序方法是( )。

2．最好和最坏时间复杂度均为O(nnlog2A．快速排序B．堆排序C．归并排序D．基数排序3．下列排序算法中，当初始数据有序时，花费时间反而最多的是( )。

A．起泡排序B．希尔排序C．堆排序D．快速排序4．若需在O（nlog2n）的时间内完成排序，且要求稳定，则可选择（）A．快速排序B．堆排序C．归并排序D．直接插入排序5．排序趟数与序列的原始状态有关的排序方法是( )排序法。

A．插入B．选择C．希尔D．快速6．已知数据表每个元素距离其最终位置不远，则最省时间的排序算法是( )。

A．堆排序B．直接插入排序C．快速排序D．直接选择排序7．关键字比较次数与数据的初始状态无关的排序算法是( )。

A．直接选择排序B．冒泡排序C．直接插入排序D．希尔排序8. 若一个元素序列基本有序，则选用（）方法较快。

A．直接插入排序B．直接选择排序C．堆排序D．快速排序9. 若要从1000个元素中得到4个最小值元素，最好采用（）方法。

A．直接插入排序B．直接选择排序C．堆排序D．快速排序10. 若要对1000个元素排序，要求既快又稳定，则最好采用（）方法。

A．直接插入排序B．归并排序C．堆排序D．快速排序11. 若要对1000个元素排序，要求既快又节省存储空间，则最好采用（）方法。

A．直接插入排序B．归并排序C．堆排序D．快速排序12. 在下列排序方法中，空间复杂性为O(log2n)的方法为（）。

A．直接选择排序B．归并排序C．堆排序D．快速排序13. 在平均情况下速度最快的排序方法为（）。

第九章查找一、选择题1、已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（）次。

A.1B.2C.3D.43、解决哈希冲突的主要方法有（）。

A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、再哈希法D.线性探测法、再哈希法、链地址法4、在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。

A.nB.log2nC.(h+1)/2D.h5、已知表长为25的哈希表，用除留取余法，按公式H(key)=key MOD p建立哈希表，则p应取（）为宜。

A.23B.24C.25D.266、设哈希表长m=14,哈希函数H(key)=key MOD11。

表中已有4个结点：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为（）。

A.8B.3C.5D.99、m阶B-树中的m是指（）。

A.每个结点至少具有m棵子树B.每个结点最多具有m棵子树C.分支结点中包含的关键字的个数D.m阶B-树的深度10、一个待散列的线性表为k={18,25,63,50,42,32,9}，散列函数为H(k)=k MOD9，与18发生冲突的元素有（）个。

A.1B.2C.3D.411、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中，这种方式主要适合于（）。

A.静态查找表B.动态查找表C.静态查找表和动态查找表D.两种表都不适合12、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为82的结点时，（B）次比较后查找成功。

A.1B.4C.2D.813、在各种查找方法中，平均查找承担与结点个数n无关的查找方法是（）。

A.顺序查找B.折半查找C.哈希查找D.分块查找14、下列二叉树中，不．平衡的二叉树是（）。