会计学二分查找考点条件：顺序存储,按关键字有序时间复杂度分析（log2n）最多要比较的次数（㏒2n+1）,理由：n个结点的判定树的深度(shēndù)与n个结点的完全二叉树深度(shēndù)相同。折半查找的二叉判定树5、设有序顺序表中的元素(yuánsù)依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908.试画出对其进行折半搜索时的判定树,并计算搜索成功的平均搜索长度。Hash查找和Hash表的创建常用Hash函数和解决冲突方法Hash表的创建与平均查找长度(chángdù)的计算时间复杂度的分析（不依赖问题的规模,与解决冲突的方法以及hash表的装填因子有关）2、已知待散列存储(cúnchǔ)的关键字序列为（4,15,38,49,33,60,27,71）,哈希函数为H（key）=keyMOD11,哈希表HT的长度为11,采用二次探测再散列法（d=12,-12,22,-22,32,…）解决冲突,试构造此哈希表,并求出在等概率情况下查找成功的平均查找长度。3、已知关键码集合{53,17,19,61,98,75,79,63,46,49}要求(yāoqiú)散列到地址区间（100,101,102,103,104,105,106,107,108,109）内,若发生冲突则用开地址法的线索探测法解决,要求(yāoqiú)写出的选用的散列函数,形成的散列表：计算查找成功的平均搜索长度。（设等概率情况）答：选用的散列函数为：H(K)=100+K%10第二(dìèr)部分排序各种排序算法的特性时间性能（最好、最坏、平均(píngjūn)情况）空间复杂度稳定性一、基于选择(xuǎnzé)的排序稳定(wěndìng)性：不稳定(wěndìng)。反例如下：堆排序的算法(suànfǎ)思想：取出根结点（最大值）元素,与最后一个位置(wèizhi)的元素交换。问题(wèntí)2：堆的创建设关键字序列为：49,38,66,90,75,10,20。请把这些关键字调整成堆顶元素(yuánsù)取最小值的堆。（画出过程）2．序列(xùliè)是堆的是(C)。A．{75,65,30,15,25,45,20,10}B．{75,65,45,10,30,25,20,15}C．{75,45,65,30,15,25,20,10}D．{75,45,65,10,25,30,20,15}三、基于(jīyú)交换的排序2.快速排序算法(suànfǎ)思想：快速排序的平均(píngjūn)性能为O(n·log2n),在同数量级算法中综合考虑,是最好的一种内部排序方法快速排序算法在最坏情况下（待排序列正序或逆序）,每次划分只得到比上一次少一个记录的子序列,另一个子序列却为空,即划分得极不均匀,此时需要执行n-1次递归调用,且比较的次数是n(n-1)/2,所以快速排序收到序列初始状态的影响,在最坏情况下算法时间复杂度为O(n2)例如(lìrú)〖例〗给定N=10个整数，范围介于0到999(M=1000)之间。是否可以(kěyǐ)在线性的时间内把它们排序?南航2010年二、解答题(共80分，8题，每题10分)23．已知数据(shùjù)序列为(86，8，234，50，116，64，68，453，24，142)，给出基数排序过程的示意图。排序方法1、在堆排序、快速排序和归并排序中：1）若只从存储空间考虑,则应首先选取哪种排序方法,其次选取哪种排序方法,最后选取哪种排序方法？答：首选堆排序（O(1)）,其次选快速排序(O(log2n)),最后选归并排序(O(n))。2）若只从排序结果的稳定性考虑,则应选取哪种排序方法？答：归并排序3）若只从平均情况下排序最快考虑,则应选取哪种排序方法？答：快速排序4）若只从最坏情况下排序最快并且要节省内存考虑,则应选取哪种排序方法？答：堆排序5）设关键字序列为：49,38,66,90,75,10,20。请把这些关键字调整成堆(chénɡduī)顶元素取最小值的堆。（画出过程）3、我们打算对n个数进行排序,由于n非常大,希望满足最坏的情况下排序时间为O（nlogn）的前提(qiántí)下,辅助空间越小越好,则选择的排序方法是（）A、快速排序B、堆排序C、冒泡排序D、归并排序8、对由n个元素组成的一个无序(wúxù)数组,不必完成全部元素的排序,即可找出最大（或最小）的元素,这是排序方法。直接插入排序在一个已有序的序列中，将待排序的元素关键字逐个与该有序序列中的元素的相应关键字作比较(bǐjiào)，确定该元素在序列中的正确位置，然后在该位置插入这个元素，形成一个新的有序序列。归并排序思想①初始时，将每个记录看成一个