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 ppsx

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

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”}