• Tiada Hasil Ditemukan

UNIVERSITI S A I N S MALAYSIA

N/A
N/A
Protected

Academic year: 2022

Share "UNIVERSITI S A I N S MALAYSIA "

Copied!
6
0
0

Tekspenuh

(1)

UNIVERSITI S A I N S MALAYSIA

Peperiksaan Kursus Semasa Cuti Panjang Sidang Akademik 2004/2005

Mei 2005

CPT201- Reka Bentuk & Analisis Algoritma

Masa : 2 jam

ARAEIAN KEPADA CALON:

Sila pastikan bahawa kertas peperiksaan ini mengandungi

LIMA

soalan di dalam ENAM muka swat yang bercetak sebelum anda mmulakan peperiksaan ini.

Jawab mana-mana EMPAT (4) soalan.

...

2/-

(2)

50

25

-

1

- 2 -

/

Y I 5

5 10 15 29

1. (a) Labelkan lengkung 1 hingga 6 di bawah dengan fungsi perkembangan yang bersesuaian:

Nilai h g s i kadar Perkm bangan

1 2 3

I r n l

i i

i 4

7 4

I i i i i t

/ /

/

/ 6

(20/100) (b) Mengapakah kita perlu berhati-hati dalam kes-kes berikut?

(i) Kita tidak seharusnya menganalisis masa perlaksanaan sesuatu penyelesaian berdasarkan pelaksanaan tertentu.

(ii) Apabila sesuatu masalah itu kecil, janganlah kita membuang banyak masa menganalisis masalah berkenaan.

(iii) Apabila membandingkan kecekapan beberapa penyelesaian, pertimbangkan perbezaan yang signifikan sahaja.

(20/100)

(c) Berikut diberikan algontma quicksort (isihan cepat) dan mergesort (isihan cantum):

quicksort (inout theArray:ItemArray, in first:integer, if (first < last)

t partition (theArray) //Pemetakan

-

Sediakan tatasusunan in 1ast:integer)

/ / theArray untuk panggilan rekursi

quicksort(S1 region of theArray) / / Rantau S1 theArray quicksort(S2 region of theArray) / / Rantau S2 theArray 1

mergesort(inout theArray:ItemArray, in first:integer, in 1ast:integer)

if (first < last)

I mergesort(Left half of thearray) / / Setengah kiri theArray mergesort(Right half of theArray)// Setengah kanan theArray merge(TheArray1 //Pencantman

-

Bersihkan tatasusunan

/ / selepas panggilan rekursi.

1

...

31-

(3)

[CPT201]

- 3 -

(i) Banding dan bezakan dari segi strategi dan kecekapan algoritma-algoritma di atas.

(ii) Apa yang terjadi jika panggilan p a r t i t i o n dihapuskan dari q u i c k s o r t danpanggilanmerge dihapuskan dari m e r g e s o r t ?

(601100)

2. (a) Satu cara untuk mengubahsuai algoritma isihan pepohon supaya algoritma berkenaan mengisih satu senarai ke dalam tertib menurun dan bukannya tertib menaik adalah dengan memasukkan output asal ke dalam sebuah tindanan.

(i) Surih algoritma isihan pepohon yang mengisih tatasusman 40 30 50 20 ke dalam tertib menurun seperti yang dicadangkan di atas.

(ii) Apakah kecekapan kaedah ini setelah pengubahsuaian tersebut dilakukan?

(201100) (b) (i) Senaraikan pengendalian-pengendalian yang menakrif ADT jadual

bersama-sama dengan huraian ringkas bagi setiap pengendalian.

(ii) Pengendalian ADT jadual yang manakah boleh digunakan untuk memaparkan semua butir data dalam jadual? Huraikan bagaimana anda menggunakan pengendalian berkenaan untuk menjalankan tugas tersebut.

(3011 00) (c) Surihkan H e a p I n s e r t (penyisipan ke dalam timbunan seperti yang diberikan

dalam kuliah) jika data asal adalah:

(i) 1 2 3 4 5 (ii) 1 1 1 1 1 (iii) 5 4 3 1 2 (iv) 5 4 3 2 1 (v) 2 2 2 2 2

Hur&an prestasi setiap kes di atas.

(50/ 1 00)

...

41-

(4)

- 4 -

3. (a) (i) Secara ringkas, huraikan konsep pepohon AVL.

(ii) Mengapakah kecekapan gelintaran pepohon AVL hampir secekap pepohon gelintaran perduaan dengan tinggi minimum?

(iii) Adakah pepohon di bawah merupakan sebuah pepohon AVL? Jika ya, beri sebab-sebabnya dan beri contoh satu pengendalian yang menyebabkan pepohon berkenaan menjadi bukan lagi sebuah pepohon AVL. Jika tidak, tunjuk bagaimana an& perlu melakukan putaran-putaran berkenaan supaya pepohon ini menjadi sebuah pepohon AVL.

(55/100) (b) Berikut diberikan pseudokod untuk penyisipan nod ke dalam jadual cincangan menggunakan perantaian berasingan. Penyisipan dilakukan di depan senarai berpaut yang berkenaan.

TableInsert (newItem, Success)

SearchKey = Kunci gelintaran NewItem I = HashIndex (SearchKey)

P = Penuding kepada sebuah nod baru

Setkan Success mengikut sama ada peruntukan ingatan if (Success)

I p

+

item = NewItem

berkenaan berjaya atau tidak

p

+

Next = T[I]

T[Il = p

1 / / end if

(i) Apakah kecekapan pengendalian di atas?

(ii) Ubahsuai pseudokod di atas supaya penyisipan dilakukan di hujung senarai berpaut berkenaan.

(iii) Apakah pula kecekapan pengendalian ini setelah diubahsuai dalam 3(b)(ii) di atas?

(45/100)

(5)

- 5 -

[CPT201]

4. (a) (i) Apakah pepohan rentang minimum?

Berikan

satu contoh aplikasi praktikal pepohon rentang minimum.

(ii) Tanpa menulis sebarang kod, huraikan dengan menggunakan perkataan anda sendiri algoritma Prim untuk mendapatkan pepohon rentang minimum.

(iii) Lakukan algoritma Prim untuk mendapatkan pepohon rentang minimum bermula dari bucu 0 ke atas graf di bawah:

(5511 00) (b) (i) Huraikan maksud istilah-istilah berikut dalam konteks kaedah luaran:

rekod data, blok, capaian blok, penimbal.

(ii) Mengapakah bilangan capaian blok perlu dikurangkan dalam pengendalian ke atas fail luaran?

(iii) Tulis fungsi (pseudokod) yang akan membaca blok-blok sebuah fail luaran secara berjujukan dan bagi setiap blok hanya rekod data terakhir sahaja diproses (dilawati) dan keseluruhan blok ditulis semula ke dalam fail berkenaan selepas pengemaskinian tersebut.

(4511 00)

5. (a) (i) Huraikan kaedah penyuaian pertama dan kaedah penyuaian terbaik.

(ii) Simulasikan kedua-dua kaedah di atas ke atas timbunan yang mempunyai empat blok bebas dalam turutan berikut yang bersaiz 25 bait, 50 bait, 30 bait dan 70 bait, dan pengendalian yang dilakukan ialah peruntukan 20 bait, diikuti p m t u k a n 45 bait, dan seterusnya peruntukan 60 bait.

(4011 00)

(b) Tanpa menulis sebarang kod huraikan dengan menggunakan ilustrasi bergrafik keadaan sebelum dan selepas pencantuman dalam algoritma CoalesceLeft (Pencantuman sebuah blok dengan jiran kirinya untuk membentuk blok yang lebih besar).

(201100)

. .

.61-

(6)

- 6 -

Algoritma beriht mencari satu subrentetan di dalam satu rentetan yang diberikan:

i n t Find (const S t r i n g & s o u r c e , c o n s t S t r i n g & t a r g e t )

I

i f ( s o u r c e o r t a r g e t i s empty)

i n t c u r r e n t = 0; / / p o s s i b l e l o c a t i o n i n t h i s w h i l e (complete match n o t found

r e t u r n -1; / / no match p o s s i b l e

& & any c h a r a c t e r s l e f t i n s o u r c e ) i f ( c u r r e n t c h a r a c t e r i n s o u r c e ! = f i r s t t a r g e t c h a r a c t e r )

e l s e {do / / found a p a r t i a l match

c u r r e n t + + ;

S t e p through s o u r c e and t a r g e t t o g e t h e r

w h i l e ( c h a r s l e f t t o compare & & s t i l l have a match);

i f (no more t a r g e t c h a r a c t e r s t o i n s p e c t ) else c u r r e n t + + ; / / k e e p l o o k i n g

return c u r r e n t ; / / found a f u l l match.

1

return -1; / / no match found 1

(i) Huraikan dengan menggunakan perkataan sendiri algoritma di atas.

(ii) Ubahsuai algoritma ini supaya semua kejadian berkenaan dilokasikan dan semua kedudukan tempat kejadian berkenaan dijumpai diletakkan di dalam sebuah tindanan. Gmakan ADT tindanan.

(iii) Apakah hasil yang dijangkakan jika kandungan tindanan berkenaan (404 00) dioutputkan?

-0000000

-

Rujukan

DOKUMEN BERKAITAN

2' (a) Satu cara untuk mengubahsuai algoritma isihan pepohon supaya algoritna berkenaan mengisih satu senarai ke dalam tertib menurun aa Ur*annya tertib menaik

The data that needs to be captured for each panel clinic are clinic name, owner of the clinic, IC number of the owner, clinic code, clinic address, whether operating

(a) Satu cara untuk mengubahsuai algoritma isihan pepohon supaya algoritma berkenaan mengisih satu senarai ke dalam tertib menurun dan bukannya tertib

(9125) (c) Dengan memberikan dasan-alasan yang sesuai ke atas jawapan anda (berdasarkan jenis sistem yang dibangunkan), cadangkan model proses perisian generik yang paling

Bahasa yang terdiri daripada semua rentetan ke atas abjad merupakan ungkapan aritmetik yang betul dari segi sintaksis ke atas integer yang melibatkm pengoperasi aritmetik

(iii) Satu lata dari sistem tertib pertama dan kedua yang dihasilkan dalam bentuk terus II.. A cascade of first- and second-order systems realized in Direct

(iii) Berapakah garisan parutan yang diperlukan untuk membezaielaskan doublet natrium di dalam tertib ke-3.

(ii) Surih algoritma isihan pepohon yang mengisih tatasusunan 40 30 50 Z0 60 70 ke dalam tertib menurun seperti yang anda cadangkan dalam 2(aXi) di atas..