下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、設(shè)一棵二叉樹的結(jié)點(diǎn)結(jié)構(gòu)為(LLINK,INFO,RLINK),ROOT為指向該二叉樹根結(jié)點(diǎn)的指針,p和q分別為指向該二叉樹中任意兩個(gè)結(jié)點(diǎn)的指針,試編寫一算法ANCESTOR(ROOT,p,q,r),該算法找到p和q的最近共同祖先結(jié)點(diǎn)r。2、設(shè)有一個(gè)數(shù)組中存放了一個(gè)無序的關(guān)鍵序列K1、K2、…、Kn?,F(xiàn)要求將Kn放在將元素排序后的正確位置上,試編寫實(shí)現(xiàn)該功能的算法,要求比較關(guān)鍵字的次數(shù)不超過n。51.借助于快速排序的算法思想,在一組無序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組r[l..h]中。若查找成功,則輸出該記錄在r數(shù)組中的位置及其值,否則顯示“notfind”信息。請編寫出算法并簡要說明算法思想。3、設(shè)從鍵盤輸入一整數(shù)的序列:a1,a2,a3,…,an,試編寫算法實(shí)現(xiàn):用棧結(jié)構(gòu)存儲輸入的整數(shù),當(dāng)ai≠-1時(shí),將ai進(jìn)棧;當(dāng)ai=-1時(shí),輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況(入棧滿等)給出相應(yīng)的信息。設(shè)有一個(gè)背包可以放入的物品重量為S,現(xiàn)有n件物品,重量分別為W1,W2,...,Wn。問能否從這n件物品中選擇若干件放入背包,使得放入的重量之和正好是S。設(shè)布爾函數(shù)Knap(S,n)表示背包問題的解,Wi(i=1,2,...,n)均為正整數(shù),并已順序存儲地在數(shù)組W中。請?jiān)谙铝兴惴ǖ南聞澗€處填空,使其正確求解背包問題。Knap(S,n)若S=0則Knap←true否則若(S<0)或(S>0且n<1)則Knap←false否則若Knap(1),_=true則print(W[n]);Knap←true否則Knap←Knap(2)_,_設(shè)有一個(gè)順序棧S,元素s1,s2,s3,s4,s5,s6依次進(jìn)棧,如果6個(gè)元素的出棧順序?yàn)閟2,s3,s4,s6,s5,s1,則順序棧的容量至少應(yīng)為多少?畫出具體進(jìn)棧、出棧過程。假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞,當(dāng)兩個(gè)單詞有相同的后綴時(shí),則可共享相同的后綴存儲空間。例如:設(shè)str1和str2是分別指向兩個(gè)單詞的頭結(jié)點(diǎn),請?jiān)O(shè)計(jì)一個(gè)盡可能的高效算法,找出兩個(gè)單詞共同后綴的起始位置,分析算法時(shí)間復(fù)雜度。將n(n>1)個(gè)整數(shù)存放到一維數(shù)組R中。設(shè)計(jì)一個(gè)盡可能高效(時(shí)間、空間)的算法,將R中保存的序列循環(huán)左移p(0<p<n)個(gè)位置,即將R中的數(shù)據(jù)(x0,x1,x2,…,xn-1),變換為(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。4、約瑟夫環(huán)問題(Josephus問題)是指編號為1、2、…,n的n(n>0)個(gè)人按順時(shí)針方向圍坐成一圈,現(xiàn)從第s個(gè)人開始按順時(shí)針方向報(bào)數(shù),數(shù)到第m個(gè)人出列,然后從出列的下一個(gè)人重新開始報(bào)數(shù),數(shù)到第m的人又出列,…,如此重復(fù)直到所有的人全部出列為止?,F(xiàn)要求采用循環(huán)鏈表結(jié)構(gòu)設(shè)計(jì)一個(gè)算法,模擬此過程。5、給定n個(gè)村莊之間的交通圖,若村莊i和j之間有道路,則將頂點(diǎn)i和j用邊連接,邊上的Wij表示這條道路的長度,現(xiàn)在要從這n個(gè)村莊中選擇一個(gè)村莊建一所醫(yī)院,問這所醫(yī)院應(yīng)建在哪個(gè)村莊,才能使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短?試設(shè)計(jì)一個(gè)解答上述問題的算法,并應(yīng)用該算法解答如圖所示的實(shí)例。(20分)6、有一種簡單的排序算法,叫做計(jì)數(shù)排序(countsorting)。這種排序算法對一個(gè)待排序的表(用數(shù)組表示)進(jìn)行排序,并將排序結(jié)果存放到另一個(gè)新的表中。必須注意的是,表中所有待排序的關(guān)鍵碼互不相同,計(jì)數(shù)排序算法針對表中的每個(gè)記錄,掃描待排序的表一趟,統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小,假設(shè)針對某一個(gè)記錄,統(tǒng)計(jì)出的計(jì)數(shù)值為c,那么,這個(gè)記錄在新的有序表中的合適的存放位置即為c。(1)(3分)給出適用于計(jì)數(shù)排序的數(shù)據(jù)表定義;(2)(7分)使用Pascal或C語言編寫實(shí)現(xiàn)計(jì)數(shù)排序的算法;(3)(4分)對于有n個(gè)記錄的表,關(guān)鍵碼比較次數(shù)是多少?(4)(3分)與簡單選擇排序相比較,這種方法是否更好?為什么?7、對二叉樹的某層上的結(jié)點(diǎn)進(jìn)行運(yùn)算,采用隊(duì)列結(jié)構(gòu)按層次遍歷最適宜。intLeafKlevel(BiTreebt,intk)//求二叉樹bt的第k(k>1)層上葉子結(jié)點(diǎn)個(gè)數(shù){if(bt==null||k<1)return(0);BiTreep=bt,Q[];//Q是隊(duì)列,元素是二叉樹結(jié)點(diǎn)指針,容量足夠大intfront=0,rear=1,leaf=0;//front和rear是隊(duì)頭和隊(duì)尾指針,leaf是葉子結(jié)點(diǎn)數(shù)intlast=1,level=1;Q[1]=p;//last是二叉樹同層最右結(jié)點(diǎn)的指針,level是二叉樹的層數(shù)while(front<=rear){p=Q[++front];if(level==k&&!p->lchild&&!p->rchild)leaf++;//葉子結(jié)點(diǎn)if(p->lchild)Q[++rear]=p->lchild;//左子女入隊(duì)if(p->rchild)Q[++rear]=p->rchild;//右子女入隊(duì)if(front==last){level++;//二叉樹同層最右結(jié)點(diǎn)已處理,層數(shù)增1last=rear;}//last移到指向下層最右一元素if(level>k)return(leaf);//層數(shù)大于k后退出運(yùn)行}//while}//結(jié)束LeafKLevel8、冒泡排序算法是把大的元素向上移(氣泡的上?。部梢园研〉脑叵蛳乱疲馀莸南鲁粒┱埥o出上浮和下沉過程交替的冒泡排序算法。48.有n個(gè)記錄存儲在帶頭結(jié)點(diǎn)的雙向鏈表中,現(xiàn)用雙向起泡排序法對其按上升序進(jìn)行排序,請寫出這種排序的算法。(注:雙向起泡排序即相鄰兩趟排序向相反方向起泡)9、假設(shè)以鄰接矩陣作為圖的存儲結(jié)構(gòu),編寫算法判別在給定的有向圖中是否存在一個(gè)簡單有向回路,若存在,則以頂點(diǎn)序列的方式輸出該回路(找到一條即可)。(注:圖中不存在頂點(diǎn)到自己的?。┯邢驁D判斷回路要比無向圖復(fù)雜。利用深度優(yōu)先遍歷,將頂點(diǎn)分成三類:未訪問;已訪問但其鄰接點(diǎn)未訪問完;已訪問且其鄰接點(diǎn)已訪問完。下面用0,1,2表示這三種狀態(tài)。前面已提到,若dfs(v)結(jié)束前出現(xiàn)頂點(diǎn)u到v的回邊,則圖中必有包含頂點(diǎn)v和u的回路。對應(yīng)程序中v的狀態(tài)為1,而u是正訪問的頂點(diǎn),若我們找出u的下一鄰接點(diǎn)的狀態(tài)為1,就可以輸出回路了。voidPrint(intv,intstart)//輸出從頂點(diǎn)start開始的回路。ptr->info=(1)_______;for((2)_______;rpos<ipos+n;rpos++)if(*rpos==*ppos)break;k=(3)_______;ptr->llink=restore(ppos+1,(4)_______,k);ptr->rlink=restore((5)_______+k,rpos+1,n-1-k);returnptr;}postorder(TNODE*ptr){if(ptr=NULL)return;postorder(ptr->llink);postorder(ptr->rlink);printf(“%c”,ptr->info);}15、后序遍歷最后訪問根結(jié)點(diǎn),即在遞歸算法中,根是壓在棧底的。采用后序非遞歸算法,棧中存放二叉樹結(jié)點(diǎn)的指針,當(dāng)訪問到某結(jié)點(diǎn)時(shí),棧中所有元素均為該結(jié)點(diǎn)的祖先。本題要找p和q的最近共同祖先結(jié)點(diǎn)r,不失一般性,設(shè)p在q的左邊。后序遍歷必然先遍歷到結(jié)點(diǎn)p,棧中元素均為p的祖先。將??饺肓硪惠o助棧中。再繼續(xù)遍歷到結(jié)點(diǎn)q時(shí),將棧中元素從棧頂開始逐個(gè)到輔助棧中去匹配,第一個(gè)匹配(即相等)的元素就是結(jié)點(diǎn)p和q的最近公共祖先。typedefstruct{BiTreet;inttag;//tag=0表示結(jié)點(diǎn)的左子女已被訪問,tag=1表示結(jié)點(diǎn)的右子女已被訪問}stack;stacks[],s1[];//棧,容量夠大BiTreeAncestor(BiTreeROOT,p,q,r)//求二叉樹上結(jié)點(diǎn)p和q的最近的共同祖先結(jié)點(diǎn)r。{top=0;bt=ROOT;while(bt!=null||top>0){while(bt!=null&&bt!=p&&bt!=q)//結(jié)點(diǎn)入棧{s[++top].t=bt;s[top].tag=0;bt=bt->lchild;}//沿左分枝向下if(bt==p)//不失一般性,假定p在q的左側(cè),遇結(jié)點(diǎn)p時(shí),棧中元素均為p的祖先結(jié)點(diǎn){for(i=1;i<=top;i++)s1[i]=s[i];top1=top;}//將棧s的元素轉(zhuǎn)入輔助棧s1保存if(bt==q)//找到q結(jié)點(diǎn)。for(i=top;i>0;i--)//;將棧中元素的樹結(jié)點(diǎn)到s1去匹配{pp=s[i].t;for(j=top1;j>0;j--)if(s1[j].t==pp){prin
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024-2025學(xué)年年七年級數(shù)學(xué)人教版下冊專題整合復(fù)習(xí)卷27.2.1 相似三角形的判定(1)(含答案)-
- 現(xiàn)金流管理的技巧計(jì)劃
- 《證券交易講義》課件
- 動態(tài)調(diào)整班級教學(xué)內(nèi)容的探索計(jì)劃
- 圖像傳感器相關(guān)行業(yè)投資規(guī)劃報(bào)告范本
- 攜手共進(jìn)幼兒園學(xué)期班級工作計(jì)劃
- 車行租賃協(xié)議三篇
- 民宿廚房租賃合同三篇
- 社區(qū)參與的美術(shù)項(xiàng)目計(jì)劃
- 社會實(shí)踐活動的設(shè)計(jì)與實(shí)施計(jì)劃
- 《惡臭污染物排放標(biāo)準(zhǔn)》(GB14554-1993)
- 涼山中小學(xué)期末考試題-涼山州2017-2018學(xué)年度上期期末試題八年級數(shù)學(xué)答案
- 10kv高壓送電方案
- 工商局網(wǎng)址下載公司章程樣本
- VDA_6.3_過程審核最新版檢查表
- 霍曼門限位設(shè)定
- (完整版)小學(xué)五年級英語語法知識匯總
- 企業(yè)級統(tǒng)一開發(fā)平臺解決方案.ppt
- 國內(nèi)外電鍍原料供應(yīng)商一覽(精)
- 高等學(xué)校開展二級學(xué)院預(yù)算績效管理的思考
- 水尺計(jì)重操作實(shí)務(wù)—
評論
0/150
提交評論