數(shù)據(jù)結構課后習題-展示頁
2025-04-03 03:02本頁面
【正文】 qa=panext。 / *利用p來指向新連接的表的表尾，初始值指向表A的頭結點*/ while(pa!=NULL amp。 /*pa表示A的當前結點*/ pb=Bnext?！窘獯稹克惴ㄈ缦拢篖inkList merge(LinkList A, LinkList B, LinkList C){ Node *pa, *qa, *pb, *qb, *p。 m=n，或 C=(a1,b1, ……an,bn,an+1,……am) mn,線性表A、B、C以單鏈表作為存儲結構，且C表利用A表和B表中的結點空間構成。} } p=q。 pnext=headnext。{*p,*q。*head)void}{iLlength/2。 inti。reverseqlist(Seqlist（1）以順序表作存儲結構，設線性表存于a[1:arrsize]的前elenum個分量中。（a1,a2,…,an）逆置為(an,an1,…,a1)。 } Llength++。 xLelem[i]){ Lelem[i+1]=Lelem[i]。 while(i=0 amp。void inserX(Seqlist *L,Elemtype x) { int i。M L= P。K P= L。I while (Pnext!=NULL) P=Pnext。G Q= P。E Snext= L。C Pnext= Snext。供選擇的語句有：A Pnext=S。c. 在表首插入S結點的語句序列是：E、L。a. 在P結點后插入S結點的語句序列是：D、A。(1) A(2) 已知L是無表頭結點的單鏈表，且P結點既不是首元素結點，也不是尾元素結點。在單鏈表中，邏輯上相鄰的元素，其物理位置不一定相鄰。在順序表中，線性表的長度在數(shù)組定義時就已經確定，是靜態(tài)保存，在鏈式表中，整個鏈表由“頭指針”來表示，單鏈表的長度是動態(tài)保存。}算法的時間復雜度：T(n)=O(n)第二章：(1)在順序表中插入或刪除一個元素，需要平均移動一半元素，具體移動的元素個數(shù)與插入或刪除的位置有關。 /*執(zhí)行次數(shù):n次*/ p=p*x。i=n。 s=a[0]。int i。}printf(“%f”,p)。i++){ p=p+a[i]*x。 for(i=1。a[i])。in。x)。 printf(“\nx=”)。 scanf(“%f”,amp。float x,a[],p。 缺點：形參須與實參對應，且返回值數(shù)量有限。討論兩種方法的優(yōu)缺點，并在算法中以你認為較好的一種實現(xiàn)輸入輸出。注意：本題中的輸入為ai(i=0,1,…n)、x和n,輸出為Pn(x0)。k++) x=x+1。j++) for(k=1。i++)for(j=1。第一章3.（1）A（2）C（3）D=x+1的語句頻度 for(i=1。i=n。j=i。k=j。 【解答】x=x+1的語句頻度為：T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6，求 一元多項式pn(x)=a0+a1x+a2x2+…….+anxn的值pn(x0),并確定算法中每一語句的執(zhí)行次數(shù)和整個算法的時間復雜度，要求時間復雜度盡可能小，規(guī)定算法中不能使用求冪函數(shù)。 算法的輸入和輸出采用下列方法（1）通過參數(shù)表中的參數(shù)顯式傳遞（2）通過全局變量隱式傳遞?！窘獯稹浚?）通過參數(shù)表中的參數(shù)顯式傳遞 優(yōu)點：當沒有調用函數(shù)時，不占用內存，調用結束后形參被釋放，實參維持，函數(shù)通用性強，移置性強。（2）通過全局變量隱式傳遞 優(yōu)點：減少實參與形參的個數(shù)，從而減少內存空間以及傳遞數(shù)據(jù)時的時間消耗 缺點：函數(shù)通用性降低，移植性差算法如下：通過全局變量隱式傳遞參數(shù)PolyValue(){ int i,n。 printf(“\nn=”)。n)。 scanf(“%f”,amp。for(i=0。i++) scanf(“%f ”,amp。 /*執(zhí)行次數(shù)：n次 */ p=a[0]。i=n。 /*執(zhí)行次數(shù)：n次*/ x=x*x。 }算法的時間復雜度：T(n)=O(n)通過參數(shù)表中的參數(shù)顯式傳遞float PolyValue(float a[ ], float x, int n) {float p,s。p=x。for(i=1。i++){s=s+a[i]*p。}return(p)。(2)線性表有順序和鏈式兩種存儲結構。(3)在順序表中，邏輯上相鄰的元素，其物理位置＿一定＿＿＿＿＿相鄰。(4)在帶頭結點的非空單鏈表中，頭結點的存儲位置由頭指針指示，首元素結點的存儲位置由頭結點指示，除首元素結點外，其它任一元素結點的存儲位置由其直接前趨的next域指示。按要求從下列語句中選擇合適的語句序列。b. 在P結點前插入S結點的語句序列是：G、K、H、D、A。d. 在表尾插入S結點的語句序列是：(K)、I、A、F。B Pnext= Pnextnext。D Snext= Pnext。F Snext= NULL。H while (Pnext!=Q) P=Pnext。J P= Q。L L= S。(3) D(4) D(5) D4. 已知順序表L遞增有序，編寫一個算法，將X插入到線性表的適當位
教學教案相關推薦
鄂ICP備17016276號-1