收藏 分销(赏)

排序-历年试题及参考答案.doc

上传人:w****g 文档编号:7378417 上传时间:2025-01-01 格式:DOC 页数:11 大小:39.54KB 下载积分:8 金币
下载 相关 举报
排序-历年试题及参考答案.doc_第1页
第1页 / 共11页
排序-历年试题及参考答案.doc_第2页
第2页 / 共11页


点击查看更多>>
资源描述
(完整)排序 历年试题及参考答案(08) 第8章 排序 (2008年1月) 11、下列排序方法中,稳定的排序方法为(   ) A、希尔排序 B、堆排序 C、快速排序 D、直接插入排序 12、对下列关键字序列进行快速排序时,所需进行比较次数最少的是(   ) A、(1,2,3,4,5,6,7,8) B、(8,7,6,5,4,3,2,1) C、(4,3,8,6,1,7,5,2) D、(2,1,5,4,3,6,7,8) 23、在快速排序、堆排序和归并排序中,最坏时间复杂度为O(n2)的排序算法有___________。 (2008年10月) 11、对长度为n的关键字序列进行堆排序的空间复杂度为( ) A、 O(log2n) B、 O(1) C、 O(n) D、 O(n*log2n) 12、已知用某种排序方法对关键字序列(51,35,93,24,13,68,56,42,77)进行排序时,前两趟排序的结果为 (35,51,24,13,68,56,42,77,93) (35,24,13,51,56,42,68,77,93) 所采用的排序方法是( ) A、 插入排序 B、 冒泡排序 C、 快速排序 D、 归并排序 23、在一般情况下用直接插入排序、选择排序和冒泡排序的过程中,所需记录交换次数最少的是 。 28、某类物品的编号由一个大写英文字母及2位数字(0…9)组成,形如E32。运用基数排序 对下列物品编号序列进行按字典序的排序,写出每一趟(分配和收集)后的结果。 E13,A37,F43,B32,B47,E12,F37,B12 第一趟: 第二趟: 第三趟: 33、阅读下列对正整数关键字序列L操作的算法,并回答问题: (1)设L=(28,19,27,49,56,12,10,25,20,50),写出f33 (L,4)的返回值; (2)简述函数f33的功能。 int Partition (SeqList*L, int low, int high); ∥对L[low…high]做划分,返回基准记录的位置,并使左部的关键字 ∥都小于或等于基准记录的关键字,右部的关键字都大于基准记录的关键字 int f33 (SeqList L, int k){ int low, high, pivotpos; low=1; high=L.length; if (k〈low || k〉high) return—1; do { pivotpos=Partition (&L, low, high);∥调用快速排序的划分算法 if (pivotpos〈k) low=pivotpos+1; else if (pivotpos>k) high=pivotpos—1; }while (pivotpos!=k); return L。data [pivotpos]; } (1) (2) (2009年1月) 12、下列关键字序列中,构成大根堆的是( ) A、5,8,1,3,9,6,2,7 B、9,8,1,7,5,6,2,33 C、9,8,6,3,5,l,2,7 D、9,8,6,7,5,1,2,3 23、对关键字序列(15,18,11,13,19,16,12,17,10,8)进行增量为5的一趟希尔排序的结果为_________。 27、对关键字序列(5,8,1,3,9,6,2,7)按从小到大进行快速排序. (1)写出排序过程中前两趟的划分结果; (2)快速排序是否是稳定的排序方法? (1) (2) 33、下列算法f33的功能是对记录序列进行双向冒泡排序。算法的基本思想为,先从前往后通过交换将关键字最大的记录移动至后端,然后从后往前通过交换将关键字最小的记录移动至前端,如此反复进行,直至整个序列按关键字递增有序为止。请在空缺处填入合适的内容,使其成为完整的算法。 #define MAXLEN 100 typedef int KeyType; typedef struct { KeyType key; InfoType otherinfo; } NodeType ; typedef NodeType SqList[ MAXLEN ]; void f33 ( SqList R, int n) { int i,j,k; NodeType t; i =0; j =n—l; while (i < j) { for ( (1) ) if (R[k]、key > R[k +l]、key) { t = R[k]; R[k] = R[k +1]; R[k +1] = t; } j—-; for (k =j; k 〉 i; k -— ) if ( (2) ) { t = R[k]; R[k] = R[k—1]; R[k-1] = t; } (3) ; } } (1) (2) (3) (2009年10月) 13、对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时,以第1个元素为基准的一次划分的结果为(   ) A、(5,1,4,3,6,2,8,7) B、(5,1,4,3,2,6,7,8) C、(5,1,4,3,2,6,8,7) D、(8,7,6,5,4,3,2,1) 24、若序列中关键字相同的记录在排序前后的相对次序不变,则称该排序算法是________的。 29、对序列(48,37,63,96,22,31,50,55,11)进行升序的堆排序,写出构建的初始(大根)堆及前两趟重建堆之后的序列状态. 初始堆: 第1趟: 第2趟: (2010年1月) 13、下列排序算法中不稳定的是( ) A、快速排序 B、归并排序 C、冒泡排序 D、直接插入排序 23、对序列{55,46,13,05,94,17,42}进行基数排序,第一趟排序后的结果是_________。 28、已知一组待排记录的关键字序列为(16,12,18,60,15,36,14,18,25,85),用堆排序方法建小根堆,请给出初始建堆后的序列。 32、数组A[]中存储有n个整数,请阅读下列程序. void f32(int A[],int n) { int i,j,k,x; k=n-1; while(k〉0) { i=k; k=0; for(j=0;j<i;j++) if(A[j]〉A[j+1]) { x=A[j]; A[j]=A[j+1]; A[j+1]=x; k=j; }//end of if }//end of while return; } 请回答下列问题: (1)当A[]={10,8,2,4,6,7}时,执行f32(A,6)后,数组A中存储的结果是什么? (2)说明该算法的功能。 (2010年10月) 12、如果在排序过程中不改变关键字相同元素的相对位置,则认为该排序方法是( ) A、不稳定的 B、稳定的 C、基于交换的 D、基于选择的 22、影响排序效率的两个因素是关键字的___________次数和记录的移动次数。 32、下面程序实现插入排序算法. typedef struct{ int key; Info otherinfo; }SeqList; void InsertSort(SeqList R[],int n) {/* 待排序列保存在R[1、、n]中*/ SeqList x; int i,j,k,lo,hi,mi; for (i=2;i〈=n;i++) { (1) ; lo=1; hi=i-l; while (lo<=hi) { mi=(lo+hi)/2; if ( (2) ) break; if (R[mi]、key〉x、key) hi=mi—l; else lo=mi+l; } if (mi=lo) k=i - mi; else k=i - mi—1; for (j=0;j<k;j++) (3) ; R[i-j]=x; } } 在空白处填写适当的内容,使该程序功能完整。 (1) (2) (3) (2011年1月) 11、平均时间复杂度为O(n log n)的稳定排序算法是( ) A、快速排序 B、堆排序 C、归并排序 D、冒泡排序 12、已知关键字序列为(51,22,83,46,75,18,68,30),对其进行快速排序,第一趟划分完成后的关键字序列是( ) A、(18,22,30,46,51,68,75,83) B、(30,18,22,46,51,75,83,68) C、(46,30,22,18,51,75,68,83) D、(30,22,18,46,51,75,68,83) 23、当待排关键字序列基本有序时,快速排序、简单选择排序和直接插入排序三种排序方法中,运行效率最高的是________________。 28、已知待排记录的关键字序列为{25,96,11,63,57,78,44},请回答下列问题: (1)画出堆排序的初始堆(大根堆); (2)画出第二次重建堆之后的堆. 参考答案 (2008年1月) 11、D 12、C 23、快速排序 (2008年10月) 11、B 12、B 23、选择排序 28、 第一趟:B32,E12,B12,E13,F43,A37,B47,F37 第二趟:E12,B12,E13,B32,A37,F37,F43,B47 第三趟:A37,B12,B32,B47,E12,E13,F37,F43 33、 (1)20 (2)查找关键字序列L中第k小的元素 (2009年1月) 12、D 23、15,12,11,10,8,16,18,17,13,19 27、对关键字序列(5,8,1,3,9,6,2,7)按从小到大进行快速排序。 (1)写出排序过程中前两趟的划分结果; (2)快速排序是否是稳定的排序方法? (1)第1趟2,3,1,5,9,6,8,7 第2趟1,2,3,5,7,6,8,9 (2)不是 33、 (1) k=i;k<j;k++ (2) R[k]。key 〈 R[k -l].key (3) i++ (2009年10月) 13、C 24、稳定 29、 初始堆:(96,55,63,48,22,31,50,37,11) 第1趟:(63,55,50,48,22,31,11,37,96) 第2趟:(55,48,50,37,22,31,11,63,96) (2010年1月) 13、A 23、{42,13,94,55,05,46,17 } 28、(12,15,14,18,16,36,18, 60,25,85) 32、 (1) {2,4,6,7,8,10} (2) 对数组A中的n个整数进行(冒泡)排序. (2010年10月) 12、B 22、比较 32、 (1) x=R[i] (2) R[mi]。key==x。key (3) R[i-j]= R[i—j-1] (2011年1月) 11、C 12、D 23、直接插入排序 28、 (1) {96,63,78,25,57,11,44} (2) {63,57,44,25,11,78,96}
展开阅读全文

开通  VIP会员、SVIP会员  优惠大
下载10份以上建议开通VIP会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        抽奖活动

©2010-2025 宁波自信网络信息技术有限公司  版权所有

客服电话:4009-655-100  投诉/维权电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服