soal sistem berkas dan jawabannya

SOAL MIDTEST SISTEM BERKAS

1.      Berapkah jumlah probe diperlukan untuk mencari nama “Maiyana” (sesuai dengan urutan absen pada matakuliah sistem berkas) bila digunakan metode sekuensial ?

Jawab :

Berkas Sekuensial merupakan sekumpulan berkas di penyimpanan sekunder yang dapat diakses secara  berurutan mulai dari rekaman pertama sampai dengan rekaman yang terakhir. Dengan rumusannya :

“ Kunci1<Kunci2<Kunci3…..Kunci i<… Kunci n ”

Sehingga :

probe yang diperlukan untuk mencari nama “Maiyana” sesuai dengan urutan absen pada matakuliah sistem berkas adalah 8 (delapan) probe.

2.      Diketahui rekaman-rekaman dengan kunci 45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759 dan 859, berapa probe diperlukan untuk menemukan rekaman dengan kunci 75 daan 759 dengan menggunakan metode sekuensial, biner dan interpolasi ?

Jawab :

1.      Metode Pencarian Sekuensial

Key : 75

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

Diperlukan 5 langkah untuk menemukan rekaman dengan kunci 75

            Key : 759

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

45, 59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859

                       

Diperlukan 15 langkah untuk menemukan rekaman dengan kunci 75

2.      Metode Pencarian Biner

Kunci : 75

    1         2          3       4           5           6              7          8              9           9             11          12            13            14           15

  [59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859]

  [59, 71, 73, 75, 89, 102, 170], 197, 207, 302, 304, 345, 704, 759, 859

TENGAH1 =[ (1+15) / 2 ] = 8 →Kcari : K tengah1→ 75 < 197

AKHIR = TENGAH1 - 1 = 7

TENGAH2 =[ (1+7 ) / 2 ] = 4 →Kcari : K tengah2→ 75 = 75

→ Ketemu, Probe = 2

Kunci : 759

  1           2          3       4           5           6              7          8              9           9             11          12            13            14           15

 [59, 71, 73, 75, 89, 102, 170,  197, 207, 302, 304, 345, 704, 759, 859]

  59, 71, 73, 75, 89, 102, 170,  197,[207, 302, 304, 345, 704, 759, 859]

  59, 71, 73, 75, 89, 102, 170,  197,  207, 302, 304, 345, 704, 759, 859

TENGAH1 =[ (1 + 15) / 2 ] = 8 →Kcari : K tengah1→ 759 > 197

AWAL = TENGAH1 + 1 = 9

TENGAH2 =[ (9 + 15 ) / 2 ] = 12 →Kcari : K tengah2→ 759 > 345

AWAL = TENGAH1 + 1 = 13

TENGAH3 =[ (13 + 15 ) / 2 ] = 14 →Kcari : K tengah2→ 345 = 345

→ Ketemu, Probe = 3

3.      Metode Pencarian Interpolasi

Kunci 75

  1           2          3       4           5           6              7          8              9           9             11          12            13            14           15

 [59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859]

 [59, 71, 73, 75, 89, 102, 170], 197, 207, 302, 304, 345, 704, 759, 859

           

           

Perhitungan :

BERIKUT1 = [ 1+ (75 – 59) (15-1)] = 1.28 = 1

                                        (859-59)

Kcari : K berikut = 75 > 59 AWAL = BERIKUT1 + 1= 2

BERIKUT2 = [ 2 + (75 – 71) (15-2)] = 2.06 = 2

                                        (859- 71)

Kcari : K berikut = 75 > 71 AWAL = BERIKUT2 + 1= 3

BERIKUT3 = [ 3 + (75 – 73) (15-3)] = 3.03 = 3

                                        (859- 73)

Kcari : K berikut = 75 > 73 AWAL = BERIKUT3 +1= 4 → Kcari:K berikut = 75=75 (ketemu) Probe:3

Kunci 759

  1           2          3       4           5           6              7          8              9           9             11          12            13            14           15

 [59, 71, 73, 75, 89, 102, 170, 197, 207, 302, 304, 345, 704, 759, 859]

 [59, 71, 73, 75, 89, 102, 170], 197, 207, 302, 304, 345, 704, 759, 859

Perhitungan :

BERIKUT1 = [ 1+ (759 – 59) (15-1)] = 13.25 = 13

                                        (859-59)

Kcari : K berikut = 759  > 704 AWAL = BERIKUT1 + 1= 14

Kcari : K berikut = 759 = 759  ketemu, Probe 1

3.      Sisipkan rekaman dengan kunci 23, 25, 27, 34, 56, 33, 76, 45, 33, 22, 34, 89, 98, 99, 45, 31 dan 23, ke dalam berkas terkecil yang diperoleh dengan menghitung factor packing ≤ 87 persen dengan menggunakan fungsi hashing kunci modulus P dan resolusi Kolisi LISCH?

Jawab :

Factor Packing =   Jumlah rekaman yang disimpan

                             Jumlah total lokasi penyimanan

Key           : 23, 25, 27, 34, 56, 33, 76, 45, 33, 22, 34, 89, 98, 99, 45, 31, 23

 23 mod 13 = 1 sisa 10 → 1

 25 mod 13 = 2 sisa 12→ 1

 27 mod 13 = 2 sisa   1→ 1

 34 mod 13 = 3 sisa   8 → 2

 56 mod 13 = 5 sisa  4 → 2

 33 mod 13 = 3 sisa   7→ 1

 76 mod 13 = 6 sisa 11 →2

 45 mod 13 = 3 sisa 6 → 2

 33 mod 13 = 3 sisa 7 → 1

 22 mod 13 = 1 sisa 11 → 1

 34 mod 13 = 3 sisa 8 → 2

 89 mod 13 = 7 sisa 0 → 1

 98 mod 13 = 7 sisa 9 → 1

 99 mod 13 = 7 sisa 10 → 1

 45 mod 13 = 3 sisa 6 → 2

 31 mod 13 = 2 sisa 5 → 1

 23 mod 13 = 1 sisa 10 → 2

                                     24 (Probe)

Probe Rate =  åProbe    =             24           = 1,41

                 å Key                    17

Packing Factor =  å  key                =             17           = 1,30

                                     N                        13

4.      Berapa rata-rata jumlah probe diperlukan untuk membaca masing-masing rekaman yang disisipkan dalam soal no 3?

Jawab :

Jumlah probe yang diperlukan untuk membaca masing-masing rekaman adalah 24 (Dua Puluh Empat Probe)

5.      Sebutkan dan jelaskan metode-metode pencarian yang anda ketahui di dalam sistem berkas ?

Jawab :

3 metode pencarian dalam system berkas :

1.      Pencarian secara sekuensial : yaitu pencarian yang dilakukan dengan memproses rekaman dalam berkas sesuai urutan keberadaan rekaman-rekaman tersebut sampai ditemukan rekaman yang dimaksud

2.      Pencarian secara biner : yaitu membandingkan kunci yang dicari dengan rekaman pada posisi tengan dari berkas dengan cara :

-          Jika kunci Cari < kunci tengah maka bagian berkas dari kunci tengah sampai akhir berkas dieliminasi.

-          Jjika kunci cari > kunci tengah maka babgian berkas mulai dari depan sampai dengan kunci tengah dieliminasi

3.      Pencarian Interpolasi : yaitu dengan menentukan posisi yang akan diperbandingkan berikutnya berdasar posisi yang diestimasi dari sisa rekaman yang belum diperiksa.

Pengaksesan berkas digolongkan kepada dua yaitu :

1. Direct Access

Direct Access Adalah suatu cara pengaksesan record yang langsung, tanpa mengakses seluruh record yang ada.

Contoh : Magnetic Disk.

2. Sequential Access

Sequential access Adalah suatu cara pengaksesan record, yang didahului pengaksesan record-record di depannya.