数据结构查找排序经典试题.doc

一、填空1、针对有n条记录的顺序表做顺序查找，假定各记录的查找机会均等，则平均查找长度ASL=_。2、在二叉平衡树中，平衡因子hl-hr的所有可能取值有_。3、在排序操作中，待排序的记录有n条，若采用直接插入排序法，则需进行_趟的插入才能完成排序。4、在排序操作中，待排序的记录有n条，若采用冒泡排序法，则至多需进行_趟的排序。5、直接插入排序算法的时间复杂度为_。6、按（ ）遍历二叉排序树，可以得到按值递增的关键字序列，在下图所示的二叉排序树中，查找关键字85的过程中，需和85进行比较的关键字序列为（ ）。50 95205570301085二、判断1、平衡二叉树中子树的深度不能大于1。（ ）2、快速排序法是稳定的排序方法。（ ）3、任何一种排序方法都必须根据关键字值比较的结果来将记录从一个地方移动到另一个地方。（ ）4、冒泡排序法是稳定的排序方法。（ ）5、折半插入排序法是稳定的排序方法。（ ）三、选择1、在排序操作中，待排序的记录有n条，若采用直接插入排序法，则需进行_趟的插入才能完成排序。 A、n B、(n-1)/2 C、n+1 D、n-12、采用顺序查找法查找长度为n的线性表时，平均查找长度为（ ） A、n B、(n-1)/2 C、n/2 D、(n+1)/23、用折半查找法在11,33,55,77,99,110,155,166,233中查找155需要进行（ ）次比较。 A、1 B、2 C、3 D、44、请指出在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用折半查找法查找12需做（）次比较。 A、5 B、4 C、3 D、25、如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ ）就是不稳定的排序方法。A、起泡排序 B、归并排序 C、直接插入排序D、简单选择排序四、综合题 1、 给定一组数6，7，9，4，3，5，8，要求（a）构造一棵平衡的二叉排序树；（b）先根遍历该树；（c）从该树中删除结点6，并保持其特性。2、 给定一组关键字43，52，10，39，91，2，14，67，请采用快速排序法将其排列成递增的序列，写出排序的中间过程。3、 给定一组数4,5,7,2,1,3,6，要求（a）构造一棵平衡的二叉排序树；（b）先根遍历该树；（c）从该树中删除结点6，并保持其特性。4、 给定一组关键字43，52，10，39，91，2，14，67，请采用选择排序法将其排列成递增的序列，写出排序的中间过程。5、 给定一组关键字54，63，21，50，102，13，25，78，请采用快速排序法将其排列成递减的序列，写出排序的中间过程。6、 6、给定一组关键字54，63，21，50，102，13，25，78，请采用冒泡排序法将其排列成递减的序列，写出排序的中间过程。7、 给定一组关键字46，55，13，42，94，5，17，70，请采用直接插入排序法将其排列成递增的序列，写出排序的中间过程。8、应用希尔排序算法从小到大进行排序，键值序列为503,17,512,908,170,897,275,653,426，增量序列为4，2，1，试写出每趟排序的结果。