計算機專業(yè)基礎綜合數(shù)據(jù)結構歷年真題試卷匯編1

計算機專業(yè)基礎綜合數(shù)據(jù)結構（串）歷年真題試卷匯編1（總分:58.00，做題時間：90分鐘）一、填空題（總題數(shù)：12,分數(shù)：24.00）設T和P是兩個給定的串，在T中尋找等于P的子串的過程稱為（1），又稱P為（2）?！疚靼搽娮涌萍即髮W1998二、5（16/6分）】正確答案：（正確答案：（1）模式匹配（2）模式串）串是一種特殊的線性表，其特殊性表現(xiàn)在（1）;串的兩種最基本的存儲方式是（2）、（3）；兩個串相等的充分必要條件是（4）?！局袊V業(yè)大學2000一、3（4分）】正確答案：（正確答案：（1）其數(shù)據(jù)元素都是字符（2）順序存儲（3）鏈式存儲（4）串的長度相等且兩串中對應位置的字符也相等）使用“求子串”subString（S,pos,len）和''聯(lián)結"concat（S1,s2）的串操作，可從串s='conduction'中的字符得到串t=”cont”，則求t的串表達式為?！颈本┕I(yè)大學2005二、4（3分）】正確答案：（正確答案：t=concat（subStIling（s，1，3），subString（s，7，1）））下列程序讀入無符號十六進制數(shù)（出現(xiàn)的字母為小寫），將其轉換為十進制數(shù)輸出。請將程序空缺部分補全。intf（char*s）{intn=0，i；for（i=0；s[i]!="\0";i++）n=n*16+（1）；returnn；}main（）{chars[10]；scanf（"％s”，s）；printf（"％d\n”（2））；}【浙江大學2002二（6分）】正確答案：(正確答案：(1)(s[i]>=977s[i]—87：s[i]-48)//"a"到"f”的ASCII碼是97到102(2)f(s))巳知U='xyxyxyxxyxy'；t='xxy'；ASSIGN(S，U)；ASSIGN(V，SUBSTR(S，INDEX(s，t)，LENCt)+1)),ASSIGN(m，'ww')求REPLACE(S，y，m)=?！緰|北大學1997一、1(5分)】正確答案：（正確答案：'xyxyxywwy'）實現(xiàn)字符串拷貝的函數(shù)strcpy為：voidstrcpy（char*s，char*t）/*copyttos*/{while（））【浙江大學1999一、5（3分）】正確答案：（正確答案：*s++=*t++或（*s++=*t++）!='\0'）下列程序判斷字符串s是否對稱；對稱則返回1，否則返回0；如f“abba”）返回1，f"abab”）返回0。intf（（1））{inti=0，j=0；while（8[j]）（2）；for（J一一；i正確答案：(正確答案：(I)chars[](或char*s)(2)j++(3)i>=j)下列算法實現(xiàn)求采用順序結構存儲的串s和串t的一個最長公共子串。voidmaxcomstr(order8tring*s，*t，intindex，length)(inti，j，k，lengthl，con；index=0；length=0；i=1；while(i<=s.1en){j=1；while(j<=t.1en){if(S[i]_=t[j])ik=1;lengthl=1;con=1;while(con)if(1){lengthl=leng七h1+1;k=k+1;)else(2);if(1engthl>length)(index=i；length=length1；)(3);}else(4)；}(5)}}【上海大學2000一、2(10分)】正確答案：（正確答案：本題算法采用順序存儲結構求串S和串t的最大公共子串。串s用i指針（1WiWs.len）。串t用j指針（1WjWr.len）。算法思想是對每個i（1WiWs.len，即程序中第一個while循環(huán)），來求從i開始的連續(xù)字符串與從f（1WjWt.len，即程序中第二個while循環(huán)）開始的連續(xù)字符串的最大匹配。程序中第三個（即最內層的）while循環(huán)，是當S中某字符（s[i]）與t中某字符（t[f]）相等時，求出局部公共子串。若該子串長度大于巳求出的最長公共子串（初始為0），則最長公共子串的長度要修改。（1）i+k<=s.len&&J+k<=t.len&&s[i+k]==t[j+k]//如果在s和t的長度內，對應字符相等，則指針k后移（加1）（2）con=0//s和t對應字符不等時置標記退出（3）j=j+k//在t串中，從第j+k字符再與s[i]比較（4）j=j+1//t串取下一字符（5）i=i+1//s串指針i后移（加1））下列是判斷是否為回文(順讀與逆讀字符串一樣，串中不含空格)的算法。#include#include#include#defineStackSize100//定義棧類型typedefstruct{chardata[StackSize]；intTop;)SeqStack；charStr[100]="madamimadam”；voidPush(SeqStack*s,charx)//進棧(if(S—>Top=：stacksize一1)printf("Stackoverflow”)；(1)；)charPop(SegStack*s)//出棧{if,(S—>Top==—1)printf(”Stackunderflow”)；return(2)；}intIsHuiwen(char*S){SeqStackT；inti,n；chartl；T.Top=一1；n=strlen(s)；//求向量長度for(i=0；i<n/2；i++)Push(&T,S[i])；//將一半字符入棧i=n/2—1；while(i>=0){tl=(3)；//每彈出一個字符與相應字符作比較if((4))return0；//不相等則返回0i一一；}return1；1//比較完畢均相等則返回1voidmain(){if(IsHuiwen(Str))printf("\n這個字符串是回文。")；elseprintf("\n這個字符串不是回文。")；}【北京交通大學2006七、2(8分)】正確答案：(正確答案：(1)S—>data[++s—>Top]=x(2)S—>dataIs—>Top一一](3)S[i](4)s[i]!=T[i])算法填空。/*copyacharacterstringfrom。from'to。to。’/voidcopystring(to,from)char*to,*from；{while(*from){(1)；++from；(2)；)*to='\0'；}/*searchalinkedlistforspecifiedvalue*/structlistrec{intvalue；structlistrec*next；)structlistrec*search(listptr,match)structlistrec*listptr；intmatch；{while(listptr!=(3))1f((4)==match)breakelse(5);return(1istptr)；}【中國海洋大學2006四(10分)】正確答案：(正確答案：(1)*to：*from(2)++to(3)null(4)listptr—>value(5)return(null))設模式T="abcabaabc"，求它的next函數(shù)的修正值nextval,下面的函數(shù)用于求模式T的nextval之值。其中，T[0]用于保存模式T的字符個數(shù)，而T[1],T[2],……，T[M]依次保存模式T的各個字符。請在該函數(shù)中的[A]、[B]處各填入一個賦值表達式，使得數(shù)組nextval能夠給出模式T的next函數(shù)的修正值nextval。voidget一nextval(sstringT,int&nextval[]){i=I,nextval[1]=0；j=0；while(i正確答案：(正確答案：[A]nextval[i]=nextval[j][B]j=nextval[j])以下程序的功能是把一個輸入字符串倒序輸出，請找出并改正其中的錯誤。voidreverse(char*s){intlen=strlen(S)；char*dest=newchar[1en]；inti=0;while(1en-一！=0){}printf(…)；return0；}【北京大學2008三(10分)】正確答案：(正確答案：(1)第一個循環(huán)體…處應是賦值語句：*(dest+i++)=*(s+len)；(2)printf的…處應該輸出倒序的字符串：“％s”，dest(3)函數(shù)類型是void，不應有返回值，要刪除return0；)二、綜合題(總題數(shù)：14，分數(shù)：34.00)串?！敬筮B海事大學1996一、10(1分)】【河海大學1998二、5(3分)】正確答案：(正確答案：串是零個至多個字符組成的有限序列。從數(shù)據(jù)結構角度講，串屬于線性結構。與線性表相比，其特殊性在于串的元素是字符，串的操作經常以整體(字符串)出現(xiàn)。)描述以下概念的區(qū)別：空格串與空串。【大連海事大學1996三、2.(1)(2分)】正確答案：(正確答案：空格是一個字符，其ASCII碼值是32?？崭翊怯煽崭窠M成的串，其長度等于空格的個數(shù)?？沾遣缓魏巫址拇?，即空串的長度是零，其ASCII碼值是0。)兩個字符串S1和S2的長度分別為m和n。求這兩個字符串最大共同子串算法的時間復雜度為T(m,n)。估算最優(yōu)的r(m,n),并簡要說明理由?！颈本┕I(yè)大學1996_、5(6分)】正確答案：(正確答案：最優(yōu)的T(m,n)是O(n)。S2是串S1的子串，且在S1中的位置是1。開始求出最大公共子串的長度恰是串S2的長度。一般情況下，T(m,n)=O(m*n)。)KMP算法(字符串匹配算法)較Brute算法(樸素的字符串匹配算法)有哪些改進？【大連海事大學1996三、l(2分)】正確答案：（正確答案：樸素的模式匹配（Brute-Force）時間復雜度是O（m*n）,KMP算法有一定改進，時間復雜度達到O（m+n）。主要優(yōu)點是主串指針不回溯。當主串很大不能一次讀入內存且經常發(fā)生部分匹配時，KMP算法的優(yōu)點更為突出。）給出字符串’abacabaaad’在KMP算法中的next和nextval數(shù)組?！颈本┼]電大學2000三、1（5分）】正確答案：（正確答案：模式串的next函數(shù)定義如下：當此集合不空時根據(jù)此定義，可求解模式串IWn-inj"abacabaaad"的next和nextval值如下：）設字符串S="aabaabaabaac’，P=aabaac’。（分數(shù)：4.00）（1）.給出S和P的next值和nextval值;正確答案：（正確答案：S的next與nextval值分別為012123456789和002002002009。P的next與nextval值分別為012123和002003o）（2）.若S作主串，P作模式串，試給出利用BF算法和KMP算法的匹配過程?！颈狈浇煌ù髮W1998二（15分）】正確答案：（正確答案：利用BF算法的匹配過程：利用KMP算法的匹配過程：第一趟匹配：aabaabaabaac第一趟匹配：aabaabaabaacaabaac（i=6，j=6）aabaac（i=6，j=6）第二趟匹配：aabaabaabaac第二趟匹配：aabaabaacaa（i=3，j=2）（aa）baac第三趟匹配：aabaabaabaac第三趟匹配：aabaabaabaaca（i=3，j=1）（成功）（aa）baac第四趟匹配：aabaabaabaacaabaac（i=9，j=6）第五趟匹配：aabaabaabaacaa（i=6，j=2）第六趟匹配：aabaabaabaaca（i=6，j=1）第七趟匹配：aabaabaabaac（成功）aabaac（i=13，j=7））設目標為t="abcaabbabcabaacbacba"，模式為p="abcabaa"°（分數(shù)：4.00）（1）.計算模式p的nextval函數(shù)值；（5分）正確答案：（正確答案：P的nextval函數(shù)值為0110132（p的next函數(shù)值為0111232）。）（2）.不寫出算法，只畫出利用KMP算法進行模式匹配時每一趟的匹配過程。（5分）【清華大學1998八（10分）】正確答案：（正確答案：利用KMP（改進的nextval）算法，每趟匹配過程如下：第一趟匹配：abcaabbabcabaacbacbaabcab（i=5，j=5）第二趟匹配：abcaabbabcabaacbacbaabc（i=7，j=3）第三趟匹配：abcaabbabcabaacbacbaa（i=7，j=1）第四趟匹配：abcaabbabcabaacbacba（成功）abcabaa（i=15，j=8））模式匹配算法是在主串中快速尋找模式的一種有效的方法，如果設主串的長度為m，模式的長度為n，則在主串中尋找模式的KMP算法的時間復雜性是多少？如果某一模式’P=-"abcaacabaca”，請給出它的NEXT。函數(shù)值及NEXT函數(shù)的修正值NEXTVAL之值?！旧虾＝煌ù髮W2000一（5分）】正確答案：（正確答案：KMP算法的時間復雜度是O（m+n）。P的NEXT和NEXTVAL值分別為01112212321和01102201320。）設目標為S="abcaabbcaaabababaabca’，模式為P="babab"°（分數(shù)：4.00）（1）.手工計算模式P的nextval數(shù)組的值；（5分）正確答案：（正確答案：p的nextval函數(shù)值為01010（next函數(shù)值為01123）。）（2）.寫出利用求得的nextval數(shù)組，按KMP算法對目標S進行模式匹配的過程。（5分）【清華大學1997四（10分）】正確答案：（正確答案：手工模擬對s的匹配過程，與上面第6題類似，為節(jié)省篇幅，故略去。）設模式串t為"abcabcacabca"，，給出其失敗函數(shù)?！炯执髮W2007二、6（3分）】正確答案：（正確答案：模式串"abcabcacabca"的失敗函數(shù)為：011123451234。）主串$="abbacbabbcabbcabbcabcaabbc”，子串=“abbcabcaa"，若用簡單模式匹配算法，查找成功需要比較多少次?若用.KMP算法，查找成功需要比較多少次?并計算出相應的NEXT[]數(shù)組和NEXTVAL：]數(shù)組值?！敬筮B理工大學2005二、4（20/4分）】正確答案：（正確答案：簡單模式匹配算法，查找成功需要比較15趟39次。若用KMP算法，查找成功需要比較，7趟27次。NEXT[]和NEXTVAL：]數(shù)組值分別是011112312和011101.302。）I-在字符串模式匹配的KMP算法中，求模式的next數(shù)組值的定義如下：——請問：（1）當j=1時，為什么要取next[1]=0?（2）為什么要取max{塒，尼最大是多少？（3）其他情況是什么情況?為什么取next[j]=17【北京郵電大學1994二（8分）】正確答案：（正確答案：（1）當模式串中第一個字符與主串中某字符比較不等（失配）時，next[1]=0表示模式串中巳沒有字符可與主串中當前字符s[t]比較，主串當前指針應后移至下一字符，再和模式串中第一個字符進行比較。（2）當主串第i個字符與模式串中第j個字符失配時，若主串f不回溯，則假定模式串第k個字符與主串第i個字符比較，k值應滿足條件1<k<j并且。"p1pk-1"="pi-k+1--pi-1-，即k為模式串向后移動的距離，k