【正文】 abcabaa(i=15,j=8)（3）數(shù)組A中，每個元素A[i,j]的長度均為32個二進位,行下標從1到9，列下標從1到11，從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。求：① 存放該數(shù)組所需多少單元？② 存放數(shù)組第4列所有元素至少需多少單元？③ 數(shù)組按行存放時，元素A[7,4]的起始地址是多少？④ 數(shù)組按列存放時，元素A[4,7]的起始地址是多少？每個元素32個二進制位，主存字長16位，故每個元素占2個字長，行下標可平移至1到11。（1）242 （2）22 （3）s+182 （4）s+142(4)請將香蕉banana用工具 H( )—Head( )，T( )—Tail( )從L中取出。L=(apple,(orange,(strawberry,(banana)),peach),pear)H（H（T（H（T（H（T（L）））））））（5）寫一個算法統(tǒng)計在輸入字符串中各個不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為AZ這26個字母和09這10個數(shù)字）。void Count（）//統(tǒng)計輸入字符串中數(shù)字字符和字母字符的個數(shù)。｛int i，num[36]；char ch；　for（i＝0；i36；i++）num[i]＝０；// 初始化　while（（ch＝getchar（））!=‘’） //‘’表示輸入字符串結(jié)束?！　　f（‘0’=ch=‘9’）｛i=ch－48。num[i]++；｝ // 數(shù)字字符　　 else　if（‘A’=ch=‘Z’）｛i=ch65+10。num[i]++；｝// 字母字符　　　　for（i=0；i10；i++） // 輸出數(shù)字字符的個數(shù)　　　　printf（“數(shù)字％d的個數(shù)＝％d\n”，i，num[i]）；　for（i＝10；i36；i++）// 求出字母字符的個數(shù)　　　　printf（“字母字符％c的個數(shù)＝％d\n”，i＋55，num[i]）；｝// 算法結(jié)束。（6）寫一個遞歸算法來實現(xiàn)字符串逆序存儲，要求不另設串存儲空間。[題目分析]實現(xiàn)字符串的逆置并不難，但本題“要求不另設串存儲空間”來實現(xiàn)字符串逆序存儲，即第一個輸入的字符最后存儲，最后輸入的字符先存儲，使用遞歸可容易做到。 void InvertStore(char A[])//字符串逆序存儲的遞歸算法。{ char ch。static int i = 0。//需要使用靜態(tài)變量scanf (%c,amp。ch)。if (ch!= 39。.39。) //規(guī)定39。.39。是字符串輸入結(jié)束標志 {InvertStore(A)。 A[i++] = ch。//字符串逆序存儲 }A[i] = 39。\039。 //字符串結(jié)尾標記}//結(jié)束算法InvertStore。（7）編寫算法，實現(xiàn)下面函數(shù)的功能。函數(shù)void insert(char*s,char*t,int pos)將字符串t插入到字符串s中，插入位置為pos。假設分配給字符串s的空間足夠讓字符串t插入。（說明：不得使用任何庫函數(shù)）[題目分析]本題是字符串的插入問題，要求在字符串s的pos位置，插入字符串t。首先應查找字符串s的pos位置，將第pos個字符到字符串s尾的子串向后移動字符串t的長度，然后將字符串t復制到字符串s的第pos位置后。 對插入位置pos要驗證其合法性，小于1或大于串s的長度均為非法，因題目假設給字符串s的空間足夠大，故對插入不必判溢出。void insert(char *s,char *t,int pos)//將字符串t插入字符串s的第pos個位置。{int i=1,x=0。 char *p=s,*q=t。 //p，q分別為字符串s和t的工作指針 if(pos1) {printf(“pos參數(shù)位置非法\n”)。exit(0)。}while(*p!=’\0’amp。amp。ipos) {p++。i++。} //查pos位置 //若pos小于串s長度，則查到pos位置時，i=pos。 if(*p == 39。/039。) {printf(%d位置大于字符串s的長度,pos)。exit(0)。} else //查找字符串的尾 while(*p!= 39。/039。) {p++。 i++。} //查到尾時，i為字符‘\0’的下標，p也指向‘\0’。 while(*q!= 39。\039。) {q++。 x++。 } //查找字符串t的長度x，循環(huán)結(jié)束時q指向39。\039。 for(j=i。j=pos 。j){*(p+x)=*p。 p。}//串s的pos后的子串右移，空出串t的位置。 q。 //指針q回退到串t的最后一個字符 for(j=1。j=x。j++) *p=*q。 //將t串插入到s的pos位置上 [算法討論] 串s的結(jié)束標記(39。\039。)也后移了，而串t的結(jié)尾標記不應插入到s中。（8）已知字符串S1中存放一段英文，寫出算法format(s1,s2,s3,n),將其按給定的長度n格式化成兩端對齊的字符串S2, 其多余的字符送S3。[題目分析]本題要求字符串s1拆分成字符串s2和字符串s3，要求字符串s2“按給定長度n格式化成兩端對齊的字符串”，即長度為n且首尾字符不得為空格字符。算法從左到右掃描字符串s1，找到第一個非空格字符，計數(shù)到n，第n個拷入字符串s2的字符不得為空格，然后將余下字符復制到字符串s3中。void format (char *s1,*s2,*s3)//將字符串s1拆分成字符串s2和字符串s3，要求字符串s2是長n且兩端對齊{char *p=s1, *q=s2。 int i=0。 while(*p!= 39。\039。 amp。amp。 *p== 39。 39。) p++。//濾掉s1左端空格 if(*p== 39。\039。) {printf(字符串s1為空串或空格串\n)。exit(0)。 } while( *p!=39。\039。 amp。amp。 in){*q=*p。 q++。 p++。 i++。}//字符串s1向字符串s2中復制 if(*p ==39。\039。){ printf(字符串s1沒有%d個有效字符\n,n)。 exit(0)。} if(*(q)==39。 39。 ) //若最后一個字符為空格，則需向后找到第一個非空格字符 {p 。 //p指針也后退 while(*p==39。 39。amp。amp。*p!=39。\039。) p++。//往后查找一個非空格字符作串s2的尾字符 if(*p==39。\039。) {printf(s1串沒有%d個兩端對齊的字符串\n,n)。 exit(0)。 } *q=*p。 //字符串s2最后一個非空字符 *(++q)=39。\039。 //置s2字符串結(jié)束標記 } *q=s3。p++。 //將s1串其余部分送字符串s3。 while (*p!= 39。\039。) {*q=*p。 q++。 p++。} *q=39。\039。 //置串s3結(jié)束標記}(9)設二維數(shù)組a[1..m, 1..n] 含有m*n 個整數(shù)。① 寫一個算法判斷a中所有元素是否互不相同?輸出相關(guān)信息(yes/no)；② 試分析算法的時間復雜度。[題目分析]判斷二維數(shù)組中元素是否互不相同，只有逐個比較,找到一對相等的元素，就可結(jié)論為不是互不相同。如何達到每個元素同其它元素比較一次且只一次？在當前行，每個元素要同本行后面的元素比較一次（下面第一個循環(huán)控制變量p的for循環(huán)），然后同第i+1行及以后各行元素比較一次，這就是循環(huán)控制變量k和p的二層for循環(huán)。int JudgEqual(ing a[m][n],int m,n) //判斷二維數(shù)組中所有元素是否互不相同，如是，返回1；否則，返回0。{for(i=0。im。i++) for(j=0。jn1。j++) { for(p=j+1。pn。p++) //和同行其它元素比較 if(a[i][j]==a[i][p]) {printf(“no”)。 return(0)。 } //只要有一個相同的，就結(jié)論不是互不相同 for(k=i+1。km。k++) //和第i+1行及以后元素比較 for(p=0。pn。p++) if(a[i][j]==a[k][p]) {printf(“no”)。 return(0)。 } }// for(j=0。jn1。j++)printf(yes”)。 return(1)。 //元素互不相同}//算法JudgEqual結(jié)束（2）二維數(shù)組中的每一個元素同其它元素都比較一次，數(shù)組中共m*n個元素，第1個元素同其它m*n1個元素比較，第2個元素同其它m*n2 個元素比較，……，第m*n1個元素同最后一個元素(m*n)比較一次,所以在元素互不相等時總的比較次數(shù)為 (m*n1)+(m*n2)+…+2+1=（m*n）(m*n1)/2。在有相同元素時,可能第一次比較就相同,也可能最后一次比較時相同,設在(m*n1)個位置上均可能相同,這時的平均比較次數(shù)約為（m*n）(m*n1)/4，總的時間復雜度是O(n4)。(10)設任意n個整數(shù)存放于數(shù)組A(1:n)中，試編寫算法，將所有正數(shù)排在所有負數(shù)前面（要求算法復雜性為0(n)）。 [題目分析]本題屬于排序問題，只是排出正負，不排出大小?？稍跀?shù)組首尾設兩個指針i和j，i自小至大搜索到負數(shù)停止，j自大至小搜索到正數(shù)停止。然后i和j所指數(shù)據(jù)交換，繼續(xù)以上過程，直到 i=j為止。void Arrange(int A[],int n) //n個整數(shù)存于數(shù)組A中，本算法將數(shù)組中所有正數(shù)排在所有負數(shù)的前面 {int i=0,j=n1,x。 //用類C編寫，數(shù)組下標從0開始 while(ij){while(ij amp。amp。 A[i]0) i++。while(ij amp。amp。 A[j]0) j。 if(ij) {x=A[i]。 A[i++]=A[j]。 A[j]=x。 }//交換A[i] 與A[j]} }//算法Arrange結(jié)束.[算法討論]對數(shù)組中元素各比較一次，比較次數(shù)為n。最佳情況(已排好,正數(shù)在前,負數(shù)在后)不發(fā)生交換，最差情況(負數(shù)均在正數(shù)前面)發(fā)生n/2次交換。用類c編寫，數(shù)組界偶是0..n1?？臻g復雜度為O(1).第5章 樹和二叉樹1．選擇題（1）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（ ）。 A．唯一的 Ｂ．有多種C．有多種，但根結(jié)點都沒有左孩子 Ｄ．有多種，但根結(jié)點都沒有右孩子（2）由3 個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（ ）A．2 B．3 C．4 D．5 （3）一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ ）。A．250 B． 500 C．254 D．501 （4）一個具有1025個結(jié)點的二叉樹的高h為（ ）。A．11 B．10 C．11至1025之間 D．10至1024之間（5）深度為h的滿m叉樹的第k層有（ ）個結(jié)點。(1=k=h) A．mk1 B．mk1 C．mh1 D．mh1（6）利用二叉鏈表存儲樹，則根結(jié)點的右指針是（ ）。A．指向最左孩子 B．指向最右孩子 C．空 D．非空（7）對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（ ）遍歷實現(xiàn)編號。A．先序 B. 中序 C. 后序 D. 從根開始按層次遍歷（8）若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用（ ）遍歷方法最合適。A．前序 B．中序 C．后序 D．按層次（9）在下列存儲形式中，（ ）不是樹的存儲形式？A．雙親表示法 B．孩子鏈表表示法 C．孩子兄弟表示法 D．順序存儲表示法（10）一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（ ）。A．所有的結(jié)點均無左孩子 B．所有的結(jié)點均無右孩子C．只有一個葉子結(jié)點 D．是任意一棵二叉樹（11）某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。A．空或只有一個結(jié)點 B．任一結(jié)點無左子樹 C．高度等于其結(jié)點數(shù) D．任一結(jié)點無右子樹（12）若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則X的前驅(qū)為（ ）。A．X的雙親 B．X的右子樹中最左的結(jié)點 C．X的左子樹中最右結(jié)點 D．X的左子樹中最右葉結(jié)點（13）引入二叉線索樹的目的是（ ）。A．加快查找結(jié)點的前驅(qū)或后繼的速度 B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親 D．使二叉樹的遍歷結(jié)果唯一（14）線索二叉樹