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

第1页共5页数据结构查找与排序练习题答案一、选择题1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为()A．（N+1）/2B.N/2C.ND.[（1+N）*N]/22.适用于折半查找的表的存储方式及元素排列要求为()A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序3.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度()A．必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减4．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。A．35/12B.37/12C.39/12D.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的链中有（）个记录。A．1B.2C.3D.411.已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除出一个记录，正确的做法是(）A.将该元素所在的存储单元清空。B.将该元素用一个特殊的元素代替C.将与该元素有相同Hash地址的后继元素顺次前移一个位置。D.用与该元素有相同Hash地址的最后插入表中的元素替代。12.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()A．k-1次B.k次C.k+1次D.k（k+1）/2次13.散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。（1）元素59存放在散列表中的地址是（）。A．8B.9C.10D.11（2）存放元素59需要搜索的次数是（）。A．2B.3C.4D.514.将10个元素散列到100000个单元的哈希表中，则（）产生冲突。A.一定会B.一定不会C.仍可能会第2页共5页15.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（）个。A.1B.2C.3D.416.下列排序方法中，哪一个是稳定的排序方法？（）A．直接选择排序B．直接插入排序C．希尔排序D．快速排序17.在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。A.直接插入排序B.气泡排序C.快速排序D.直接选择排序18.比较次数与排序的初始状态无关的排序方法是()。A.直接插入排序B.起泡排序C.快速排序D.简单选择排序19.对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。A.选择B.快速C.希尔D.冒泡20.一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A.(38,40,46,56,79,84)B.(40,38,46,79,56,84)C.(40,38,46,56,79,84)D.(40,38,46,84,56,79)21.就平均性能而言，目前最好的内排序方法是()排序法。A.冒泡B.希尔插入C.交换D.快速22．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为()排序法。A.插入B.选择C.希尔D.快速23.用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）。A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,4024.直接插入排序在最好情况下的时间复杂度为（）A.O(logn)B.O(n)C.O(n*logn)D.O(n2)25.对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是()A.lB.4C.3D.226.对下列关键字序列用快速排序法进行排序时，速度最快的情形是（）。A.{21,25,5,17,9,23,30}B.{25,23,30,17,21,5,9}C.{21,9,17,30,25,23,5}Ｄ.{5,9,17,21,23,25,30}27.快速排序方法在（）情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序28.对n个记录进行希尔排序，所需要的辅助存储空间为（）。A.O（1og2n）B.O（n）C.O（1）D.O（n2）29.下列四个序列中，哪一个是堆（）。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1530.就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（）A.堆排序〈快速排序〈归并排序B.堆排序〈归并排序〈快速排序C.堆排序〉归并排序〉快速排序D.堆排序快速排序归并排序E.以上答案都不对第3页共5页二、判断题1.查找相同结点的效率折半查找总比顺序查找高。×2.对无序表用二分法查找比顺序查找快。×3.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。√4.二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值。×5.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。×6.对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。×7.二叉树中除叶结点外,任一结点X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值≥该结点（X）的值,则此二叉树一定是二叉排序树。×8.在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。×9.采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。√10.在散列检索中，“比较”操作一般也是不可避免的。√11.散列函数越复杂越好，因为这样随机性好，冲突概率小.×12.Hash表的平均查找长度与处理冲突的方法无关。×13.负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。√14.若散列表的负载因子α1，则可避免碰撞的产生。×15.哈希表的平均查找长度不为0，是因为哈希函数在绝大多数情况下是多对一的映射，即存在冲突。√16.可以创建一种查找表，其在十亿个元素中查找与在10个元素中查找所用的时间差不多。√17．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。√18.内排序要求数据一定要以顺序方式存储。×19.排序算法中的比较次数与初始元素序列的排列无关。×20.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。×21.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。×22.直接选择排序算法在最好情况下的时间复杂度为O（N）。×23.在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。×24.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。×25.快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。×26.堆是满二叉树。×27.在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。√28.堆排序是稳定的排序方法。×29.归并排序辅助存储为O（1）。×30.冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。×31.快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。×32.归并排序在任何情况下都比所有简单排序速度快。×33.快速排序总比简单排序快。×三、填空题第4页共5页1.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__n__次。2.在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__5_3.在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是1,3,6,8,11,13,16,19______。4.有序表(12,18,24,35,47,50,62,83,90,115，134)使用二分法查找90时，需____2___次查找成功，查100时，需____3______次才能确定不成功。5.平衡因子的定义是__________6.高度为8的平衡二叉树的结点数至少有___54___个。7.动态查找表和静态查找表的重要区别在于前者包含有__插入__和__删除__运算，而后者不包含这两种运算。四、应用题1.假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：(1).画出描述折半查找过程的判定树；(2).若查找元素54，需依次与那些元素比较?(3).若查找元素90，需依次与那些元素比较?(4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。2.一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。按照中序遍历遍历的顺序将值标上3.依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树(1)试画出生成之后的二叉排序树;(2)对该二叉排序树作中序遍历，试写出遍历序列;(3)假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。4.设哈希函数H（k）=3Kmod11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时的平均查找长度；（1）散列地址012345678910关键字412493813243221比较次数11121212ASLsucc=（1+1+1+2+1+2+1+2）/8=11/8（2）519423678第5页共5页ASLsucc=11/85.整形数组A的十个元素值分别是6，2，9，7，3，8，4，5，0，试用第一元素中的值6作为枢轴，试写出快速排序第一次分割后A中的结果。用第一元素中的值6作为枢轴，快速排序第一次分