【正文】 q=qlink。qlink=NULL。/*r指向最后一個bm1結(jié)點 */ *head=q。} 該算法的時間復雜度為O(n+m),但比順序存儲節(jié)省時間(不需要移動元素,只需改變指針),空間復雜度為O(1) struct node { elemtype data。}NODE。head=ah。b=bh。amp。q=blink。blink=r。b=q。while(blink!=bh)b=blink。} if(blink==bh)/*b的結(jié)點個數(shù)小于a的結(jié)點個數(shù) */ {r=alink。blink=r。} 該算法的時間復雜度為O(n+m), struct node { elemtype data。}NODE。/*qh為序號是偶數(shù)的鏈表頭指針 */ r=rh。while(p!=NULL){ rlink=p。i++。if(p!=NULL){ qlink=p。j++。} } rhdata=i。qhdata=j。} struct node { elemtype data。}NODE。p=head。plink=head。struct node *link。void del(NODE *x,NODE *y){ NODE *p,*q。p=y。while(qnext!=NULL)/* 把后一個結(jié)點數(shù)據(jù)域前移到前一個結(jié)點*/ { pdata=qdata。p=q。/* 刪除最后一個結(jié)點*/ free(q)。（A）edcba（B）decba（C）dceab（D）abcde（）。（A）ST〉top!=0（B）ST〉top==0（C）ST〉top!=m0（D）ST〉top=m0 (最多元素為m0)為棧滿的條件是（）。（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1 [0,m1]存放其元素值,已知其頭尾指針分別是front和rear則當前隊列中的元素個數(shù)是（）（A）(rearfront+m)%m（B）rearfront+1（C）rearfront1（D）rearfront （）（A）都是先進后出（B）都是先進先出（C）只允許在端點處插入和刪除元素（D）沒有共同點 *(b+c)d的后綴表達式是（）。、棧和隊列都是_____________________結(jié)構(gòu),可以在線性表的______________位置插入和刪除元素，對于棧只能在________插入和刪除元素，對于隊列只能在_______插入元素和_________刪除元素。(正確/錯誤)，元素a1，a2，a3，a4，a5和a6依次通過一個棧，一個元素出棧后即進入隊列Q，若6個元素出隊列的順序是a3，a5，a4，a6，a2，a1則棧S至少應(yīng)該容納_____個元素。試編寫對任一棧作進棧和出棧運算的C函數(shù)push（x,i)和pop(i),i=l,2。要求在整個數(shù)組元素都被占用時才產(chǎn)生溢出。一個棧s1用于插入元素,：一、選擇題 CCCD二、填空題先進先出；先進后出線性 ； 任何 ；棧頂；隊尾；對頭正確的 3三、算法設(shè)計題1.define M 100 elemtype stack[M]。int push(elemtype x,int i){if(top1top2==1)return(1)。if(i==2)stack[top2]=x。}int pop(elemtype *px,int i){ if(i==1)if(top1==0)return(1)。*px=stack[top1]。} else if(i==2)if(top2==M1)return(1)。*px=stack[top2]。} } s1[MAXSIZE],s2[MAZSIZE]。void enqueue(elemtype x){if(top1==MAXSIZE)return(1)。return(0)。top2=0。x)。} pop(s2,amp。while(!empty(s2)){ pop(s2,amp。push(s1,x)。concat(head(tail(s)),head(tail(tail(s))))= ‘dc’。(一個結(jié)點存放一個字符)方式下,寫出采用簡單算法實現(xiàn)串的模式匹配的C語言函數(shù)int L_index(t,p)。int S_strlen(char s[]){int i。s[i]!=39。i++)。} void S_strcpy(char s1[],char s2[])// { int i。s1[i]!=39。i++)s2[i]=s1[i]。39。struct node *link。NODE *L_strcpy(NODE *s1){ NODE *s2,*t1,*t2,*s。else { t1=s1。s2=t2。sdata=t1data。t2=s。} t2link=NULL。s2=s2link。return(s2)。struct node *link。int L_index(NODE *t,NODE *p){ NODE *t1,*p1,*t2。t1=t。while(t1!=NULL){ p1=p。while(p1data==t1dataamp。p1!=NULL){ p1=p1link。} if(p1==NULL)return(i)。t1=t2。} 第五章 數(shù)組和廣義表一、選擇題（）（A）建立與刪除（B）索引和修改（C）查找和修改（D）查找與索引(每個字符占一個存儲單元)組成的串,行下標i的范圍從0到4,列下標j的范圍從0到5,M按行存儲時元素M[3][5]的起始地址與M按列存儲時元素()的起始地址相同。（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+180（C）SA+222（D）SA+225 ,即（）。（A）正確（B）錯誤,為了節(jié)省存儲,將其下三角部分按行序存放在一維數(shù)組B[1,n(n1)/2]中,對下三角部分中任一元素ai,j(i（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]的地址是_____________________。,采用壓縮存儲方式(以行序為主,且A[0][0]=1),則A[8][5]的地址是__________________。6的二維數(shù)組,其每個元素占用3個存儲單元,并且A[0][0]的存儲地址為1000,元素A[1][3]的存儲地址為___________,該數(shù)組共占用_______________個存儲單元。編寫一個函數(shù)計算出1n的矩陣A的所有馬鞍點。n和m由鍵盤輸入,打印出最后剩下的猴子號。 編寫下列程序:(1)求廣義表表頭和表尾的函數(shù)head()和tail()。(3)計算廣義表所有原子結(jié)點數(shù)據(jù)域(設(shè)數(shù)據(jù)域為整型〉之和的函數(shù)sum_GL()。因此,實現(xiàn)本題功能的程序如下: include define m 3 define n 4 void minmax(int a[m][n]){ int i1,j,have=0。for(i1=0。} for(i1=0。j=m*/ for(j=0。count=0。} } } 3.include “” include “” typedef struct node { int tag。char data。struct node *link。NODE *creat_GL(char **s){ NODE *h。ch=*(*s)。if(ch!=39。){ h=(NODE*)malloc(sizeof(NODE))。(39。h=creat_GL(s)。h=ch。ch=*(*s)。if(h!=NULL)if(ch==39。)hlink =creat_GL(s)。return(h)。if(p ==NULL)printf(“ ”)。} else printf(“%c”,p)。if(plink!=NULL){ printf(“,”)。} } } NODE *copy_GL(NODE *p){ NODE *q。q=(NODE *)malloc(sizeof(NODE))。if(ptag)q =copy_GL(p)。qlink=copy_GL(plink)。} NODE *head(NODE *p)/*求表頭函數(shù) */ { return(p)。} int sum(NODE *p)/*求原子結(jié)點的數(shù)據(jù)域之和函數(shù) */{ int m,n。else { if(ptag==0)n=p。if(plink!=NULL)m=sum(plink)。return(n+m)。NODE *q。elseif(ptag==1amp。p==NULL)return 1。while(p!=NULL){ if(ptag==0)h=0。h=depth(q)。p=plink。} } main(){ NODE *hd,*hc。p=gets(s)。p)。prn_GL(tail(hd))。printf(“copy after:”)。printf(“sum:%dn”,sum(hd))。} 第六章 樹和二叉樹一、選擇題,t所指結(jié)點沒有左子樹的充要條件是（）（A）t〉left==NULL（B）t〉ltag==1（C）t〉ltag=1且t〉left=NULL（D）以上都不對,任一結(jié)點均有指向其前趨和后繼的線索,這種說法（A）正確（B）錯誤（C）不同情況下答案不確定,任意一個結(jié)點均處在其子女結(jié)點的前面,這種說法（）(A)正確(B)錯誤（C）不同情況下答案不確定,所以二叉樹是一種特殊的樹,這種說法（）（A）正確（B）錯誤（C）不同情況下答案不確定,則此類二叉樹中所包含的結(jié)點數(shù)至少為（）。中序遍歷序列是debac,它的前序遍歷序列是（）。（A）bdgcefha（B）gdbecfha（C）bdgaechf（D）gdbehfca 、小于其右孩子的值。（A）3（B）4（C）5（D）6 ,根結(jié)點的右邊（）（A）只有右子樹上的所有結(jié)點（B）只有右子樹上的部分結(jié)點（C）只有左子樹上的部分結(jié)點（D）只有左子樹上的所有結(jié)點 （）。（A）二叉鏈表（B）廣義表存儲結(jié)構(gòu)（C）三叉鏈表（D）順序存儲結(jié)構(gòu) ,m個樹葉,n個結(jié)點,深度為h,則（）（A）n=h+m（B）h+m=2n（C）m=h1（D）n=2h1 ,中序為uwtvs,那么該二叉樹的后序為（）（A）uwvts（B）vwuts（C）wuvts（D）wutsv （）個結(jié)點。（）。（）、右子樹的高度之差的絕對值不大于2（）三、填空題,___________,_______________。,中序序列為DBGEAHFIJC,寫出后序序列_______________。1）先序和中序遍歷，得到的結(jié)點訪問順序一樣。_________________________ 3）先序和后序遍歷，得到的結(jié)點訪問順序一樣。這棵二叉樹中度為2的結(jié)點有______________________個。四、問答題:第h層上的結(jié)點都是葉結(jié)點,其余各層上每個結(jié)點都有m棵非空子樹。(2)整棵樹結(jié)點數(shù)。(4)編號為i的結(jié)點的第j個孩子結(jié)點(若有)的編號。(2)分別計算在BT中查找各元素所要進行的元素間的比較次數(shù)及平均比較次數(shù)。,其權(quán)值分別為3,7,8,2,6,10,14,試以它們?yōu)槿~結(jié)點構(gòu)造一棵哈夫曼樹(請按照每個結(jié)點的左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)的次序構(gòu)造〉,并計算出帶權(quán)路徑長度WPL及該樹的結(jié)點總數(shù)。(1)試畫出對應(yīng)的編碼哈夫曼樹(要求左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán))。(3)求出傳送電文的總長度。五、算法設(shè)計已知一棵具有n個結(jié)點的完全二叉樹被順序存儲在一維數(shù)組A[n]中,試編寫一個算法輸出A[i]結(jié)點的雙親和所有孩子。樹可采用二叉樹的存儲結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問題。除根外，每個分支引出一個結(jié)點，則樹共有k*n1 +1個結(jié)點。return。} void child(int a[],int n,int i)/*i為序號 */{ int queue[MAX],front=0,tail=0,p。tail++。struct node *lchild,*rchild。NODE *T。ch=getchar()。 39。else { *T=(NODE *)malloc(sizeof(NODE))。create(amp。create(amp。? } } void inorder(NODE *p)//中序編歷二叉樹 { if(p!=NULL){ inorder(plchild)。? inorder(prchild)。void count(NODE *p)//統(tǒng)計出二叉樹中單孩子的結(jié)點數(shù)方法1 { if(p!=NULL){ count(plchild)。amp。amp。count(prchild)。if(plchild!=NULLamp。prchild==NULL||plchild==NULLamp。prchild!=NULL)(*num1)++。} } int onechild(NODE *t)//統(tǒng)計出二叉樹中單孩子的結(jié)點數(shù)方法2 { int num1,num2。else if(tlchild==NULLamp。trchild!=NULL||tlchild!=NULLamp。trchild==NULL)return(onechild(tlchild)+onechild(trchild)+1)。num2=onechild(trchild)。} } int sum(NODE *t)//統(tǒng)計出二叉樹中所有結(jié)點數(shù) {if(t==NULL)return(0)。} i