1.Mudah
Apakah algoritma?
- AJujukan langkah yang terhingga dan jelas ditakrifkan yang menyelesaikan masalah
- BStruktur data yang menyimpan nombor
- CMana-mana program komputer yang mempunyai antara muka grafik
- DBahasa pengaturcaraan yang direka untuk menulis formula matematik
2.Mudah
Satu gelung bermula dengan i = 1 dan menggandakan i pada setiap lelaran sehingga i > n. Berapa banyak lelaran yang dijalankannya?
- AKira-kira n
- BKira-kira log₂ n
- CKira-kira n²
- DKira-kira n / 2
3.Mudah
Apakah maksudnya jika sesuatu operasi berjalan dalam masa O(1)?
- AIa memproses tepat satu elemen bagi setiap saat masa larian
- BIa hanya boleh dijalankan sekali
- CMasa larinya tidak bertambah dengan saiz input
- DIa sentiasa mengambil tepat satu saat
4.Sederhana
Apakah penyelesaian hubungan jadi semula T(n) = T(n − 1) + O(n)?
- AO(2ⁿ)
- BO(n²)
- CO(n)
- DO(n log n)
5.Sederhana
Anda mengisih tatasusunan n elemen sekali dan kemudian menjawab k pertanyaan keahlian dengan carian binari. Apakah jumlah kosnya?
- AO(n log n + k log n)
- BO(k n log n)
- CO(n + k)
- DO(nk)
6.Sederhana
Carian pertama lebar pada graf tidak berpemberat mencari:
- ASusunan topologi dalam semua graf
- BLaluan terpendek dalam graf yang mengandungi pemberat sisi negatif
- CPokok rentang minimum
- DLaluan terpendek dari segi bilangan sisi dari nod permulaan
7.Sukar
Mengapakah carian binari tidak memberikan masa O(log n) pada senarai berpaut tunggal?
- ACarian binari memerlukan memori dua kali ganda
- BSampai ke elemen tengah mengambil O(n) langkah, kerana tiada akses indeks langsung
- CSenarai berpaut tidak boleh disusun
- DPerbandingan pada nod senarai berpaut lebih perlahan
8.Sukar
Masalah galas 0/1 yang diselesaikan dengan pengaturcaraan dinamik mengambil masa O(nW). Mengapakah ini dipanggil pseudo-polinomial?
- AKerana ia hanya berfungsi untuk W = 0
- BKerana algoritma itu dirawakkan dan masa larinya berbeza-beza bagi setiap input
- CKerana n sentiasa kecil
- DW ialah satu nombor, jadi masanya eksponen dalam bilangan bit yang digunakan untuk menulis W
Kunci jawapan
- 1. A · Jujukan langkah yang terhingga dan jelas ditakrifkan yang menyelesaikan masalah
- 2. B · Kira-kira log₂ n
- 3. C · Masa larinya tidak bertambah dengan saiz input
- 4. B · O(n²)
- 5. A · O(n log n + k log n)
- 6. D · Laluan terpendek dari segi bilangan sisi dari nod permulaan
- 7. B · Sampai ke elemen tengah mengambil O(n) langkah, kerana tiada akses indeks langsung
- 8. D · W ialah satu nombor, jadi masanya eksponen dalam bilangan bit yang digunakan untuk menulis W
Penyelesaian langkah demi langkah yang lengkap: berlatih topik ini di examproblems.com.