答案《數(shù)據(jù)結構》試卷

廈門大學?—數(shù)據(jù)結構—?課程期中試卷信息科學與技術學院計算機科學系2003年級 專業(yè)主考教師： 試卷類型：(A卷/B卷)任選5題((1,2),(3,4),(5,6),(7,8)中必須至少做一題)，每題20分一、試設計一個雙棧結構，它有兩個端點endl和end2,滿足從endl端插入的表目只能從endl端被刪除，從end2端插入的表目只能從end2端被刪除，并給出指定端i(i=1,2)的進棧push(S,e,i和出棧pop(S,e,i)操作的算法描述。再設計一個算法，它能夠將一個有限長度的數(shù)據(jù)序列a1,a2,…，an,按照下標奇偶序號交替的方式將ai(1<i<n)分別從兩端入棧，然后將數(shù)據(jù)出棧以實現(xiàn)整個數(shù)據(jù)序列的倒排。該雙棧宜采用順序存儲、棧頂迎面增長的存儲方式，其形式定義如下：#defineSTACK_SIZE1000typedefstruct{SElemTypebase[STACK_SIZE];SElemType*top[3];//top[1]表示end1端的棧頂指針，top[2]表示end2端的棧頂指針

//初始值分別為base和base+STACK_SIZE-1}DSqStack;指定端i(i=1,2)的進棧push(S,e,i)和出棧pop(S,e,i)操作的算法描述如下:Statuspush(DSqStack&S,SElemTypee,inti){if(S.top[1]-S.top[2]==1)//棧滿exit(OVERFLOW);elseif(i==1)*S.top[1]++=e;elseif(i==2)*S.top[2]--=e;elsereturnERROR;returnOK;Statuspop(DSqStack&S,SElemType&e,inti){if(i==1){if(S.top[1]==S.base)returnERROR;e=*--S.top[1]=e;returnOK;}elseif(i==2){if(S.top[2]==S.base+STACK_SIZE-1)returnERROR;e=*++S.top[2];returnOK;}elsereturnERROR;}基于上述結構的數(shù)據(jù)序列的倒排算法描述如下：Statusresevers(DSqStack&S,SElemTypea[],intn){for(j=1;j<=n;j++)if(j%2==0)push(S,a[j-1],2);elsepush(S,a[j-1],1);for(j--;j>=1;j--)if(j%2==0)pop(S,a[n-j],2);elsepop(S,a[n-j],1);returnOK;}二、利用兩個棧S1、S2模擬一個隊列(如客戶隊列)時，如何用棧的運算實現(xiàn)隊列的插入、刪除運算。使用算法描述。解：利用兩個棧S1、S2模擬一個隊列(如客戶隊列)時，當需要向隊列中輸入元素時，用S1來存放輸入元素，用push運算實現(xiàn)。當需要從隊列中輸出元素時，到棧 S2中去取，如果S2為空，那么將S1中的元素全部送入到S2中，然后再從S2中輸出元素。判斷隊空的條件是：S1和S2同時為空。StatusEnQueue(DataTypex){ifStackFull(S1){//S1棧滿ifStackEmpty(S2){//S1棧滿，S2?？誻hile(!StackEmpty(S1)){Pop(S1,y);Push(S2,y);//棧S1的內容反向搬到棧S2Push(S1,x);returnOK;}else//S1棧滿，S2棧非空，那么不可進行插入操作returnERROR；}else{//S1棧不滿，那么直接進棧Push(S1,x);returnOK;}}

StatusDeQueue(DataType&x){if!StackEmpty(S2){Pop(S2,x);returnOK;}else{if!StackEmpty(S1){while(!StackEmpty(S1)){Pop(S1,y);Push(S2,y);}//棧S1的內容反向搬到棧S2Pop(S2,x);returnOK;}else//棧S1和S2都為空returnERROR;}}三、模式匹配算法是在主串中快速尋找模式的一種有效的方法。如果設主串的長度為 m,模式串的長度為n，那么在主串中尋找模式的 KMP算法的時間復雜性是多少？如果某一模式p=〞bcaacabaca，請給出它的next函數(shù)值及nextval函數(shù)值。解：在主串中尋找模式的KMP算法的時間復雜度是O(n+m)。模式p=^abcaacabaca,它的next函數(shù)值及nextval函數(shù)值分別是：j 1 2模式 j 1 2模式 a bnext[j] 0 1nextval[j]0 13 4 5 6 7c a a c a1 1 2 2 11 0 2 2 08 9 10 11b a c a2 3 2 11 3 2 0四、編寫算法對讀入的一段文字(設以字符“＃〞結束)，統(tǒng)計其中所出現(xiàn)的字符及其頻度要求采用雙向循環(huán)鏈表存儲，每讀入一個字符就掃描鏈表，假設在表中已有該字符，那么其頻度增加1，同時調整鏈表中各結點之間的次序，使其按頻度非遞增排列，假設表中尚無該字符,那么在表尾插入該字符的一個結點，相應的頻度設為1。typedefstructElemType{charkey;unsignedintfreq;}ElemType;typedefstructDuLNode{ElemTypeData;StructDuLNode*prior,*next;}DuLNode,*DuLinkList;//設帶頭結點，其freq=0StatusStat(DuLinkList&L){getchar(ch);while(ch!='#'{p=L;while((p->next!=L)&&(p->data.key!=ch))p=p->next;if(p->data.key==ch){p->data.freq++;q=p->prior;while((q!=L)&&(q->data.freqvp->data.freq)q=q->prior;if((q!=p->prior)&&(q->data.freq>=p->data.freq){p->prior->next=p->next;p->next->prior=p->prior;p->next=q->next;p->prior=q;q->next=p;p->next->prior=p;}}else{if(!(p=(DuLiinkList)malloc(sizeof(DuLNode))))returnERROR;p->data.key=ch;p->data.freq=1;p->prior=L->prior;p->next=L;L->prior->next=p;L->prior=p;}getchar(ch);}}五、設矩陣A是一個n階稀疏方陣，下標分別從0到n—1。A中對角線上有t個m階下三角陣A0、A1、……、At—1〔如以下圖〕，且mxt=n。在為矩陣A設計的壓縮存儲方案中，問用于存儲矩陣A的一維數(shù)組B的大小？假設將這些下三角陣中的元素以行序為主序存放，設A中某元素a[i][j]存放在b[k]中，試給出求解k的計算公式?！矓?shù)組B的下標也從0開始〕一維數(shù)組B的大小為(1+m)/2*m*t=(1+m)*n/2k丄m(m1)/2(iMODm1)iMODm/2jMODmm六、對下面給出的廣義表做：(1)給出廣義表的數(shù)據(jù)結構(2)畫出以下廣義表的存儲結構圖(3)利用取表頭和表尾的操別離出原子e(給出GetHeadGetTail的操作序列)(a,((),b),(((e))))答：(1)廣義表有兩種存儲結構，頭尾鏈和擴展線性鏈(寫出其中一個即可)頭尾鏈typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{AtomTypeatom;struct{structGLNode*hp,*tp;}ptr;};}*GList擴展線性鏈typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{AtomTypeatom;structGLNode*hp;};structGLNode*tp;}*GList(2)兩種存儲結構下的存儲結構圖如下(只要寫出對應的一種即可) ：頭尾鏈(a,(().b),(((e)))) ((().b),(((e))))10a10b((((e))))(((e)))((e))(e)0e擴展線性鏈(a,(().b),(((e)))) ((().b),(((e))))10a10b((((e))))(((e)))((e))(e)0e擴展線性鏈((e))(e)(3)別離出來的序列為：GetHead(GetHead(GetHead(GetHead(GetTail(GetTail(L))))))七、編寫算法求二叉樹中任意兩個結點最近的共同祖先，并分析算法的時間復雜性。自然語言描述:1．[初始化]獲取二叉樹T，任意兩結點P，Q2．[查找到任意兩點的路徑]使用遞歸算法做：A?假設樹根為結點P,那么返回。B.記錄當前樹根為路徑中的一點。C.遞歸遍歷樹根的左子樹D.遞歸遍歷樹根的右子樹E.假設左右子樹中都找不到，那么從路徑中刪除樹根結點[查找最近祖先]遍歷樹根到結點P和Q的路徑，找到兩條路徑上最后一個相同結點，該結點為最近祖先[算法結束]程序描述：intfound=FALSE;Bitree*Find_Near_Ancient(BitreeT,Bitreep,Bitreeq)//求二叉樹T中結點p和q的最近共同祖先{Bitreepathp[100],pathq[100]//設立兩個輔助數(shù)組暫存從根到p,q的路徑Findpath(T,p,pathp,0);found=FALSE;Findpath(T,q,pathq,0);//求從根到p,q的路徑放在pathp和pathq中for(i=0;pathp[i]==pathq[i]&&pathp[i];i++);//查找兩條路徑上最后一個相同結點returnpathp[--i];}//Find_Near_AncientvoidFindpath(BitreeT,Bitreep,Bitreepath[],inti)//求從T到p路徑的遞歸算法{if(T==p){found=TRUE;return;//找到}path[i]=T;//當前結點存入路徑if(T->lchild)Findpath(T->lchild,p,path,i+1);//在左子樹中繼續(xù)尋找if(T->rchild&&!found)Findpath(T->rchild,p,path,i+1);//在右子樹中繼續(xù)尋找if(!found)path[i]=NULL;//回溯}//Findpath算法復雜性分析：算法中Findpath的時間復雜性為：0(n)(因為最壞情況下需要遍歷所有的二叉樹結點)查找最后一個相同結點的復雜性為：O(n)(因為最壞情況下路徑為二叉樹所有結點)所以算法的時間復雜性為：0(n)八、編寫算法判斷一棵用二叉鏈表存儲的二叉樹是否為完全二叉樹。自然語言描述：[初始化]初始化一個隊列Q,將二叉樹的根結點入隊，置flag=O表示未發(fā)現(xiàn)存在某個結點的孩子為空；[按層序遍歷二叉樹，并相應修改flag]循環(huán)直到隊列為空將隊首結點出隊；假設該結點有左子樹且flag=O，那么將左子樹的根結點入隊；假設該結點無左子樹且 flag=O，那么flag=1；假設該結點有左子樹且flag=1，那么不是完全二叉樹，退出；假設該結點有右子樹且flag=O，那么將右子樹的根結點入隊；假設該結點無右子樹且 flag=O，那么flag=1；假設該結點有右子樹且flag=1，那么不是完全二叉樹，退出；[算法