Baøi taäp Toång hôïp CTDL 1 (Phaàn 2) 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:3

Thêm vào BST

Báo xấu

46
lượt xem 3
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 2) Nguyeãn Tri Tuaán – Khoa CNTT, ñaïi hoïc KHTN TP.HCM ---oOo--Baøi 13: Cho moät caây nhò phaân tìm kieám t coù caáu truùc nuùt laø BST_NODE ñöôïc khai baùo nhö sau: struct BST_NODE { int Key; // Khoaù cuûa nuùt int So_lan; // Soá laàn xuaát hieän cuûa khoaù trong caây struct BST_NODE *Left, *Right; } struct BST_TREE { struct BST_NODE *pRoot; // Nuùt goác cuûa caây } struct BST_TREE t; // Caây t a. Haõy vieát thuû tuïc/haøm thöïc hieän thao taùc xoaù phaàn töû coù khoaù X. Caùch xoaù nhö...

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 2) Nguyeãn Tri Tuaán – Khoa CNTT, ñaïi hoïc KHTN

Baøi taäp Toång hôïp CTDL 1 (Phaàn 2) Nguyeãn Tri Tuaán – Khoa CNTT, ñaïi hoïc KHTN TP.HCM ---oOo--- Baøi 13: Cho moät caây nhò phaân tìm kieám t coù caáu truùc nuùt laø BST_NODE ñöôïc khai baùo nhö sau: struct BST_NODE { // Khoaù cuûa nuùt int Key; // Soá laàn xuaát hieän cuûa khoaù trong caây int So_lan; struct BST_NODE *Left, *Right; } struct BST_TREE { // Nuùt goác cuûa caây struct BST_NODE *pRoot; } // Caây t struct BST_TREE t; a. Haõy vieát thuû tuïc/haøm thöïc hieän thao taùc xoaù phaàn töû coù khoaù X. Caùch xoaù nhö sau: • Neáu phaàn töû X coù toàn taïi, giaûm field So_lan cuûa noù 1 ñôn vò. • Neáu phaàn töû X khoâng toàn taïi, thoâng baùo. b. Haõy vieát 1 thuû tuïc/haøm in leân maøn hình giaù trò cuûa caùc phaàn töû ñang toàn taïi trong caây theo thöù töï NLR. Ghi chuù: moät phaàn töû ñöôïc goïi laø coù toàn taïi trong caây neáu So_lan > 0. Baøi 14: Cho thuaät toaùn nhö sau: for (i = 0; i < n-1; i++) { max = i + 1; for (j = i+1; j
while (IsEmpty(q) == 0) { DeQueue(q, y); printf(“%d “, y); } Haõy cho bieát keát quaû in ra maøn hình khi thi haønh ñoaïn chöông trình treân laø gì ? Baøi 16: a. Haõy neâu 1 öu ñieåm vaø 1 khuyeát ñieåm maø theo baïn laø tieâu bieåu nhaát cuûa phöông phaùp saép xeáp Quick-sort khi caøi ñaët baèng ñeä qui. b. Haõy neâu 1 ñieåm khaùc bieät cô baûn nhaát (theo baïn) cuûa caáu truùc Danh saùch lieân keát ñôn so vôùi caáu truùc Maûng ñoäng. Baøi 17: Xeùt thuaät toaùn tìm tuaàn töï moät soá nguyeân X cho tröôùc trong moät maûng a goàm 1000 soá nguyeân. Trong töøng tröoøng hôïp sau, haõy cho bieát soá phaàn töû toái ña coù theå ñöôïc duyeät trong quaù trình tìm kieám: a. Tröôøng hôïp 1: caùc phaàn töû cuûa maûng a chöa ñöôïc saép xeáp. b. Tröôøng hôïp 2: caùc phaàn töû cuûa maûng a ñöôïc saép xeáp taêng daàn. c. Tröôøng hôïp 3: caùc phaàn töû cuûa maûng a ñöôïc saép xeáp giaûm daàn. Baøi 18: Cho 2 xaâu lieân keát T1 vaø T2. Giaû thieát moãi phaàn töû cuûa chuùng chæ coù 2 thoâng tin : - Khoùa cuûa nuùt (laø soá nguyeân) - Con troû ñeán phaàn töû keá Vieát chöông trình taïo moät xaâu lieân keát T noái töø 2 xaâu T1 vaø T2 sao cho : - Caùc phaàn töû trong T coù giaù trò taêng - Khoâng coù tröôøng hôïp truøng nhau - Xaùc ñònh chi phí thuaät toaùn Baøi 19: Cho moät xaâu ñôn T, moãi nuùt cuûa noù chöùa caùc thoâng tin sau : Key : kieåu Integer Next : con troû chæ ñeán phaàn töû keá Vieát chöông trình C/Pascal taùch xaâu T thaønh 2 xaâu T1 vaø T2, trong ñoù T1 chöùa caùc phaàn töû coù khoùa > 0 vaø T2 chöùa caùc phaàn töû coù khoùa < 0. Ñaùnh giaù chi phí thuaät toaùn. Baøi 20: Cho moät caây nhò phaân tìm kieám, moãi phaàn töû cuûa caây laø moät soá nguyeân. Neáu aùp duïng phöông phaùp duyeät NLR ta coù keát quaû: 563792084 Neáu aùp duïng phöông phaùp duyeät LNR ta coù keát quaû: 724359610 Haõy veõ caây treân. Baøi 21: Nguyen Tri Tuan – Khoa CNTT ĐHKHTN Tp.HCM 2/3
Cho moät caây nhò phaân coù caùc phaàn töû sau (moãi phaàn töû xuaát hieän 1 laàn): 854013792 Neáu aùp duïng phöông phaùp duyeät NLR ñeå tính toång caùc nuùt laù, ta coù keát quaû baèng 22. Neáu aùp duïng phöông phaùp duyeät LNR ñeå tính toång caùc nuùt khoâng phaûi laø laù, ta coù keát quaû baèng 18. Haõy chæ ra caùc nuùt laù cuûa caây. Baøi 22: Cho moät caây nhò phaân coù caùc nuùt nhö sau: 874596312 Bieát toång caùc nuùt laù baèng 39. Haõy chæ ra caùc nuùt laù cuûa caây treân. Baøi 23: Cho moät caây nhò phaân coù caáu truùc nuùt laø NODE, haõy: a. Vieát thuû tuïc/haøm ñeå tính toång soá nuùt coù 1 nhaùnh con (con traùi HAY con phaûi) baèng caùch duøng thuaät toaùn duyeät goác giöõa NLR. b. Thieát laäp 1 coâng thöùc ñeä qui ñeå thöïc hieän yeâu caàu ôû caâu [a]. Caøi ñaët coâng thöùc naøy thaønh thuû tuïc/haøm. Baøi 24: Haõy neâu 2 öu ñieåm cuûa phöông phaùp saép xeáp Shaker sort so vôùi phöông phaùp saép xeáp Bubble sort. --- Heát phaàn 2 --- Nguyen Tri Tuan – Khoa CNTT ĐHKHTN Tp.HCM 3/3