【文章內(nèi)容簡介】 { int x； scanf(x)； if(x=0) sum=0 else {test(sum)。 sum+=x。} printf(sum)； } 從鍵盤上輸入一個逆波蘭表達(dá)式，用偽碼寫出其求值程序。規(guī)定：逆波蘭表達(dá)式的長度不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔,操作符只可能有+、*、/四種運算。例如：234 34+2*$第四章 串一、 選擇題 串是一種特殊的線性表，其特殊性體現(xiàn)在( 　)。 A) 可以順序存儲 　 　B) 數(shù)據(jù)元素是一個字符 C) 可以鏈接存儲 　　 D) 數(shù)據(jù)元素可以是多個字符有兩個串P和Q，求P在Q中首次出現(xiàn)的位置的運算稱(　　 )。 A ) 模式匹配　　 B) 連接　 C) 求子串 　 　D) 求串長設(shè)S為一個長度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串（非空且不同于S本身）的個數(shù)為（ ）。A） n2 B）(n2/2)+(n/2) C）(n2/2)+(n/2)1 D） (n2/2)(n/2)1 設(shè)串s1=39。ABCDEFG39。,s2=39。PQRST39。,函數(shù)concat(x,y)返回x和y串的連接串，subString(s,i,j)返回串s的從序號i的字符開始的j個字符組成的子串，Strlength(s)返回串s的長度，則concat(subString(s1,2,Strlength(s2)),subString(s1,Strlength(s2),2)))的結(jié)果串是( )。 A) BCDEF　 　 B) BCDEFG 　　 C) BCPQRST　　 　 D) BCDEFEF順序串中，根據(jù)空間分配方式的不同，可分為( )。 A) 直接分配和間接分配 B) 靜態(tài)分配和動態(tài)分配 C) 順序分配和鏈?zhǔn)椒峙? D) 隨機(jī)分配和固定分配設(shè)串S=”abcdefgh”，則S的所有非平凡子串（除空串和S自身的串）的個數(shù)是（ ）。A) 8 ； B) 37； C) 36； D) 35。設(shè)主串的長度為n，模式串的長度為m，則串匹配的KMP算法時間復(fù)雜度是（ ）。A) O(m) ； B) O(n)； C) O(m+n)； D) O(n* m)。已知串S=‘a(chǎn)aab’,其Next數(shù)組值為（ ）。A．0123 B．1123 C．1231 D．1211二、 填空題 在空串和空格串中，長度不為0的是( )。 空格串是指( )，其長度等于( )。按存儲結(jié)構(gòu)不同，串可分為( )、（ ）、（ ）。C語言中，以字符(　　 )表示串值的終結(jié)。在塊鏈串中，為了提高存儲密度，應(yīng)該增大( ).假設(shè)每個字符占1個字節(jié)，若結(jié)點大小為4的鏈串的存儲密度為50%，則其每個指針占( 　)個字節(jié)。串操作雖然較多，但都可通過五種操作（ ）、（ ）、（ ）、 （ ）、（ ）構(gòu)成的最小子集中的操作來實現(xiàn)。設(shè)串S=’Ilikeputer .’，T=’’，則Length (S ) = （ ）。Index(S,T,1) = ( )在KMP算法中，next[j]只與（ ）串有關(guān)，而與（ ）串無關(guān)。字符串’ababaaab’的nextval函數(shù)值為（ ）。1兩個字符串相等的充分必要條件是（ ）。12．實現(xiàn)字符串拷貝的函數(shù) strcpy為： void strcpy(char *s , char *t) /*copy t to s*/{ while ( ________ ) ； } 三、 問答題與算法題 簡述下列每對術(shù)語的區(qū)別：空串和空格串：串常量和串變量：主串和子串：目標(biāo)串和模式串。在C語言中假設(shè)有如下的串說明：　char s1[30]=Stocktom, s2[30]=March51999, s3[30], 　(１)在執(zhí)行下列語句后，s3的值是什么?strcpy(s3,s1)。 strcat(s3,)。 strcat(s3,s2)。 　(２)調(diào)用函數(shù)strcmp(s1,s2)的返回值是什么? 　(３)調(diào)用函數(shù)strcmp(s1[5],Ton)的返回值是什么? 　(４)調(diào)用函數(shù)strlen(strcat(s1,s2))的返回值是什么? ３、 利用C的庫函數(shù)strlen,strcpy和strcat寫一算法void StrInsert(char *S, char *T, int i),將串T插入到串S的第i個位置上。若i大于S的長度，則插入不執(zhí)行。void StrInsert(char *S, char *T, int i)利用C的庫函數(shù)strlen 和strcpy(或strcpy)寫一算法void StrDelete(char *S,int i, int m)刪去串S中從位置i開始的連續(xù)m個字符。若i≥strlen(S),則沒有字符被刪除；若i+m≥strlen(S),則將S中從位置i開始直至末尾的字符均刪去。void StrDelete(char *S, int i ,int m) //串刪除若S和T是用結(jié)點大小為1的帶頭結(jié)點的單鏈表存儲的兩個串，試設(shè)計一個算法找出S中第一個不在T中出現(xiàn)的字符。 　Int indexst(LinkList S, linkLint T)　在KMP算法中，求下列模式串的next[j]。（1） ‘a(chǎn)baabcac’ （2）’aaabaaba’設(shè)目標(biāo)為t=‘a(chǎn)bcaabbabcabaacbacba’,模式為p=‘a(chǎn)bcabaa’（1）計算模式p的naxtval函數(shù)值；（2）不寫出算法,只畫出利用KMP算法進(jìn)行模式匹配時每一趟的匹配過程。11．寫一個遞歸算法來實現(xiàn)字符串逆序存儲，要求不另設(shè)串存儲空間。第五章 數(shù)組與廣義表一、 選擇題稀疏矩陣的一般壓縮方法是( )。 A) 二維數(shù)組 B) 廣義表 C) 三元組表 D) 一維數(shù)組設(shè)矩陣A是一個對稱矩陣，為了節(jié)省空間，將其下三角部分按行優(yōu)先存放在一維數(shù)組B中。對下三角矩陣中任一元素aij (i=j)，在一維數(shù)組B中下標(biāo)ｋ的值是( 　)。 A) i(i1)/2+j1 　 B) i(i1)/2+j C) i(i+1)/2+j1 D) i(i+1)/2+j在稀疏矩陣的三元組表示法中，每個三元組表示( )。 A) 矩陣中數(shù)據(jù)元素的行號、列號和值 B) 矩陣中非零元素的值 C) 矩陣中非零元素的行號和列號 D) 矩陣中非零元素的行號、列號和值對稀疏矩陣進(jìn)行壓縮存儲是為了( 　)。 A) 便于進(jìn)行矩陣運算 B) 便于輸入和輸出 C) 節(jié)約存儲空間 D) 降低運算的時間復(fù)雜度 假設(shè)以行序為主序存儲二維數(shù)組A=array[1..100，1..100]，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC[5，5]=（ ）。 A） 808 B） 818 C）1010 D） 1020 設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A[5，8]的存儲首地址為( )。A） BA+141 B） BA+180 C） BA+222 D） BA+225廣義表是線性表的推廣，它們之間的區(qū)別在于(　　 )。 A) 能否使用子表 　B) 能否使用原子項 C) 表的長度 　 D) 是否能為空已知廣義表L=（（x,y,z），a，（u，t，w）），從L表中取出原子項t的運算是（ ）。A. head（tail（tail（L））） B. tail（head（head（tail（L）））） C. head（tail（head（tail（L）））） D. head（tail(head（tail（tail（L）））)）已知廣義表: A=(a,b), B=(A,A), C=(a,(b,A),B),下列運算的結(jié)果是: tail(head(tail(C))) =( )。A）（a） B） A C） a D） (b) E） b F） (A) 廣義表運算式Tail(((a,b),(c,d)))的操作結(jié)果是（ ）。A） ( ) B） c,d C） ((c,d)) D） d1廣義表（（a,b,c,d））的表頭是（ ），表尾是（ ）。A） a B）（） C）（a,b,c,d） D）（b,c,d）1設(shè)廣義表L=（（a,b,c）），則L的長度和深度分別為（ ）。 A） 1和1 B） 1和3 C） 1和2 D）2和31下面說法不正確的是( )。 A） 廣義表的表頭總是一個廣義表 B） 廣義表的表尾總是一個廣義表C） 廣義表難以用順序存儲結(jié)構(gòu) D） 廣義表可以是一個多層次的結(jié)構(gòu)1已知廣義表LS＝((a,b,c),(d,e,f)),運用head和tail函數(shù)取出LS中原子e的運算是( )。 A）head(tail(LS)) B） tail(head(LS))C）head(tail(head(tail(LS))) D) head(tail(tail(head(LS))))1設(shè)一個廣義表中結(jié)點的個數(shù)為n，則求廣義表深度算法的時間復(fù)雜度為( )。 A) O(1) B) O(n) C) O(n2) D) O(log2n)二、 填空題n維數(shù)組中的每個元素都最多有( )個直接前趨。對于一個一維數(shù)組A[12]，若一個數(shù)據(jù)元素占用字節(jié)數(shù)為S，首地址為1，則A[i](i=0)的存儲地址為( )，若首地址為d，則A[i]的存儲地址為( )。已知二維數(shù)組A[m][n]采用行優(yōu)先順序存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址LOC（A[0][0]），則A[i][j]的地址是( )。 多維數(shù)組中，數(shù)據(jù)元素的存放地址直接可通過地址計算公式計算出。因此，數(shù)組是一種( )存取結(jié)構(gòu)。 矩陣的壓縮存儲就是為多個相同的非零元素分配( )個存儲空間，零元素不分配空間。遞歸是算法設(shè)計的重要方法，遞歸由（ ）項和（ ）項構(gòu)成。用遞歸的方法求廣義表LS的深度DEPTH(LS)，寫出基本項和遞歸項。 基本項：遞歸項： 廣義表( a , ( a , b ) , d , e , ((i , j ) , k ) ) 的長度是（ ），深度是（ ）。廣義表((a) , (( b ) , c ) , (((d )))) 的長度是（ ），深度是（ ）。設(shè)廣義表S=((a , b) , ( c , d))，GetHeat(S)和GetTail(S)是取廣義表的表頭和表尾函數(shù)。則 GetHeat(GetTail(S)) = ( ) ， GetTail (GetHeat (S)) =( )。設(shè)廣義表S=(a , b , ( c , d) , (e , (f , g )))，GetHeat(S)和GetTail(S)是取廣義表的表頭和表尾函數(shù)。則GetHeat(GetTail(GetHeat (GetTail(GetTail(S)))))= ( )1二維數(shù)組a[4][5][6]（下標(biāo)從0開始計，a有4*5*6個元素），每個元素的長度是2，則a[2][3][4]的地址是( ) 。(設(shè)a[0][0][0]的地址是1000,數(shù)據(jù)以行為主方式存儲)1設(shè)有二維數(shù)組A[0..9,0..19],其每個元素占兩個字節(jié)，第一個元素的存儲地址為100，若按列優(yōu)先順序存儲，則元