設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn),則此類二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為(2h-1 )。已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表,結(jié)點(diǎn)結(jié)構(gòu)為(data, link)。假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下,請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法,查找出鏈表中倒數(shù)第k(k為正整數(shù))個(gè)位置上的結(jié)點(diǎn)。若查找成功,算法輸出該結(jié)點(diǎn)的data域的值,并返回1;否則,只返回0。要求:
(1) 描述算法的基本設(shè)計(jì)思想;
(2) 用算法描述語(yǔ)言描述算法;
(3) 給出算法的時(shí)間復(fù)雜性分析。
您可能感興趣的試卷
你可能感興趣的試題
最新試題
單鏈表類型定義如下:用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)待排數(shù)據(jù),鏈表頭指針為head。下列直接選擇排序算法對(duì)鏈表按升序進(jìn)行排序,請(qǐng)?zhí)顚?xiě)適當(dāng)內(nèi)容使算法完整。
閱讀下列算法,并回答問(wèn)題:設(shè)棧S=(1,2,3,4,5,6,7),其中7為棧頂元素。調(diào)用函數(shù)f30(S)后,(1)第一個(gè)循環(huán)結(jié)束后,棧T和隊(duì)列Q中的內(nèi)容各是什么?(2)第三個(gè)循環(huán)語(yǔ)句結(jié)束后,棧S中的內(nèi)容是什么?
實(shí)現(xiàn)二分查找的遞歸章法如下,在相應(yīng)位置填寫(xiě)適當(dāng)?shù)膬?nèi)容使算法完整。
已知某二叉樹(shù)的后序遍歷序列是CEFDBA,中序遍歷序列是CBEDFA。與該二叉樹(shù)對(duì)應(yīng)的樹(shù)或森林中,葉子的數(shù)目是()個(gè)。
設(shè)二叉樹(shù)采用二叉鏈表方式存儲(chǔ),root指向根結(jié)點(diǎn),r所指結(jié)點(diǎn)為二叉樹(shù)中任一給定的結(jié)點(diǎn)。則可以通過(guò)改寫(xiě)()算法,求出從根結(jié)點(diǎn)到結(jié)點(diǎn)r之間的路徑。
只要無(wú)向圖中有權(quán)重相同的邊,其最小生成樹(shù)就不可能唯一。
則該隊(duì)列為滿隊(duì)列的條件為()(采用少用一個(gè)空間的方法)
對(duì)給定的數(shù)據(jù)集{84,47,25,15,21}排序,進(jìn)行2趟簡(jiǎn)單選擇排序的結(jié)果是()
若三維數(shù)組a[4][5][6]的基地址是100,每個(gè)元素占用2個(gè)存儲(chǔ)單元,則數(shù)組a中最后一個(gè)元素的存儲(chǔ)地址是()。
數(shù)據(jù)元素在計(jì)算機(jī)的存儲(chǔ)映像包括()