算法與設(shè)計(jì)六套試卷

學(xué)習(xí)必備歡迎下載學(xué)習(xí)必備歡迎下載學(xué)習(xí)必備歡迎下載算法設(shè)計(jì)與分析試卷A卷-20080525-參考答案-第二版-byzzm（含試題預(yù)測、課堂筆記）試題答案：簡答題答：如果一個算法不需要額外的存儲空間（除個別存儲單元以外），我們把它稱為是在位的。答：如下圖，求A到C的最短距離。Dijkstra算法只需一步，就計(jì)算出A到C最短路徑為A-C，長度為3；事實(shí)上，圖中因?yàn)榇嬖谪?fù)權(quán)重的邊，A到C的最短路徑應(yīng)是A-B-C，長度為2。AACB34-2答：對問題的部分或全部輸入做預(yù)處理，然后對獲得的額外信息進(jìn)行存儲，以加速后面問題的求解。我們把這個方法稱為輸入增強(qiáng)。答：解法一：Mindist(A[0..n-1])dist←∞fori←0ton-2do forj←i+1ton-1do if│A[i]-A[j]│<dist dist←│A[i]-A[j]│Returndist解法二：Mindist(A[0..n-1])將數(shù)組A復(fù)制到數(shù)組B； 用O(nlogn)的排序算法對Ｂ進(jìn)行升序排序；dist←B[1]-B[0];fori←1ton-2do ifB[i+1]-B[i]<dist dist←B[i+1]-B[i]Returndist解析：解法一將基本操作│A[i]-A[j]│<dist的運(yùn)算次數(shù)從n2將為(n2-n)/2；解法二采用輸入增強(qiáng)技術(shù)，算法的效率取決于排序算法的效率。原題并沒有明確說明算法要改進(jìn)到什么程度。答：求數(shù)組A中兩個元素的最大差值；基本操作是：A[i]<min和A[i]>max；函數(shù)中循環(huán)體共循環(huán)n次，每次都執(zhí)行兩個基本操作，所以基本操作執(zhí)行次數(shù)為2n，其算法效率類型為O(n)。解析：第（2）小題中，每次循環(huán)都要比較，但不是每次循環(huán)都要賦值，因而比較操作是基本操作。第（3）小題由于題目要求計(jì)算，最好寫出基本計(jì)算過程。答x(2k)=x(2k-1)+2k；x(2k-1)=x(2k-2)+2k-1；……x(2)=x(1)+2；x(1)=1；則x(2k)=2k+2k-1+…+2+1=2k+1–1O(logn)答：解法一：編碼過程：DDBC@A01010110A，B，C，D，@的編碼分別為111，100，101，0，110。100010111001010解碼后為：BDC@DCD解法二：編碼過程：DDBC@A10101001A，B，C，D，@的編碼分別為000，011，010，1，001，100010111001010解碼后為：DADBD@C解析：哈夫曼樹不唯一，且C和@出現(xiàn)頻率相同，所以編碼還有其他可能性，以上兩解法僅供參考。答：h(30)=8；h(20)=9；h(56)=1；h(75)=9；h(31)=9；h(19)=8。開散列表如下：1010……9810563020197531平均比較次數(shù)為：(1+1+2+1+2+3)/6=1.67解析：數(shù)組里為散列值，元素存儲在其散列值對應(yīng)的鏈表中。在（1）小題中，每次插入新的元素，是放在其散列值對應(yīng)的鏈表的末端。例如：在以上基礎(chǔ)上插入元素41的結(jié)果如下，請大家自己比較：1010……981056302019753141答：（聽說堆排序不做要求，估計(jì)會換成平衡二叉樹的生成過程。）答：A={1，3，4，9，13，34}和B={2，5，16，22}合并為C的步驟如下：1<2，故1插入C={}，得C={1}；3>2，故2插入C={1}，得C={1，2}；3<5，故3插入C={1，2}，得C={1，2，3}；4<5，故4插入C={1，2，3}，得C={1，2，3，4}；9>5，故5插入C={1，2，3，4}，得C={1，2，3，4，5}；9<16，故9插入C={1，2，3，4，5}，得C={1，2，3，4，5，6}；13<16，故13插入C={1，2，3，4，5，6}，得C={1，2，3，4，5，6，13}；34>16，故16插入C={1，2，3，4，5，6，13}，得C={1，2，3，4，5，6，13，16}；34>22，故22插入C={1，2，3，4，5，6，13，16}，得C={1，2，3，4，5，6，13，16，22}；34插入C={1，2，3，4，5，6，13，16，22}，得C={1，2，3，4，5，6，13，16，22，34}；因?yàn)楹喜⑴判蚓褪墙惶姹闅v數(shù)組A和B，并把它們中的元素非遞減地插入數(shù)組C中，基本操作就是對A和B數(shù)組的遍歷。假設(shè)A和B的規(guī)模分別為m和n，合并排序算法最壞情況下的時(shí)間效率是O(m+n)。解析：A和B自身內(nèi)部已經(jīng)排序試題預(yù)測：簡答題簡述什么是在位的算法？答：如果一個算法除了個別存儲單元以外,不需要額外的存儲空間,我們把它稱為是在位的.簡述什么是穩(wěn)定的排序算法？答：如果一個排序算法保留了等值元素在輸入中的相對順序,它就被稱為是穩(wěn)定的.某某排序算法的時(shí)間復(fù)雜度，是否穩(wěn)定？哪些排序算法是穩(wěn)定的算法？哪些不是穩(wěn)定的算法，請舉出例子。哪些排序算法的時(shí)間復(fù)雜度是O(nlogn)？排序時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性平均情況最壞情況最好情況直接插入排序O(n2)O(n2)O(n)O(1)穩(wěn)定冒泡算法O(n2)O(n2)O(n)O(1)穩(wěn)定快速排序O(nlogn)O(n2)O(nlogn)O(nlogn)不穩(wěn)定直接選擇排序O(n2)O(n2)O(n2)O(1)不穩(wěn)定希爾排序O(nlogn)O(nlogn)O(1)不穩(wěn)定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不穩(wěn)定歸并排序O(nlogn)O(nlogn)O(nlogn)O(1)穩(wěn)定基數(shù)排序O(d(n+r))O(d(n+r))O(d(n+r))O(n+r)穩(wěn)定解析：冒泡排序、快速排序、直接選擇排序、直接插入排序比較基礎(chǔ)，可能會考察。請簡述符號t(n)∈θ(g(n)),t(n)∈Ω(g(n)),t(n)∈Ο(g(n))的含義。答：t(n)∈θ(g(n))成立的條件是:對于所有足夠大的n,t(n)的上界由g(n)的常數(shù)倍所確定,也就是說,存在大于0的常數(shù)c和非負(fù)的整數(shù)n0,使得:對于所有的n>=n0來說,t(n)<=cg(n)；t(n)∈Ω(g(n))成立的條件是:對于所有足夠大的n,t(n)的下界由g(n)的常數(shù)倍所確定,也就是說,存在大于0的常數(shù)c和非負(fù)的整數(shù)n0,使得:對于所有的n>=n0來說,t(n)>=cg(n)；t(n)∈Ο(g(n))成立的條件是:對于所有足夠大的n,t(n)的上界和下界都由g(n)的常數(shù)倍所確定,也就是說,存在大于0的常數(shù)c1和C2和非負(fù)的整數(shù)n0,使得:對于所有的n>=n0來說,c2g(n)<=t(n)<=c1g(n)解析：只要記住，θ(g(n))是t(n)<=cg(n)，也就是有上界；t(n)∈Ω(g(n))是t(n)>=cg(n)，也就是有下界；t(n)∈Ο(g(n))，c2g(n)<=t(n)<=c1g(n)，也就是上下界都有。C、C1、C2為某常數(shù)。其他語言可以自己組織，不影響大局。順序查找和折半查找的時(shí)間效率類型。答：O(n)，O(logn)分析代碼效率類型常見的O(n2)代碼：Mindist(A[0..n-1])dist←∞fori←0ton-1doforj←0ton-1doifi≠jand│A[i]-A[j]│<distdist←│A[i]-A[j]│Returndist常見的O(logn)代碼：X（n） ifi=1 return1 returnX(n/2)+n常見的O(n)代碼：Secret(A[0..n-1])min←A[0];max←A[0]fori←1tondoifA[i]<minmin←A[i]ifA[i]>maxmax←A[i]Returnmax-min常見的O(n3)代碼：Sum(A[0...n-1][0..n-1][0..n-1])S=0fori←1ton-1doforj←1ton-1dofork←1ton-1doS+=A[i][j][k]ReturnS常見的O(nlogn)代碼：解析：分析代碼效率類型，主要是觀察代碼形態(tài)。計(jì)算循環(huán)或遞歸的次數(shù)，認(rèn)清基本操作，對這兩個進(jìn)行分析，然后得出效率類型。斐波那契數(shù)列遞歸算法：Fib(n){ if(n==0)return0; if(n==1)return1; returnF(n-1)+F(n-2);}直觀的動態(tài)規(guī)劃法：Fib(n){ F[0]=0; F[1]=1; for(i=2;i<=n;i++) F[i]=F[i-1]+F[i-2]; ReturnF[n];}節(jié)省空間的動態(tài)規(guī)劃法Fib(n){ F[0]=0; F[1]=1; for(i=2;i<=n;i++) F[n%2]+=F[(n+1)%2]; ReturnF[n%2];}解析：遞歸算法從定義公式直接導(dǎo)出，非常直觀，但是很多計(jì)算是重復(fù)的。直觀的動態(tài)規(guī)劃法，避免了重復(fù)計(jì)算，單空間復(fù)雜度是O(n)，即該算法不是在位的。節(jié)省時(shí)間的動態(tài)規(guī)劃法，只用了兩個額外的存儲空間來保存上一步的計(jì)算結(jié)果。運(yùn)用霍納法則計(jì)算多項(xiàng)式的值(挺好考的)當(dāng)x=3時(shí)，計(jì)算p(x)=2x4-x3-3x2+x-5。答：系數(shù)2-131-5X=323*2+(-1)=53*5+3=183*18+1=553*55+(-5)=160解析：具體代碼為：Horner(a[0..n],x){ P=a[n]; for(i=n-1;i>=0;i--) P=x*P+a[i] ReturnP;}平衡二叉樹旋轉(zhuǎn)（很大可能考）以5，6，8，3，2，4，7的順序插入數(shù)字，請畫出構(gòu)造AVL樹（平衡二叉樹，平衡查找樹）的過程。5505-1605-26-180L(5)608050618051306280523130L(5)618030502062803-1512040LR(6)506-1304020805-16-23040208120RL(6)50703040208060解析：注意點(diǎn)在于平衡因子計(jì)算和四種旋轉(zhuǎn)。平衡因子是指左右子樹高度差，達(dá)到平衡時(shí)，值可以為0，-1，1，否則則是非平衡狀態(tài)，需要旋轉(zhuǎn)。有四種旋轉(zhuǎn)方法。加入新元素后，從新元素到根節(jié)點(diǎn)修改平衡因子。遞歸解決二叉樹相關(guān)問題：前序遍歷：voidPreOrderTravel（BtTreeT）{ Visit(T); if(T->lchild!=NULL)PreOrderTravel(T->lchild); if(T->rchild!=NULL)PreOrderTravel(T->rchild);}中序遍歷：voidInOrderTravel（BtTreeT）{ if(T->lchild!=NULL)InOrderTravel(T->lchild); Visit(T); if(T->rchild!=NULL)InOrderTravel(T->rchild);}后續(xù)遍歷：voidPostOrderTravel（BtTreeT）{ if(T->lchild!=NULL)PostOrderTravel(T->lchild); if(T->rchild!=NULL)PostOrderTravel(T->rchild);Visit(T);}樹高度計(jì)算：Height（BtTreeT）{ if(T==NULL)return0; lheight=Height(T->lchild); rheight=Height(T->rchile); returnlheight>rheight?lheight+1:rheight+1;}課堂筆記：基礎(chǔ)算法的分析步驟漸進(jìn)符號的含義、定義基本效率類型，證明優(yōu)異遞歸算法，注意定理斐波那契數(shù)列，分治法和動態(tài)規(guī)劃法兩種實(shí)現(xiàn)方式的時(shí)間效率區(qū)別（重點(diǎn)掌握）蠻力排序、查找合并排序、快速排序二叉樹相關(guān)的算法，如遞歸計(jì)算二叉樹高度（重點(diǎn)掌握）插入排序拓?fù)渑判颍己酥攸c(diǎn)）高斯消去法解方程組，兩段代碼的比較平衡查找樹，AVL樹的四種旋轉(zhuǎn)操作霍納法則和二進(jìn)制冪，與P120的計(jì)算公式比較，從左到右，從右到左字符串匹配二項(xiàng)式系數(shù)Floyd算法哈夫曼樹算法分析與設(shè)計(jì)試卷2007秋,計(jì)算機(jī)科學(xué)系姓名: 學(xué)號: 專業(yè): 翻譯以下專業(yè)詞匯:（21分）DynamicprogrammingFeasiblesolutionReductionPrefixComponentdesignLocalreplacementIntractability請回答以下問題:（32分）算法的時(shí)間復(fù)雜性是如何度量的?為什么說在算法的時(shí)間和空間關(guān)系上,時(shí)間是決定性因素(dominantfactor)?我們通常所說的有效(efficient)算法或?qū)嶋H可行算法是指何種算法?字符串的子串(substring)和子序列(subsequence)有何不同?每一個NP問題都是難解的嗎?Turing歸約與Karp歸約有何相同?有何差異?一個最大化問題的近似比為C的相對近似算法可以給我們什么樣的保證?如果從問題P1多項(xiàng)式時(shí)間歸約為問題問題P2,說明問題P1比問題P2難還是簡單?對于任何正整數(shù)n以下算法計(jì)算n!.其時(shí)間復(fù)雜性幾何?是多項(xiàng)式時(shí)間的嗎?（11分）m=1Fori=1tondo m=m*iEndforOutputm（12分）畫出字符串S=acabcac的后綴樹(suffixtree)及其隱含后綴樹(implicitsuffixtree).構(gòu)造一族0,1字符串,使得其后綴樹各邊上所標(biāo)記的子串長度之和的增長速度大于Q(n),這里的n為字符串的長度.關(guān)于NP-Completeness：（12分）寫出通常證明一個問題P是NP-complete的過程.論述使用限制（restriction）技術(shù)證明NP-completeness的合理性。分別用限制技術(shù)和非限制技術(shù)兩種方法證明如下問題的NP-completeness。HittingSetInstance:CollectionCofsubsetsofasetS,positiveintegerK.集合S上的一些子集的集合C，及正整數(shù)K。Question:isthereasubsetS’íSwith|S’|￡KandsuchthatS’?c1Fforeveryc?C?是否存在S的子集S’滿足|S’|￡K并且對C中每一個c?C有S’?c1F？關(guān)于近似算法：（12分）優(yōu)化形式的圖著色問題敘述為：用盡可能少的色對于圖G的各個頂點(diǎn)進(jìn)行染色使得相鄰定點(diǎn)著色不同。證明：若P1NP,則該問題不存在近似性能比小于4/3的多項(xiàng)式時(shí)間近似算法(Hint:usetheNP-completenessofGraph3-Colorability)。背包問題的優(yōu)化版本可如下描述：KNAPSACKInstance:項(xiàng)目集U，總投資額度B?Z+，對每個項(xiàng)目u?U有所需投資s(u)?Z+和預(yù)計(jì)收益v(u)?Z+兩項(xiàng)指標(biāo)，其中s(u)￡B。Objective:求U’íU使得?u?U’s(u)￡B并且?u?U’v(u)達(dá)到最大。證明對于該問題不存在多項(xiàng)式時(shí)間絕對近似算法。證明以下算法是對以上背包問題的一個性能比為2的近似算法。將U中項(xiàng)目按照收益/投資比率從大到小排序，設(shè)排序結(jié)果為u1,u2,…,un,滿足v(u1)/s(u1)3v(u2)/s(u2)3…3v(un)/s(un).U’=F,i=1，p=0，F(xiàn)ori=1tondo Ifs(ui)￡Bthen U’=U’è{ui},p=p+s(ui),B=B-s(ui)Endif EndFor求出滿足v(uj)=max{v(u1),v(u2),…,v(un)}的整數(shù)jIfP<v(uj)thenU’={uj}OutputU’考試課程：考試課程：班級：姓名：學(xué)號：-------------------------------------------------密----------------------------------封-----------------------------線----------------------------------------------------------------------------------------------------------密----------------------------------封-----------------------------線---------------------------------------------------------、=1\*GB2⑴證明：令F(N)=O(f),則存在自然數(shù)N1、C1，使得對任意的自然數(shù)N，有：F(N)……………..（2分）同理可令G(N)=O(g),則存在自然數(shù)N2、C2，使得對任意的自然數(shù)N，有：G(N)……………..（3分）令C3=max{C1,C2},N3=max{N1,N2},則對所有的N，有：F(N)G(N)……………..（5分）故有：O(f)+O(g)=F(N)+G(N)因此有：O(f)+O(g)=O(f+g)……………..（7分）=2\*GB2⑵解：=1\*GB3①因?yàn)椋河蓾u近表達(dá)式的定義易知：的漸近表達(dá)式?！?.（3分）=2\*GB3②因?yàn)椋河蓾u近表達(dá)式的定義易知：21是21+1/n的漸近表達(dá)式?！?.（6分）2、解：經(jīng)分析結(jié)論為：（1）………….（5分）（2）；………….（10分）（3）；………….（15分）3、解：用分治法求解的算法代碼如下：intpartition(floatA[],intp,intr){inti=p,j=r+1;floatx=a[p];while(1){while(a[++i]<x);while(a[--j]>x);if(i>=j)break;a[i]……………..（4分）};a[p]=a[j];a[j]=x;returnj;……………..（7分）}voidQuicksort(floata[],intp,intr){if(p<r){intq=partition(a,p,r);……………..（10分）Quicksort(a,p,q-1);Quicksort(a,q+1,r);}};Quicksort(a,0,n-1);……………..（13分）4、解：用動態(tài)規(guī)劃算法求解的算法代碼如下：intlcs_len(char*a,char*b,intc[][N]){intm=strlen(a),n=strlen(b),i,j;for(i=0;i<=m;i++)c[i][0]=0;for(j=1;j<=n;j++)c[0][j]=0;……………..（4分）for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(a[i-1]==b[j-1])c[i][j]=c[i-1][j-1]+1;elseif(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j];elsec[i][j]=c[i][j-1];……………..（7分）returnc[m][n];……………..（8分）};char*build_lcs(chars[],char*a,char*b){intk,i=strlen(a),j=strlen(b),c[N][N];k=lcs_len(a,b,c);s[k]=’\0’while(k>0){if(c[i][j]==c[i-1][j])i--;……………..（11分）elseif(c[i][j]==c[i][j-1])j--;else{s[--k]=a[i-1];i--,j--;}}returns;……………..（15分）}5、解：intgreedy(vecter<int>x,intn){intsum=0,k=x.size();for(intj=0;j<k;j++)if(x[j]>n){cout<<”Nosolution”<<endl;return-1;……………..（6分）}for(inti=0,s=0;i<k;i++){s+=x[i];if(s>n){sum++;s=x[i];}……………..（9分）}returnsum;……………..（12分）}6、解：此題用動態(tài)規(guī)劃算法求解：intdist(){intm=a.size();intn=b.size();vector<int>d(n+1,0);for(inti=1;i<=n;i++)d[i]=i;……………..（5分）for(i=1;i<=m;i++){inty=i-1;for(intj=1;j<=n;j++){intx=y;y=d[j];intz=j>1?d[j-1]:i;……………..（10分）intdel=a[i-1]==b[j-1]?0:1;d[j]=min(x+del,y+1,z+1);……………..（13分）}}returnd[n];……………..（16分）}7、解：解答如下：voidcompute(){k=1;while(!search(1,n)){k++;if(k>maxdep)break;init();};……………..（6分）if(found)output();……………..（9分）elsecout<<”NoSolution!”<<endl;}boolsearch(intdep,intn){if(dep>k)returnfalse;……………..（11分）for(inti=0;i<2;i++){intn1=f(n,i);t[dep]=I;……………..（13分）if(n1==m||search(dep+1,n1)){found=true;out();returntrue;}returnfalse;……………..（16分）}福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院2006—2007學(xué)年第二學(xué)期考試B卷考生信息欄＿＿＿＿＿＿學(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿裝訂線專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)年級：20XX級課程名稱:算法設(shè)計(jì)與分析任課教師：潘日晶試卷類別：開卷（）閉卷（√）考試用時(shí)：120分鐘考試時(shí)間:年月日午點(diǎn)分題號一二三四五總得分評卷人得分題號六七八九十得分一．填空題（每空2分，共30分）1．算法的五個特性是。2．在忽略常數(shù)因子的情況下，O，和三個符號中，提供了算法運(yùn)行時(shí)間的一個確切界限。3．設(shè)Dn表示大小為n的輸入集合，t(I)表示輸入為I時(shí)算法的運(yùn)算時(shí)間，則算法的最壞情況下時(shí)間復(fù)雜性W(n)=。4．分治算法的時(shí)間復(fù)雜性常常滿足如下形式的遞歸方程：其中，a表示。5．動態(tài)規(guī)劃算法中存儲子問題的解是為了。6．在一個問題的狀態(tài)空間樹中，若從根到某結(jié)點(diǎn)的路徑對應(yīng)該問題的一個解，則稱該結(jié)點(diǎn)為一個結(jié)點(diǎn)。7．分治法不同于動態(tài)規(guī)劃，其分解出的子問題是。8．貪心算法通過一系列局部最優(yōu)選擇來求解問題，最終能得到問題的最優(yōu)解。9．PQ式的分支限界法中，對于活結(jié)點(diǎn)表中的結(jié)點(diǎn)，其下界函數(shù)值越，優(yōu)先級越高。10．快速排序、插入排序和歸并排序算法中，算法不是分治算法。11．在隨機(jī)算法中，LasVegas算法的特點(diǎn)是。12．若對一個問題的求解可轉(zhuǎn)化為對其性質(zhì)相同的子問題的求解，則稱該問題滿足。13．下面算法的基本運(yùn)算是運(yùn)算。算法SPLIT輸入：正整數(shù)n，數(shù)組A[1..n]。輸出：…。i=1考生信息欄＿＿＿＿＿＿學(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿＿＿裝訂線x=A[1]forj=2tonifA[j]<=xtheni=i+1ifijthenA[i]A[j]endifendforA[i]A[1]w=ireturnw,AendSPLIT14．下面算法的功能是，其時(shí)間復(fù)雜性階為()。算法EX1輸入：實(shí)數(shù)x和非負(fù)整數(shù)n。輸出：…y=ex1(x,n)outputyendEX1過程ex1(x,m)ifm=0theny=1elsey=ex1(x,)y=y*yifm為奇數(shù)theny=x*yendifreturnyendex1二．計(jì)算題和簡答題（每小題7分，共21分）1．將下列各函數(shù)按階分類，同階的分為一類，并將各類的階按從低到高的順序排列：f1(n)=1000f2(n)=6n+n-5f3(n)=3nf4(n)=f5(n)=1f6(n)=4n+n/logn-1f7(n)=2()f8(n)=nlogn+2．算法A和算法B解同一問題，設(shè)算法A的時(shí)間復(fù)雜性滿足遞歸方程，算法B的時(shí)間復(fù)雜性滿足遞歸方程，若要使得算法A時(shí)間復(fù)雜性的階高于算法B時(shí)間復(fù)雜性的階，a的最大整數(shù)值可取多少？3．對于字符集合M={A,B,C,D,E,F}，設(shè)這些字符在文本中出現(xiàn)的頻率分別為8,1,3,10,6,5，畫出字符集合M的Huffman編碼樹，并給出各字符的Huffman編碼。三．算法填空題（共34分）1．（10分）下面是求解分?jǐn)?shù)背包問題的貪心算法。分?jǐn)?shù)背包問題：設(shè)有一個容量為C的背包，n個物品的集合U={u1,u2,…,un}，物品ui的體積和價(jià)值分別為sj和vj，C,sj,vj都是正實(shí)數(shù)。在U中選擇物品裝入背包，使得裝入背包的物品總價(jià)值最大。設(shè)允許取每種物品的一部分裝入背包?？忌畔冢撸撸撸撸撸邔W(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿＿＿裝訂線算法GREEDY_KANPSACK輸入：表示背包容量的實(shí)數(shù)C,物品數(shù)n,表示n個物品的體積和價(jià)值的實(shí)數(shù)數(shù)組s[1..n]和v[1..n]。輸出：裝入背包的物品的最大總價(jià)值maxv和相應(yīng)的最優(yōu)解x[1..n]。fori=1tony[i]=v[i]/s[i]endford=sort(y,n)//對y[1..n]按降序地址排序，排序結(jié)果返回//到數(shù)組d[1..n]中,使得//y[d[1]]>=y[d[2]]>=…>=y[d[n]]。fori=1tonx[i]=0i=1;maxv=0;rc=Cwhile(1)j=d[i]if(2)thenx[j]=1;rc=rc-s[j]elsex[j]=(3)(4)endifmaxv=(5)i=i+1endwhilereturnmaxv,x[1..n]endGREEDY_KNAPSACK2．（10分）下面是用回溯法求解圖的m著色問題的算法（求出所有解）。圖的m著色問題：給定一個無向連通圖G和m種顏色，給圖G的所有頂點(diǎn)著色，使得任何兩相鄰頂點(diǎn)的顏色不同。算法m-COLORING輸入：正整數(shù)m,n和含n個頂點(diǎn)的無向連通圖G的鄰接矩陣graph。輸出：圖G的m著色問題的所有解,若無解，則輸出nosolution。flag=falsek=1;x[1]=0whilek>=1while(1)x[k]=x[k]+1ifcolor(k)thenif(2)thenflag=true;outputx[1..n]elsek=(3)(4)endifendifendwhile(5)endwhileifnotflagthenoutput“nosolution”endm-COLORING過程color(k)//在前k-1個頂點(diǎn)已著色的情況下，判斷第k個頂點(diǎn)是否可著顏色x[k],是則考生信息欄＿＿＿＿＿＿學(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿＿＿裝訂線//返回true,否則返回false。……endcolor3．（14分）設(shè)有n種不同面值的硬幣，面值分別為（=1），每種硬幣的個數(shù)不限，要求用最少個數(shù)的硬幣，兌換價(jià)值為m的錢（m為非負(fù)整數(shù)）。設(shè)f[k,j]表示用面值為的硬幣兌換價(jià)值為k的錢所用硬幣的最少個數(shù)，則下面是解該最優(yōu)化問題的最優(yōu)值和最優(yōu)解的動態(tài)規(guī)劃算法。算法CHANGING輸入：正整數(shù)n，非負(fù)整數(shù)m，存儲n種硬幣面值的數(shù)組c[1..n]，其中c[1]=1。輸出：兌換價(jià)值為m的錢所用硬幣的最少個數(shù)和存儲最優(yōu)解信息的數(shù)組s[0..m,1..n]。f[0..m,1..n]=-1min=coinchanging(m,n)returnmin,sendCHANGING過程coinchanging(k,j)//求用面值為c[1],c[2],…,c[j]的硬幣兌換價(jià)值為k的錢所用硬//幣的最少個數(shù)，并返回。同時(shí)記錄最優(yōu)解的信息于數(shù)組s中。iff[k,j]=(1)thenifj=1thenf[k,j]=kelseminx=coinchanging(k,j-1);i0=0fori=1tox=(2)+iifx<minxthenminx=x;i0=(3)endifendforf[k,j]=(4)s[k,j]=(5)endifendifreturnf[k,j]endcoinchanging算法SOLUTION輸入：正整數(shù)n，非負(fù)整數(shù)m，存儲n種硬幣面值的數(shù)組c[1..n]，存儲最優(yōu)解信息的數(shù)組s[0..m,1..n]。輸出：用最少的硬幣個數(shù)兌換價(jià)值為m的錢的最優(yōu)解x[1..n](x[i]表示所兌換出的面值為c[i]的硬幣的個數(shù))。x[n]=s[m,n];k=m-x[n]*c[n]fori=n-1to1x[i]=(6);k=(7)endforoutputx[1..n]endSOLUTION考生信息欄＿＿＿＿＿＿學(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿＿＿裝訂線四．算法設(shè)計(jì)題（15分）1.寫出一個隨機(jī)算法，對于一個由n個整數(shù)組成的序列，求其中的第1~k小元素（即序列按升序排序后的前k個元素），并給出該算法的期望時(shí)間復(fù)雜性的階。2005計(jì)本《算法設(shè)計(jì)與分析》期考試卷(B)標(biāo)準(zhǔn)答案填空題：1.有窮性，確定性，可行性，有>=0個輸入，有>0個輸出2.3.4.分解出的需要求解的子問題的個數(shù)5.避免重復(fù)求解子問題6.答案7.相互獨(dú)立的（不重疊的）8.不一定9.小10.插入排序算法11.總是或者得到正確的解或者找不到解。12.遞歸關(guān)系13.比較14.求的值(logn)計(jì)算題和簡答題：這些函數(shù)按不同的階分成如下4類：Θ(1):f1,f5Θ(n):f3,f6,f7Θ(nlogn):f2,f8Θ():f4各類的階按從低到高的順序排列的結(jié)果是：Θ(1),Θ(n),Θ(nlogn),Θ()2.解：分別記算法A和算法B的時(shí)間復(fù)雜性為和，解相應(yīng)的遞歸方程得：依題意，要求最大的整數(shù)a使得。顯然，當(dāng)a<=4時(shí)，；當(dāng)a>4時(shí)，a<=16。所以，所求的a的最大整數(shù)值為15。3.字符集合M的Huffman編碼樹是：各字符的Huffman編碼：A:01B:1000C:1001D:11E:00F:101算法填空題：(1)rc>0andi<=n(2)s[j]<=rc(3)rc/s[j](4)rc=0(5)maxv+v[j]*x[j](1)x[k]<m(2)k=n(3)k+1(4)x[k]=0(5)k=k-13.(1)–1(2)coinchanging(k-i*c[j],j-1)(3)i(4)minx(5)i0(6)s[k,i](7)k-x[i]*c[i]算法設(shè)計(jì)題：1.算法RANDOMIZEDSELECT輸入：整數(shù)n,k,1<=k<=n,以及n個元素的整數(shù)數(shù)組A[1..n]。輸出：A中的第1~k小元素。rselect(A,1,n,k)endRANDOMIZEDSELECT過程rselect(A,low,high,k)//求A[low..high]中的前k小元素并輸出。v=random(low,high)mm=A[v]將A[low..high]分成三個數(shù)組：A1={a|a<mm},A2={a|a=mm},A3={a|a>mm}if|A1|>=kthenrselect(A1,1,|A1|,k)elseif|A1|+|A2|>=kthen輸出A1的所有元素以及k-|A1|個mm值else輸出A1和A2的所有元素rselect(A3,1,|A3|,k-|A1|-|A2|)endifendifreturnendrselect該算法的時(shí)間復(fù)雜性的階是(n)。福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院2006—2007學(xué)年第二學(xué)期考試A卷考生信息欄＿＿＿＿＿＿學(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿裝訂線專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)年級：20XX級課程名稱:算法設(shè)計(jì)與分析任課教師：潘日晶試卷類別：開卷（）閉卷（√）考試用時(shí)：120分鐘考試時(shí)間:2007年1月13日下午18點(diǎn)30分題號一二三四五總得分評卷人得分題號六七八九十得分一．填空題（每空2分，共30分）1．算法的時(shí)間復(fù)雜性指算法中的執(zhí)行次數(shù)。2．在忽略常數(shù)因子的情況下，O、和三個符號中，提供了算法運(yùn)行時(shí)間的一個上界。3．設(shè)Dn表示大小為n的輸入集合，t(I)表示輸入為I時(shí)算法的運(yùn)算時(shí)間,p(I)表示輸入I出現(xiàn)的概率，則算法的平均情況下時(shí)間復(fù)雜性A(n)=。4．分治算法的時(shí)間復(fù)雜性常常滿足如下形式的遞歸方程：其中，g(n)表示。5.分治算法的基本步驟包括。6．回溯算法的基本思想是。7．動態(tài)規(guī)劃和分治法在分解子問題方面的不同點(diǎn)是。8．貪心算法中每次做出的貪心選擇都是最優(yōu)選擇。9．PQ式的分支限界法中，對于活結(jié)點(diǎn)表中的結(jié)點(diǎn)，其下界函數(shù)值越小，優(yōu)先級越。10．選擇排序、插入排序和歸并排序算法中，算法是分治算法。11．隨機(jī)算法的一個基本特征是對于同一組輸入，不同的運(yùn)行可能得到的結(jié)果。12.對于下面的確定性快速排序算法，只要在步驟3前加入隨機(jī)化步驟，就可得到一個隨機(jī)化快速排序算法，該隨機(jī)化步驟的功能是。算法QUICKSORT輸入：n個元素的數(shù)組A[1..n]。輸出：按非降序排列的數(shù)組A中的元素?？忌畔冢撸撸撸撸撸邔W(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿＿＿裝訂線1.quicksort(1,n)endQUICKSORT過程quicksort(A,low,high)//對A[low..high]中的元素按非降序排序。2.iflow<highthen3.w=SPLIT(A,low,high)//算法SPLIT以A[low]為主元將A[low..high]劃分成兩部//分，返回主元的新位置。4.quicksort(A,low,w-1)5.quicksort(A,w+1,high)6．endifendquicksort13．下面算法的基本運(yùn)算是運(yùn)算，該算法的時(shí)間復(fù)雜性階為()。算法SPLIT輸入：正整數(shù)n，數(shù)組A[1..n]。輸出：…。i=1x=A[1]forj=2tonifA[j]<=xtheni=i+1ifijthenA[i]A[j]endifendforA[i]A[1]w=ireturnw,AendSPLIT二．計(jì)算題和簡答題（每小題7分，共21分）1．用O、、表示函數(shù)f與g之間階的關(guān)系，并分別指出下列函數(shù)中階最低和最高的函數(shù)：(1)f(n)=100g(n)=(2)f(n)=6n+ng(n)=3n(3)f(n)=n/logn-1g(n)=(4)f(n)=g(n)=(5)f(n)=g(n)=2．下面是一個遞歸算法，其中，過程pro1和pro2的運(yùn)算時(shí)間分別是1和。給出該算法的時(shí)間復(fù)雜性T(n)滿足的遞歸方程，并求解該遞歸方程，估計(jì)T(n)的階（用表示）。算法EX1輸入：正整數(shù)n，n=2k。輸出：…ex1(n)endEX1過程ex1(n)ifn=1thenpro1(n)else考生信息欄＿＿＿＿＿＿學(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿＿＿裝訂線pro2(n)ex1(n/2)endifreturnendex13．用Floyd算法求下圖每一對頂點(diǎn)之間的最短路徑長度，計(jì)算矩陣D0，D1，D2和D3，其中Dk[i,j]表示從頂點(diǎn)i到頂點(diǎn)j的不經(jīng)過編號大于k的頂點(diǎn)的最短路徑長度。三．算法填空題（共34分）1．（10分）設(shè)n個不同的整數(shù)按升序存于數(shù)組A[1..n]中，求使得A[i]=i的下標(biāo)i。下面是求解該問題的分治算法。算法SEARCH輸入：正整數(shù)n，存儲n個按升序排列的不同整數(shù)的數(shù)組A[1..n]。輸出：A[1..n]中使得A[i]=i的一個下標(biāo)i，若不存在，則輸出nosolution。i=find((1))ifi>0thenoutputielseoutput“nosolution”endSEARCH過程find(low,high)//求A[low..high]中使得A[i]=i的一個下標(biāo)并返回，若不存在，//則返回0。if(2)thenreturn0elsemid=if(3)thenreturnmidelseifA[mid]<midthenreturnfind((4))elsereturn(5)endifendifendifendfind2．(10分)下面是求解矩陣鏈乘問題的動態(tài)規(guī)劃算法。矩陣鏈乘問題：給出n個矩陣M1,M2,…,Mn,Mi為riri+1階矩陣，i=1,2,…,n，求計(jì)算M1M2…Mn所需的最少數(shù)量乘法次數(shù)。記Mi,j=MiMi+1…Mj,i<=j。設(shè)C[i,j],1<=i<=j<=n,表示計(jì)算Mi,j的所需的最少數(shù)量乘法次數(shù)，則算法MATCHAIN輸入：矩陣鏈長度n,n個矩陣的階r[1..n+1],其中r[1..n]為n個矩陣的行數(shù)，r[n+1]為第n個矩陣的列數(shù)。輸出：n個矩陣鏈乘所需的數(shù)量乘法的最少次數(shù)?？忌畔冢撸撸撸撸撸邔W(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿＿＿裝訂線fori=1tonC[i,i]=（1）ford=1ton-1fori=1ton-dj=(2)C[i,j]=∞fork=i+1tojx=(3)ifx<C[i,j]then(4)=xendifendforendforendforreturn(5)endMATCHAIN3．(14分)下面是用回溯法求解馬的周游問題的算法。馬的周游問題：給出一個nxn棋盤，已知一個中國象棋馬在棋盤上的某個起點(diǎn)位置（x0,y0），求一條訪問每個棋盤格點(diǎn)恰好一次，最后回到起點(diǎn)的周游路線。（設(shè)馬走日字。）算法HORSETRAVEL輸入：正整數(shù)n，馬的起點(diǎn)位置(x0,y0)，1<=x0,y0<=n。輸出：一條從起點(diǎn)始訪問nxn棋盤每個格點(diǎn)恰好一次，最后回到起點(diǎn)的周游路線；若問題無解，則輸出nosolution。tag[1..n,1..n]=0dx[1..8]={2,1,-1,-2,-2,-1,1,2}dy[1..8]={1,2,2,1,-1,-2,-2,-1}flag=falsex=x0;y=y0;tag[x,y]=1m=n*ni=1;k[i]=0while(1)andnotflagwhilek[i]<8andnotflagk[i]=(2)x1=x+dx[k[i]];y1=y+dy[k[i]]if((x1,y1)無越界andtag[x1,y1]=0)or((x1,y1)=(x0,y0)andi=m)thenx=x1;y=y1tag[x,y]=(3)ifi=mthenflag=trueelsei=(4)(5)endifendifendwhilei=i-1(6)(7)endwhileifflagthenoutputroute(k)//輸出路徑elseoutput“nosolution”endHORSETRAVEL考生信息欄＿＿＿＿＿＿學(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿＿＿裝訂線四．算法設(shè)計(jì)題（15分）1.一個旅行者要駕車從A地到B地，A、B兩地間距離為s。A、B兩地之間有n個加油站，已知第i個加油站離起點(diǎn)A的距離為公里，0=，車加滿油后可行駛m公里，出發(fā)之前汽車油箱為空。應(yīng)如何加油使得從A地到B地沿途加油次數(shù)最少？給出用貪心法求解該最優(yōu)化問題的貪心選擇策略，寫出求該最優(yōu)化問題的最優(yōu)值和最優(yōu)解的貪心算法，并分析算法的時(shí)間復(fù)雜性。福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院2006—2007學(xué)年第二學(xué)期考試C卷考生信息欄＿＿＿＿＿＿學(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿裝訂線專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)年級：20XX級課程名稱:算法設(shè)計(jì)與分析任課教師：潘日晶試卷類別：開卷（）閉卷（√）考試用時(shí)：120分鐘考試時(shí)間:年月日午點(diǎn)分題號一二三四五總得分評卷人得分題號六七八九十得分一．填空題（每空2分，共30分）1．計(jì)算復(fù)雜性包括兩個方面。2．在忽略常數(shù)因子的情況下，提供了算法運(yùn)行時(shí)間的一個界。3．算法的平均情況下時(shí)間復(fù)雜性A(n)=，其中Dn表示大小為n的輸入集合，t(I)表示輸入為I時(shí)算法的運(yùn)算時(shí)間,p(I)表示。4．從算法時(shí)間復(fù)雜性的角度看，時(shí)間復(fù)雜性階為的算法是實(shí)際可接受的。5．用動態(tài)規(guī)劃算法解題時(shí)，，算法的效率越高。6．分治算法的基本步驟包括。7．回溯算法的搜索順序是。8．貪心法通常用于求解問題。9．PQ式的分支限界法中，活結(jié)點(diǎn)表的結(jié)構(gòu)是。10．Prim算法、Dijkstra算法、快速排序算法和Huffman算法中不是貪心算法。11．一個問題滿足遞歸關(guān)系是指。12．隨機(jī)算法不同于確定性算法，對于同一輸入，不同的運(yùn)行執(zhí)行的時(shí)間。13對于下面的確定性二分查找算法，只要將步驟3改為隨機(jī)化步驟，就可得到一個隨機(jī)化查找算法。算法BISEARCH輸入：正整數(shù)n，n個元素的升序數(shù)組A[1..n]和元素x。輸出：如果存在j，1<=j<=n使得x=A[j]，則輸出j，否則輸出0。1.low=1;high=n;j=02.while(low<=high)and(j=0)3.mid=4.ifx=A[mid]thenj=mid5.elseifx<A[mid]thenhigh=mid-1考生信息欄＿＿＿＿＿＿學(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿＿＿裝訂線elselow=mid+17.endif8.endif9.endwhile10.returnjendBISEARCH14．下面算法的基本運(yùn)算是運(yùn)算，該算法中第4步執(zhí)行了次。算法COUNT輸入：正整數(shù)n（n=）。輸出：count的值。1.count=02.whilen>=13.forj=1ton4.count=count+15.endfor6.n=n/27.endwhileendCOUNT二．計(jì)算題和簡答題（每小題7分，共21分）1．用表示下列各函數(shù)的階，并按階從低到高的順序排列這些函數(shù)。n3/(n+5),2n+3n/2,5n2log3n+n3log2n,n!+nn,log(logn)/10002．下面是一個分治算法，其中，過程pro1和pro2的運(yùn)算時(shí)間分別是1和n。給出該算法的時(shí)間復(fù)雜性T(n)滿足的遞歸方程，并求解該遞歸方程，估計(jì)T(n)的階（用表示）。算法EX2輸入：正整數(shù)n，n=2k。輸出：…ex2(1,n)endEX2過程ex2(low,high)iflow>=highthenpro1()elsem=ex2(low,m)ex2(m+1,high)pro2(low,high)endifreturnendex23．設(shè)矩陣M1，M2，M3，M4，M5的階如下：M1：102M2：25M3：52M4：24M5：410。下面表1和表2是用動態(tài)規(guī)劃算法MATCHAIN求矩陣鏈乘積M1M2M3M4M5所需的最少數(shù)量乘法次數(shù)的有關(guān)結(jié)果，考生信息欄＿＿＿＿＿＿學(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿＿＿裝訂線C[1,1]=0C[1,2]=100C[1,3]=60C[1,4]=C[1,5]=C[2,2]=0C[2,3]=20C[2,4]=36C[2,5]=C[3,3]=0C[3,4]=40C[3,5]=180C[4,4]=0C[4,5]=80C[5,5]=0表1S[1,1]=0S[1,2]=2S[1,3]=2S[1,4]=S[1,5]=S[2,2]=0S[2,3]=3S[2,4]=4S[2,5]=S[3,3]=0S[3,4]=4S[3,5]=4S[4,4]=0S[4,5]=5S[5,5]=0表2其中，C[i,j]表示求MiMi+1…Mj所需的最少數(shù)量乘法次數(shù)，S[i,j]表示相應(yīng)的最優(yōu)解信息。填充表1和表2中空缺的數(shù)據(jù)，并根據(jù)數(shù)組S確定求M1M2M3M4M5的最優(yōu)順序（通過加括號表示）。三．算法填空題（共34分）（10分）下面是快速排序算法。算法QUICKSORT輸入：正整數(shù)n，n個元素的數(shù)組A[1..n]。輸出：按非降序排列的數(shù)組A中的元素。quicksort(A,1,n)endQUICKSORT過程quicksort(A,low,high)//將A[low..high]中的元素按非降序快速排序。iflow<highthenw=SPLIT(A,low,high)

quichsort((1))quichsort((2))endifendquicksort過程SPLIT(A,low,high)//以A[low]為主元劃分A[low..high],返回主元的新位置。i=low;x=A[low]forj=low+1tohighifA[j]<=xtheni=(3)ifi≠jthen(4)endifendfor(5)w=ireturnwendSPLIT2.(10分)下面是用回溯法解n皇后問題的算法（求出所有解）。n皇后問題：在nxn棋盤上放置n個皇后使得任何兩個皇后不能互相攻擊。（如果兩個皇后處在同一行，或同一列，或同一斜線上，則她們能互相攻擊。）算法NQUEENS輸入：正整數(shù)n。輸出：n皇后問題的一個解x[1..n],若無解，則輸出Nosolution。flag=falsek=1;x[1]=0考生信息欄＿＿＿＿＿＿學(xué)院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學(xué)號＿＿＿＿＿裝訂線while(1)whilex[k]<nx[k]=(2)ifplace(k)thenifk=nthenflag=true；outputx[1..n] elsek=(3)(4)endifendifendwhile(5)endwhileifnotflagthenoutput“Nosolution”endNQUEENS過程place(k)//判斷第k行皇后是否與前k-1行皇后沖突，是則返回false,否//則返回true?！璭ndplace3.（14分）下面是解可復(fù)選的背包問題的動態(tài)規(guī)劃算法。問題描述：有一個容量為C的背包和n種物品，每種物品的個數(shù)都是無限的。設(shè)第i種物品的體積和價(jià)值分別為si和vi，C,si,vi都是正整數(shù)，i=1,2,…,。在這n種物品中選擇物品裝入背包，使得

裝入背包的物品總價(jià)值最大。設(shè)每種物品都可選擇任意個裝入背包。設(shè)f[i,j]表示背包容量為j，在第1~i種物品中進(jìn)行選擇的可復(fù)選背包問題的最優(yōu)值，則算法KNAPSACK輸入：物品種數(shù)n,n種物品的體積數(shù)組s[1..n]和價(jià)值數(shù)組v[1..n],背包容量C。輸出：裝入背包物品的最大總價(jià)值maxv，以及存儲最優(yōu)解信息的數(shù)組H[0..n,0..C]。f[0..n,0..C]=-1maxv=knapsack(n,C)returnmaxv,HendKNAPSACK過程knapsack(i,j)//從第1~i種物品中選擇物品裝入容量為j的背包中，求背包中物品/