【正文】 p)。}int judge(char str[],int n) //判斷str序列的合法性{ int i,tag。 //鏈棧ls初始化 for (i=0。) //為I時(shí)進(jìn)棧 Push(ls,str[i])。 return 0。 //其他值無(wú)效退出 } } tag=StackEmpty(ls)。 char str2[]=IOOIOIIO。 printf( %s序列%s合法的\n,str1,judge(str1,8)?是:不是)。}練習(xí)題41. 單項(xiàng)選擇題（1）串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。答：①不包含任何字符（長(zhǎng)度為0）的串 ②由一個(gè)或多個(gè)空格（僅由空格符）組成的串（2）對(duì)于帶頭結(jié)點(diǎn)的鏈串s，串為空的條件是（ ）。所以，非平凡子串的個(gè)數(shù)=n+(n1)+(n2)+…+2=。要求空間復(fù)雜度為O(1)。s,char x,char y){ int i。}（2）設(shè)計(jì)一個(gè)算法，判斷鏈串s中所有元素是否為遞增排列的。 if (p!=NULL) { while (pnext!=NULL) { q=pnext。}（3）假設(shè)以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)一個(gè)串s，設(shè)計(jì)一個(gè)算法求串s中最長(zhǎng)等值子串。 LinkString *p=snext,*q。 while (p!=NULL amp。 } if (nmax) max=n。對(duì)應(yīng)的程序如下：include include //包含順序串的基本運(yùn)算函數(shù)SqString maxstr(SqString s,SqString t){ SqString str。 for (k=1。amp。 mlen=tlen。 //繼續(xù)掃描s中第i字符之后的字符 } for (i=0。 return str。 printf(s:)。 printf(求s、t的最大公共子串str\n)。}練習(xí)題51. 單項(xiàng)選擇題（1）假設(shè)有60行70列的二維數(shù)組a[1..60,1..70]（數(shù)組下標(biāo)從1開(kāi)始）以列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000，每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第58列的元素a[32,58]的存儲(chǔ)地址為（ ）。(i1)/2+j1 (i1)/2+j (i+1)/2+j1 (i+1)/2+j答：B（5）有一個(gè)二維數(shù)組A，行下標(biāo)的范圍是0～8，列下標(biāo)的范圍是1～5，每個(gè)數(shù)組元素用相鄰的4個(gè)字節(jié)存儲(chǔ)。若按行存儲(chǔ)，則A[3,5]和A[5,3]的第一個(gè)字節(jié)的地址分別是（ ② ）和（ ③ ）。假設(shè)存儲(chǔ)數(shù)組元素A[1,0]的第一個(gè)字節(jié)的地址是0，則存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是（ ② ）。 答：C2. 填空題（1）三維數(shù)組A[c1..d1,c2..d2,c3..d3]（c1≤d1，c2≤d2，c3≤d3）共含有（ ）個(gè)元素。（3）二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，并且A[0][0]的存儲(chǔ)地址是200，則A[6][12]的地址是（ ）。答：i(i1)/2+j。對(duì)應(yīng)的算法如下：void move(ElemType A[],int n){ int i=0,j=n1。 if (ij) { tmp=A[i]。解：矩陣轉(zhuǎn)置是將矩陣中第i行第j列的元素與第j行第i列的元素互換位置。 for (i=0。j++) { tmp=A[i*n+j]。設(shè)計(jì)一個(gè)算法求出mn的矩陣A的所有馬鞍點(diǎn)。 for (i=0。jn。j++) //計(jì)算出每列的最大值元素，放入max[1..n]之中 { max[j]=A[0][j]。 } for (i=0。j++) if (min[i]==max[j]) { printf((%d, %d):%d\n, i, j, A[i][j])。 int i, j。jn。 //調(diào)用minmax()找馬鞍點(diǎn)}（4）設(shè)有二維數(shù)組A[m][n]，其元素為整數(shù)，每行每列都按從小到大有序，試給出一個(gè)算法求數(shù)組中值為x的元素的行號(hào)i和列號(hào)j。 while (im amp。 //修改行號(hào) else //a[i][j]==x { flag=1。設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)兩個(gè)二維數(shù)組的相加運(yùn)算。 //存放二維數(shù)組元素 int m,n。 =y。 if (i=0 amp。 j=0 amp。 return 1。 if (i=0 amp。 j=0 amp。 return 1。i。 printf(%3d,[k])。 ElemType x,y。i++) for (j=0。 Setij(C,i,j,x+y)。 InitMat(A,2,3)。 Setij(A,1,0,1)。 DispMat(A)。 Setij(B,0,2,2)。 printf(B:\n)。 AddMat(A,B,C)。 DestroyMat(B)。其余的結(jié)點(diǎn)分成為m（m≥0）個(gè)（ ② ）的集合TT…、Tm，每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱為Ti的雙親結(jié)點(diǎn)，Ti稱為T的子樹(shù)（1≤i≤m）。每棵樹(shù)都能唯一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹(shù)，由一棵樹(shù)轉(zhuǎn)換成的二叉樹(shù)中，一個(gè)結(jié)點(diǎn)N的左孩子是N在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的（ ③ ），而N的右孩子是它在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的（ ④ ）。A. 35 B. 28 C. 77 D. 78答：D（7）下列敘述中，正確的是（ ）。A. i B. 233。 D. C. 235。A. 247 B. 248 C. 249 D. 250答：B（13）若唯一確定一棵二叉樹(shù)，只需要知道該二叉樹(shù)的（ ）。lchild == NULL ltag==1ltag==1且plchild==NULL 答：B（17）根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是（ ）。答：350（4）設(shè)一棵完全二叉樹(shù)具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹(shù)有（ ① ）個(gè)葉子結(jié)點(diǎn)，有（ ② ）個(gè)度為2的結(jié)點(diǎn)，有（ ③ ）個(gè)單分支結(jié)點(diǎn)。（7）對(duì)含有n個(gè)結(jié)點(diǎn)的二叉樹(shù)進(jìn)行中序遞歸遍歷，該算法平均空間復(fù)雜度為（ ）。（2）試求含有n0個(gè)葉子結(jié)點(diǎn)的完全二叉樹(shù)的總結(jié)點(diǎn)數(shù)。答：① 。證明：讓T是一棵完全二叉樹(shù)，S是它的一棵子樹(shù)。③ 。（3）某二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)如下：1234567891011121314151617181920EAFDHCGIB① 畫出該二叉樹(shù)；② 寫出結(jié)點(diǎn)值為D的雙親結(jié)點(diǎn)及左、右子樹(shù)。答：333. 簡(jiǎn)答題（1）一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別？答：度為2的樹(shù)從形式上看與二叉樹(shù)很相似，但它的子樹(shù)是無(wú)序的，而二叉樹(shù)是有序的，即在一般樹(shù)中若某結(jié)點(diǎn)只有一個(gè)孩子，就無(wú)需區(qū)分其左右次序，而在二叉樹(shù)中即使是一個(gè)孩子也有左右之分。答：2i1（6）深度為h的完全二叉樹(shù)至少有（ ① ）個(gè)結(jié)點(diǎn)，至多有（ ② ）個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從1開(kāi)始），則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是（ ③ ）。答：5（2）一棵深度為6的滿二叉樹(shù)有（ ① ）個(gè)分支結(jié)點(diǎn)和（ ② ）個(gè)葉子結(jié)點(diǎn)。 答：D（15）一棵二叉樹(shù)的后序遍歷序列為D、A、B、E、C，中序遍歷序列為D、E、B、A、C，則先序遍歷序列為（ ）。+1答：D（11）一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）。 C. 235。A. 16 B. 32 答：C（9）對(duì)一個(gè)滿二叉樹(shù)，有m個(gè)葉子結(jié)點(diǎn)，n個(gè)結(jié)點(diǎn)，深度為h，則（ ）。 ，但根結(jié)點(diǎn)都沒(méi)有左孩子 ，但根結(jié)點(diǎn)都沒(méi)有右孩子答：A（5）假定一棵度為3的樹(shù)中結(jié)點(diǎn)數(shù)為50，則其最小高度為（ ）。①： ②： ③： （或度） 答：①A ②A ③C（3）二叉樹(shù)（ ① ）。}練習(xí)題61. 單項(xiàng)選擇題（1）樹(shù)最適合用來(lái)表示（ ）。 DispMat(C)。 InitMat(C,2,3)。 Setij(B,1,1,2)。 Setij(B,0,0,2)。 Setij(A,1,2,1)。 Setij(A,0,1,1)。}void DestroyMat(Mat2 M) //銷毀二維數(shù)組M{ free()。j++) { Getij(A,i,j,x)。 //兩數(shù)組行列數(shù)不同返回0 for (i=0。 }}int AddMat(Mat2 A,Mat2 B,Mat2 amp。j。 //參數(shù)錯(cuò)誤返回0}void DispMat(Mat2 M) //輸出二維數(shù)組{ int i,j,k。 j) { k=i*+j。 i amp。 //參數(shù)錯(cuò)誤返回0}int Getij(Mat2 M,int i,int j,ElemType amp。 j) { k=i*+j。 i amp。}int Setij(Mat2 amp。void InitMat(Mat2 amp。解：對(duì)應(yīng)的程序如下：include include typedef int ElemType。 } return flag。 j=0) if (a[i][j]!=x) if (a[i][j]x) j。解：由于算法要求比較次數(shù)不多于m+n次，因此不能按行掃描數(shù)組的每一元素，否則比較次數(shù)在最壞情況下可達(dá)mn次。a[i][j])。im。 } if (!have) printf(沒(méi)有鞍點(diǎn)\n)。i++) //判定是否為馬鞍點(diǎn) for (j=0。im。 } for (j=0。i++) //計(jì)算出每行的最小值元素，放入min[m]之中 { min[i]=A[i][0]。實(shí)現(xiàn)程序如下：include define m 3define n 4void minmax(int A[m][n]){ int i, j, have=0。 A[j*n+i]=tmp。i++) for (j=0。對(duì)應(yīng)的算法如下：void trans(ElemType A[], int n){ int i, j。 A[j]=tmp。 while (ij) { while (A[i]!=0) i++。答：行下標(biāo)、列下標(biāo)和元素值3. 算法設(shè)計(jì)題（1）假定數(shù)組A[0..n1]的n個(gè)元素中有多個(gè)零元素，設(shè)計(jì)一個(gè)算法將A中所有的非零元素依次移到A的前端。答：1208（5）有一個(gè)10階對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式（以行序?yàn)橹鞔鎯?chǔ)下三角部分，且A[0][0]存放在B[1]中），則A[8][5]在B中的地址是（ ）。（2）已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A[0][0])，則A[i][j]的地址是（ ）。若按列存儲(chǔ)，則A[5,7]的第一個(gè)字節(jié)的地址是（ ④ ）。 答：①H ②C ③E ④A ⑤F（6）有一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1～6，列下標(biāo)的范圍是0～7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。假設(shè)存儲(chǔ)數(shù)組元素A[0,1]的第一個(gè)字節(jié)的地址是0。 答：D（3）一個(gè)nn的對(duì)稱矩陣，如果采用壓縮存儲(chǔ)以行或列為主序放入內(nèi)存，則壓縮存儲(chǔ)的容量是（ ）。 printf(str:)。 printf(t:)。 Assign(s,aababcabcdabcde)。i++) //將最大公共子串復(fù)制到str中 [i]=[midx+i]。 //繼續(xù)掃描t中第j+tlen字符之后的字符 } else j++。k++) tlen++。amp。 //用(midx,mlen)保存最大公共子串 while (i) //用i掃描串s { j=0。}上機(jī)實(shí)驗(yàn)題4兩個(gè)非空串s和t采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，設(shè)計(jì)一個(gè)算法求這兩個(gè)串最大公共子串，并用相關(guān)數(shù)據(jù)進(jìn)行測(cè)試。 pdata==qdata) { n++。 q=p。用max存放最大平臺(tái)長(zhǎng)度，掃描串s，計(jì)算一個(gè)平臺(tái)的長(zhǎng)度n，若n大于max，則置max為n。 else //逆序時(shí)返回0 return 0。當(dāng)所有元素是遞增排列時(shí)返回1。i。從頭開(kāi)始遍歷串s，一旦找到字符x便將其替換成y。答：所有可能的條件為：（1）s1和s2為空串（2）s1或s2其中之一為空串（3）s1和s2為相同的串（4）若兩串長(zhǎng)度不等，則長(zhǎng)串由整數(shù)個(gè)短串組成。（3）對(duì)于一個(gè)含有n個(gè)字符的鏈串s，查找第i個(gè)元素的算法的時(shí)間復(fù)雜度為（ ）。A. abcd C.abcABC D.21AB答：D（3）兩個(gè)串相等必有串長(zhǎng)度相等且（ ）。 printf( %s序列%s合法的\n,str3,judge(str3,8)?是:不是)。 char str4[]=IIIOOIOO。 return tag。 } else { DestroyStack(ls)。O39。i++) { if (str[i]==39。 LStack *ls。 }}int StackEmpty(LStack *ls) //判斷?？者\(yùn)算算法{ if (ls==NULL) return 1。