<tt id="iwmsi"></tt>
  • <xmp id="iwmsi">
  • 浙江大學遠程教育2015數據結構與算法離線作業答案 - 圖文 - 下載本文

    時,當把第七個記錄(關鍵字是60)插入到有序表時,為尋找插入位置需比較 3 次。

    【34,7,4】插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序、和基數排序方法中,不穩定的排序方法有 希爾排序 、 選擇排序 、 快速排序 堆排序 。

    6

    二、綜合題(選自教材《數據結構》各章習題,采用word文件格式上傳)

    【1,1,3】試分析下面一段代碼的時間復雜度:

    if ( A > B ) {

    for ( i=0; i

    for ( j=N*N; j>i; j-- ) A += B; }

    else {

    for ( i=0; ii; j-- ) A += B; }

    答:if中的時間復雜度為:O(n*n2),即O(n3)

    else中的時間復雜度為:O(n*n)即O(n2) 整段時間復雜度為max(O(n3),O(n2)),即O(n3)

    【2,1,3】測試例1.3中秦九韶算法與直接法的效率差別。令f(x)?1??i?1xi/i,計算f(1.1)的值。利用clock()函數得到兩種算法在同一機器上的運行時間。 答:

    #include #include #include clock_t start,stop; double duration; #define MAXN 101

    7

    100#define MAXK 1e7

    double f1(int n ,double a[],double x); double f2(int n ,double a[],double x); //秦九昭算法

    double f1(int n ,double a[],double x){ int i ; double p = a[n]; for(i=n;i>0;i--)

    p = a[i-1] + x * p;

    return p;

    }

    //直接算法

    double f2(int n ,double a[],double x){ int i ; double p = 1.0; for(i=1;i<=n;i++)

    p += a[i]*pow(x,i);

    return p;

    }

    8

    int main(){

    int i ;

    double a[MAXN] ;

    a[0]=1.0;

    for(i=1;i

    a[i]=1.0/((double)i);

    start = clock(); for(i=1;i

    f2(MAXN-1,a,1.1);

    stop = clock();

    duration = ((double)(stop-start))/CLK_TCK/MAXK ; printf(\直接算法:\

    printf(\printf(\

    start = clock(); for(i=0;i

    f1(MAXN-1,a,1.1);

    stop = clock();

    9

    }

    duration = ((double)(stop-start))/CLK_TCK/MAXK ; printf(\秦九昭算法:\

    printf(\printf(\return 0;

    【3,1,3】 試分析最大子列和算法1.3的空間復雜度。

    答:若記整體時間復雜度為T(N)。通過遞歸實現“分”的復雜度為2T(N/2)。求跨分界線的最大子列和有兩個簡單的for循環,所用步驟一共不超過N,可以在O(N)時間完成。其他步驟都只需要常數O(1) T(1)=O(1);

    T(N)=2T(N/2)+ O(N)

    =2[2T((N/2)/2)+ O(N/2)]+O(N)=22T (N/22)+2 O(N) =……=2kT (N/2k)+k O(N)

    不斷對分到N/2k =1,即2k =N,可得到T(N)=NT(1)+logN·O(N)= O(NlogN)

    【4,1,3】試給出判斷N是否為質數的O(N)的算法。 答:

    #include #include

    10





    白小姐结果开奖结果小说