數(shù)據(jù)結(jié)構(gòu)問題解答

1、4、若有n個元素的序列近似有序，即除掉少數(shù)K個元素后是有序序列且Kdata==pjdata)pi=pinextpj=pjnextelse失配時回溯到主串的下一個字符ps=psnextpi=pspj=t如果匹配成功返回主串中匹配的起始位置if(pj==NULL)returnpselsereturnNULLdataNext但在最壞情況下，每次劃分只能舍棄一個元素，比較次數(shù)達(dá)到N(N1)…(NK)=N(N1)2K(K1)2，時間復(fù)雜度為O(N

2、2K2)，由于K遠(yuǎn)小于N，可近似為O(N2)。不過，通過調(diào)整選取軸記錄的方法（如采用“三者取中”，以及其他精心構(gòu)造的方法），可以減少（甚至消除）最壞情況出現(xiàn)的可能性。故可以認(rèn)為，該方法的平均時間復(fù)雜度為O(NKlogK)。總結(jié)一下上面幾種方法的時間復(fù)雜度：序號時間復(fù)雜度最好情況最壞情況K遠(yuǎn)小于N時K=N2時（1）O(KN)O(KN)O(KN)O(KN)O(N2)（2）O(KlogKK(NK))O(KlogKNK)O(KlogKK(NK)

3、)O(KN)O(N2)（3）O(K(NK)logK)O(NK)O(K(NK)logK)O(NlogK)O(NlogN)（4）O(NKlogN)O(NK)O(NKlogN)O(NKlogN)O(NlogN)（5）O(NKlogK)O(NKlogK)O(N2K2)O(NKlogK)O(NlogN)三、數(shù)學(xué)歸納法證明非空滿K叉樹的葉子結(jié)點數(shù)目為(K1)N1，其中N為分支結(jié)點數(shù)目【分析】思路應(yīng)該是比較清楚，只要注意滿K叉樹的基本形式，注意到樹中

4、只有分支結(jié)點和葉子結(jié)點，其中分支結(jié)點必有K個孩子。由于滿K叉樹中分支結(jié)點數(shù)N是一層一層增長的，存在K倍關(guān)系，可根據(jù)樹的高度歸納得出結(jié)論。但是，實際上，即便不是滿K叉樹，只要能夠保證樹中只有度為K的結(jié)點和葉子結(jié)點，也可以得到相同的結(jié)論。而此時如果用歸納法證明，就可以根據(jù)分支結(jié)點數(shù)N進(jìn)行遞推（每增加一個分支結(jié)點，會使葉子節(jié)點數(shù)增加K1），這樣會更自然一些。也許這才是該問題令人困惑的地方。下面，首先用歸納法證明如果K叉樹只包含葉子結(jié)點和N個度

5、為K的結(jié)點，則葉子節(jié)點有(K1)N1個。由于任何非空的滿K叉樹一定滿足上述條件，所以在題目給定的條件下，結(jié)論成立。證明思路僅供參考?！緟⒖冀獯稹孔C明：首先，用歸納法證明如果一棵K叉樹只包含葉子結(jié)點和N個度為K的結(jié)點，則葉子節(jié)點數(shù)為(K1)N1.當(dāng)度為K的結(jié)點數(shù)N=0時，葉子結(jié)點數(shù)=(K1)N1=1，結(jié)論成立.假設(shè)度為K的結(jié)點數(shù)N=n時結(jié)論成立，即有葉子結(jié)點數(shù)=(K1)n1.當(dāng)N=n1時，與N=n相比，可以任選一個葉子結(jié)點擴展為度為K的分

6、支結(jié)點，因此，葉子結(jié)點數(shù)增加了K1個.此時葉子結(jié)點數(shù)=[(K1)n1](K1)=(K1)(n1)1，結(jié)論成立。所以，一顆只包含葉子結(jié)點和N個度為K的結(jié)點的K叉樹，葉子結(jié)點數(shù)為(K1)N1.因為，任何非空的滿K叉樹中只有葉子結(jié)點和度為K的分支結(jié)點，故原命題成立。即：非空滿K叉樹葉子結(jié)點數(shù)為(K1)N1.五、有一個由英文書目構(gòu)成的文件（書名不定長度，以“；”為分割符）；讀入該文件，對這一書目單按字典排序，將結(jié)果以文件方式存儲。編程實現(xiàn)之。【