設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn),則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為(2h-1 )。已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表,結(jié)點(diǎn)結(jié)構(gòu)為(data, link)。假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下,請?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法,查找出鏈表中倒數(shù)第k(k為正整數(shù))個(gè)位置上的結(jié)點(diǎn)。若查找成功,算法輸出該結(jié)點(diǎn)的data域的值,并返回1;否則,只返回0。要求:
(1) 描述算法的基本設(shè)計(jì)思想;
(2) 用算法描述語言描述算法;
(3) 給出算法的時(shí)間復(fù)雜性分析。
您可能感興趣的試卷
你可能感興趣的試題
最新試題
當(dāng)需要用一個(gè)形式參數(shù)直接改變對應(yīng)實(shí)參的值時(shí),該形式參數(shù)應(yīng)說明為()
遞歸算法具有兩個(gè)特性分別是()
下列可以直接用循環(huán)結(jié)構(gòu)即可將遞歸轉(zhuǎn)換為非遞歸的是()
一個(gè)抽象類型包括數(shù)據(jù)對象、()和一組處理數(shù)據(jù)的操作。
在打印楊輝三角形前N行的算法中,需要申請一個(gè)N*N的二維數(shù)組存放楊輝三角形N行數(shù)據(jù)。
若無向圖中任意兩個(gè)不同的頂點(diǎn)間都有路徑,則稱該圖為()。
數(shù)據(jù)元素在計(jì)算機(jī)的存儲(chǔ)映像包括()
只要無向圖中有權(quán)重相同的邊,其最小生成樹就不可能唯一。
一棵二叉樹的先序序列是:CEDBA,中序序列是:DEBAC ,則該二叉樹的后序序列是()
通過表達(dá)式()可以獲取帶頭結(jié)點(diǎn)的單鏈表L中首元素結(jié)點(diǎn)的數(shù)據(jù)值。