數(shù)據(jù)結(jié)構(gòu)試題精選（4）-判斷和填空[1]_跨考網(wǎng)

判斷題

　　1．KMP算法的特點是在模式匹配時指示主串的指針不會變小。（??? ）【北京郵電大學 2002 一、4 （1分）】

　　2．設(shè)模式串的長度為m,目標串的長度為n，當n≈m且處理只匹配一次的模式時，樸素的匹配（即子串定位函數(shù)）算法所花的時間代價可能會更為節(jié)省。（??? ）【長沙鐵道學院 1998 一、1 (1分)】

　　3．串是一種數(shù)據(jù)對象和操作都特殊的線性表。（??? ）【大連海事大學 2001 1、L? (1分)】

　　填空題

　　1．空格串是指__(1)__，其長度等于___(2)__。 【西安電子科技大學 2001軟件 一、4（2分）】

　　2．組成串的數(shù)據(jù)元素只能是________。 【中山大學 1998? 一、5 （1分）】

　　3．一個字符串中________稱為該串的子串 。 【華中理工大學 2000 一、3（1分）】

　　4．INDEX（‘DATASTRUCTURE’， ‘STR’）=________?！?a target="_blank">福州大學 1998 二、4 (2分)】

　　5．設(shè)正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復雜度為________。

　　【重慶大學 2000 一、4】

　　6．模式串P=‘a(chǎn)baabcac’的next函數(shù)值序列為________?！疚靼?a target="_blank">電子科技大學 2001軟件 一、6（2分）】

　　7．字符串’ababaaab’的nextval函數(shù)值為________。 【北京郵電大學 2001 二、4 （2分）】

　　8．設(shè)T和P是兩個給定的串，在T中尋找等于P的子串的過程稱為__(1)__，又稱P為__(2)__。

　　【西安電子科技大學 1998 二、5 （16/6分）】

　　9．串是一種特殊的線性表，其特殊性表現(xiàn)在__(1)__；串的兩種最基本的存儲方式是__(2)__、__(3)__；兩個串相等的充分必要條件是__(4)__。 【中國礦業(yè)大學 2000 一、3 （4分）】

　　10．兩個字符串相等的充分必要條件是_______。 【西安電子科技大學 1999軟件 一、1 （2分）】

　　11．知U=‘xyxyxyxxyxy’；t=‘xxy’；

　　ASSIGN（S，U）；

　　ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；

　　ASSIGN（m，‘ww’）

　　求REPLACE（S，V，m）= ________。 【東北大學 1997 一、1? (5分)】

　　12．實現(xiàn)字符串拷貝的函數(shù) strcpy為：

　　void strcpy(char *s , char *t) /*copy t to s*/

　　{ while? (________)

　　}?? 【浙江大學 1999 一、5 (3分)】

　　13．下列程序判斷字符串s 是否對稱，對稱則返回1，否則返回0；如 f("abba")返回1，f("abab")返回0；

　　int f((1)________)

　　{int?? i=0,j=0;

　　while (s[j])(2)________;

　　for(j--; i<j? && s[i]==s[j]; i++,j--);

　　return((3)_______)

　　}?? 【浙江大學 1999 一、6 (3分)】

　　14．下列算法實現(xiàn)求采用順序結(jié)構(gòu)存儲的串s和串t的一個最長公共子串。

　　程序（a）

　　PROCEDURE? maxcomstr(VAR s,t : orderstring; VAR index,length : integer);

　　VAR i,j,k,length1:integer;? con:boolean;

　　BEGIN

　　index :=0; length :=0;? i :=1;

　　WHILE(i<=s.len) DO

　　[j:=1;

　　WHILE (j<=t.len) DO

　　[ IF (s[i]=t[j])? THEN

　　[ k:=1;? length1:=1;? con:=true;

　　WHILE? con? DO

　　IF (1)__THEN [length1:=length1+1;k:=k+1;] ELSE(2) _;

　　IF (length1>length) THEN [index:=i; length:=length1; ]

　　(3)____;

　　]

　　ELSE (4)____;

　　]

　　(5) ___;

　　]

　　END;

　　程序(b)

　　void? maxcomstr(orderstring *s,*t; int index, length)

　　{int i,j,k,length1,con;

　　index=0;length=0;i=1;

　　while (i<=s.len)

　　{j=1;

　　while(j<=t.len)

　　{ if (s[i]= =t[j])

　　{ k=1;length1=1;con=1;

　　while(con)

　　if (1) _ { length1=length1+1;k=k+1; }? else (2) __;

　　if (length1>length) { index=i;? length=length1; }

　　(3)____;

　　}

　　else (4) ___;

　　}

　　(5) __

　　}? }? 【上海大學 2000 一、2 （10分）】