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

51
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 1) Nguyeãn Tri Tuaán – Khoa CNTT, ñaïi hoïc KHTN TP.HCM ---oOo--Baøi 1: Cho moät caây nhò phaân coù goác laø Root, moãi nuùt chöùa moät soá nguyeân. a. Haõy vieát chöông trình tính trung bình coäng cuûa caùc nuùt trong caây. b. Haõy vieát chöông trình tính trung bình coäng cuûa caùc soá döông trong caây. c. Haõy vieát chöông trình tính trung bình coäng cuûa caùc soá aâm trong caây. d. Haõy vieát chöông trình tính tæ soá: R= a/b Vôùi a = toång soá caùc nuùt coù giaù trò ...

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

Baøi taäp Toång hôïp CTDL 1 (Phaàn 1) Nguyeãn Tri Tuaán – Khoa CNTT, ñaïi hoïc KHTN TP.HCM ---oOo--- Baøi 1: Cho moät caây nhò phaân coù goác laø Root, moãi nuùt chöùa moät soá nguyeân. a. Haõy vieát chöông trình tính trung bình coäng cuûa caùc nuùt trong caây. b. Haõy vieát chöông trình tính trung bình coäng cuûa caùc soá döông trong caây. c. Haõy vieát chöông trình tính trung bình coäng cuûa caùc soá aâm trong caây. d. Haõy vieát chöông trình tính tæ soá: R= a/b Vôùi a = toång soá caùc nuùt coù giaù trò > 0 b = toång soá caùc nuùt coù giaù trò < 0 Baøi 2: a. Haõy choïn caáu truùc döõ lieäu thích hôïp ñeå bieåu dieãn trong boä nhôù chính moät töø ñieån taàn soá goàm toái ña 1000 töø, moãi töø coù ñoä daøi 10 kyù töï, ñi keøm vôùi moãi töø laø soá laàn xuaát hieän cuûa töø ñoù (ñaõ ñöôïc thu thaäp töø moät soá vaên baûn naøo ñoù). Yeâu caàu : - thôøi gian truy caäp ñeán moät töø laø toái thieåu - Boä nhôù ñöôïc duøng laø toái thieåu b. Giaû söû caáu truùc döõ lieäu bieåu dieãn töø ñieån taàn soá (caâu a.) ñaõ ñöôïc ñònh nghóa vaø chöùa ñaày ñuû döõ lieäu. Vieát chöông trình C/Pascal lieät keâ ra 100 töø coù taàn soá lôùn nhaát. Baøi 3: Haõy tính chi phí cho caùc thuaät toaùn sau trong caùc tröôøng hôïp toát nhaát, xaáu nhaát, trung bình: a) for (i = 0; i < n; i++) if (a[i] == k) return 1; return 0; b) for (i = 0; i < n; i++) for (j = 0; j < n; j++) b[i][j] += c; c) for (i = 0; i < n; i++) for (j = i+1; j < n; j++) b[i][j] -= c; Baøi 4: a. Haõy vieát 1 ñoaïn chöông trình yeâu caàu ngöøôi duøng nhaäp vaøo 1 soá nguyeân N vaø tieán haønh caáp phaùt 1 maûng ñoäng chöùa N soá kieåu long. b. Cho moät caáu truùc DEMO goàm coù 3 field nhö sau: struct DEMO { int one; long two; char three[10]; } Haõy khai baùo 1 bieán con troû p vôùi kieåu DEMO; caáp phaùt boä nhôù cho con troû p; vaø gaùn vaøo caùc field cuûa p laàn löôït caùc giaù trò sau {1, 500000, “Hello”} Nguyen Tri Tuan – Khoa CNTT ĐHKHTN Tp.HCM 1/3
Baøi 5: Cho moät danh saùch lieân keát ñôn nhö sau: a. p1 = pHead->pNext; b. p3 = p1->pNext->pNext; c. p3->data = p1->data; d. pCurr = p1; while (pCurr != NULL) { pCurr->data *= 5; pCurr = pCurr->pNext; } ÖÙng vôùi moãi tröôøng hôïp [a] – [d], haõy veõ laïi danh saùch, theå hieän roõ söï thay ñoåi. Baøi 6: Cho moät ngaên xeáp s vaø 1 ñoaïn chöông trình nhö sau: struct STACK s; int x, y = 5; Push(s, 8); Push(s, y); Push(s, 9); Pop(s, x); Push(s, 18); Pop(s, x); Push(s, 22); while (IsEmpty(s) == 0) { Pop(s, x); 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 7: ta coù 100.000 töø tieáng Anh, moãi töø daøi khoâng quaù 10 kyù töï. Giaû söû maùy tính cuûa baïn coù 1MB boä nhôù coøn troáng. Haõy cho bieát caáu truùc döõ lieäu naøo coù theå duøng ñeå löu toaøn boä döõ lieäu noùi treân ? Lyù giaûi söï löïa choïn cuûa baïn (ngaén goïn). Khai baùo caáu truùc naøy baèng C/PASCAL. Baøi 8: Haõy veõ caây caân baèng neáu ta tieán haønh taïo caây vôùi döõ lieäu caùc nuùt theâm vaøo theo thöù töï sau (giaû söû caây ban ñaàu laø roãng): MNOFCGHUAE Baøi 9: Haõy aùp duïng thuaät toaùn hieäu chænh Heap ñeå hieäu chænh daõy sau thaønh 1 Heap (ghi roõ töøng böôùc): 5; 25; 15; 8; 7; 28; 1; 4; 10; 9 Nguyen Tri Tuan – Khoa CNTT ĐHKHTN Tp.HCM 2/3
Baøi 10: Cho moät caây nhö hình 1. Cho bieát tröôùc nuùt P. Haõy vieát caùc leänh caàn thieát ñeå chuyeån caây sang daïng bieåu dieãn ôû hình 2. Baøi 11: Cho moät caây nhò phaân tìm kieám nhö hình veõ. Haõy cho bieát thöù töï cuûa caùc phaàn töû khi theâm vaøo caây ra sao ñeå coù ñöôïc caáu truùc naøy ? (Giaû söû luùc ñaàu caây roãng) Neáu keát quaû pheùp duyeät caây treân laø: 3 7 9 5 12 20 18 15 10. Haõy cho bieát ngöôøi ta ñaõ aùp duïng pheùp duyeät naøo ? Baøi 12: Haõy vieát moät thuû tuïc/haøm taïo moät danh saùch lieân keát ñôn töø caây treân sao cho giaù trò caùc phaàn töû trong danh saùch coù thöù töï giaûm daàn. Bieát goác cuûa caây laø ROOT. --- Heát phaàn 1 --- Nguyen Tri Tuan – Khoa CNTT ĐHKHTN Tp.HCM 3/3