數(shù)據(jù)結(jié)構(gòu)習題精編：串和數(shù)組

1、數(shù)據(jù)結(jié)構(gòu)習題精編：串和數(shù)組20、選擇題1下面關(guān)于串的的敘述中，不正確的是A 串是字符的有限序列B 空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運算D 串既可以采用順序存儲，也可以采用鏈式存儲2下面關(guān)于串的的敘述中，正確的是A 空串就是空白串B 串相等指的是串的長度相等C.串的長度必須大于零D.串是一種特殊的線性表3字符串是一種特殊的線性表，它與一般線性表的區(qū)別是A 字符串是一種線性結(jié)構(gòu)B 字符串可以進行復(fù)制操作C.字符串可以順序存儲也可以鏈式存儲D 字符串由字符構(gòu)成并且通常作為整體參與操作4串s="Data Structure "中長度為3 的子串的數(shù)目是A9B11C12

2、D145若串S="software" ，則 S 的子串的數(shù)目是A8B35C36D376已知串S= "string" ， T="this" ，執(zhí)行運算StrLength(StrCopy(S,T) 的結(jié)果是A2B4C6D107若串S="SCIENCESTUDY" ，則調(diào)用函數(shù)StrCopy(P,SubString(S,1,7) 后得到AP="STUDY"B P="SCIENCE" CS="STUDY"DS="SCIENCE"8若字符串采用鏈

3、式存儲，每個字符占用一個字節(jié)，每個指針在占用四個字節(jié)，則該字符串的存儲密度為9為查找某一特定單詞在文本中出現(xiàn)的位置，可應(yīng)用的串運算是A 20%B 25%C 50%D 75%A 串聯(lián)接10當目標串的長度為的比較次數(shù)B 求子串n,模式串的長度為C.串比較D 子串定位m時，樸素的模式匹配算法最好情況下字符A m11當目標串的長度為的比較次數(shù)B nn,模式串的長度為C n-mD n+mm時，樸素的模式匹配算法最壞情況下字符A mB nC (n-m+1)*mD n*m12.已知串S="aaab",其Next數(shù)組的元素值依次為A 0、 1、 2、 3 B 1、 1、 2、 3C 1 、

4、 2、 1、 1D 1、 2、 3、 113串"ababaaababaa" 的 next 數(shù)組為A 011234223456 B 01212111121214字符串"ababaabab" 的 nextval 為C 0123012322345D 012345678999A (0,1,0,1,0,0,0,1,1)B (0,1,0,1,0,1,0,1,1)C (0,1,0,1,0,2,1,0,1)D(0,1,0,1,0,4,1,0,1)15二維數(shù)組A1020 采用按行為主序的存儲方式，每個元素占若 A00 的存儲地址為300，則A810 的地址為A 660B

5、732C 98016二維數(shù)組A56 采用按列為主序的存儲方式，每個元素占4 個存儲單元，D 11323 個存儲單元，若A00 的存儲地址是100，則A43 的存儲地址是A 157B 166C 169D 18117二維數(shù)組A 按行優(yōu)先順序存儲，其中每個元素占1 個存儲單元。若A11 的存儲地址為 420， A33 的存儲地址為446，則A55 的存儲地址為A 470B 471C 472D 47318假設(shè)以行優(yōu)先順序存儲三維數(shù)組R696 ，其中元素R000 的地址為2100，每個元素占4 個存儲單元，則存儲地址為2836 的元素是A R333 B R334C R434D R43519設(shè)二維數(shù)組A1

6、. m1. n (即 m 行 n 列)按行存儲在數(shù)組B1. m*n 中，則二維數(shù)組元素Aij 在一維數(shù)組B 中的下標為A(i-1 ) *n+j-1 B(i-1 ) *n+jC i*( j-1 )D j*m+i-120設(shè)有二維數(shù)組A810 ， A00 的存儲地址為LOC ，每個元素占2L 個存儲單元，在以行序為主序的存儲方式下，某數(shù)據(jù)元素的地址為LOC+50L ，則在以列序為主序的存儲方式下，該元素的存儲地址為ALOC+26LB LOC+42LCLOC+50LDLOC+84L21對矩陣壓縮存儲是為了A.方便運算B.方便存儲C.提高運算速度D.減少存儲空間22.設(shè)有一個10階的對稱矩陣A,采用行優(yōu)

7、先壓縮存儲方式，ai,i為第一個元素，其存儲地址為1,每個元素占一個字節(jié)空間，則 a8,5的地址為A i3B 32C 33D 7523設(shè)有一個對稱矩陣ANN ， A11 為首元素，將其下三角(包括對角線)元素以行優(yōu)先順序存儲到一維數(shù)組元素T1 至 TN(N+1) 2中，則任一上三角元素A皿(i<j)存于Tk中，下標k為A i(i-1) 2+j B i(i+1) 2+j C j(j-1) 2+iD j(j+1) 2+i24設(shè)A 是 n*n 的對稱矩陣，將A 的對角線及對角線上方的元素以列為主的次序存放在一維數(shù)組 B1.n(n+1)/2中，對上述任一元素aij (K j j 且i <)

8、j在B中的位置為A i(i-l)/2+j-1 B i(i-l)/2+jC j(j-l)/2+i-1Dj(j-l)/2+i25設(shè)有一5 階上三角矩陣A55 ，現(xiàn)將其上三角中的元素按列優(yōu)先順序存放在一維數(shù)組 B15 中。已知A11 存放在 B1 中，其地址為100，每個元素占用2 個存儲單元，則A34 的地址為A 116B 118C 120D 12226將一個三對角矩陣A100100 ，按行優(yōu)先存入一維數(shù)組B298 中， A11 存放在 B1 中。 A 中元素 A6665 ，在 B 數(shù)組中的位置K 為A 194B 195C 197D 19827有一個100*90 的稀疏矩陣，非0 元素有 10 個

9、(均為整數(shù))。設(shè)每個整型數(shù)占2個字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是A 20B 60C 66D 1800028下面關(guān)于廣義表的說法中，不正確的是下面關(guān)于廣義表的說法中，不正確的是A 廣義表的表頭總是一個廣義表C.廣義表難以用順序結(jié)構(gòu)存儲B 廣義表的表尾總是一個廣義表29已知廣義表的表頭為30廣義表(已知廣義表的表頭為a,A (a,b,c)Ba，(b， c)， d，表尾為(a,(b,c)b，c)D.廣義表可以是,則此廣義表為C (a),b,c)個多層次的結(jié)構(gòu)D (a,b,c)e)的表頭為A a31設(shè)廣義表L=A 1 和 132設(shè)廣義表L=A cBa， b，a，(B b，B(a)c)1和c

10、)b， c33.對于廣義表 A,若A ( )C a,(b,c)的長度和深度分別為C1 和 3D (a,(b,c)D 2和 3GetTail (L)操作后的結(jié)果為C(b， c)GetHead(A) 等于 GetTail(A) ，則表 A 為B ( )C( ),( )D ( b， c)D ( ),( ),( )34.對廣義表 L=(a, b), (c, d), (e, f)執(zhí)行操作 GetTail(GetTail(L)的結(jié)果是A( )B(f)C(e,f)D(e,f)35對廣義表L=(a， b)， c， d) 執(zhí)行操作GetTail(GetHead(L) 的結(jié)果是AbB(b)C(d)D( c，d)3

11、6 已知廣義表A=(a,b) ， B=(A,A) ， C=(a,(b,A),B) ， 執(zhí)行操作GetTail(GetHead(GetTail(C)后的結(jié)果為A bB (b)C AD (A)37 .從廣義表LS= (p, q), r, s)中分解出原子q的運算是A GetTail (GetHead (LS)B GetHead (GetTail (GetHead (LS)C GetHead (GetTail (LS)D GetTail (GetTail (GetHead (LS)38 .已知廣義表LS=(a, b, c), (d, e, f),從LS中分離出原子 e的運算是A GetHead(Ge

12、tTail(LS)B GetTail(GetHead(LS)C GetHead(GetTail(GetHead(GetTail(LS)D GetHead(GetTail(GetTail(GetHead(LS)、填空題39 空格串是指，其長度等于。40 組成串的數(shù)據(jù)元素只能是。3 串是一種特殊的線性表，其特殊性表現(xiàn)在； 串的兩種最基本的存儲方式是 ；兩個串相等的充分必要條件是。4若串S1="ABCDEFG", S2="9876" ,S3="#",S4="012345" ，執(zhí)行Concat(Replace(S1,Sub

13、String(S1,StrLength(S2),StrLength(S3),S3),SubString(S4,Index(S2, "8"),StrLength(S2)4 設(shè)T 和 P 是兩個給定的串，在T 中尋找等于P 的子串的過程稱為，又稱 P 為 。6 Index( "DATASTRUCTURE" ， "STR" ) =。7 設(shè)正文串長度為n， 模式串長度為m， 則串匹配的KMP 算法的時間復(fù)雜度為。8 模式串P="abaabcac"的next函數(shù)值序列為。9 字符串"ababaaab"的n

14、extval函數(shù)值序列為 。10已知串U="xyxyxyxxyxy" ， t=" xxy" ；依次執(zhí)行StrAssign ( S， U )；StrAssign( V， SubString( S， Index( S， t)，StrLength ( t) +1 )；StrAssign ( m， "ww" )；Replace( S， V， m)； 后， S= ， V= 。11設(shè)串S="abcdefgh" ， T="xyzw" 。依次執(zhí)行SubString(X ， S， 3， StrLength(T)

15、；SubString(Y ， S， StrLength(T) ， 2)；Concat(Z， X， Y)；后，串 Z 的值為 。12實現(xiàn)字符串拷貝的函數(shù)strcpy 可寫為：void strcpy(char *s ， char *t)/ copy t to swhile () ；13有一個二維數(shù)組A85 ，每個數(shù)組元素用相鄰的4 個字節(jié)存儲，存儲器按字節(jié)編址，假設(shè)存儲數(shù)組第1 個元素 A00 的第一個字節(jié)的地址是0，存儲數(shù)組A 的最后一個元素的第一個字節(jié)的地址是。若按行序優(yōu)先存儲，則A34 和 A53 的第一個字節(jié)的地址是和 。若按列序優(yōu)先存儲，則A24 和 A71 的第一個字節(jié)的地址是和 。1

16、4 一個 10 階對稱矩陣A， 采用行優(yōu)先順序壓縮存儲上三角元素，設(shè)第 1 個元素 a11的存儲地址為0，每個元素占有1 個字節(jié)的存儲空間，則a45 的地址為。15設(shè)一個6 階的下三角矩陣B 按行優(yōu)先順序壓縮存儲在一維數(shù)組A 中，其中A0 存儲矩陣的第一個元素B11 ，則 A14 存儲的元素是。 若將 B 按列序優(yōu)先順序壓縮存儲在一維數(shù)組A中，則A14存儲的元素是 。16稀疏矩陣一般有兩種壓縮存儲方法，即和 。17 一個廣義表的長度是指 ， 而表的深度是指。 廣義表G=(a,b,(c,d,(e,f),G)的長度為 。廣義表L=(a,(b,()的深度為 。18設(shè)廣義表L=() ， () ，則 G

17、etHead(L) 是 ， GetTail(L) 是 ， L 的長度是;深度是 。廣義表(a, b) , c, d)的表頭是 ,表尾是19用廣義表的取表頭GetHead 和取表尾GetTail 的運算，從廣義表LS=(b,c,(f),(d)中分解出原子c 的操作為。20 . 設(shè)廣義表A=(a， b， (c， d)， (e， (f， g)， 用廣義表的取表頭GetHead 和取表尾GetTail運算，從A 中分解出原子d 的操作為。三、解答題1設(shè)有對稱矩陣Ann (行和列下標均從1 開始)，將其上三角元素逐行存于數(shù)組Bn*(n+1)/2 中，使得Bk=aij ( 1<=i， j<=n

18、， 0<=k<=n*(n+1)/2-1 )。試推導(dǎo)出由i、 j 和 n計算 k 的一般公式。21 在nXn矩陣A中，所有下標值滿足關(guān)系式 i+j v n+l的元素aij (1<=i, j<=n)的值 均為0,現(xiàn)將A中其它元素按行優(yōu)先順序依次存儲到長度為n(n+1)/2的一維數(shù)組sa中，其中元素ai,n存儲在sa中。(1)設(shè)n=10,元素a49存儲在sap中，寫出下標 p的值。(2)設(shè)元素aij (1<=i, j<=n,且i+j v n+l)存儲在sak中,寫出由i、j和n計算k 的一般公式。0%*0 %I 兄522 設(shè)有n階三對角矩陣，將其三條對角線上的元素

19、逐行地存于數(shù)組B1.3n-2中，使得Bk=aij。(1)設(shè)n=100,將一個A100100的三對角矩陣，按行優(yōu)先存入一維數(shù)組B1.m中，試確定m的值，并求 A中元素A7778在B數(shù)組中白位置 K。(2)求用i、j表示k的下標變換公式。(3)求用k表示i、j的下標變換公式。4 .設(shè)A和B均為n階下三角矩陣，在下三角區(qū)域中各有 n (n+1) /2個元素。另設(shè)有 一個二維數(shù)組 C,它有n行n+1歹U。試設(shè)計一個方案，將兩個矩陣A和B中的下三角區(qū)域元素存放于同一個C中，寫出所給出方案的代碼段。并給出計算A的矩陣元素aij和B的矩陣元素bij在C中的存放位置下標的公式。設(shè) A、B、C三個矩陣的行、列下

20、標均從 1開始。5 .設(shè)有稀疏矩陣 A如下(矩陣元素的行列下標均從 1開始)：(1)若矩陣A采用三元組順序表存儲，試給出其三元組表。 (2)若矩陣采用十字鏈表存儲，試畫出該矩陣的十字鏈表。6 .利用廣義表的 GetHead和GetTail操作寫出函數(shù)表達式，把以下各小題中的單元素 banana從廣義表中分離出來：(1) L1= (apple, pear, banana, orange)(2) L2= ( (apple, pear) , ( banana, orange)(3) L3= ( ( ( ( apple) ) ) , ( ( pear) ) , ( banana) , orange)

21、(4) L4= a apple, (pear, (banana) , orange)7 .畫出廣義表(a), b), (), d), (e, f)的兩種存儲結(jié)構(gòu)圖示。8 .已知廣義表如下：A= (B, V)B= (x, L)L= (a, b) (1)寫出下列操作的結(jié)果GetTail (A) =。GetHead ( B) =。 (2)畫出廣義表 A所對應(yīng)的圖形(樹形結(jié)構(gòu))。四、分析題1.閱讀下列函數(shù)，并回答問題。void fun441(int A, int n)int i,j,m;for (i=1; i<n; i+)for (j=0; j<i; j+)m=Ai*n+j;Ai*n+j=

22、Aj*n+i;Aj*n+i=m;( 1)已知矩陣B=，將其按行優(yōu)先存于一維數(shù)組A 中，寫出執(zhí)行函數(shù)調(diào)用Fun441(A， 3)后，矩陣B 的值。(2)簡述函數(shù) void fun441(intA口，int n)的功能。2閱讀下列函數(shù)，并回答問題。void fun442(char str81)char temp, *begin, *end,*p1,*p2;if(str = NULL)return;begin=str;end=str+strlen(str)-1;while(begin < end)temp = *begin; *begin = *end; *end= temp; begin+;

23、 end-;begin = end = str;while(*begin != '0')if(*begin =' ')begin +; end +;continue;else if(*end = ' ' | *end = '0')for (p1=begin,p2=end-1; p1<p2; p1+,p2-)temp=*p1; *p1=*p2; *p2=temp;if (*end!='0') begin = +end;else begin=end;elseend +;( 1)設(shè)有 char str81= ”I

24、am a good worker! ”，執(zhí)行函數(shù)fun442( str) 后，字符串str 的內(nèi)容是什么？( 2)簡述函數(shù)void fun442(char str81) 的功能。3.下面函數(shù)的功能是判斷字符串s是否對稱，若對稱則返回 true,否則返回false。例如，fun443（"abba"）返回true, f（"abab"）返回false。請在劃線處填上適當?shù)囊粋€表達式，將 程序補充完整。bool fun443（char s）int i=0,j=0;while （sj）;/ （ 1 ）for（j-; i<j && si=sj;

25、 ） ;/ （ 2）return ;/ （ 3）4設(shè)S 和 T 是用結(jié)點大小為1 的單鏈表存儲的兩個串。下面函數(shù)的功能是找出串S 中T 中出現(xiàn)的字符。請在劃線處填上適當?shù)膬?nèi)容，將程序補充完整。struct LNodechar data;struct LNode *next;typedef LNode *LinkStr;char SearchNo（LinkStr S, LinkStr T） / 查找不在T 中出現(xiàn)的字符LinkStr p,q;p=S;/ （ 1）/ （2）/ （ 3）/ 指針恢復(fù)串T 的開始結(jié)點/ （ 4）q=T;while () while()q=q->next;if (

26、)return p->data;q=T;return NULL;5下面程序的功能是生成從外到內(nèi)是連續(xù)的自然數(shù)排列的回旋方陣。例如，當n=3 和n=4 時的回旋方陣如下圖1 所示。N=3N418711211102962131693453141584567圖 1 由外向內(nèi)回旋方陣 請在劃線處填上適當?shù)膬?nèi)容，將程序補充完整。#include <iostream>#include <iomanip> using namespace std;#define N 10int main()int aNN=0;int n,row,col,num=0;" cin>&

27、gt;n;/ 第 0 行第 0 列輸入起始1/ 數(shù)組中的數(shù)不超過n*ncout<<" 請輸入方陣的行數(shù)n( n<=10)：num=arow=0col=0=1;while(num<n*n) while()/ (1)a+rowcol=+num;/ 向下填充while()/(2)arow+col=+num;/ 向右填充while()/(3)a-rowcol=+num;/ 向上填充while()/(4)arow-col=+num;/ 向左填充for(row=0;row<n;row+)/打印全部數(shù)組元素for(col=0;col<n;col+)cout<

28、;<setw(4)<<arowcol;cout<<endl;return 0;五、設(shè)計題1 利用 C 的庫函數(shù)strlen、 strcpy 和 strcat 編寫一個函數(shù)void StrInsert(char *S ， int pos，char *T),將串T插入到串S的第pos個字符之前。若pos大于S的長度，則插入不執(zhí)行。利用函數(shù)strlen 和 strcpy 編寫一個函數(shù)void StrDelete(char *S ， int pos， int len) 刪去串S 中從位置pos開始的連續(xù)len個字符。若posn strlen(S),則沒有字符被刪除；若 i

29、+m > strlen(S), 則將S中從位置pos開始直至末尾的字符均刪去。2編寫一個程序，將一個文本串用事先給定的字母映射表進行加密和解密。設(shè)字母映射表為：a b c d e f g h i j k l m n o p q r s t u v w x y zq w e r t y u I o p a s d f g h j k l z x c v b n m3 編寫一個程序，將一個含有數(shù)字和非數(shù)字字符的字符串中連續(xù)的數(shù)字作為一個整體，依次存放到一維整型數(shù)組a中(設(shè)字符串中的數(shù)均不超過最大機器整數(shù))。例如，有字符串“ak123xyz45678.90?+! 302gen4563”，將 1

30、23 存入 a 0, 456 存入 a 1, 78 存入 a2,90存入a3。(說明：為簡單起見，不考慮 78.90是一個浮點數(shù)，而是分成78和90兩個整數(shù))4蛇形矩陣編寫程序，將自然數(shù) 1、2、N2按蛇形方式逐個順序存入N階方陣。例如，當 N=3和 N=4 時的方陣如下圖2 所示。N=3N = 413413410258259116796812157131416圖 2 斜線蛇形陣5設(shè)稀疏矩陣用三元組的表示形式，且表中的元素已經(jīng)按行優(yōu)先的順序排列好，編寫一個函數(shù)void AddSMatrix(TSMatrix a, TSMatrix b,TSMatrix &c) 實現(xiàn)兩個稀疏矩陣A 和

31、B相加，結(jié)果矩陣C 仍用三元組表示。參考答案 一、選擇題1 B2 D3 D4C5 D6 B7 B8 A9 D10 A11C12 A13 A14 D15 C16 A17 C18B19 B20 D21 D22 C23 C24 D25A26 B27 C28 A29 A30 A31 C32D33 B34 D35 B36 D37 B38 C二、填空題1由空格字符(ASCII 值 32)所組成的字符串空格個數(shù)2字符3 其數(shù)據(jù)元素都是字符的字符也相等4 ABC#G12347 O(m+n)10 xyxyxywwy12 *s+=*t+ 或 (13 15676 112順序存儲和鏈式存儲5模式匹配模式串8 0112

32、2312xxyx*s+=*t+ ) != 0136 6014 28串的長度相等且兩串中對應(yīng)位置6 59 0101042111 cdefde15. B6316.三元組十字鏈表17. 表中元素的個數(shù)表展開后所含括號的層數(shù)(或廣義表中括弧的重數(shù))4 318. ()( () )22(a, b)(c, d)19. GetHead(GetTail(LS)20. GetHead(GetTail(GetHead(GetTail(GetTail(A)三、解答題1 .當i<=j時，aij位于對稱矩陣的上三角。上三角矩陣第一行有n個元素，第i-1行有n-(i-1 )+1個元素，第一行到第i-1行是等腰梯形，元

33、素數(shù)為(n+(n-(i-1)+1)(i-1)/2，而aij 是第i行上第j-i+1個元素，故元素aij在一維數(shù)組中的存儲位置(下標 k)為：k=(n+(n-(i-1)+1)(i-1)/2+0-i+1)-1=(2n-i+2)(i-1)/2+j-i當i>=j時，aij位于對稱矩陣的下三角，此時相當于按列序優(yōu)先存儲到B數(shù)組中。同理可以推知，k=(2n-j+2)(j-1)/2+i-j(驗證程序請參閱隨書光盤的程序文件xiti4_3_1.cpp )2 . (1) p=9。(2)當i+jvn+l時，aij位于矩陣的右下三角。下三角矩陣第一行有1個元素，第i-1行有i-1個元素，第一行到第i-1行的元

34、素數(shù)為i*(i-1)/2 ,而aij是第i行上第i+j-n個元 素，故元素aij在一維數(shù)組中的存儲位置(下標 k)為：K=i*(i-1)/2+i+j-n-1(驗證程序請參閱隨書光盤的程序文件xiti4_3_2.cpp )3 .(1)三對角矩陣第一行和最后一行各有兩個非零元素，其余每行均有三個非零元素，所以共有 3n-2個元素。即 m=3*100-2=298。A7778位于第77行的第3個位置，前76行有3*76-1個元素，所以k=3*76+2=230 。(2)主對角線左下對角線上的元素下標間有i=j+1關(guān)系，k與i和j的關(guān)系為k=3(i-1);主對角線上元素下標間有關(guān)系i=j , k與i和j的

35、關(guān)系為k=3(i-1)+1 ;主對角線右上那條對角線上元素下標間有關(guān)系i=j-1 , k與i和j的關(guān)系為k=3(i-1)+2。綜合以上三等式，有 k=2(i-1)+j(1<=i , j<=n ,|i-j|<=1 )(3) i=k/3+1 ; (1WkW3-2)/ k/3 取小于 k/3 的最大整數(shù)j = k-2(i-1) = k-2(k/3) = k%3+k/3(驗證程序請參閱隨書光盤的程序文件xiti4_3_3.cpp )4. 方案為將A的下三角區(qū)域中的元素存放于C的下三角區(qū)域中，B的下三角區(qū)域中的元素轉(zhuǎn)置后存放于C的上三角區(qū)域中。代碼段為：for(i=1;i<=N;

36、i+)/ 將 A 和 B 存儲到 C 中for(j=1;j<=i;j+)cij=aij;for(j=i+1;j<=N+1;j+)cij=bj-1i;A的矩陣元素aij和B的矩陣元素bij在C中的存放位置下標的公式為：Aij=Cij;(1<=i<=n, 1<=j<=i )Bij=Cji+1;(1<=i<=n, 1<=j<=i )(驗證程序請參閱隨書光盤的程序文件xiti4_3_4.cpp )5. (1)A.data1115A.data2144A.data3168A.data4233A.data5347A.data6516ie(2)該矩陣

37、的十字鏈表如圖 3所示。圖3 題3-5(2)答圖6. (1) GetHead (GetTail (GetTail (L1)(2) GetHead (GetHead (GetTail (L2)(3) GetHead (GetHead (GetTail (GetTail (L3)(4) GetHead (GetHead (GetTail (GetHead (GetTail (L4)7 .所給廣義表的兩種存儲結(jié)構(gòu)如圖4所示。圖4 題3-7答圖8 . (1) (y)x(2)廣義表A所對應(yīng)的圖形如圖 5所示。題3-8 (2)答圖圖5四、分析題1. (1)(2)實現(xiàn)按行優(yōu)先存于一維數(shù)組A中的矩陣的轉(zhuǎn)置。2

38、. ( 1) worker! good a am I(2)翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。3. (1)j+(2) i+,j-4. ( 1) p (或 p!=NULL )(2)(3) q=NULL (或!q )(4)5. (1) row+1<n && !arow+1col (3) row-1>=0&&!arow-1col五、設(shè)計題1. void StrInsert(char *S, int pos,char *T)/在串S的第pos個字符之前插入串 T char *Temp;Temp=new char strlen(S)+1; / if

39、(pos<=strlen(S) strcpy(Temp,&Spos); / 將第(3) i>=jq&&p->data!=q->datap=p->next(2) col+1<n&&!arowcol+1(4) col-1>=0&&!arowcol-1設(shè)置一個臨時串pos位起以后的字符拷貝到臨時串中strcpy(&Spos, T);/ 將串 T 拷貝到串S 的第 i 個位置處，覆蓋后面的字符strcat(S,Temp); / 把臨時串中的字符聯(lián)接到串S 后面delete Temp;void St

40、rDelete(char *S, int pos ,int len)/ 從串 S 中刪除第pos 個字符起長度為len 的子串char *Temp;Temp=new char strlen(S)+1;/設(shè)置一個臨時串if(pos+len<strlen(S)strcpy (Temp, &Spos+len); / 把刪除的字符以后的字符保存到臨時串中strcpy( &Spos,Temp);/ 用臨時串中的字符覆蓋位置i 之后的字符else if (pos+len>=strlen(S) && pos<strlen(S)strcpy(&Spos

41、,"0");/ 把位置 pos 的元素置為'0'，表示串結(jié)束delete Temp;2 #include <iostream>#include <string.h>using namespace std;void EncryptAndDecipher(char Original27, char Cipher27, char *T);int StrMatch(char *s,char c);int main()char Original27="abcdefghijklmnopqrstuvwxyz" / 加密及解密映射

42、表char Cipher27 ="qwertyuiopasdfghjklzxcvbnm"char str81;cout<<" 請輸入一個待加密字符串："cin>>str;EncryptAndDecipher(Original, Cipher, str);cout<<" 加密后，字符串為："<<str<<endl;EncryptAndDecipher(Cipher, Original, str);cout<<" 解密后，字符串為："<<

43、;str<<endl;return 0;int StrMatch(char *s,char c)int i;for (i=0; i< strlen(s); i+)if (c=si) return i;/ 匹配成功，返回位置return -1;/ 映射表中沒有相應(yīng)字符void EncryptAndDecipher(char Original27, char Cipher27, char *T) / 加密和解密，加密是Original 作為明文，Cipher 作為密文，解密時相反。int i,m;for (i=0; i < strlen(T); i+)m=StrMatch(

44、 Original, Ti);if(m!=-1) Ti=Cipherm;3思路：從左到右掃描字符串，初次碰到數(shù)字字符時，作為一個整數(shù)的開始，然后進 行拼數(shù)（即將連續(xù)出現(xiàn)的數(shù)字字符拼成一個整數(shù)，直到碰到非數(shù)字字符為止），一個整數(shù)拼 完，存入數(shù)組，再準備拼下一整數(shù)，如此下去，直至整個字符串掃描結(jié)束。#include <iostream>#include <iomanip>using namespace std;int main()int cnt=0,a40,i,num;/ 整數(shù)存儲到數(shù)組a， cnt 保存整數(shù)個數(shù)char str81;cout<<" 請

45、輸入一個長度不超過80 的字符串："<<endl;cin.getline(str,81,'n');i=0;while (stri!='0')if (stri>='0' && stri<='9')/ 是數(shù)字字符num=0;/ 整數(shù)初始化為0while (stri>='0' && stri<='9')/ 拼數(shù)num=num*10+stri-'0'i+;acnt+=num;if (stri='0'

46、) break; i+;if (cnt=0)cout<<" 字符串中不含有數(shù)字字符！ "<<endl;else cout<<" 字符串中不含"<<cnt<<" 個數(shù)，依次為："<<endl;for (i=0;i<cnt;i+) cout<<ai<<""cout<<endl;return 0;4思路1：“蛇形”方式是按“副對角線”平行的各對角線，從右上到左下，再從左下到右上，存放 n2個整數(shù)。對角線共 2

47、n-1條，用一個循環(huán)for (k=1;k<=2*n-1;k+) 來填寫2*n-1條對角線。在副對角線上方，有 n-1條對角線，第k (1<=k<n)條對角線上有k個元 素，數(shù)組元素坐標(i, j)之和為k+1。副對角線下方，有 n-1條對角線，第k條對角線上 有 2*n-k 個元素。它與第2*n-k 條對角線對稱，其元素的下標等于其對稱元素的相應(yīng)坐標各加(k-n)。#include <iostream>#include <iomanip> using namespace std;#define N 10int main()int i,j,n,k,p,q

48、,m;int a NN;cin>>n;m=1;for (k=1;k<=2*n-1;k+)/ 共填 2*n-1 條對角線if (k<n) q=k;else q=2*n-k;/ 副對角線以下的各條對角線上的元素數(shù)for (p=1; p<=q; p+)if (k%2=0) i=q-p+1; j=p; else i=p;j=q-p+1; if(k>=n) i=i+n-q; j=j+n-q;/ k 為偶數(shù)時從右上到左下，/ 否則從左下向右上填數(shù)/ 修改副對角線下方的下標i 和 jaij=m;m+;/ 為填下個數(shù)作準備，m 變化范圍1.n*n。for(i=1;i<

49、=n;i+)for(j=1;j<=n;j+)cout<<setw(4)<<aij;cout<<endl;return 0;思路 2：仔細分析方陣中數(shù)的填法，是按“從右上到左下”的”蛇形”，沿平行于副對角線的各條對角線上，將自然數(shù)從小到大填寫。當從右上到左下時，坐標i 增加，坐標j 減小， 當 j 減到小于0 時結(jié)束，然后 j 從 0 開始增加，而 i 從當前值開始減少，到 i<0 時結(jié)束。然后繼續(xù)如此循環(huán)。當過副對角線后，在 i>n-1 時， j=j+2 ， 開始從左下向右上填數(shù)；而當 j>n-1時， i=i+2 ，開始從右上向左下的

50、填數(shù)，直到n*n 個數(shù)填完為止。#include <iostream>#include <iomanip> using namespace std;#define N 10int main()int i,j,n,k;int a NN;cin>>n;i=0; j=0; k=1;/ i,j 是矩陣元素的下標,k 是要填入的自然數(shù)while (i<n && j<n)while(i<n && j>-1)/ 從右上向左下填數(shù) aij=k+; i+ ;j-; if(j<0)&&(i<n)

51、 j=0;/ 副對角線及以上部分的新i,j 坐標else j=j+2; i=n-1;/ 副對角線以下的新的i,j 坐標while(i>-1 && j<n) / 從左下向右上 aij=k+; i-; j+; if (i<0 && j<n) i=0;else i=i+2; j=n-1;for(i=0;i<n;i+)for(j=0;j<n;j+)cout<<setw(4)<<aij;cout<<endl;return 0;5思路：首先判斷三元組A、 B 表示的矩陣是否行列相同，若相同才能進行矩陣的加法運算。設(shè)置三個變量i、 j 和 p 分別指向矩陣A、 B 和 C 對應(yīng)三元組中的當前元素。初始時， i=j=1 ， p=0。若a、 b 表的指針均沒有到表尾(while (i<=a.tu)&&(j<=b.tu) )，重復(fù)下列步驟：( 1)若 a 表元素的i 域值小于b 表元素的i 域值，將a 表當前元素插入到c 表表