數(shù)據(jù)結(jié)構(gòu)單元練習(xí)_第1頁
數(shù)據(jù)結(jié)構(gòu)單元練習(xí)_第2頁
數(shù)據(jù)結(jié)構(gòu)單元練習(xí)_第3頁
數(shù)據(jù)結(jié)構(gòu)單元練習(xí)_第4頁
數(shù)據(jù)結(jié)構(gòu)單元練習(xí)_第5頁
已閱讀5頁,還剩15頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、單元練習(xí)5一判斷題(下列各題,正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打;錯(cuò)誤的打 )()(1)串是n個(gè)字母的有限序列。()(2)串的數(shù)據(jù)元素是一個(gè)字符。()(3)串的長度是指串中不同字符的個(gè)數(shù)。()(4)如果兩個(gè)串含有相同的字符,則說明它們相等。()(5)如果一個(gè)串中所有的字母均在另一個(gè)串中出現(xiàn),則說明前者是后者的子串。()(6)串的堆分配存儲(chǔ)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。()(7)“DT”是“DATA”的子串。()(8)串中任意個(gè)字符組成的子序列稱為該串的子串。()(9)子串的定位運(yùn)算稱為模式匹配。()(10)在鏈串中為了提高存儲(chǔ)密度,應(yīng)該增大結(jié)點(diǎn)的大小。二填空題(1) 由零個(gè)或多個(gè)字符組成的有限序列稱為 字符串(或

2、串) 。(2) 字符串按存儲(chǔ)方式可以分為:順序存儲(chǔ)、鏈接存儲(chǔ)和 堆分配存儲(chǔ) 。(3) 串的順序存儲(chǔ)結(jié)構(gòu)簡稱為 順序串 。(4) 串順序存儲(chǔ)非緊湊格式的缺點(diǎn)是: 空間利用率低 。(5) 串順序存儲(chǔ)緊湊格式的缺點(diǎn)是對(duì)串的字符處理 效率低 。(6) 串鏈接存儲(chǔ)的優(yōu)點(diǎn)是插入、刪除方便,缺點(diǎn)的 空間利用率低 。(7) 在C或C+語言中,以字符 0 表示串值的終結(jié)。(8) 空格串的長度等于 空格的個(gè)數(shù) 。(9) 在空串和空格串中,長度不為0的是 空格串 。(10) 兩個(gè)串相等是指兩個(gè)串相長度等,且對(duì)應(yīng)位置的 字符都相同 。(11) 設(shè)S=My Music,則LenStr(s)= _ 8 。(12) 兩個(gè)字

3、符串分別為:S1=Today is,S2=30 July,2005,ConcatStr(S1,S2)的結(jié)果是: Today is 30 July,2005 。(13) 求子串函數(shù)SubStr(Today is 30 July,2005,13,4)的結(jié)果是: July 。(14) 在串的運(yùn)算中,EqualStr(aaa,aab)的返回值為 m,則模式匹配算法最壞情況下的時(shí)間復(fù)雜度為: (n-m+1)*m 。三選擇題(1)串是一種特殊的線性表,其特殊性體現(xiàn)在( B )。A.可以順序存儲(chǔ) B數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ) D數(shù)據(jù)元素可以是多個(gè)字符(2)某串的長度小于一個(gè)常數(shù),則采用( B )存儲(chǔ)

4、方式最節(jié)省空間。 A鏈?zhǔn)?B順序 C堆結(jié)構(gòu)D無法確定(3)以下論述正確的是( C )。 A空串與空格串是相同的 Btel是Teleptone的子串 C空串是零個(gè)字符的串 D. 空串的長度等于1(4)以下論述正確的是( B )。 A空串與空格串是相同的 Bton是Teleptone的子串 C空格串是有空格的串 D. 空串的長度等于1(5)以下論斷正確的是( A )。 A是空串, 空格串 BBEIJING是BEI JING的子串 CsomethingSomethig DBIT=BITE(6)設(shè)有兩個(gè)串S1和S2,則EqualStr(S1,S2)運(yùn)算稱作( D )。 A. 串連接 B模式匹配 C.

5、求子串 D串比較(7)串的模式匹配是指( D )。A判斷兩個(gè)串是否相等C找某字符在主串中第一次出現(xiàn)的位置B對(duì)兩個(gè)串比較大小D找某子串在主串中第一次出現(xiàn)的第一個(gè)字符位置(8)若字符串ABCDEFG采用鏈?zhǔn)酱鎯?chǔ),假設(shè)每個(gè)字符占用1個(gè)字節(jié),每個(gè)指針占用2個(gè)字節(jié)。則該字符串的存儲(chǔ)密度為( D )。 A20 B40 C50 D333(9)若字符串ABCDEFG采用鏈?zhǔn)酱鎯?chǔ),假設(shè)每個(gè)指針占用2個(gè)字節(jié),若希望存儲(chǔ)密度50,則每個(gè)結(jié)點(diǎn)應(yīng)存儲(chǔ)( A )個(gè)字符。 A2 B3 C4D5(10)設(shè)串S1=I AM,S2=A SDUDENT,則ConcatStr(S1,S2)=( B )。 AI AM BI AM A

6、SDUDENT CIAMASDUDENT D. A SDUDENT(11)設(shè)S=,則LenStr(S)=( A )。A0 B1 C2 D3(12)設(shè)目標(biāo)串T=AABBCCDDE,模式P=ABCDE,則該模式匹配的有效位移為 ( A )。A0 B1 C2 D3(13)設(shè)目標(biāo)串T=AABBCCDDEEFF,模式P=CCD,則該模式匹配的有效位移為 ( D )。A2 B3 C4 D. 5(14)設(shè)目標(biāo)串T=aabaababaabaa,模式P=abab,樸素匹配算法的外層循環(huán)進(jìn)行了( D )次。 A1 B9 C4 D5(15)樸素模式匹配算法在最壞情況下的時(shí)間復(fù)雜度是( D )。 AO(m) BO(n

7、) C0(m+n) D0(m*n)(16)S=morning,執(zhí)行求子串函數(shù)SubStr(S,2,2)后的結(jié)果為( B )。Amo Bor Cin Dng(17)S1=good,S2=morning,執(zhí)行串連接函數(shù)ConcatStr(S1,S2)后的結(jié)果為( A )。 Agoodmorning Bgood morning CGOODMORNING DGOOD MORNING(18)S1=good,S2=morning,執(zhí)行函數(shù)SubStr(S2,4,LenStr(S1)后的結(jié)果為( B )。 AgoodBning Cgo Dmorn(19)設(shè)串S1=ABCDEFG,S2=PQRST ,則Con

8、catStr(SubStr(S1,2,LenStr(S2),SubStr(S1,LenStr(S2),2)的結(jié)果串為( D )。 ABCDEF BBCDEFG CBCPQRST D. BCDEFEF(20)若串S=SOFTWARE,其子串的數(shù)目最多是:( C ) 。 A35 B36 C37 D38 (8+7+6+5+4+3+2+1+1=37)四程序題填空(每空2分,共50分)1下面程序是把兩個(gè)串r1和r2首尾相連的程序,即:r1=r1+r2,試完成程序填空。typedef Struct char vecMAXLEN; / 定義合并后串的最大長度int len; / len為串的長度St ;vo

9、id ConcatStr(Str *r1,Str *r2) / 字符串連接函數(shù)int i;cout vecvec;if(r1-len+r2-len MAXLEN )cout 兩個(gè)串太長,溢出!;else for(i=0;ilen ;i+) / 把r2連接到r1 r1-vec r1-len+i =r2-veci; r1-vecr1-len+i= 0 ; / 添上字符串結(jié)束標(biāo)記r1-len= r1-len+r2-len ; / 修改新串長度 2. 設(shè)x和y兩個(gè)串均采用順序存儲(chǔ)方式,下面的程序是比較x 和y兩個(gè)串是否相等的函數(shù),試完成程序填空。#define MAXLEN 100typedef st

10、ruct char vecMAXLEN; len; str;int same (x,y)str *x,*y; int i=0,tag=1; if (x-len != y-len) return (0); / (或 ) else while ( ilen & tag ) if ( x-veci != y-veci ) tag=0 ; i+ ; ( 或 i=i+1 ) return (tag); 3下面算法是判斷字符串是否為回文(即正讀和倒讀相同),試完成程序填空。解: #include stdio.htypedef struct char vecMAXLEN; int len; str;void

11、 Palindrome (str s) int i=0; ing j= s.len-1 ; while ( j-i=1 ) if ( s.veci= s.vecj ) i+; j- ;continue / (或 j=j+1 ) else break; if ( j-i=1 ) coutIt is not a palindromen; else coutIt is a palindromen;五編程題1 設(shè)下面所用的串均采用順序存儲(chǔ)方式,其存儲(chǔ)結(jié)構(gòu)定義如下,請(qǐng)編寫下列算法:#define MAXLEN 100typedef struct char vecMAXLEN; int len; str;

12、(1) 將串中r中所有其值為ch1的字符換成ch2的字符。(2) 將串中r中所有字符按照相反的次序仍存放在r中。(3) 從串r中刪除其值等于ch的所有字符。(4) 從串r1中第index個(gè)字符起求出首次與字符r2相同的子串的起始位置。(5) 從串r中刪除所有與串r3相同的子串(允許調(diào)用第(4)小題的函數(shù))。(6) 編寫一個(gè)比較x 和y兩個(gè)串是否相等的函數(shù)。2設(shè)計(jì)一算法判斷字符串是否為回文(即正讀和倒讀相同)3設(shè)計(jì)一算法從字符串中刪除所有與字串del相同的子串4設(shè)計(jì)一算法統(tǒng)計(jì)字符串中否定詞not的個(gè)數(shù)1解:(1)算法思想:從頭至尾掃描r串,對(duì)于值為ch1的元素直接替換成ch2即可。 str *t

13、rans (r,ch1,ch2) str *r; char ch1,ch2; int i; for (i=0;ilen;i+)if (r-veci=ch1) r-veci=ch2; return(r); (2)算法思想是:將第一個(gè)元素與最后一個(gè)元素交換,第二個(gè)元素與倒數(shù)第二個(gè)元素交換,依次類推,便將該串的所有字符反序了。 str *invert (r) str *r; int i; char x; for (i=0;ilen%2) ;i+) x=r-veci; r-veci=r-r-len-i+1; r-vecr-len-i+1=x; return (r ); (3)算法思想:從頭到尾掃描r串

14、,對(duì)于值為ch的元素用移動(dòng)的方式進(jìn)行刪除。 str *delall (r,ch) str *r; char ch; int i,j;for (i=0;ilen;i+)if (r-veci=ch) for (j=i;jlen;j+) r-veci=r-veci+1; r-len=r-len-1; return (r ); (4)算法思想:從第index個(gè)元素開始掃描r1,當(dāng)其元素值與r2的第一個(gè)元素的值相同時(shí),判定它們之后的元素值是否依次相同,直到r2結(jié)束為止,若都相同則返回,否則繼續(xù)上述過程直到r1掃描完為止。 int partposition(r2,r1,index) str *r2, *r

15、1; int index; int i,j,k; for (i=index;r1-veci;i+) for (j=i,k=0;r1-vecj=r2-veck;j+,k+) if (!r2-veck+1) return(i); return(-1);(5)算法思想:從位置1開始調(diào)用第(4)小題的函數(shù)partposition(),若找到了一個(gè)相同子串,則調(diào)用delsubstring(),再相同的方法查找后面位置的相同子串。 str *delstringall(r,r3) str *r, *r3; int i=0; while (ilen) if (partposition(r,r3,i)!=-1)

16、 delsubstring(r,i,r3-len) i+; (6)兩個(gè)串相等的條件是兩個(gè)串的長度相等,且兩個(gè)串的對(duì)應(yīng)的字符必須都相同。int same(x,y)str *x,*y; int i=0,tag=1; if (x-len!=y-len) return(0); else while (ilen & tag) if (x-veci!=y-veci) tag=0; i+; return(tag); 2解:#include stdio.htypedef struct char *head; int length; Hstring;void isPalindrome(Hstring s) in

17、t i=0; int j=s.length-1; while (j-i=1) if (s.headi=s.headj) i+; j-; continue; else break; if (j-i=1) printf(Tt is not a palindromen ); else printf(it is a palindromen);3解:#include stdio.h#include string.htypedef struct char *head; int length;Hstring;char *DeleteSubString(Hstring S,Hstring T) int i=0

18、; int j,k; int Slength=S.length; int Tlength=T.length; char *tail; while (i=Slenght-Tlength) j=0;k=i; while (jTlength & S.headk=T.headj) / 在位移i用樸素的模式匹配 j+; k+; if (j=Tlength) / 若匹配則執(zhí)行下面的程序 if (i=0) / 若位于頭位置則改變頭指針 S.head=S.head+Tlength; S.length-=Tlength; Slength-=Tlength; i=0; else if (i+TlengthSlen

19、gth) / 若位于中間則拼接兩端 tail=S.head+i+Tlength; strcpy(S.head+i,tail); S.length-=Tlength; Slength-=Tlength; else / 若位于尾部則割去 strncpy(S.head+i,”0”,1); else / 若不匹配則i加1 i+; return S.head;4解:#include stdio.h#include string.hint Find_word(char *text, const char *word) int textlength=strlen(text); int wordlength=strlen(word); int i,j,k; int count=0;for (i=0;itextlength-wordlen

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論