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