2014(下)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)

1、2014下《數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)提綱復(fù)習(xí)提綱第1章緒論緒論有關(guān)術(shù)語；算法、算法復(fù)雜度的分析和計算方法例題：例題：1下面算法的時間復(fù)雜度為O(n)。intf(unsignedintn)if(n==0||n==1)return1elsereturennf(n–1)2f（i=1，s=0；inext=ssnext=p）；注意在某個已知結(jié)點前插需要執(zhí)行的語句？2注意循環(huán)（鏈）隊列的判空和判滿的條件？（看書理解?。?對于一個具有n個結(jié)點的單鏈表，

2、在已知的結(jié)點p后插入一個新結(jié)點的時間復(fù)雜度為O(1)，在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為O(n)。4.在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為(rearl)％n==front。執(zhí)行出隊操作后其頭指針front如何5.線性表采用鏈式存儲時，結(jié)點的存儲地址連續(xù)與否均可6.鏈式棧刪除棧頂元素的操作序列為top=topnext.7.在單鏈表中，指針p指向元素為x的結(jié)

3、點，實現(xiàn)“刪除x的后繼”的語句是pnext=pnextnext.8.判定“帶頭結(jié)點的鏈隊列為空”的條件是Q.front==Q.rear.9.假設(shè)以數(shù)組seqn［m］存放循環(huán)隊列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊列中隊尾元素的位置和元素的個數(shù)。則隊滿的條件表達式為quelen==m；隊空的條件表達式quelen==0；隊頭元素位置的表達式7.無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷

4、時的時間復(fù)雜度為O(n2)用鄰接表作為圖的存儲上述復(fù)雜度O(ne).8.在含n個頂點和e條邊的無向圖的鄰接矩陣中零元素的個數(shù)為n2－2e.9.設(shè)有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d，則e和d的關(guān)系為d=e.10.設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=d211.掌握最小生成樹算法.例如使用普里姆（Prim）算法以A為源點，構(gòu)造下圖的最小代價生成樹，畫出各步的結(jié)果。12.已知有向圖G如下所示