Baøi taäp Toång hôïp CTDL 1 (Phaàn 4) Nguyeãn Tri Tuaán – Khoa CNTT, ñaïi hoïc KHTN ppsx

Nguyen Tri Tuan – Khoa CNTT ĐHKHTN Tp.HCM 1/1

Baøi taäp Toång hôïp CTDL 1 (Phaàn 4)

Nguyeãn Tri Tuaán – Khoa CNTT, ñaïi hoïc KHTN TP.HCM

---oOo---

Baøi 37:

Cho moät caây nhò phaân coù goác laø Root.

Haõy vieát ñoaïn chöông trình kieåm tra xem caây naøy coù phaûi laø caây caân baèng khoâng ?

(Giaû söû ta ñaõ coù haøm tính chieàu cao cuûa nuùt p nhö sau: int Chieu_Cao(NODE *p))

Baøi 38:

Cho daõy soá f(n) = 1 neáu n = 0 hay n = 1

f(n-1) + f(n-2) neáu n > 1

a. Haõy vieát moät thuû tuïc/haøm ñeä qui tính giaù trò cuûa f(n), vôùi n ñöôïc nhaäp vaøo töø baøn phím.

b. Haõy vieát moät thuû tuïc/haøm khoâng ñeä qui tính giaù trò cuûa f(n), vôùi n ñöôïc nhaäp vaøo töø

baøn phím. Söû duïng Stack ñeå khöû ñeä qui.

Baøi 39:

Cho moät maûng 2 chieàu kích thöôùc NxN. Phaùt sinh ngaãu nhieân giaù trò caùc phaàn töû cuûa maûng

trong khoaûng [0-5]. Vieát chöông trình nhaäp vaøo vò trí (i, j) baát kyø, ñeám soá löôïng caùc phaàn töû coù

cuøng giaù trò vaø lieân thoâng vôùi phaàn töû taïi vò trí (i, j).

Thöïc hieän cuøng yeâu caàu nhö treân nhöng söû duïng stack ñeå khöû ñeä qui.

Baøi 40:

a. Vieát laïi thuaät toaùn duyeät caây nhò phaân theo kieåu LNR.

b. Aùp duïng kyõ thuaät haøng ñôïi ñeå caøi ñaët thuaät toaùn duyeät caây theo möùc.

Baøi 41:

Cho tröôùc moät caáu truùc stack S.

Cho tröôùc caùc haøm thao taùc treân stack goàm:

- IsEmpty : kieåm tra stack S coù roãng khoâng ? [1: roãng, 0: khoâng roãng]

- IsFull : kieåm tra stack S coù traøn khoâng ? [1: traøn, 0: khoâng traøn]

- Push : theâm moät phaàn töû vaøo stack S.

- Pop : laáy phaàn töû ôû ñænh stack S.

Cho tröôùc moät caây nhò phaân coù goác laø Root.

Haõy vieát thuû tuïc/haøm ñeám soá nuùt trong caây maø khoâng duøng giaûi thuaät ñeä qui.

HD. Khöû ñeä qui baèng caùch duøng stack S.

--- Heát phaàn 4 ---