2． 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,執(zhí)行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index

(S2,‘8’),length(S2)))，其結(jié)果為（E ）

A．ABC###G0123        B．ABCD###2345    C．ABC###G2345     D．ABC###2345 

E．ABC###G1234       F．ABCD###1234      G．ABC###01234

3．設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（C ）。

A．求子串             B．聯(lián)接       C．匹配           D．求串長

4. 設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（B ）。

A. 13    B. 33   C. 18     D. 40

5. 對稀疏矩陣進行壓縮存儲目的是（ C ）。

A．便于進行矩陣運算     B．便于輸入和輸出   C．節(jié)省存儲空間     D．降低運算的時間復(fù)雜度

6. 廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為（D ）。

Head(Tail(Head(Tail(Tail(A)))))

A. (g)     B. (d)   C. c      D. d

7. 設(shè)廣義表L=（（a,b,c）），則L的長度和深度分別為（ C ）。

A. 1和1     B. 1和3   C. 1和2      D. 2和3

 

二、判斷題

1．串是一種數(shù)據(jù)對象和操作都特殊的線性表。（√ ）

2. 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（√ ）

3. 數(shù)組是同類型值的集合。（× ）

4. 數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。（ × ）

5. 一個稀疏矩陣Am*n采用三元組形式表示， 若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運算。（× ）

6. 二維以上的數(shù)組其實是一種特殊的廣義表。（ √ ）

7. 廣義表中的元素或者是一個不可分割的原子，或者是一個非空的廣義表。（× ）

 

三、填空 

1．空格串是指由空格字符（ASCII值32）所組成的字符串 ，其長度等于空格個數(shù)。

2．組成串的數(shù)據(jù)元素只能是 字符。

3．一個字符串中任意個連續(xù)的字符組成的子序列稱為該串的子串 。

4. 數(shù)組的存儲結(jié)構(gòu)采用順序存儲結(jié)構(gòu)存儲方式。

5. 所謂稀疏矩陣指的是非零元很少(t＜＜m*n)且分布沒有規(guī)律。

6. 廣義表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是: head(tail(tail(head(tail(head(A))))))。

 

四、應(yīng)用題

1．名詞解釋：串

答：串是零個至多個字符組成的有限序列。從數(shù)據(jù)結(jié)構(gòu)角度講，串屬于線性結(jié)構(gòu)。與線性表的特殊性在于串的元素是字符。 

 

2．描述以下概念的區(qū)別：空格串與空串。

答：空格是一個字符，其ASCII碼值是32。空格串是由空格組成的串，其長度等于空格的個數(shù)。空串是不含任何字符的串，即空串的長度是零。 

 

3. 特殊矩陣和稀疏矩陣哪一種壓縮存儲后失去隨機存取的功能？為什么？

答：特殊矩陣指值相同的元素或零元素在矩陣中的分布有一定規(guī)律，因此可以對非零元素分配單元（對值相同元素只分配一個單元），將非零元素存儲在向量中，元素的下標(biāo)i和j和該元素在向量中的下標(biāo)有一定規(guī)律，可以用簡單公式表示，仍具有隨機存取功能。而稀疏矩陣是指非零元素和矩陣容量相比很小（t＜＜m*n），且分布沒有規(guī)律。用十字鏈表作存儲結(jié)構(gòu)自然失去了隨機存取的功能。即使用三元組表的順序存儲結(jié)構(gòu)，存取下標(biāo)為i和j的元素時，要掃描三元組表，下標(biāo)不同的元素，存取時間也不同，最好情況下存取時間為O(1)，最差情況下是O(n)，因此也失去了隨機存取的功能。 

 

4. 試敘述一維數(shù)組與有序表的異同。

答：一維數(shù)組屬于特殊的順序表，和有序表的差別主要在于有序表中元素按值排序（非遞增或非遞減），而一維數(shù)組中元素沒有按元素值排列順序的要求。 

 

5. 一個n╳n的對稱矩陣，如果以行或列為主序存入內(nèi)存，則其容量為多少？

答：n(n+1)/2（壓縮存儲） 或n2（不采用壓縮存儲） 

 

五、算法設(shè)計題

1．設(shè)s、t為兩個字符串，分別放在兩個一維數(shù)組中，m、n分別為其長度，判斷t是否為s的子串。如果是,輸出子串所在位置（第一個字符）,否則輸出0.（注：用程序?qū)崿F(xiàn)）

答：[題目分析]判斷字符串t是否是字符串s的子串，稱為串的模式匹配，其基本思想是對串s和t各設(shè)一個指針i和j，i的值域是0..m-n，j的值域是0..n-1。初始值i和j均為0。模式匹配從s0和t0開始，若s0=t0，則i和j指針增加1，若在某個位置si!=tj，則主串指針i回溯到i=i-j+1，j仍從0開始，進行下一輪的比較，直到匹配成功（j>n-1），返回子串在主串的位置（i-j）。否則，當(dāng)i>m-n則為匹配失敗。

    int index(char s[],t[],int m,n)

    //字符串s和t用一維數(shù)組存儲，其長度分別為m和n。本算法求字符串t在字符串s中的第一次出現(xiàn)，如是，輸出子串在s中的位置，否則輸出0。

    {int i=0,j=0;

    while (i<=m-n && j<=n-1)

         if (s[i]==t[j]){i++;j++;} //對應(yīng)字符相等，指針后移。

         else {i=i-j+1;j=0;} //對應(yīng)字符不相等，I回溯，j仍為0。

    if(i<=m-n && j==n) {printf(“t在s串中位置是%d”,i-n+1);return(i-n+1);}//匹配成功

        else return(0); //匹配失敗

    }//算法index結(jié)束

    main ()//主函數(shù)

     {char s[],t[]; int m,n,i;

      scanf(“%d%d”,&m,&n); //輸入兩字符串的長度

      scanf(“%s”,s); //輸入主串

      scanf(“%s”,t); //輸入子串

      i=index(s,t,m,n);

    }//程序結(jié)束

    [程序討論]因用C語言實現(xiàn)，一維數(shù)組的下標(biāo)從0開始，m-1是主串最后一個字符的下標(biāo)，n-1是t串的最后一個字符的下標(biāo)。若匹配成功，最佳情況是s串的第0到第n-1個字符與t匹配，時間復(fù)雜度為o（n）；匹配成功的最差情況是，每次均在t的最后一個字符才失敗，直到s串的第m-n個字符成功，其時間復(fù)雜度為o（（m-n）*n），即o（m*n）。失敗的情況是s串的第m-n個字符比t串某字符比較失敗，時間復(fù)雜度為o（m*n）。之所以串s的指針i最大到m-n，是因為在m-n之后,所剩子串長度已經(jīng)小于子串長度n，故不必再去比較。算法中未討論輸入錯誤（如s串長小于t串長）。     另外，根據(jù)子串的定義，返回值i-n+1是子串在主串中的位置，子串在主串中的下標(biāo)是i-n。