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

Chia sẻ: Nguyễn Hữu Thiên Sơn | Ngày: | Loại File: PDF | Số trang:2

Thêm vào BST

Báo xấu

43
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 (pNULL) return (1 + fn(p-Next)); else...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

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 (pNULL) 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. Nguyen Tri Tuan – Khoa CNTT ĐHKHTN Tp.HCM 1/2
Baøi 31: Cho moät maûng a goàm n phaàn töû kieåu Integer. Ta coù theå saép xeáp maûng a baèng caùch : + Töø maûng a, taïo moät caây nhò phaân tìm kieám T. + Duyeät caây T vaø ñöa caùc nuùt trôû laïi maûng a. Yeâu caàu : a. Cho bieát phöông phaùp duyeät caây T ñeå ñöa caùc nuùt leân maûng sao cho maûng ñöôïc saép taêng daàn. b. Cho bieát caáu truùc caây T (khai baùo baèng C/PASCAL). c. Xaây döïng caùc thuû tuïc (baèng C/PASCAL): + Taïo caây nhò phaân T töø maûng a. + Thuû tuïc duyeät caây ñeå ñöa caùc phaàn töû trôû laïi maûng sao cho maûng ñöôïc saép taêng daàn. Baøi 32: Haõy caøi ñaët thuaät toaùn Quicksort khoâng duøng ñeä qui. Baøi 33: a. Haõy caøi ñaët thuaät toaùn duyeät caây nhò phaân (NLR) khoâng duøng ñeä qui (duøng stack) b. Haõy caøi ñaët thuaät toaùn duyeät caây nhò phaân theo möùc khoâng duøng ñeä qui (duøng queue) Baøi 34: haõy so saùnh (ngaén goïn) söï gioáng vaø khaùc nhau cuûa 2 caáu truùc Caây nhò phaân tìm kieám vaø Danh saùch lieân keát ñôn. Baøi 35: Cho moät danh saùch lieân keát ñôn. Cho bieát ñòa chæ P, Q taïi caùc vò trí nhö hình 1. Haõy vieát caùc leänh caàn thieát ñeå chuyeån danh saùch sang daïng bieåu dieãn ôû hình 2. Baøi 36: Cho moät caây nhò phaân tìm kieám vôùi goác laø Root, giaù trò löu tröõ taïi moãi nuùt laø moät soá nguyeân (int). Haõy vieát ñoaïn chöông trình tìm phaàn töû nhoû nhaát trong caây. --- Heát phaàn 3 --- Nguyen Tri Tuan – Khoa CNTT ĐHKHTN Tp.HCM 2/2