数据结构查找和排序习题

一、选择题，则折半查找55需要1、已知一个有序表为（11，22，33，44，55，66，77，88，99）比较（A.1）次。B.2C.3D.4）。3、解决哈希冲突的主要方法有（A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、再哈希法D.线性探测法、再哈希法、链地址法在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。4、A.nB.log2nC.(h+1)/2D.h5、已知表长为25的哈希表，用除留取余法，按公式H(key)=keyMODp建立哈希表，则）为宜。p应取（A.23B.24C.25D.266、设哈希表长m=14,哈希函数H(key)=keyMOD11。表中已有4个结点：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为（）。A.8B.3C.5D.9）。9、m阶B-树中的m是指（A.每个结点至少具有m棵子树B.每个结点最多具有m棵子树C.分支结点中包含的关键字的个数D.m阶B-树的深度10、一个待散列的线性表为k={18,25,63,50,42,32,9}，散列函数为H(k)=kMOD9，与18发生冲突的元素有（）个。A.1B.2C.3D.411、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中，这种方式主要适合于（）。A.静态查找表B.动态查找表C.静态查找表和动态查找表D.两种表都不适合12、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为（B）次比较后查找成功。82的结点时，A.1B.4C.2D.8）。13、在各种查找方法中，平均查找承担与结点个数n无关的查找方法是（A.顺序查找B.折半查找C.哈希查找D.分块查找平衡的二叉树是（）。14、下列二叉树中，不．15、对一棵二叉排序树按（）遍历，可得到结点值从小到大的排列序列。A.先序B.中序C.后序D.层次16、解决散列法中出现的冲突问题常采用的方法是（）。A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法17、对线性表进行折半查找时，要求线性表必须（A.以顺序方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序）。B.以链接方式存储二、填空题。1、在散列函数H(key)=key％p中，p应取，当用折半查找902、已知有序表为（12，18，24，35，47，50，62，83，90，115，134）时，需进行次查找可确定成功。。3、具有相同函数值的关键字对哈希函数来说称为遍历后，其关键字序列是一个有序表。4、在一棵二叉排序树上实施在散列存储中，装填因子α的值越大，则存取元素时发生冲突的可能性就越5、α值越小，则存取元素发生冲突的可能性就越。三、判断题（）1、折半查找只适用于有序表，包括有序的顺序表和链表。（）2、二叉排序树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的；结点必无右孩子。（）哈希表的查找效率主要取决于哈希表造表时所选取的哈希函数和处理冲突的方法。3、（）4、平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。（）5、AVL是一棵二叉树，其树上任一结点的平衡因子的绝对值不大于1。四、综合题1、选取哈希函数H（k）=（k）MOD11。用二次探测再散列处理冲突，试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。2、设哈希表HT表长m为13，哈希函数为H(k)=kMODm，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。3、设散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34）,散列函数H（K）=Kmod6，采用线性探测法解决冲突，要求：（1）构造散列表；（2）求查找数34需要比较的次数。4、已知下面二叉排序树的各结点的值依次为1－9，请标出各结点的值。5、若依次输入序列{62,68,30,61,25,14,53,47,90,84}中的元素，生成一棵二叉排序树。画出生成后的二叉排序树（不需画出生成过程）。6、设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77},采用哈希函数H(key)=keyMOD13,采用开放地址法的二次探测再散列方法解决冲突，试在0－18的散列空间中对关键字序列构造哈希表，画出哈希表，并求其查找成功时的平均查找长度。7、已知关键字序列{11,2,13,26,5,18,4,9}，设哈希表表长为16，哈希函数H(key)=keyMOD13，处理冲突的方法为线性探测法，请给出哈希表，并计算在等概率的条件下的平均查找长度。8、设散列表的长度为m=13，散列函数为H(k)=kMODm，给定的关键码序列为19，14，23，1，68，20，84，27，55，11，13，7，试写出用线性探查法解决冲突时所构造的散列表。9、依次读入给定的整数序列{7,16,4,8,20,9,6,18,5}，构造一棵二叉排序树,并计算在等概率情况下该二叉排序树的平均查找长度ASL。（要求给出构造过程），采用哈10、设有一组关键字（19，1，23，14，55，20，84，27，68，11，10，77）希函数H(key)=key%13，采用二次探测再散列的方法解决冲突，试在0-18的散列地址空间中对该关键字序列构造哈希表。第十章内部排序

一、选择题1、若需要在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序B.堆排序C.归并排序D.直接插入排序2、下列排序方法中（）方法是不稳定的。A.冒泡排序B.选择排序C.堆排序D.直接插入排序）方3、一个序列中有10000个元素，若只想得到其中前10个最小元素，则最好采用（法。A.快速排序B.堆排序C.插入排序D.归并排序一组待排序序列为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为（4、A.79,46,56,38,40,80B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,38）。）情况下最不利于发挥其长处。5、快速排序方法在（A.要排序的数据量太大B.要排序的数据中有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数6、排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置，这是（）排序的基本思想。A.堆排序B.直接插入排序C.快速排序D.冒泡排序）。7、在任何情况下，时间复杂度均为O(nlogn)的不稳定的排序方法是（A.直接插入B.快速排序C.堆排序D.归并排序）算法最快。8、如果将所有中国人按照生日来排序，则使用（A.归并排序B.希尔排序C.快速排序D.基数排序）。9、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（A.O(log2n)B.O(1)C.O(n)D.O(nlog2n)10、排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。A.希尔排序B.冒泡排序C.插入排序D.选择排序，则利用堆排序的方法建立的初始11、一组记录的的序列未（46，79，56，38，40，84）堆为（）。A.79，46，56，38，40，80B.84，79，56，38，40，46C.84，79，56，46，40，38D.84，56，79，40，46，3812、用某种排序方法对线性表（25，84，21，47，15，27，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.快速排序13、设有1024个无序的元素，希望用最快的速度挑选出其中前5个最大的元素，最好选用（A.冒泡排序B.选择排序C.快速排序D.堆排序）。14、下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（A.快速排序B.堆排序C.归并排序15、希尔排序的增量序列必须是（A.递增的B.递减的）。C.随机的D.非递减的）。D.基数排序二、填空题1、在插入和选择排序中，若初始数据基本正序，则选用，若初始数据基本反序，则选用。2、在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有。三、判断题1、直接选择排序是一种稳定的排序方法。2、快速排序在所有排序方法中最快，而且所需附加空间也最少。3、直接插入排序是不稳定的排序方法。4、选择排序是一种不稳定的排序方法。五、综合题1、写出用直接插入排序将关键字序列{54,23,89,48,64,50,25,90,34}排序过程的每一趟结果。2、设待排序序列为{10,18,4,3,6,12,1,9,15,8}请写出希尔排序每一趟的结果。增量序列为5，3，2，1。3、已知关键字序列{418，347，289，110，505，333，984，693，177}，按递增排序，求初始堆（画出初始堆的状态）。4、有一关键字序列（265，301，751，129，937，863，742，694，076，438），写出希尔排序的每趟排序结果。（取增量为5，3，1）5、对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：（1）平均时间复杂度低于O（n2）的排序方法；（2）所需辅助空间最多的排序方法；6、对关键子序列（72，87，61，23，94，16，05，58）进行堆排序，使之按关键字递减次序排列（最小堆），请写出排序过程中得到的初始堆和前三趟的序列状态。第七章查找

一、单项选择题1．在长度为n的线性表中进行顺序查找，在等概率的情况下，查找成功的平均查找长度是。A．nB．n(n+1)／2C．(n-1)／2D．(n+1)／22．在长度为n的顺序表中进行顺序查找，查找失败时需与键值比较次数是。A．nB．1C．n-1D．n+l3．对线性表进行顺序查找时，要求线性表的存储结构是。A．倒排表B．索引表C．顺序表或链表D．散列表4．对线性表用二分法查找时要求线性表必须是。A．顺序表B．单链表C．顺序存储的有序表D．散列表5．在有序表A[80]上进行二分法查找，查找失败时，需对键值进行最多比较次数是。A．20B．40C．10D．76．在长度为n的有序顺序表中，采用二分法查找，在等概率的情况下，查找成功的平均查找长度是。2

A.O(n)B．O(nlog2n)C．O(n)D．O(log2n)7．设顺序表为{4，6，12，32，40，42，50，60，72，78，80，90，98}，用二分法查找72，需要进行的比较次数是。A．2B．3C．4D．58．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则应采用的查找方法是。A．顺序查找B．二分法查找C．分块查找D．都不行9．在采用线性探查法处理冲突的散列表中进行查找，查找成功时所探测位置上的键值。A．一定都是同义词B．一定都不是同义词C．不一定是同义词D．无任何关系10．在查找过程中，若同时还要做插入、删除操作，这种查找称为。A．静态查找B．动态查找C．内部查找D．外部查找二、填空题1．在有序表A[30]上进行二分查找，则需要对键值进行4次、5次比较查找成功的记录个数分别为、，在等概率的情况下，查找成功的平均查找长度是。2．散列法存储的基本思想是由，确定记录的存储地址。3．对一棵二叉排序树进行遍历，可以得到一个键值从小到大次序排列的有序序列。4．对有序表A[80]进行二分查找，则对应的判定树高度为，判定树前6层的结点个数为，最高一层的结点个数是，查找给定值K，最多与键值比较次5．对于表长为n的线性表要进行顺序查找，则平均时间复杂度为，若采用二分查找，则平均时间复杂度为。6．在散列表中，装填因子。值越大，则插入记录时发生冲突的可能性。7．在散列表的查找过程中与给定值K进行比较的次数取决于、和。8．在使用分块查找时，除表本身外，尚需建立一个，用来存放每一块中最高键值及。9．若表中有10000个记录，采用分块查找时，用顺序查找确定记录所在的块，则分成块最好，每块的最佳长度，在这种情况下，查找成功的平均检索长度为。10．用n个键值构造一棵二叉排序树，最低高度是。13.高度为6的平衡二叉排序树，其每个分支结点的平衡因子均为0，则该二叉树共有(24)个结点。15．m阶B+树，除根结点外的每个结点最多有棵子树值，最少有棵子树。三、应用题1．画出对长度为13的有序表进行二分查找的一棵判定树，并求其等概率时查找成功的平均查找长度。查找失败时需对键值的最多比较次数。2．将整数序列{8，6，3，1，2，5，9，7，4}中的数依次插入到一棵空的二叉排序树中，求在等概率情况下，查找成功的平均查找长度，查找失败时对键值的最多比较次数。再画出从二叉排序树中删除结点6和8的结果。3．将整数序列{8，6，3，1，2，5，9，7，41中的数依次插入到一棵空的平衡二叉排序树中，求在等概率情况下，查找成功的平均检索长度，查找失败时对键值的最多比较次数4．按不同的输入顺序输入4，5，6，建立相应的不同形态的二叉排序树。5．设有键值序列{25，40，33，47，12，66，72，87，94，22，5，58}散列表长为12，散列函数为H(key)=key％11，用拉链法处理冲突，请画出散列表，在等概率情况下，求查找成功的平均查找长度和查找失败的平均查找长度。6．已知一个散列函数为H(key)=key％13，采用双散列法处理冲突，H1(key)=key％11+1，探查序列为di=(H(key)+i*H1(key))％m，i=1，2，…m-1，散列表见表1，要求回答下列问题：(1)对表中键值21，57，45和50进行查找时，所需进行的比较次数各为多少?(2)在等概率情况下查找时，查找成功的平均查找长度是多少?012345678910111250表12157散列表4537四、算法设计题1．设二叉树用二叉链表表示，且每个结点的键值互不相同，请编写判别该二叉树是否为二叉排序树的非递归算法。第八章排序

一、单项选择题1.对n个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方法，初始序列在（1）情况下，与排序码值总比较次数最少，在（2）情况下，与排序码值总比较次数最多；用直接插入排序方法，初始序列在（3）情况下，与排序码值总比较次数最少，在（4）情况下，与排序码值总比较次数最多；用快速排序方法在（5）情况下，与排序码值总比较次数最少，在（5）情况下与排序码值总比较次数最多。(1)-(6)：A．按排序码值从小到大排列B．按排序码值从大到小排列C．随机排列(完全无序)D．基本按排序码值升序排列2．用冒泡排序方法对n个记录按排序码值从小到大排序时，当初始序列是按排序码值从大到小排列时，与码值总比较次数是（7）。(7)：A．n-1B．nC．n+1D．n(n-1)／23.下列排序方法中，与排序码值总比较次数与待排序记录的初始序列排列状态无关的是(8)。(8)：A．直接插入排序B．冒泡排序C．快速排序D．直接选择排序4．将6个不同的整数进行排序，至少需要比较(9)次，至多需要比较(10)次。(9)-(10)：A．5B．6C．15D．215．若需要时间复杂度在O(nlog2n)内，对整数数组进行排序，且要求排序方法是稳定的，则可选择的排序方法是(11)。(11)：A．快速排序B．归并排序C．堆排序D．直接插入排序6．当待排序的整数是有序序列时，采用(12)方法比较好，其时间复杂度为O(n)，而2

采用（13）方法却正好相反，达到最坏情况下时间复杂度为O(n)；无论待排序序列2

排列是否有序，采用（14）方法的时间复杂度都是O(n)。(12)-(14)：A．快速排序B．冒泡排序C．归并排序D．直接选择排序7．堆是一种(15)排序。(15)：A．插入B．选择C．交换D．归并8．若一组记录的排序码值序列为{40，80，50，30，60，70}，利用堆排序方法进行排序，初建的大顶堆是(16)。(16)：A．80，40，50，30，60，70B．80，70，60，50，40，30C．80，70，50，40，30，60D．80，60，70，30，40，509．若一组记录的排序码值序列为{50，80，30，40，70，60}利用快速排序方法，以第一个记录为基准，得到一趟快速排序的结果为（17）。(17)：A．30，40，50，60，70，80B．40，30，50，80，70，60C．50，30，40，70，60，80D．40，50，30，70，60，8010．下列几种排序方法中要求辅助空间最大的是（18）。(18)：A．堆排序B．直接选择排序C．归并排序D．快速排序11．已知A[m]中每个数组元素距其最终位置不远，采用下列(19)排序方法最节省时间。(19)：A．直接插入B．堆C．快速D．直接选择12．设有10000个互不相等的无序整数，若仅要求找出其中前10个最大整数，最好采用（20）排序方法。(20)：A．归并B．堆C．快速D．直接选择13．在下列排序方法中不需要对排序码值进行比较就能进行排序的是（21）。(21)：A：基数排序B．快速排序C．直接插入排序D．堆排序14.给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典序列的次序进行排列，希尔(Shell)排序的第一趟(d1=5)结果应为（22），冒泡排序(大数下沉)的第一趟排序结果应为（23），快速排序的第一趟排序结果为（24），二路归并排序的第一趟排序结果是（25）。(22)-(25)：A．{B，F，C，J，A，E，D，I，C，H}B．{C，B，D，A，E，F，I，C，J，H}C．{B，F，C，E，A，I，D，C，H，J}D．{A，B，D，C，E，F，I，J，C，H}二、填空题1．内部排序方法按排序采用的策略可划分为五类：（1）、（2）、（3）、（4）、（5）。2．快速排序平均情况下的时间复杂度为（6），其最坏情况下的时间复杂度为（7）。3．当待排序的记录个数n很大时，应采用平均时间复杂度为（8）即（9）、（10）、（11），在这些方法中当排序码值是随机分布时，采用（12）排序方法的平均时间复杂度最小。当希望排序方法是稳定时，应采用(13)排序方法，若只从节省空间考虑，最节省空间的是（14）方法。4．对一组整数{60，40，90，20，10，70，50，80}进行直接插入排序时，当把第7个整数50插入到有序表中时，为寻找插人位置需比较（15）次。5．从未排序序列中挑选最小(最大)元素，并将其依次放到已排序序列的一端，称为（16）排序。6．对n个记录进行归并排序，所需要的辅助存储空间是（17），其平均时间复杂度是（18），最坏情况下的时间复杂度是（19）。7．对n个记录进行冒泡排序，最坏情况下的时间复杂度是（20）。8．对20个记录进行归并排序时，共需进行（21）趟归并，在第三趟归并时是把最大长度为（22）的有序表两两归并为长度为（23）的有序表。三、应用题1．举例说明本章介绍的排序方法中哪些是不稳定的?2．已知排序码值序列{17，18，60，40，7，32，73，65，85}，请写出冒泡排序每一趟的排序结果。3．对于排序码值序列{10，18，14，13，16，12，11，9，15，8}，给出希尔排序(dl=5，d2=2，d3=1)的每一趟排序结果。4．判断下列序列是否为大顶堆?若不是，则把它们调整为大顶堆。(1){90，86，48，73，35，40，42，58，66，20}(2){12，70，34，66，24，56，50，90，86，36}四、算法设计题1．在带表头结点的单链表上，编写一个实现直接选择排序的算法。2．请编写一个快速排序的非递归算法。