Kuis 3 - ASD - A

Semua algoritma pencarian memiliki tujuan akhir yang sama, yaitu menemukan elemen berdasarkan search key. Namun, perbedaan utama antar algoritma pencarian dapat dianalisis berdasarkan

• Waktu eksekusi program dalam kondisi nyata (runtime pada prosesor tertentu)

• Cara pengurutan elemen sebelum pencarian dilakukan

• Jumlah data yang bisa disimpan dalam array

• Besarnya kompleksitas waktu yang diukur menggunakan notasi Big O

Pernyataan manakah yang paling tepat menggambarkan makna dari kompleksitas waktu O(1) dalam analisis algoritma?

• Algoritma dengan O(1) hanya melakukan satu perbandingan pada setiap kasus input

• Kompleksitas O(1) berarti waktu eksekusi akan selalu nol pada ukuran input berapa pun

• O(1) menunjukkan bahwa jumlah operasi tidak bertambah seiring pertambahan ukuran input

• O(1) hanya berlaku jika seluruh data telah disortir sebelumnya

Sebuah algoritma memeriksa apakah elemen pertama dari array bernilai sama dengan salah satu elemen lainnya dalam array yang berisi n elemen. Berapa jumlah perbandingan maksimum (at most) yang diperlukan algoritma tersebut?

• n

• n - 1

• log n

• n / 2

Mengapa algoritma dengan kompleksitas O(n²) menjadi tidak praktis untuk digunakan pada dataset yang sangat besar, seperti array berisi satu miliar elemen?

• Karena kompleksitas O(n²) hanya berlaku untuk struktur data bertipe linked list

• Karena O(n²) berarti jumlah operasi tumbuh secara eksponensial terhadap ukuran input

• Karena jumlah operasi meningkat secara kuadratik, menyebabkan waktu eksekusi menjadi sangat besar seiring bertambahnya ukuran data

• Karena algoritma O(n²) selalu memerlukan sorting tambahan sebelum dieksekusi

Diberikan array berikut:

[10, 50, 30, 70, 80, 60, 20, 90, 40]

Jika algoritma Linear Search digunakan untuk mencari elemen 20, berapa banyak perbandingan yang dilakukan hingga elemen tersebut ditemukan?

• 5

• 6

• 7

• 8

Diberikan array:

A = {3, 8, 2, 15, 99, 52, 77, 31}, dan target pencarian: v = 77

Jika digunakan Linear Search, maka berapa banyak perbandingan yang dilakukan hingga elemen ditemukan dan berapa posisi indeks (i) yang dikembalikan?

• 5 perbandingan, posisi 4

• 7 perbandingan, posisi 6

• 8 perbandingan, posisi 7

• 9 perbandingan, posisi 8

Diberikan array awal: [5, 1, 4, 2, 8]

Jika algoritma Bubble Sort digunakan untuk mengurutkan array tersebut dalam urutan naik (ascending), maka berapa jumlah total pertukaran (swapping) yang terjadi hingga array benar-benar terurut?

• 4

• 5

• 6

• 7

Diberikan array berikut:

A = [5, 3, 2, 4]

Jika array tersebut diurutkan menggunakan algoritma Bubble Sort dalam urutan menaik (ascending), berapa jumlah total pertukaran (swap) yang dilakukan hingga array benar-benar terurut?

• 2

• 3

• 4

• 5

Algoritma Selection Sort dikenal mudah diimplementasikan namun kurang efisien untuk data berukuran besar. Hal ini disebabkan oleh ….

• Jumlah pertukaran (swap) dalam Selection Sort sangat tinggi dibanding Bubble Sort

• Selection Sort melakukan pertukaran pada setiap perbandingan yang dilakukan

• Selection Sort selalu memindahkan elemen terbesar ke awal array

• Selection Sort tetap melakukan n – 1 pencarian minimum meskipun array sudah terurut

Perhatikan potongan program C++ di atas. Salah satu baris program mengandung syntax error yang menyebabkan program tidak dapat dikompilasi. Baris manakah yang mengandung kesalahan, dan apa penyebabnya?

• if(arr[i]==key) – karena operator perbandingan seharusnya menggunakan satu tanda sama dengan

• int n = sizeof(arr)/sizeof(arr[0]); – karena sizeof tidak bisa digunakan pada array dalam fungsi main()

• (result==-1) ? cout<<"data tidak ditemukan" : cout<<"data ditemukan pada indeks ke-"<<result; – karena ternary operator tidak dapat digunakan langsung tanpa blok atau tanda kurung

• return i; – karena tidak boleh mengembalikan nilai dari dalam blok if pada loop