数据结构练习题(含标准答案)(DOC)

#/18查找长度为__。__在各种查找方法中，平均查找长度与结点个数无关的查找方法是_3折.半查找的存储结构仅限于__，_且_是___。_假设在有序线性表 上进行折半查找，则比较一次查找成功的结点数为，则比较二次查找成功的结点数为__，_则_比较三次查找成功的结点数为___，则_比较四次查找成功的结点数为__，_则_比较五次查找成功的结点数为__，_平均查找长度为___。_对于长度为的线性表，若进行顺序查找，则时间复杂度为 ；若采用折半法查找，则时间复杂度为 ；6已知有序表为（，，457,23, 1 ）,当用折半查找 时，需进行次查找可确定成功；查找时，需进行次查找成功；查找时，需进行一次查找才能确定不成功。7二叉排序树的查找长度不仅与有关，也与二叉排序树的有关。8一个无序序列可以通过构造一棵树而变成一个有序树，构造树的过程即为对无序序列进行排序的过程。9平衡二叉排序树上任一结点的平衡因子只可能是—、_或—。O法构造的哈希函数肯定不会发生冲突。1在散列函数 中，应取 若.在散列存储中，装填因子a的值越大，则 ；a的值越小，则。8在3综合练习题:画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。选取哈稀函数（）（）的散列地址空间中对关键字序列（2选取哈稀函数（）（）的散列地址空间中对关键字序列（25在已知一组关键字｛4，938，衡。1,53,46,）3造0哈,希1表3，,并0求1等,概6率7情况下查找成功时的平均查找长度。76，13，27，44，82，35，50，｝画出由此生成的二叉排序树，注意边插入边平习题答案（） 、哈希表查（） 、哈希表查2找在法顺序存储3结在构、有序的a（a为装填因子）（依题意，构造一棵有序二叉树，共则： （ ）（）、2个结点，第一层1个结点，第二层2个结点，第三层4个结点，第四层5（依题意，构造一棵有序二叉树，共则： （ ）（）、.结点个数、生成过程.二叉排序8树.直接定1址01.1素数12.存取元素时发生冲突的可能性就越大、存取元素时发生冲突的可能性就越小习题9排序9在1单项选择题在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是若若。若若希尔排序 起泡排序 插入排序 选择排序设有100个0无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用若若若排若序法。起泡排序 快速排序 堆排序 基数排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是若若。若若插入排序 选择排序 快速排序 归并排序一组记录的排序码为（4，679，56，3，840，84），则利用堆排序的方法建立的初始堆为若若。若若，，，，， ，，，，，5在一组记录的关键码为（46，79，56，3，840，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为若若若。若一组记录的排序码为（—―,,5,2—―0,—），其中含有个长度为的有序表，按归并排序的方法对该序列进行一趟归并后的结果为 __.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为__。__希尔排序 起泡排序 插入排序 选择排序.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为___。_希尔排序 归并排序 插入排序 选择排序.用某种排序方法对线性表（2，584，2，_4，__，52_，68，_5，20）进行排序时，元素序列的变化情况如下：⑴⑵⑶⑷则所采用的排序方法是__。__选择排序 希尔排序 归并排序 快速排序_0.下述几种排序方法中，平均查找长度最小的是___。_插入排序 选择排序 快速排序 归并排序__.下述几种排序方法中，要求内存量最大的是__。__插入排序选择排序 快速排序 归并排序_2.快速排序方法在__情__况下最不利于发挥其长处。要排序的数据量太大 要排序的数据中含有多个相同值要排序的数据已基本有序 要排序的数据个数为奇数9.2填空题（将正确的答案填在相应的空中）_.在对一组记录（54，_，89，62_，_5，_，26，045，8）_进行直接插入排序时，当把第_个记录60插入到有序表时，为寻找插入位置需比较__。__2.在利用快速排序方法对一组记录（5，4_8，96，2_，_5，_2，60，45，8_）进行快速排序时，递归调用而使用的栈所能达到的最大深度为__，__共需递归调用的次数为___，_其中第二次递归调用是对__一__组记录进行快速排序。_.在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取___方_法，其次选取__方_法_，最后选取__方_法_；若只从排序结果的稳定性考虑，则应选取___方_法；若只从平均情况下排序最快考虑，则应选取___方_法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取__方_法_。.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有___。_.在在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是___，需要内存容量最多的是__。__.在堆排序和快速排序中，若原始记录接近正序或反序，则选用__，_若_原始记录无序，则最好选用___。__.在插入和选择排序中，若初始数据基本正序，则选用___；_若初始数据基本反序，则选用__。__对个元素的序列进行起泡排序时，最少的比较次数是 。综合题以关键码序列（），_为_0例,，8手9工_执,行2以_下5排,序6算5法_，,写4出2每6一趟排序结以关键码序列（束时的关键码状态：（_）直接插入排序；（） 希尔排序（增量 ）；（_）快速排序；堆排序；归并排序；基数排序。2.判别以下序列是否为堆（小顶堆或大顶堆）