山東大學(xué)網(wǎng)絡(luò)教育期末生理學(xué)a卷-資料下載頁(yè)
2024-11-15 13:19本頁(yè)面
【正文】 受待排序初始序列的影響，時(shí)間復(fù)雜度為O(N)的排序算法是簡(jiǎn)單選擇排序_，在排序算法的最后一趟開始之前，所有元素都可能不在其最終位置上的排序算法是_直接插入排序。三、解答題1．某廣義表的表頭和表尾均為（a,(b,c)），畫出該廣義表的圖形表示。2．已知二叉樹的先序序列和中序序列分別為HDACBGFE和ADCBHFEG。（1）畫出該二叉樹；（2）畫出與（1）求得的二叉樹對(duì)應(yīng)的森林。3．已知帶權(quán)圖的鄰接表如下所示，其中邊表結(jié)點(diǎn)的結(jié)構(gòu)為：依此鄰接表從頂點(diǎn)C出發(fā)進(jìn)行深度優(yōu)先遍歷。（1）畫出由此得到的深度優(yōu)先生成樹；（2）寫出遍歷過(guò)程中得到的從頂點(diǎn)C到其它各頂點(diǎn)的帶權(quán)路徑及其長(zhǎng)度。參考答案： .(1)(2)3.(1)(2)頂點(diǎn)C到頂點(diǎn)A的帶權(quán)路徑為（C,D,B,A），其長(zhǎng)度為8+20+11=39 頂點(diǎn)C到頂點(diǎn)B的帶權(quán)路徑為（C,D,B），其長(zhǎng)度為8+20=28 頂點(diǎn)C到頂點(diǎn)D的帶權(quán)路徑為（C,D），其長(zhǎng)度為8 頂點(diǎn)C到頂點(diǎn)E的帶權(quán)路徑為（C,D,B,F,E），其長(zhǎng)度為8+20+9+14=51 頂點(diǎn)C到頂點(diǎn)F的帶權(quán)路徑為（C,D,B,F），其長(zhǎng)度為8+20+9=37四、算法設(shè)計(jì)題1．已知中序線索二叉樹T右子樹不空。設(shè)計(jì)算法，將S所指的結(jié)點(diǎn)作為T的右子樹中的 一個(gè)葉子結(jié)點(diǎn)插入進(jìn)去，并使之成為TT的右子樹的（中序序列）第一個(gè)結(jié)點(diǎn)（同時(shí)要修改 相應(yīng)的線索關(guān)系）。2．寫出在中序線索二叉樹里；找指定結(jié)點(diǎn)在后序下的前驅(qū)結(jié)點(diǎn)的算法。參考答案：：[題目分析]若使新插入的葉子結(jié)點(diǎn)S成T右子樹中序序列的第一個(gè)結(jié)點(diǎn)，則應(yīng)在T的右子樹中最左面的結(jié)點(diǎn)（設(shè)為p）處插入，使S成為結(jié)點(diǎn)p的左子女。則S的前驅(qū)是T， ThrTreeInsert(BiThrTree T,S)//在中序線索二叉樹T的右子樹上插入結(jié)點(diǎn)S，使S成為T右子樹中序遍歷第一個(gè)結(jié)點(diǎn){p=Trchild。//用p去指向T的右子樹中最左面的結(jié)點(diǎn) while(pltag==0)p=plchild。Sltag=1。Srtag=1。//S是葉子，其左右標(biāo)記均為1 Slchild=T。Srchild=p。//S的前驅(qū)是根結(jié)點(diǎn)T，后繼是結(jié)點(diǎn)p plchild=S。pltag=0。//將p的左子女指向S，并修改左標(biāo)志為0 }//結(jié)束 ThrTreeInsert 2．答案：[題目分析]在后序序列中，若結(jié)點(diǎn)p有右子女，則右子女是其前驅(qū)，若無(wú)右子女而有左子女，則左子女是其前驅(qū)。若結(jié)點(diǎn)p左右子女均無(wú)，設(shè)其中序左線索指向某祖先結(jié)點(diǎn)f（p是f右子樹中按中序遍歷的第一個(gè)結(jié)點(diǎn)），若f有左子女，則其左子女是結(jié)點(diǎn)p在后序下的前驅(qū)；若f無(wú)左子女，則順其前驅(qū)找雙親的雙親，一直繼續(xù)到雙親有左子女（這時(shí)左子女是p的前驅(qū)）。還有一種情況，若p是中序遍歷的第一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)p在中序和后序下均無(wú)前驅(qū)。BiThrTree InPostPre(BiThrTree t,p)//在中序線索二叉樹t中，求指定結(jié)點(diǎn)p在后序下的前驅(qū)結(jié)點(diǎn)q {BiThrTree q。if(prtag==0)q=prchild。//若p有右子女，則右子女是其后序前驅(qū)else if(pltag==0)q=plchild。//若p無(wú)右子女而有左子女，左子女是其后序前驅(qū)。else if(plchild==null)q=null。//p是中序序列第一結(jié)點(diǎn)，無(wú)后序前驅(qū) else //順左線索向上找p的祖先，若存在，再找祖先的左子女 {while(pltag==1 amp。amp。 plchild!=null)p=plchild。if(pltag==0)q=plchild。//p結(jié)點(diǎn)的祖先的左子女是其后序前驅(qū)else q=null。//僅右單枝樹（p是葉子），已上到根結(jié)點(diǎn)，p結(jié)點(diǎn)無(wú)后序前驅(qū)} return(q)。}//結(jié)束InPostPre
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1