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 potx

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

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ö 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<n; j++)

if (a[j] < a[max]) max = j;

if (a[max] < a[i]) {

Temp = a[max];

a[max] = a[i];

a[i] = Temp;

}

}

Haõy tính chi phí cho thuaät toaùn treân trong caùc tröôøng hôïp toát nhaát, xaáu nhaát, trung bình:

Baøi 15:

Cho moät haøng ñôïi q vaø 1 ñoaïn chöông trình nhö sau:

struct QUEUE q;

int x = 5, y = 3;

EnQueue(q, 8);

EnQueue(q, 9);

EnQueue(q, y);

DeQueue(q, x);

EnQueue(q, 18);

DeQueue(q, x);

EnQueue(q, 22);