查找和排序.doc

1. 对于长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为_。（2005年4月）A. log2n B. n/2 C. n D. n+1分析 对线性表进行顺序查找时，从表中第一个元素开始，将给定的值与逐个元素的关键字比较，直到两者相符，查找到所要找的元素为止。最坏的情况下，要查找的元素是表中最后一个或查找失败，这两种情况都会与表中所有元素进行比较，因此比较次数为n。答案 C2. 在长度为 64 的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。（2006年9月）A63 B64 C6 D7 分析 同上答案 B3. 下列叙述中正确的是_。（2010年3月）A. 对长度为n的有序链表进行查找，最坏情况下需要的比较次数为nB. 对长度为n的有序链表进行对分查找，最坏情况下需要比较的次数为（n/2）C. 对长度为n的有序链表进行对分查找，最坏情况下需要比较的次数为（）D. 对长度为n的有序链表进行对分查找，最坏情况下需要比较的次数为（n）分析 对链表，只能进行顺序查找，那么在最坏的情况下，需要比较n次。答案 A4. 在长度为n的线性表中，寻找最大项至少需要比较 次。（2010年9月）答案 15. 下列数据结构中，能用二分法进行查找的是_。（2005年9月）A.顺序存储的有序线性表 B.线性链表C.二叉链表 D.有序线性链表分析 二分法查找只适用于顺序存储的线性有序表，对于顺序存储的非有序线性表和线性链表（不管是有序还是无序）都只能采用顺序查找。答案 A6. 在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是_。（2008年9月）A.O(n)B.O(n2)C.O(log2n)D.O(nlog2n)分析 二分法查找在最坏的情况下，需要比较log2n次，而顺序查找需要比较n次。答案 C7. 已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当使用二分法查找值为90的元素时，查找成功的比较次数为_。A.1B.2C.3D.4答案 B8. 对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为_。（2006年4月）分析 最坏情况下，对长度为n的线性表，冒泡排序需要比较的次数为n(n-1)/2=10*（10-1）/2=45。答案 459. 冒泡排序在最坏情况下的比较次数是。（2007年9月）A.（n1）/2 B.nlog2 n C.n（n1）/2 D./2 答案 C10. 对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是。（2005年4月）A.冒泡排序为n/2 B. 冒泡排序为nC.快速排序为nD. 快速排序为n(n-1)/2分析 快速排序的平均时间效率最佳，为O( nlog2n)，但若初始序列有序或者基本有序时，快速排序蜕化为冒泡排序。故在最坏情况下，快速排序的比较次数为n(n-1)/2。答案 D11. 对长度为n的线性表排序，在最坏的情况下，比较次数不是n(n-1)/2的排序方法是_。（2008年4月）A.快速排序B.冒泡排序C.直接插入排序D.堆排序答案 D12. 下列排序方法中，最坏情况下比较次数最多的是_。（2009年3月）A.冒泡排序B.简单选择排序C.直接插入排序D.堆排序答案 D13. 希尔排序法属于哪一种类型的排序法_。A.