數(shù)據(jù)結(jié)構(gòu)串、數(shù)組和廣義表練習(xí)題及答案

 

一 選擇題

1．下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？（B ）

A．串是字符的有限序列     B．空串是由空格構(gòu)成的串    C．模式匹配是串的一種重要運(yùn)算     D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)

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è)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（C ）。

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

4. 設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（B ）。

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

5. 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是（ C ）。

A．便于進(jìn)行矩陣運(yùn)算     B．便于輸入和輸出   C．節(jié)省存儲(chǔ)空間     D．降低運(yùn)算的時(shí)間復(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的長(zhǎng)度和深度分別為（ C ）。

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

 

二、判斷題

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

2. 稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。（√ ）

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

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

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

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

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

 

三、填空 

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

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

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

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

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

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

 

四、應(yīng)用題

1．名詞解釋：串

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

 

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

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

 

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

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

 

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

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

 

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

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

 

五、算法設(shè)計(jì)題

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

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

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

    //字符串s和t用一維數(shù)組存儲(chǔ)，其長(zhǎng)度分別為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++;} //對(duì)應(yīng)字符相等，指針后移。

         else {i=i-j+1;j=0;} //對(duì)應(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); //輸入兩字符串的長(zhǎng)度

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

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

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

    }//程序結(jié)束

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