數(shù)據(jù)結(jié)構(gòu)試題精選（4）-算法設(shè)計(jì)_跨考網(wǎng)

　算法設(shè)計(jì)

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

　　2．輸入一個(gè)字符串，內(nèi)有數(shù)字和非數(shù)字字符，如：ak123x456 17960?302gef4563，將其中連續(xù)的數(shù)字作為一個(gè)整體，依次存放到一數(shù)組ａ中，例如123放入ａ［０］,456放入ａ［１］，…　…　。編程統(tǒng)計(jì)其共有多少個(gè)整數(shù)，并輸出這些數(shù)?！?a target="_blank">上海大學(xué) 1998 一 （13分）】

　　3． 以順序存儲(chǔ)結(jié)構(gòu)表示串，設(shè)計(jì)算法。求串S中出現(xiàn)的第一個(gè)最長(zhǎng)重復(fù)子串及其位置并分析算法的時(shí)間復(fù)雜度?！?a target="_blank">東南大學(xué) 2000 五 （15分）】

　　類似本題的另外敘述有：

　?。?）如果字符串的一個(gè)子串（其長(zhǎng)度大于1）的各個(gè)字符均相同，則稱之為等值子串。試設(shè)計(jì)一算法，輸入字符串S，以“！”作為結(jié)束標(biāo)志。如果串S中不存在等值子串，則輸出信息“無等值子串”，否則求出（輸出）一個(gè)長(zhǎng)度最大的等值子串。

　　例如：若S=“abc123abc123!”，則輸出“無等值子串”；若S=“abceebccadddddaaadd!”，則輸出“ddddd”。

　　【華中科技大學(xué) 2001】

　　4．假設(shè)串的存儲(chǔ)結(jié)構(gòu)如下所示，編寫算法實(shí)現(xiàn)串的置換操作?！?a target="_blank">清華大學(xué) 1995 五（15分）】

　　TYPE strtp =RECORD

　　ch: ARRAY[1..maxlen]? OF? char;

　　curlen:0..maxlen

　　END;

　　5．函數(shù)void insert(char*s,char*t,int pos)將字符串t插入到字符串s中，插入位置為pos。請(qǐng)用c語(yǔ)言實(shí)現(xiàn)該函數(shù)。假設(shè)分配給字符串s的空間足夠讓字符串t插入。（說明：不得使用任何庫(kù)函數(shù)）

　　【北京航空航天大學(xué) 2001 六 （10分）】

　　6．設(shè)計(jì)一個(gè)二分檢索的算法,在一組字符串中找出給定的字符串,假設(shè)所有字符串的長(zhǎng)度為4。

　?。?）簡(jiǎn)述算法的主要思想；(3分)

　?。?）用PASCAL語(yǔ)言分別對(duì)算法中用到的類型和變量作出說明；(3分)

　?。?）用類PASCAL語(yǔ)言或自然語(yǔ)言寫算法的非遞歸過程； (8分)

　?。?）分析該算法的最大檢索長(zhǎng)度；(3分)

　?。?）必要處加上中文注釋。(3分)

　　【山東工業(yè)大學(xué) 1995 八 （20分）】

　　7．設(shè)計(jì)一PASCAL 或C語(yǔ)言的函數(shù) atoi(x).其中X 為字符串，由0--9十個(gè)數(shù)字符和表示正負(fù)數(shù)的‘-’組成，返回值為整型數(shù)值 ?！?a target="_blank">浙江大學(xué) 1994 二? (7分)】

　　8．已知字符串S1中存放一段英文，寫出算法format(s1,s2,s3,n),將其按給定的長(zhǎng)度n格式化成兩端對(duì)齊的字符串S2, 其多余的字符送S3。 【首都經(jīng)貿(mào)大學(xué) 1998 三、8（15分）】

　　9．串以靜態(tài)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，結(jié)構(gòu)如下所述，試實(shí)現(xiàn)串操作equal算法.

　　CONST? maxlen=串被確認(rèn)的最大長(zhǎng)度

　　TYPE? strtp=RECORD

　　ch:ARRAY[1..maxlen] OF char;

　　curlen:0..maxlen

　　END;

　　(以一維數(shù)組存放串值，并設(shè)指示器curlen指示當(dāng)前串長(zhǎng))【北京輕工業(yè)大學(xué) 1998 一 （12分）】

　　10．編寫程序，統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為A-Z這26個(gè)字母和0-9這10個(gè)數(shù)字）?！?a target="_blank">西北大學(xué) 2000 四 (10分)】

　　11．寫一個(gè)遞歸算法來實(shí)現(xiàn)字符串逆序存儲(chǔ)，要求不另設(shè)串存儲(chǔ)空間。 【西南交通大學(xué) 2000 三、2】

　　12．已知三個(gè)字符串分別為s=’ab…abcaabcbca…a’，s’=’caab’,? s’’=’bcb’。利用所學(xué)字符串基本運(yùn)算的函數(shù)得到結(jié)果串為：s’’’=’caabcbca…aca…a’，要求寫出得到上結(jié)果串S’’’所用的函數(shù)及執(zhí)行算法。【東北大學(xué) 1998 一、1 (10分)】

　　13．S=“S1S2…Sn”是一個(gè)長(zhǎng)為N的字符串，存放在一個(gè)數(shù)組中，編程序?qū)改造之后輸出：

　?。?）將S的所有第偶數(shù)個(gè)字符按照其原來的下標(biāo)從大到小的次序放在S的后半部分；

　?。?）將S的所有第奇數(shù)個(gè)字符按照其原來的下標(biāo)從小到大的次序放在S的前半部分；

　　例如：

　　S=‘ABCDEFGHIJKL’

　　則改造后的S為‘ACEGIKLJHFDB’?！局锌圃河?jì)算所 1995】

　　14．編一程序，對(duì)輸入的一表達(dá)式（字符串），輸出其TOKEN表示。表達(dá)式由變量A，B，C，常數(shù)（數(shù)字）0，1，…，9，運(yùn)算符+，*和括號(hào)“（”，“）”組成。首先定義符號(hào)的類碼：

　　符號(hào)變量常量*+（）

　　類碼012345

　　其次定義符號(hào)的TOKEN表示：

　　其中NAMEL是變量名表（不允許有相同名），CONST是常量表（不允許有相同數(shù)）。

　　例如，假設(shè)有表達(dá)式（A+A*2）+2*B*3#，則將生成如下TOKENL：

　　【吉林大學(xué) 1995 一? (20分)】