數(shù)據(jù)結(jié)構(gòu)參考答案(1-3)

1、數(shù)據(jù)結(jié)構(gòu)參考答案第一頁，編輯于星期五：十二點 四十一分。算法題規(guī)范跟書上格式一樣考試時要求先寫算法，再寫偽代碼復雜的代碼有注釋例2-1 利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合A=AB。1.初值 獲取線性表LA和LB2.合并線性表 對于LB中的每一個元素x做如下操作： 若 （x不屬于LA） 則 將x插入到LA的末尾3.算法結(jié)束第二頁，編輯于星期五：十二點 四十一分。規(guī)范void union(List &La，List Lb) La_len=Listlength(La); Lb_len=Listlength(Lb); for(i=1;i=Lb_len;i+) GetEl

2、em(Lb，i，e); if(!LocateElem(La，e，equal)ListInsert(La，+La_len，e); 第三頁，編輯于星期五：十二點 四十一分。1.8(5)for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=(y+1)*(y+1)y+;第四頁，編輯于星期五：十二點 四十一分。1.8(8)x=91;y=100;while(y0)if(x100)x-=10;y-else x+;注意:if,else算一個整體11*100=11001.10按增長率從小到大的順序排列下列各函數(shù):書上參考答案:第五頁，編輯于星期五：十二點 四十一分。1.10問題:N=1

3、N=2N=4N=8N=16N=32N=64N=128N=2561.333e+0001.778e+0003.160e+0009.989e+000 9.977e+0019.955e+0039.910e+0079.821e+0159.645e+0311.500e+0002.250e+0005.063e+0002.563e+0016.568e+0024.314e+0051.861e+0113.465e+0221.201e+0451.000e+0002.000e+0001.600e+0015.120e+0026.554e+0043.355e+0076.872e+0105.629e+0141.845e+0

4、19從表中可以看出,順序應(yīng)該為:第六頁，編輯于星期五：十二點 四十一分。1.10數(shù)學推倒如下:分別取以2為底的對數(shù)正確答案:第七頁，編輯于星期五：十二點 四十一分。1.20試編寫算法求一元多項式 ,并確定算法中每一語句的執(zhí)行次數(shù)和整個算法的時間復雜度.注意選擇你認為比較好的輸入和輸出方法.本題的輸入為void calpnx()scanf(x0,n); /輸入x0,n 1For(i=0;i=n;i+) /輸入ai scanf(ai); n+1 x=1,pn=0; /x表示x0i,pn記錄最后結(jié)果 1 for(i=0;i=n;i+) pn+=ai*x; n+1 x*=x0; n+1 printf(

5、pn); 1 時間復雜度O(n+1)=O(n)第八頁，編輯于星期五：十二點 四十一分。2.212.21 試寫一算法,實現(xiàn)順序表的就地逆置,即利用原表的存儲空間將線性表void reverse(SqList &L)for (i=0,j=i.length-1;ij;i+,j-)L.elemi L.elemj;第九頁，編輯于星期五：十二點 四十一分。2.292.29 已知A,B和C為三個遞增有序的線性表,現(xiàn)要求對A表做如下操作:刪去那些即在B表中出現(xiàn)又在C表中出現(xiàn)的元素。試對順序表編寫實現(xiàn)上述操作的算法，并分析你的算法的時間復雜度（注意：題中沒有特別指明同一表中的元素值各不相同）。第十頁，編輯于星期

6、五：十二點 四十一分。void sqlist-deletesame(SqList &A,Sqlist B Sqlist C)ai=bi=ci=alen=0; /ai,bi,ci分別為指向數(shù)組A,B,C的下標，alen為數(shù)組A的新長度while(aiA.length&biB.length&ciC.length)if(B.elembiC.elemci) ci+;else/相同元素same=B.elembi;while(biB.length&B.elembi=same) bi+;while(ciC.length&C.elemci=same) ci+;while(aiA.length&A.elemai

7、same)/保留不相同的A.elemalen+=A.elemai+;while(aiA.length&A.elemai=same) ai+;/去掉相同的while(ainext;pc=C-next;pa=A-next;prepa=A;/prepa為pa前一個結(jié)點while(pb&pc&pa)if(pb-datadata) pb=pb-next;else if(pb-datapc-data) pc=pc-next;else/相同元素 same=pb-data; while(pb&pb-data=same) pb=pb-next; while(pc&pc-data=same) pc=pc-next

8、; while(pa&pa-datanext; while(pa&pa-data=same)/去掉相同的 t=pa;pa=pa-next;free(t); prepa-next=pa;第十三頁，編輯于星期五：十二點 四十一分。2.38算法時間復雜度與2.29相同2.38 設(shè)有一個雙向循環(huán)鏈表，每個結(jié)點中除有prior,date,next三各域外，還增設(shè)了一個訪問頻度域freq。在鏈表被起用之前，頻度域freq的值均初始化為零，而每當對鏈表進行一次LOCATE(L,x)的操作后，被訪問的結(jié)點（即元素值等于x的結(jié)點)中的頻度域freq的值便增1，同時調(diào)整鏈表中結(jié)點之間的次序，使其按訪問頻度非遞增的

9、次序順序排序，以便始終保持被頻繁訪問的結(jié)點總是靠近表頭結(jié)點。試編寫符合上述要求的LOCATE操作的算法。第十四頁，編輯于星期五：十二點 四十一分。DuLNode * LOCATE(DuLinkList &L, ElemType x)p=L.next;while(p.data!=x&p!=L) p=p-next;if(p=L)return NULL;p-freq+;q=p-pre;while(q-freqfreq&q!=L)q=q-pre;if(q!=p-pre)p-pre-next=p-next;p-next-pre=p-pre; /把p從原來位置斷開q-next-pre=p;/把p插入新位置

10、p-next=q-next;q-next=p;p-pre=q;return p;第十五頁，編輯于星期五：十二點 四十一分。2.392.39已知稀疏多項式 試采用存儲量同多項式項數(shù)m成正比的順序存儲結(jié)構(gòu)，編寫求 , 并分析你的算法的時間復雜度。分析：采用順序結(jié)構(gòu)存儲，并假設(shè)按指數(shù)項從小到大存儲第十六頁，編輯于星期五：十二點 四十一分。Float CalSqPolyValue(SqPoly p,int x0)sum=0,x=1,preexp=0;for(i=0;ip.length;i+)for(j=preexp;jtws.top1) return OVERFLOW;/判溢出if(i=0) tws.

11、base0tws.top0+=x;else tws.base0tws.top1-=x;else return ERROR;return OK;第二十三頁，編輯于星期五：十二點 四十一分。Status pop(Dbstace &tws,int i,Elemtyep &e)if(i=0) if(tws.top0=tws.base0) return OVERFLOW;e=tws.base0-tws.top0;else if(i=1)if(tws.top1=tws.base1) return OVERFLOW;e=tws.base0+tws.top1;else return ERROR;return

12、OK;第二十四頁，編輯于星期五：十二點 四十一分。3.193.19假設(shè)一個算術(shù)表達式中可以包含三種括號：圓括號“(”和“）”，方括號“”和“”和花括號“”和“”,且這三種括號可以按任意的次序嵌套使（如：()。編寫判別給定表達式中所包含括號是否正確匹配對出現(xiàn)的算法（已知表達式已存入數(shù)據(jù)元素為字符的順序表中）。第二十五頁，編輯于星期五：十二點 四十一分。Status Brackets_test(char *str)InitStack(s);for(p=str;*p;p+)c=*p;if(c=(|c=|c=) Push(s,c);/左括號入棧elseif(StackEmpty(s) return E

13、RROR;Pop(s,e);if(c=)&e!=() return ERROR;/判斷匹配else if(c=&e!=) return ERROR;else if(c=&e!=) return ERROR;if(!stackEmpty(s) return ERROR;/判斷棧是否為空return OK;第二十六頁，編輯于星期五：十二點 四十一分。3.283.28假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素結(jié)點（注意不設(shè)頭指針），試編寫相應(yīng)的隊列初始化，入隊列和出隊列的算法。typedef struct QNodeElemType data;Struct Qnode *next

14、;*Queueptr;Typedef structQueueptr rear;CycleLinkQueue;第二十七頁，編輯于星期五：十二點 四十一分。Status InitQueue(CycleLinkQueue &Q) Q.rear=(QueuePtr) malloc(sizeof(Qnode);if(!Q.rear) exit(OVERFLOW);Q.rear-next=Q.rear;/指向自己return OK;Status EnQueue(CycleLinkQueue &Q,int x) /不同于數(shù)組，動態(tài)申請 p=(QueuePtr)malloc(sizeof(Qnode);/生成

15、新結(jié)點if(!p) return OVERFLOW;p-data=x;q=Q.rear;while(q-next!=Q.rear)/找到插入位置q=q-next;q-next=p;/插入p-next=Q.rear;return OK;第二十八頁，編輯于星期五：十二點 四十一分。Status DeQeuue(CycleLinkQueue &Q,ElemType &e) if(Q.rear-next=Q.rear) return ERROR;p=Q.rear-next;/頭結(jié)點e=p.data;Q.rear-next=p-next;/刪除頭結(jié)點free(p);/釋放結(jié)點return OK;第二十九頁，編輯于星期五：十二點 四十一分。3.323.32試利用循環(huán)隊列編寫求k階斐波那契序列中前n+1項 的算法，要求滿足 , 其中max為某個約定的常熟。（注意：本題所用循環(huán)隊列的容量僅為k,則在算法執(zhí)行結(jié)束時，留在循環(huán)隊列中的元素應(yīng)是所求k階斐波那契序列中的最