第1题:在长度为n的有序链表中进行查找，最坏情况下需要比较的次数为()。
A、n-1
B、n/2
C、n
D、与有序顺序表的对分查找相同
参考解析∶最坏情况为:查找的元素为表中最后一个元素或查找的元素不在表中，则需要比较表中所有元素，所以最坏情况下需要比较次数为n。本题答案为C选项。
第2题:对长度为8的数组进行快速排序，最多需要的比较次数为（ )。
A、8
B、28
c、56
D、64
参考解析:对长度为n的线性表进行快速排序，最坏情况下需要比较的次数为n(t-1)2。数组属于线性表，故对长度为8的数组进行快速排序，最多需要的比较次数为8(8-1)/2=28。本题答案为B选项。
第3题:在快速排序法中，每经过一次数据交换（或移动）后( )。
A、不会产生新的逆序
B、只能消除一个逆序
c、能消除多个逆序
D、消除的逆序个数一定比新产生的逆序个数多
参考解析:在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。快速排序的思想是:从线性表中选取一个元素，设为T，将线性表中后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成两部分（称两个子表），T插入到其分割性线的位置处，这个过程称为线性表的分割，然后再用同样的方法对分割出的子表再进行同样的分割。快速排序不是对两个相邻元素进行比较，可以实现通过一次交换而消除多个逆序，但由于均与T（基准元素〉比较，也可能会产生新的逆序。本题答案为C选项。
第4题:设顺序表的长度为16，对该表进行简单插入排序。在最坏情况下需要的比较次数为()。
A、30
B、60
c、120
D、15
参考解析:对长度为n的线性表进行简单插入排序，最坏情况下需要比较的次数为n(n-1)/2。故对长度为16的线性表进行简单插入排序，最坏情况下需要比较的次数为16(16-1)/2=120。本题答案为C选项。
第5题:设顺序表的长度为40，对该表进行冒泡排序。在最坏情况下需要的比较次数为（）。
A、40
B、41
c、780
D、820
参考解析：对长度为n的线性表进行冒泡排序，最坏情况下需要比较的次数为n(n-1)2。故对长度为40的线性表进行冒泡排序，最坏情况下需要比较的次数为40(40-1)/2=780。本题答案为C选项。
第6题:在长度为97的顺序有序表中作二分查找，最多需要的比较次数为( )。
A、6
B、7
c、48
D、96
参考解析:对于长度为n的有序线性表，在最坏情况下，二分法查找需要比较log2n次。故本题需要比较的次数为log297。由于1og297>6，所以需要比较次数为7。本题答案为B选项。
第7题:设顺序表的长度为n。下列算法中，最坏情况下比较次数等于n(n-1)2的是( )。
A、堆排序
B、快速排序
c、顺序查找
D、寻找最大项
参考解析:最坏情况下比较次数:堆排序为nlog2n，快速排序为n(n-1)2，顺序查找为n，寻找最大项为n-1。故最坏情况下比较次数等于n(n-1)/2的是快速排序。本题答案为B选项。
第8题:在希尔排序法中，每经过一次数据交换后（ )。
A、不会产生新的逆序
B、只能消除一个逆序
c、能消除多个逆序
D、消除的逆序个数一定比新产生的逆序个数多
参考解析:在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。希尔排序的基本思想是，先取一个整数（称为增量) d1<n，把全部数据元素分成d1组，所有距离为d1倍数的元素放在一组中，组成了一个子序列，对每个子序列分别进行简单插入排序，然后取d2<d1重复上述分组和排序工作，直到di=1，即所有记录在一组中为止。希尔排序可以实现通过一次交换而消除多个逆序。本题答案为C选项。
第9题:下列排序法中，每经过一次元素的交换会产生新的逆序的是( )。
A、快速排序
B、冒泡排序
c、简单插入排序
D、简单选择排序
参考解析:在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。快速排序的思想是:从线性表中选取一个元素，设为T，将线性表中后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成两部分（称两个子表），T插入到其分害性线的位置处，这个过程称为线性表的分割，然后再用同样的方法对分割出的子表再进行同样的分割。快速排序不是对两个相邻元素进行比较，可以实现通过一次交换而消除多个逆序，但由于均与T（基准元素）比较，也可能会产生新的逆序。本题答案为A选项。
第10题:设表的长度为n。下列查找算法中，在最坏情况下，比较次数最少的是( )。
A、顺序查找
B、寻找最大项
c、寻找最小项
D、有序表的二分查找
参考解析∶最坏情况下比较次数:有序表的二分查找为log2n，顺序查找为n，寻找最大项为n-1，寻找最小项为n-1。故比较次数最少的是有序表的二分查找。本题答案为D选项。
第11题:设表的长度为15。则在最坏情况下，快速排序所需要的比较次数为（ )。
A、15
B、55
c、75
D、105
参考解析:对长度为n的线性表进行快速排序，最坏情况下需要比较的次数为n(n-1)2。故对长度为15的线性表进行快速排序，最坏情况下需要比较的次数为15(15-1)/2=105。本题答案为D选项。
第12题:设顺序表的长度为n。下列排序方法中，最坏情况下比较次数小于n(n-1)2的是()。
A、堆排序
B、快速排序
c、简单插入排序
D、冒泡排序
参考解析:最坏情况下比较次数:堆排序为nlog2n，快速排序为n(n-1)2，简单插入排序为n(n-1)/2，冒泡排序为n(n-1)2。本题答案为A选项。
第13题:设表的长度为20。则在最坏情况下，冒泡排序的比较次数为（ ）。
A、19
B、20
c、90
D、190
参考解析:对长度为n的线性表进行冒泡排序，最坏情况下需要比较的次数为n(n-1)/2。故对长度为20的线性表进行冒泡排序，最坏情况下需要比较的次数为20(20-1)/2=190。本题答案为D选项。
第14题:下列算法中，最坏情况下时间复杂度最低的是( )。
A、堆排序
B、寻找最大项
c、顺序查找
D、有序表的对分查找
参考解析:最坏情况下时间复杂度:有序表的对分查找为O(log2n)，寻找最大项为O(n-1)，顺序查找为o(n)，堆排序为O(nlog2n)。故最坏情况下时间复杂度最低的是有序表的对分查找。本题答案为D选项。
第15题:为了对有序表进行对分查找，则要求有序表（ )。
A、只能顺序存储
B、只能链式存储
c、可以顺序存储也可以链式存储
D、任何存储方式
参考解析:能使用二分法查找（对分查找）的线性表必须满足两个条件:①用顺序存储结构;②线性表是有序表。本题答案为A选项。
第16题:在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为（ )。
A、(n+1)/2
B、n
c、3n/4
D、n/4
参考解析:在长度为n的顺序表中查找一个元素，最好情况为查找的元素在顺序表的第一个位置，需要比较的次数为1，最坏情况为查找的元素在顺序表的最后一个位置，需要比较的次数为n。因为题目中明确元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为(1+2+...+n)n=(n+1)n/2)/n=(n+1)/2。本题答案为A选项。
第17题:设表的长度为n。在下列结构所对应的算法中，最坏情况下时间复杂度最低（即比较次数）的是( ) 。
A、有序链表查找
B、循环链表中寻找最大项
c、堆排序
D、希尔排序
参考解析∶最坏情况下，有序链表查找的比较次数为n，循环链表中寻找最大项的比较次数为n-1，堆排序比较次数为nlog2n，希尔排序比较次数为nr(1<r<2)。故最坏情况下时间复杂度最低的是循环链表中寻找最大项。本题答案为B选项。
第18题:下列序列中不满足堆条件的是（ )。
A、 (98，95，93，94，89，85，76，64，55，49)
B、(98，95，93，94，89，90，76，64，55，49)
c、 ( 98，95，93，94，89，90，76，80，55，49)
D、( 98，95，93，96，89，85，76，64，55，49)
参考解析:若有n个元素的序列(h1，h2，…，hn)，将元素按顺序组成一棵完全二叉树，当且仅当满足下列条件时称为堆:①情况称为大根堆，所有节点的值大于或等于左右子节点的值;②情况称为小根堆，所有节点的值小于或等于左右子节点的值。D选项中h1>h2，h2<h4，不符合堆条件。本题答案为D选项。
第19题:下列叙述中正确的是（ )。
A、快速排序法适用于顺序存储的线性表
B、快速排序适用于链式存储的线性表
c、链式存储的线性表不可能排序
D、堆排序适用于非线性结构
参考解析:快速排序是借助数据元素的“交换”来进行排序的，链式存储由于不连续性不适合进行数据元素“交换”，B选项错误。对链式存储的钱钱性表可以进行排序，如进行简单插入排序，C选项错误。堆排序是选择类排序法，实现对线性表的排序，不适用于堆排序，D选项错误。本题答案为A选项。