数据结构习题-5

第8章 查找8.1选择题1顺序查找法适合于存储构造为（）的线性表。 A）散列存储 B）顺序存储或链接存储 C）压缩存储 D）索引存储2下面哪些操作不属于静态查找表（）A）查询某个特定元素与否在表中B）检索某个特定元素的属性C）插入一种数据元素D）建立一种查找表3下面描述不对的的是（）A）顺序查找对表中元素寄存位置无任何规定，当n较大时，效率低。B）静态查找表中核心字有序时，可用二分查找。C）分块查找也是一种静态查找表。D）常常进行插入和删除操作时可以采用二分查找。4散列查找时，解决冲突的措施有（）A）除留余数法B）数字分析法 C）直接定址法 D）链地址法5若表中的记录顺序寄存在一种一维数组中，在等概率状况下顺序查找的平均查找长度为（）A）O（1）B）O(log2n) C）O(n) D）O(n2)6对长度为4的顺序表进行查找，若第一种元素的概率为1/8，第二个元素的概率为1/4，第三个元素的概率为3/8，第四个元素的概率为1/4，则查找任一种元素的平均查找长度为（）A）11/8 B）7/4 C）9/4 D）11/47静态查找表与动态查找表两者的主线差别在于（）A）它们的逻辑构造不同样 B）施加在其上的操作不同 C）所涉及的数据元素的类型不同样 D）存储实现不同样8若查找表中的记录按核心字的大小顺序寄存在一种一维数组中，在等概率状况下二分法查找的平均检索长度是（）A）O(n)B）O(log2n)C）O(nlog2n) D）O(log2n)2)9对有14个数据元素的有序表R14（假设下标从1开始）进行二分查找，搜索到R4的核心码等于给定值，此时元素比较顺序依次为（）。A）R1，R2，R3，R4 B）R1，R13，R2，R3C）R7，R3，R5，R4 D）R7，R4，R2，R310设有一种长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较（）次。A）9B）8C）7D）6 11请指出在顺序表2,5,7,10,14,15,18,23,35,41,52中，用二分法查找核心码12需做（）次核心码比较。A）2B）3 C）4 D）512从具有 n 个结点的二叉排序树中查找一种元素时，在最坏状况下的时间复杂度为 ( ) 。 A )O (n) B） O（1） C） O (log 2 n) D）O (n 2 ) 13分块查找时拟定块的查找可以用顺序查找，也可以用（ ），而在块中只能是（ ）A）静态查找，顺序查找B）二分查找，顺序查找 C）二分查找，二分查找D）散列查找，顺序查找14采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相似，假设采用顺序查找来拟定结点所在的块时，每块应分（ ）个结点最佳。A）10B）25 C）6 D）62515采用分块查找法（块长为s，以二分查找拟定块）查找长度为n的线性表时，每个元素的平均查找长度为（ ）A）s+n B）log2ns/2 C）log2 (n/s+1)+s/2 D）(n+s)/2 16对一棵二叉排序树根结点而言，左子树中所有结点与右子树中所有结点的核心字大小关系是（）A）不不小于 B）不小于C）等于D）不不不小于17若二叉排序树中核心字互不相似，则下面命题中不对的的是（ ）A）最小元和最大元一定是叶子B）最大元必无右孩子C）最小元必无左孩子D）新结点总是作为叶结点插入二叉排序树 18设二叉排序树中核心字由1至1000的整数构成，现要查找核心字为363的结点，下述核心字序列（）不也许是在二叉排序树上查找到的序列? A）2,252,401,398,330, 344,397,363B）924, 220, 911, 244, 898, 258, 362, 363C）2, 399, 387, 219, 266, 382, 381, 278, 363 D）925, 202, 911, 240, 912, 245, 36319在初始为空的散列表中依次插入核心字序列(MON,TUE,WED,THU,FRI,SAT,SUN),散列函数为H(k)=i MOD 7，其中，i为核心字k的第一种字母在英文字母表中的序号，地址值域为 0:6 ，采用线性再散列法解决冲突。插入后的散列表应当如（）所示。 A）0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B） 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C） 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D） 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON20若根据查找表建立长度为 m 的散列表，采用线性探测法解决冲突，假定对一种元素第一次计算的散列地址为 d ，则下一次的散列地址为 ( ) 。 A） d B） (d+1)%m C） (d+1)/m D） d+121若根据查找表建立长度为 m 的散列表，采用二次探测法解决冲突，假定对一种元素第一次计算的散列地址为 d ，则第四次计算的散列地址为 ( ) 。 A )(d+1)%m B） (d-1)%m C） (d+4)%m D） (d-4)%m 22下面有关散列查找的说法中对的的是（ ）A）直接定址法所得地址集合和核心字集合的大小不一定相似。B）除留余数法构造的哈希函数H(key)=key MOD p，其中P必须选择素数。C）构造哈希函数时不需要考虑记录的查找频率。D）数字分析法合用于对哈希表中浮现的核心字事先懂得的状况。23下面有关散列冲突解决的说法中不对的的是（ ）A）解决冲突即当某核心字得到的哈希地址已经存在时，为其寻找另一种空地址。B）使用链地址法在链表中插入元素的位置随意，即可以是表头表尾，也可以在中间。C）二次探测可以保证只要哈希表未填满，总能找到一种不冲突的地址。D）线性探测可以保证只要哈希表未填满，总能找到一种不冲突的地址。24设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7其他地址为空，如用二次探测解决冲突，核心字为49的结点的地址是（）A）8B）3C）5D）98.2填空题1在散列函数H(key)=key%p中，p应取_。2采用分块查找法（块长为s，以顺序查找拟定块）查找长度为n的线性表时的平均查找长度为_。3己知一种有序表为(12,18,20,25,29,32,40,62,83,90,95,98)，当二分查找值为29和90的元素时，分别需要_次和_次比较才干查找成功；若采用顺序查找时，分别需要_次和_次比较才干查找成功。4从一棵二叉排序树中查找一种元素时，若元素的值等于根结点的值，则表白 _ ，若元素的值不不小于根结点的值，则继续向 _查找，若元素的值不小于根结点的值，则继续向 _ 查找。5二分查找的存储构造仅限于 _，且是_。6假设在有序线性表A1.20上进行二分查找，则比较一次查找成功的结点数为 _个 ，比较二次查找成功的结点数为_ ，比较三次查找成功的结点数为_ ，比较四次查找成功的结点数为_ ，比较五次查找成功的结点数为_，平均查找长度为_ 。7在对有20个元素的递增有序表作二分查找时，查找长度为5的元素的下标从小到大依次为_。（设下标从1开始）8对于线性表（70,34,55,23,65,41,20,100）进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有_个，散列地址为7的元素有_ 个。9索引顺序表上的查找分两个阶段：_、_。10分块查找中，要得到最佳的平均查找长度，应对256个元素的线性查找表提成_块，每块的最佳长度是_。若每块的长度为8，则等概率下平均查找长度为_。11_是一棵二叉树，如果不为空，则它必须满足下面的条件：A）若左子树不空，则左子树上所有结点的值均不不小于根的值。B）若右子树不空，则右子树上所有结点的值均不小于根的值。C）其左右子树均为二叉排序树。13假定有k个核心字互为同义词，若用线性探测法把这些同义词存入散列表中，至少要进行_次探测。8.3应用题1设有序表为(a, b, c, d, e, f, g, h, i, j, k, p, q)，请分别画出对给定值a, g和n进行折半查找的过程。2已知一棵二叉排序树如下： （1）如果删除核心字28，画出新二叉树。（2）若查找56，需和哪些核心字比较。3已知散列表的地址区间为011，散列函数为H(k)=k % 11，采用线性探测法解决冲突，将核心字序列20,30,70,15,8,12,18,63,19依次存储到散列表中，试构造出该散列表，并求出在等概率状况下的平均查找长度。4设散列函数为H(k)=k % 11，采用拉链法解决冲突，将上例中核心字序列依次存储到散列表中，并求出在等概率状况下的平均查找长度。5假定一种待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT13，若采用除留余数法构造散列函数和线性探测法解决冲突，试求出每一元素的初始散列地址和最后散列地址，画出最后得到的散列表，求出平均查找长度。第9章 排序9.1选择题 1从末排序的序列中依次取出一种元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序措施称为（）排序法。 A）插入 B）选择 C）希尔 D）二路归并2下面多种排序措施中，最佳状况下时间复杂度为O(n)的是（）A）迅速排序 B）直接插入排序 C）堆排序 D）归并排序3用某种排序措施对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化状况如下：25 84 21 47 15 27 68 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则所采用的排序措施是（ ）选择排序）希尔排序）归并排序）迅速排序4下面给出的四种排序法中，（）排序是不稳定排序法。A）插入 B）冒泡 C）二路归并 D）堆5迅速排序措施在（）状况下最不利于发挥其长处。）要排序的数据量太大）要排序的数据中具有多种相似值）要排序的数据已基本有序）要排序的数据个数为奇数6一组记录的核心码为（46,79,56,38,40,84），则运用迅速排序的措施，以第一种记录为基准得到的一次划提成果为（）38,40,46,56,79,84B）40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,84,56,797对记录的核心码50，26，38，80，70，90，8，30，40，20进行排序，各趟排序结束时的成果为：50,26,38,80,70,90 ,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序措施是（）A）迅速排序 B）基数排序 C）希尔排序 D）归并排序 8在文献“局部有序”或文献长度较小的状况下，最佳内部排序措施是（）A）直接插入排序 B）冒泡排序 C）简朴选择排序 D）归并排序9在下列算法中，（）算法也许浮现下列状况：在最后一趟开始之前，所有的元素都不在其最后的位置上。 A）堆排序 B）冒泡排序 C）插入排序 D）迅速排序10设有5000个无序的元素，但愿用最迅速度挑选出其中前10个最大的元素，在如下的排序措施中，采用（）措施最佳A）迅速排序 B）堆排序 C）基数排序11对给出的一组核心字14，5，19，20，11，19。若按核心字非递减排序，第一趟排序成果为14，5，19，20，11，19，问采用的排序算法是（）A）简朴选择排序 B）迅速排序 C）希尔排序 D）二路归并排序12如下序列不是堆的是（）A）100,85,98,77,80,60,82,40,20,10,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,2013下面排序措施中，核心字比较次数与记录的初始排列无关的是（）A）希尔排序 B）冒泡排序 C）直接插入排序 D）直接选择排序14一组记录的核心字为45，80，55，40，42，85，则运用堆排序的措施建立的初始堆为（）A）80,45,50,40,42,85 B）85,80,55,40,42, 45C）85,80,55,45,42,40 D）85,55,80,42,45,4015一组记录的核心字为25，50，15，35，80，85，20，40，36，70，其中具有5个长度为2的有序表，用归并排序措施对该序列进行一趟归并后的成果为（）A）15,25,35,50,20,40,80,85,36,70B）15,25,35,50,80,20,85,40,70,36C）15,25,50,35,80,85,20,36,40,70D）15,25,35,50,80,20,36,40,70,8516n个元素进行冒泡排序的过程中，最佳状况下的时间复杂度为（）A）O(1) B）O(log2n) C）O(n2) D）O(n)17n个元素进行迅速排序的过程中，第一次划分最多需要移动（）次元素(涉及开始将基准元素移到临时变量的那一次)。 A）n2 B）n-1 C）n D）n+l18下述几种排序措施中，规定内存量最大的是（）A）插入排序 B）选择排序 C）迅速排序 D）归并排序19下面排序措施中，时间复杂度不是O(n2)的是（）A）直接插入排序 B）二路归并排序 C）冒泡排序 D）直接选择排序20对下列4个序列用迅速排序措施进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列（）A）70,75,82,90, 23,16,10,68 B）70,75,68,23,10,16,90,82C）82,75,70,16,10,90,68,23 D）23,10,16,70,82,75,68,909.2填空题1当数据量特别大需借助外部存储器对数据进行排序，则这种排序称为_。2在堆排序、迅速排序和归并排序中，若从节省存储空间考虑，则应一方面选用_措施，另一方面选用_措施；若只从排序成果的稳定性考虑，则应先择_措施；若只从平均状况下排序的速度来考虑，则选择_措施；若只从最坏状况下排序最快并且要节省内存考虑，则应选用_措施。3对n个元素的序列进行冒泡排序，至少的比较次数是_，此时元素的排列状况为_，在_状况下比较次数最多，其比较次数为_（4）_ _。4希尔排序是把记录按下标的一定增量分组，对每组记录进行直接插入排序，随着增量_，所提成的组涉及的记录越来越多，当增量的值为_时，整个数组合为一组。5直接插入排序需借助的存储单元个数（空间复杂度）为_，最佳状况下直接插入排序的算法时间复杂度为_，最坏状况下该算法的时间复杂度为_。6对n个数据进行简朴选择排序，所需进行的核心字间的比较次数为_，时间复杂度为_。7对于核心字序列(12，13，11，18，60，15，7，20，25，100)，用筛选法建堆，必须从键值为_的核心字开始。8对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较_次。9若对顺序存储在AlA9的记录(76，38，62，53，80，74，83，65，85)进行堆排序，已知除第一种元素76外，以其他元素为根的结点都已是堆，则对第一种元素进行筛运算时，它将最后被筛到A数组下标为_的位置上。10在时间复杂度为O(log2n)的排序措施中，_排序措施是稳定的；在时间复杂度为O(n)的排序措施中，_排序措施是不稳定的。11设表中元素的初态是按键值递增的，若分别用堆排序、迅速排序、冒泡排序和归并排序措施对其仍按递增顺序进行排序，则_最省时间，_最费时间。12从一种无序序列建立一种堆的措施是：一方面将要排序的n个键值分放到一棵_的各个结点中，然后从i=_的结点Ki开始，逐渐把以Ki-1、Ki-2、K1为根的子树排成堆，直到以Kl为根的树排成堆，就完毕了建堆的过程。13在归并排序中，若待排序记录的个数为20，则共需要进行_趟归并，在第三趟归并中，是把长度为_的有序表归并为长度为_的有序表。9.3应用题 1设待排序的排序码序列为12, 2, 16, 30, 28, 10, 16*, 20, 6, 18, 试分别写出使用如下排序措施每趟排序后的成果。并阐明做了多少次排序码比较。（1） 直接插入排序（2） 希尔排序（增量为5,2,1）（3） 起泡排序（4） 迅速排序（5） 基数排序（6） 堆排序 （7）直接选择排序 2对一种具有7个记录的文献进行迅速排序，请问：（1）在最佳状况下需进行多少次比较？并给出一种最佳状况初始排列的实例。（2）在最坏状况下需进行多少次比较？为什么？并给出此时的实例。3如果某个文献经内排序得到80个初始归并段，试问：（1）若使用多路归并执行3趟完毕排序，那么应取的归并路数至少应为多少？（2）如果操作系统规定一种程序同步可用的输入/输出文献的总数不超过15个，则按多路归并至少需要几趟可以完毕排序？如果限定这个趟数，可取的最低路数是多少？