【文章內(nèi)容簡介】 DE *)malloc(sizeof(NODE))。s2=t2。while(t1!=NULL){s=(NODE *)malloc(sizeof(NODE))。sdata=t1data。t2link=s。t2=s。t1=t1link。}t2link=NULL。s=s2。s2=s2link。free(s)。return(s2)。}} 2.include typedef struct node{char data。struct node *link。}NODE。int L_index(NODE *t,NODE *p) {NODE *t1,*p1,*t2。?int i。t1=t。i=1。while(t1!=NULL){p1=p。t2=t1link。while(p1data==t1dataamp。amp。p1!=NULL) {p1=p1link。t1=t1link。}if(p1==NULL) return(i)。i++。t1=t2。}return(0)。}第五章 數(shù)組和廣義表一、選擇題 1. 常對數(shù)組進行的兩種基本操作是（ ）（A）建立與刪除（B）索引和修改（C）查找和修改（D）查找與索引(每個字符占一個存儲單元)組成的串,行下標i的范圍從0到4,列下標j的范圍從0到5,M按行存儲時元素M[3][5]的起始地址與M按列存儲時元素( ) 的起始地址相同。（A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4][8][10]中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內(nèi),存放該數(shù)組至少需要的單元數(shù)是（ ）。（A）80（B）100（C）240（D）270[8][10]中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內(nèi),該數(shù)組按行存放時,元素A[7][4]的起始地址為（ ）。（A）SA+141（B）SA+144（C）SA+222（D）SA+225[8][10]中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內(nèi),該數(shù)組按列存放時,元素A[4][7]的起始地址為（ ）。（A）SA+141（B）SA+180（C）SA+222（D）SA+225,即（ ）。（A） 二維數(shù)組和三維數(shù)組（B）三元組和散列（C）三元組和十字鏈表 （D）散列和十字鏈表,只要把每個元素的行下標和列下標互換,就完成了對該矩陣的轉(zhuǎn)置運算,這種觀點（ ）。（A）正確（B）錯誤,為了節(jié)省存儲,將其下三角部分按行序存放在一維數(shù)組B[1,n(n1)/2]中,對下三角部分中任一元素ai,j(i=j),在一組數(shù)組B的下標位置k的值是（ ）。（A）i(i1)/2+j1（B）i(i1)/2+j（C）i(i+1)/2+j1 (D)i(i+1)/2+j二、填空題 [m][n]采用行序為主方式存儲,每個元素占k個存儲單元,并且第一個元素的存儲地址是LOC(A[0][0]),則A[0][0]的地址是_____________________。[10][20]采用列序為主方式存儲,每個元素占一個存儲單元,并且A[0][0]的存儲地址是200,則A[6][12]的地址是________________。,采用壓縮存儲方式(以行序為主,且A[0][0]=1),則A[8][5]的地址是__________________。[1..n*(n+1)/2]中,若按行序為主存儲,則A[i][j]對應的S中的存儲位置是________________。6的二維數(shù)組,其每個元素占用3個存儲單元,并且A[0][0]的存儲地址為1000,元素A[1][3]的存儲地址為___________,該數(shù)組共占用_______________個存儲單元。三、算法設計 [i][j]滿足條件:A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,則稱之為該矩陣的一個馬鞍點。編寫一個函數(shù)計算出1n的矩陣A的所有馬鞍點。,選舉辦法如下:所有猴子按1,2,...,n編號圍坐一圈,從1號開始按...、m報數(shù),凡報m號的退出到圈外,如此循環(huán)報數(shù),直到圈內(nèi)剩下只猴子時,這只猴子就是大王。n和m由鍵盤輸入,打印出最后剩下的猴子號。編寫一程序?qū)崿F(xiàn)上述函數(shù)。編寫下列程序:(1)求廣義表表頭和表尾的函數(shù)head()和tail()。(2)計算廣義表原子結點個數(shù)的函數(shù)count_GL()。(3)計算廣義表所有原子結點數(shù)據(jù)域(設數(shù)據(jù)域為整型〉之和的函數(shù)sum_GL()。 參考答案：一、選擇題1. C 3. C 4. C 5. B B B 二、填空題loc(A[0][0])+(n*i+j)*k 332 42 i*(i+1)/2+j+1 1039；72 三、算法設計題1.算法思想：依題意,先求出每行的最小值元素,放入min[m]之中,再求出每列的最大值元素,放入max[n]之中,若某元素既在min[i]中,又在max[j]中,則該元素A[i][j]便是馬鞍點,找出所有這樣的元素,即找到了所有馬鞍點。因此,實現(xiàn)本題功能的程序如下:include define m 3define n 4void minmax(int a[m][n]){int i1,j,have=0。int min[m],max[n]。for(i1=0。i1m。i1++)/*計算出每行的最小值元素,放入min[m]之中*/{min[i1]=a[i1][0]。for(j=1。jn。j++)if(a[i1][j]min[i1]) min[i1]=a[i1][j]。}for(j=0。jn。j++)/*計算出每列的最大值元素,放入max[n]之中*/{max[j]=a[0][j]。for(i1=1。i1m。i1++)if(a[i1][j]max [j]) max[j]=a[i1][j]。}for(i1=0。i1m。i1++)for(j=0。jn。j++)if(min[i1]==max[j]){printf((%d,%d):%d\n,i1,j,a[i1][j])。have=1。 }if(!have) printf(沒有鞍點＼n)。} 2.算法思想:本題用一個含有n個元素的數(shù)組a,初始時a[i]中存放猴子的編號i,計數(shù)器似的值為0。從a[i]開始循環(huán)報數(shù),每報一次,計數(shù)器的值加1,凡報到m時便打印出a[i]值(退出圈外的猴子的編號),同時將a[i]的值改為O(以后它不再參加報數(shù)),計數(shù)器值重新置為0。該函數(shù)一直進行到n只猴子全部退出圈外為止,最后退出的猴子就是大王。因此,現(xiàn)本題功能的程序如下:include main(){int a[100]。int count,d,j,m,n。scanf(%d %d,amp。m,amp。n)。/* n=m*/for(j=0。jn。j++)a[j]=j+1。count=0。d=0。while(dn)for(j=0。jn。j++)if(a[j]!=0){count++。if(count==m){printf(% d ,a[j])。a[j]=0。count=0。d++。}}} 3.include include typedef struct node{ int tag。union{struct node *sublist。char data。}dd。struct node *link。}NODE。NODE *creat_GL(char **s){NODE *h。char ch。ch=*(*s)。(*s)++。if(ch!=39。\039。){h=(NODE*)malloc(sizeof(NODE))。if(ch==39。(39。){htag=1。h=creat_GL(s)。}Else{htag=0。h=ch。}}elseh=NULL。ch=*(*s)。(*s)++。if(h!=NULL)if(ch==39。,39。)hlink =creat_GL(s)。elsehlink=NULL。return(h)。}void prn_GL(NODE *p){if(p!=NULL){if(ptag==1){printf(()。if(p ==NULL)printf( )。elseprn_GL(p )。}elseprintf(%c,p)。if(ptag==1)printf())。if(plink!=NULL){printf(,)。prn_GL(plink)。}}}NODE *copy_GL(NODE *p){NODE *q。if(p==NULL) return(NULL)。q=(NODE *)malloc(sizeof(NODE))。qtag=ptag。if(ptag)q =copy_GL(p )。elseq =p。qlink=copy_GL(plink)。return(q)。}NODE *head(NODE *p) /*求表頭函數(shù) */{return(p)。} NODE *tail(NODE *p) /*求表尾函數(shù) */{return(plink)。}int sum(NODE *p) /*求原子結點的數(shù)據(jù)域之和函數(shù) */{ int m,n。if(p==NULL) return(0)。else{ if(ptag==0) n=p。else n=sum(p)。if(plink!=NULL)m=sum(plink)。else m=0。return(n+m)。}}int depth(NODE *p) /*求表的深度函數(shù) */{int h,maxdh。NODE *q。if(ptag==0) return(0)。else if(ptag==1amp。amp。p==NULL) return 1。else{maxdh=0。while(p!=NULL){if(ptag==0) h=0。else{q=p。h=depth(q)。}if(hmaxdh)maxdh=h。p=plink。}return(maxdh+1)。}}main(){NODE *hd,*hc。char s[100],*p。p=gets(s)。hd=creat_GL(amp。p)。prn_GL(head(hd))。prn_GL(tail(hd))。hc=copy_GL(hd)。printf(copy after:)。prn_GL(hc)。 printf(sum:%d\n,sum(hd))。printf(depth:%d\n,depth(hd))。}第六章 樹和二叉樹一、選擇題 ,t所指結點沒有左子樹的充要條件是（ ）（A）t〉left==NULL （B）t〉ltag==1（C）t〉ltag=1且t〉left=NULL（D）以上都不對,任一結點均有指向其前趨和后繼的線索,這種說法（A）正確 （B）錯誤 （C）不同情況下答案不確定,任意一個結點均處在其子女結點的前面,這種說法（ ）(A)正確 (B)錯誤 （C）不同情況下答案不確定,所以二叉樹是一種特殊的樹,這種說法（ ）（A）正確 （B）錯誤 （C）不同情況下答案不確定,則此類二叉樹中所包含的結點數(shù)至少為（ ）。（A）2h （B）2h1（C）2h+1（D）h+1。中序遍歷序列是debac,它的前序遍歷序列是（ ）。（A）acbed （B）decab（C）deabc （D）cedba,那么T中結點的前序就是T2中結點的（ ）（A）前序（B）中序（C）后序（D）層次序,中序遍歷的結點訪問順序是dgbaechf,則其后序遍歷的結點訪問順序是（ ）。（A）bdgcefha （B）gdbecfha （C）bdgaechf （D）gdbehfca、小于其右孩子的值。這種說法（ ）（A）正確（B）錯誤（C）不同情況下答案不確定,具有3個結點的二叉樹有（ ）種。（A）3（B）4（C）5（D）6,根結點的右邊（ ）（A）只有右子樹上的所有結點（B）只有右子樹上的部分結點（C）只有左子樹上的部分結點（D）只有左子樹上的所有結點（ ）。（A）有序數(shù)據(jù)元素（B）無序數(shù)據(jù)元素（C）元素之間具有分支層次關系的數(shù)據(jù)（D）元素之間無聯(lián)系的數(shù)據(jù)、中序和后序遍歷序列中的相對次序（ ）（A）不發(fā)生改變（B）發(fā)生改變（C）,最佳方案是二叉樹采用（ ）存儲結構。（A）二叉鏈表（B）廣義表存儲結構（C）三叉鏈表（D）順序存儲結構,m個樹葉,n個結點,深度為h,則（ ）（A）n=h+m （B）h+m=2n（C）m=h1（D）n=2h1,中序為uwtvs,那么該二叉樹的后序為（ ）（A）uwvts （B）vwuts（C）wuvts （D）wutsv（ ）個結點。（A）10（B）12（C）15（D）17二、判斷題 。（ ）。（ ）。（ ）、右子樹的高度之差的絕對值不大于2（ ）三、填空題 ,___________,_______________。,樹與二叉樹是兩種不