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

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

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

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

---oOo---

Baøi 25:

Vieát thuaät toaùn tìm phaàn töû thay theá trong thao taùc “Xoaù moät phaàn töû P coù 2 con trong caây

BST”, söû duïng nguyeân taéc “Tìm phaàn töû taän cuøng beân traùi cuûa nhaùnh phaûi P”.

Baøi 26:

Cho moät danh saùch lieân keát ñôn vôùi phaàn töû ñaàu laø Head. Haõy cho bieát taùc duïng cuûa haøm sau

neáu lôøi goïi haøm laø fn(Head).

int fn ( NODE *p )

{

if (p<>NULL) return (1 + fn(p->Next));

else return 0;

}

Baøi 27:

Haõy phaùt bieåu coâng thöùc ñeä qui ñeå tính caùc giaù trò sau ñaây:

a. Soá nuùt cuûa caây nhò phaân tìm kieám.

b. Toång giaù trò caùc nuùt trong caây (giaû söû moãi phaàn töû laø moät soá nguyeân).

Caøi ñaët thaønh thuû tuïc/haøm caùc coâng thöùc ñaõ neâu ôû treân.

Baøi 28:

Giöõa caáu truùc caây nhò phaân tìm kieám vaø caáu truùc maûng caùc phaàn töû ñöôïc saép thöù töï taêng daàn,

coù nhöõng ñieåm gioáng vaø khaùc nhau nhö theá naøo ?

Baøi 29:

Ta coù 4 ñoái töôïng:

- Ñieåm (pixel): bao goàm toaï ñoä x, toïa ñoä y.

- Ñoaïn thaúng (line): ñöôïc xaùc ñònh bôûi 2 ñieåm (x1, y1) laø ñieåm baét ñaàu – (x2, y2) laø

ñieåm keát thuùc.

- Hình chöõ nhaät (rectangle): ñöôïc xaùc ñònh bôûi 2 ñieåm (x1, y1) laø goùc treân beân traùi – (x2,

y2) laø goùc döôùi beân phaûi.

- Hình troøn (circle): ñöôïc xaùc ñònh bôûi moät ñieåm (x, y) laø taâm; vaø R laø baùn kính.

Haõy ñònh nghóa (baèng C/PASCAL) caùc kieåu döõ lieäu cho 4 ñoái töôïng treân maø anh(chò) cho laø

hôïp lyù nhaát.

Baøi 30:

Cho moät xaâu ñôn coù phaàn töû ñaàu laø Head, moãi phaàn töû cuûa xaâu bao goàm:

Key : khoùa löu tröõ, kieåu int;

Next : con troû ñeán phaàn töû keá tieáp trong xaâu;

a. Haõy vieát moät haøm khoâng ñeä qui ñeám soá phaàn töû trong xaâu.

b. Haõy vieát moät haøm ñeä qui ñeám soá phaàn töû trong xaâu.