软件设计师案例分析每日一练试题（2024/9/1）

当前位置：信管网 >> 软件设计师 >> 每日一练 >> 文章内容

来源：信管网 2024年09月02日【所有评论】

软件设计师案例分析当天每日一练试题地址：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总：www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题（2024/9/1）在线测试：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2024/9/1

软件设计师案例分析每日一练试题内容（2024/9/1）

【说明】
希尔排序算法又称最小增量排序算法，其基本思想是:
步骤1 :构造一个步长序列delta1、delta2...、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
void shellsort(int data[ ], int n){
int *delta,k,i,t,dk,j;
k=n;
delta=(int *)nalloc(sizeof(int)*(n/2));
if(i=0)
do{
( 1 ) ;
delta[i++]=k;
}while ( 2 ) ;
i=0;
while((dk=delta[i])>0){
for(k=delta[i];kif( ( 3 ) ) {
t=data[k];
for(j=k-dk;j>=0&&tdata[j+dk]=data[j];
}/*for*/
( 4 ) ; //data[j+dk]=t;
}/*if*/
++i;
}/*while*/
}

【问题1】（8分）
根据说明和c代码，填充c代码中的空(1) ~ (4)。
【问题2】（4分）
根据说明和c代码，该算法的时间复杂度(5)O(n2) (小于、等于或大于)。该算法是否稳定(6) ( 是或否)。
【问题3】（3分）
对数组(15、9、7、8、20、-1、 4)用希尔排序方法进行排序，经过di-趟排后得到的数组为(7)。信管网试题答案与解析：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2024/9/1
信管网考友试题答案分享：

信管网cnit**************：
＜br /＞＜img src=＂http://pic.cnitpm.com/upload/2023/02/tbimg/02-26/1677397109.jpg＂ /＞

信管网cnit**************：
＜br /＞＜img src=＂http://pic.cnitpm.com/upload/2022/11/tbimg/11-02/1667342311.jpg＂ /＞

信管网cnit**************：
1. k ＝ k/2 k ＞= 1 data[j + dk] ＞= data[j] data[j+dk]=t 2, 大于否

信管网yire*：
1、k ＝ k/2 2、k＞1 3、k＞0 4、data[j+dk] ＝ t 5、小于 6、否 7、4、9、-1、8、20、7、15

信管网cnit**************：
１　１：ｋ＝ｋ／／２　２：ｋ＞１　３：ｋ＞０；ｋ－－　４：２：小于　是３：7，9，15，－1，8，20，4　　

信管网试题答案与解析：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2024/9/1