單元6一、選擇題12345DBDCD678910CABBB1112131415CACAA1617181920CCBCC2122232425CDCDB2627282930CBDDA二、填空題1．O(n2)2．O(1)3．交換4．O(log2n)5．O(n2)6．堆7．n-118．希爾9．O(1)10．穩(wěn)定三、判斷題12345√??√?四、簡答題1．初始：54，23，89，48，64，50，25，90，34第1趟：（23，54），89，48，64，50，25，90，34第2趟：（23，54，89），48，64，50，25，90，34第3趟：（23，48，54，89），64，50，25，90，34第4趟：（23，48，54，64，89），50，25，90，34第5趟：（23，48，50，54，64，89），25，90，34第6趟：（23，25，48，50，54，64，89），90，34第7趟：（23，25，48，50，54，64，89，90），34第8趟：（23，25，48，50，54，64，89，90，34）2．{418，347，289，110，505，333，984，693，177}變成{984,693,418,347,505,333,289,110,177}。3．(1)希爾、快速、堆、歸并(2)歸并4．根據(jù)堆的定義可知堆中元素滿足下面中的某一個(gè)式子的關(guān)系：QUOTE或QUOTEQUOTE由此可知因此(1)(2)(4)是大根堆，是堆，(3)不是堆。(3)調(diào)整為（100,98,66,85,80,60,40,77,82,10,20）后成為大根堆。5．初始：17，18，60，40，7，32，73，65，85第1趟：17，18，40，7，32，60，65，73，85第2趟：17，18，7，32，40，60，65，73，85第3趟：17，7，18，32，40，60，65，73，85第4趟：7，17，18，32，40，60，65，73，85第5趟：7，17，18，32，40，60，65，73，85第5趟無元素交換，則排序結(jié)束。6．初始：503，87，512，61，908，170，897，275，653，462第1趟：[462，87，275，61，170]503[897，908，653，512]第2趟：[170，87，275，61]462，503[897，908，653，512]第3趟：[87，61]170[275]462，503[897，908，653，512]第4趟：61[87]170[275]462，503[897，908，653，512]第5趟：61，87，170，[275]462，503[897，908，653，512]第6趟：61，87，170，275，462，503[897，908，653，512]第7趟：61，87，170，275，462，503[512，653]897[908]第8趟：61，87，170，275，462，503，512，[653]897[908]第9趟：61，87，170，275，462，503，653，897[908]第10趟：61，87，170，275，462，503，653，897，9087．初始：70，83，100，65，10，32，7，9第1趟：（70，83），100，65，10，32，7，9第2趟：（70，83，100），65，10，32，7，9第3趟：（65，70，83，100），10，32，7，9第4趟：（10，65，70，83，100），32，7，9第5趟：（10，32，65，70，83，100），7，9第6趟：（7，10，32，65，70，83，100），9第7趟：（7，9，10，32，65，70，83，100）8．依題意，采用基數(shù)排序法排序的各趟的結(jié)果如下：初始：503，87，512，61，908，170，897，275，653，462第1趟（按個(gè)位排序）：170，61，462，512，503，653，275，87，897，908第2趟（按十位排序）：503，908，512，653，61，462，170，275，87，897第3趟（按百位排序）：61，87，170，275，462，503，512，653，897，9089．初始：10,18,4,3,6,12,1,9,18,8分成5個(gè)子序列的結(jié)果：10，1，4，3，6，12，18，9，18，8再分為2個(gè)子序列的結(jié)果：4，1，6，3，10，8，18，9，18，12最后結(jié)果：1，3，4，6，8，9，10，12，18，1810．采用2路歸并排序的結(jié)果如下：初始：10,18,4,3,6,12,1,9,18,8第1趟：10，18，3，4，6，12，1，9，8，18第2趟：3，4，10，18，1，6，9，12，8，18第3趟：1，3，4，6，9，10，12，18，8，18最后1趟歸并得結(jié)果：1，3，4，6，8，9，10，12，18，18五、算法設(shè)計(jì)題1.publicstaticvoidbinaryInsertSort(Objectdata[],intn) { Objecttmp; inti,j,mid,low,high; for(i=1;i<n;i++){ tmp=data[i];//保存待插入的元素 low=0; high=i-1; while(low<=high){//在data[low..high]中折半查找有序插入的位置 mid=(low+high)/2;//折半 if(pareTo(data[mid])<0) high=--mid;//插入點(diǎn)在低半?yún)^(qū) else low=++mid;//插入點(diǎn)在高半?yún)^(qū) } for(j=i-1;j>=low;j--) data[j+1]=data[j];//元素后移 data[low]=tmp;//插入到正確位置 } }2． publicclassDataSort{//用于存儲(chǔ)數(shù)字及其數(shù)位之和的映射關(guān)系staticHashMap<Integer,Integer>map=newHashMap<>();publicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);intn=scan.nextInt();//讀取輸入的整數(shù)n，表示范圍是1到nintm=scan.nextInt();//讀取輸入的整數(shù)m，表示要輸出排序后數(shù)組的第m個(gè)元素scan.close();//將【1~n】保存到數(shù)組int[]arr=newint[n];for(inti=0;i<n;i++){arr[i]=i+1;//初始化數(shù)組，元素值為1到n}//算法sort(arr);//輸出答案System.out.println(arr[m-1]);}publicstaticvoidsort(int[]arr){//存儲(chǔ)鍵值對，鍵為數(shù)字，值為該數(shù)字的數(shù)位之和for(inti=0;i<=arr.length-1;i++){intsum=0;//將當(dāng)前數(shù)字轉(zhuǎn)換為字符串，以便逐個(gè)獲取數(shù)位for(intk=0;k<String.valueOf(arr[i]).length();k++){//獲取當(dāng)前數(shù)位的值（字符轉(zhuǎn)換為數(shù)字）并累加到sumsum+=String.valueOf(arr[i]).charAt(k)-'0';}map.put(arr[i],sum);//將數(shù)字及其數(shù)位之和存入map}//利用選擇排序的思想，遍歷所有鍵，先對數(shù)位之和進(jìn)行比較，再對字面值進(jìn)行比較for(inti=0;i<arr.length-1;i++){for(intj=i+1;j<arr.length;j++){//交換if(map.get(arr[i])>map.get(arr[j])){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}elseif(map.get(arr[i])==map.get(arr[j])){