【试题四】希尔排序
【说明】
希尔排序算法又称最小增量排序算法,其基本思想是:
步骤1 :构造一个步长序列delta、deltak、 deltak ,其中delta1=n/2 ,后面的每个delta是前一个的1/2 , deltak=1;
步骤2 :根据步长序列、进行k趟排序;
步骤3 :对第i趟排序,根据对应的步长delta,将等步长位置元素分组,对同一组内元素在原位置上进行直接插入排序。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
data:待排序数组data,长度为n,待排序数据记录在data[0]、data[1]、…、data[n-1]中。
n:数组a中的元素个数。
delta:步长数组。
(2)C程序
#include
#include
/*
data:待排序数组data,长度为n,待排序数据记录在data[0]、data[1]、...、data[n-1]中。
n:数组a中的元素个数。
delta:步长数组。
*/
void shellsort1(int data[ ], int n){
int *delta,k,i,t,dk,j;
k=n;
delta=(int *)malloc(sizeof(int)*(n/2));
if(i=0)
do{
k=k/2 ; //填空1
delta[i++]=k;
}while(k>1) ; //填空2
i=0;
while((dk=delta[i])>0){
for(k=delta[i];k=0&&t
[问题1]根据说明和c代码,填充c代码中的空(1) ~ (4)。
[问题2]根据说明和c代码,该算法的时间复杂度(5)0(n2) (小于、等于或大于)。该算法是否稳定(6)(是或否)。
[问题3]对数组(15、9、7、8、20、-1、 4)用希尔排序方法进行排序,经过第一趟排后得到的数组为(7)。
【参考答案】
(1)k=k/2
(2)k>1
(3)data[k] (4)data[j+dk]=k
(5)小于
(6)否
(7)(4,9,-1,8,20,7,15)
【试题六】在线支付
阅读下列说明和(java++代码),将应填入(n)处的字句写在答题纸对应栏内。
[说明]在线支付是电子商务的一个重要环节,不同的电子商务平台提供不同的支付接口,现在需要给不同的商务平台的支付接口,使得客户在不同平台购物时, 不需要关系具体的支付接口。拟采用中介在( Mediator )设计模式来实现该需求,所设计的类图如图6-1所示
package test_2020_2;
interface WebServiceMediator{
public void buy(double money,WebService service);//填空1
public void SetAmazon(WebService amazon);
public void SetEbay(WebService ebay);
}
abstract class WebService{
protected WebServiceMediator mediator;//填空2
public abstract void SetMediator(WebServiceMediator mediator);
public abstract void buyService(double money);//填空3
public abstract void search(double money);
}
class ConcreteMediator implements WebServiceMediator{
private WebService amazon;
private WebService ebay;
public ConcreteMediator() {
amazon = null;
ebay = null;
}
@Override
public void SetAmazon(WebService amazon) {
this.amazon=amazon;
}
@Override
public void SetEbay(WebService ebay) {
this.ebay=ebay;
}
public void buy(double money,WebService service){
if (service == amazon)
amazon.search(money);
else
ebay.search(money);
}
}
class Amazon extends WebService{
@Override
public void SetMediator(WebServiceMediator mediator) {
this.mediator=mediator;
}
@Override
public void buyService(double money) {
mediator.buy(money,this);//填空4
}
@Override
public void search(double money) {
System.out.println("Amazon receive: "+money);
}
}
class Ebay extends WebService{
@Override
public void SetMediator(WebServiceMediator mediator) {
this.mediator=mediator;
}
@Override
public void buyService(double money) {
}
@Override
public void search(double money) {
mediator.buy(money,this);//填空5
}
}
public class WebServiceTest {
public static void main(String[] args) {
}
}
【参考答案】
(1) void buy(double money, WebService service)
(2) WebServiceMediator
(3) abstract void buyService(double money)
(4) mediator.buy(money, this)
(5) mediator.buy(money, this)
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
相关推荐: 如何在 🤗 Space 上托管 Unity 游戏
你知道吗?Hugging Face Space 可以托管自己开发的 Unity 游戏!惊不惊喜,意不意外?来了解一下吧! Hugging Face Space 是一个能够以简单的方式来构建、托管和分享项目或应用样例的平台。虽然通常更多地是应用在机器学习样例中,…