算法與數(shù)據(jù)結(jié)構(gòu)C語言習(xí)題參考答案6-9章

1.現(xiàn)在有一個(gè)已排序的字典，請(qǐng)改寫二分法檢索算法，使之當(dāng)排序碼key在字典中重復(fù)出現(xiàn)時(shí)算法能找出第一個(gè)key出現(xiàn)的元素下標(biāo)(用*position來保存)。保持算法時(shí)一般的二分法檢索算法只要找出關(guān)鍵碼key在字典中的一個(gè)下標(biāo)。在比較的過程中，一旦發(fā)現(xiàn)相等，記錄下當(dāng)前下標(biāo)mid就符合要求。程序如下：數(shù)據(jù)結(jié)構(gòu)字典采用6.1.4節(jié)中的順序表示法。二分法檢索算法}改寫后的算法想要找出關(guān)鍵碼key在字典中第一次出現(xiàn)的下標(biāo)。在比較中，如果遇到相(1)如果當(dāng)前下標(biāo)mid等于0,或者key與pdic->element[mid-1].key不等，那么mid一定是key第一次出現(xiàn)的下標(biāo)，返回mid即可。(2)如果情形(1)不成立，那么mid一定大于等于key第一次出現(xiàn)的下標(biāo)，需要在low和mid-1之間繼續(xù)進(jìn)行搜索，找出key第一次出現(xiàn)的下標(biāo)。下面算法中，加粗的部分是對(duì)原算法的修改。修改后的二分法檢索算法if(pdic->element[mid].key==key){}}代價(jià)分析該算法的時(shí)間復(fù)雜度為O(logn)。2.試編寫一算法求出指定結(jié)點(diǎn)在給定的二叉排序樹中所在的層數(shù)?！敬稹坎捎?.1.3節(jié)中字典的二叉排序樹表示。if(p->key==pnode->key)if(p->key>pnode->key){}}代價(jià)分析3.試編寫一算法在給定的二叉排序樹上找出任意兩個(gè)不同結(jié)點(diǎn)最近的公共祖先(若在兩結(jié)點(diǎn)A,B中，A是B的祖先，則認(rèn)為A,B最近的公共祖先就是A)。數(shù)據(jù)結(jié)構(gòu)同上題4.設(shè)計(jì)一個(gè)有效的算法，在1000個(gè)無序的元素中，挑選出其中前5個(gè)最大的元素。數(shù)據(jù)結(jié)構(gòu)typedefintKeyType;typedefstruct/*記錄的其它字段*/typedefstruct這里不需要整體排序，故選擇一種能較快得出最終排序段的前一部分的算法改造即可，如直接選擇排序，起泡排序，堆排序都能最先得出前5個(gè)最大元素。綜合考慮算法的時(shí)間代價(jià)，選擇直接選擇排序算法改造即可。算法函數(shù)返回一個(gè)數(shù)組，數(shù)組中存著挑出的元素，為動(dòng)態(tài)分配的。returnNULL;}{returnNULL;{}}代價(jià)分析0(n*m)(設(shè)從n個(gè)元素中選出m個(gè)最大元素)。5.寫一個(gè)算法來判斷對(duì)給定有向圖中的指定頂點(diǎn)是否至少存在一條有向邊指向它?！敬稹繄D有三種表示方法：出邊表(鄰接表的一種),入邊表(鄰接表的一種)和鄰接矩陣。相應(yīng)的有三種算法。設(shè)n為頂點(diǎn)數(shù)，m為邊數(shù)。對(duì)于出邊表，順次搜索一遍邊即可，時(shí)間代價(jià)為O(m)。對(duì)于入邊表，判斷指定頂點(diǎn)的邊表頭指針是否非空即可，時(shí)間代價(jià)為0(1)。對(duì)于鄰接矩陣，搜索矩陣中指定頂點(diǎn)對(duì)應(yīng)的列，判斷其中是否有非0元即可，時(shí)間代價(jià)以出邊表為例，給出一個(gè)算法如下。數(shù)據(jù)結(jié)構(gòu)采用9.1.3節(jié)中有向圖的鄰接表(出邊表)表示法。p=g.vexs[i].edgelist}代價(jià)分析該算法的時(shí)間復(fù)雜度為0(m)。6.設(shè)計(jì)一個(gè)算法，確定(無權(quán))圖中每一對(duì)結(jié)點(diǎn)之間的可達(dá)關(guān)系?！敬稹繑?shù)據(jù)結(jié)構(gòu)采用圖的鄰接矩陣表示法。這里介紹Warshall算法，該算法解決了(無權(quán))圖的可達(dá)性問題。算法用到了一個(gè)矩陣a(a作為算法的參數(shù)之一)。開始時(shí)，對(duì)矩陣a中元素賦值，使a與圖的鄰接矩陣相等。這樣，矩陣a記錄的就是所有直接的邊連接。算法的核心部分是一個(gè)三重循環(huán)。其中外重循環(huán)的循環(huán)次數(shù)為n,每次循環(huán)更新a中的元素。循環(huán)一次后，a中記錄的就是所有直接連接或者只經(jīng)由結(jié)點(diǎn)0而形成的通路的情況。循環(huán)k(1≤k≤n)次后，a中記錄的就是所有至多只經(jīng)由結(jié)點(diǎn)0,1,..,k-1而形成的通路的情況。這樣，算法結(jié)束時(shí)，矩陣a中記錄的就是每一對(duì)結(jié)點(diǎn)之間的可達(dá)性信息。a[j[]為1,表示從結(jié)點(diǎn)i到結(jié)點(diǎn)j是可達(dá)的；為0,則表示不可達(dá)。代價(jià)分析算法的核心部分是一個(gè)三重循環(huán),每重的循環(huán)次數(shù)為n,因此該算法的時(shí)間代價(jià)為O(n3)。調(diào)試結(jié)果該示例程序計(jì)算下圖的可達(dá)性：運(yùn)行結(jié)果如下：000001010000000111011110000、00,00【下載