Asas Sains Komputer questionssoalan, bab 3

NameNamaClassKelasDateTarikh

Algoritma

34 marksmarkah. Guna mod Latihan untuk menyemak setiap jawapan, atau mod Peperiksaan untuk menjawab semua soalan dahulu. Sediakan kertas kosong dan pensel untuk menulis jejak (trace) dan senarai selepas setiap lelaran.

Bahagian A: soalan objektif

11 marksmarkah

Jawab semua soalan. Pilih satu jawapan yang betul bagi setiap soalan.

QuestionSoalan 1

Apakah maksud search?

Proses menyusun item dalam senarai mengikut urutan tertentu
Proses untuk mendapatkan suatu item tertentu yang terkandung dalam satu senarai
Proses memisahkan item ke dalam beberapa baldi
Proses menukar kedudukan dua item yang bersebelahan

Show answerTunjuk jawapanHide answerSembunyi jawapan

Search ialah proses mendapatkan suatu item tertentu dalam satu senarai (ms. 62). A ialah sort, C ialah bucket sort dan D ialah langkah dalam bubble sort.

For the teacherUntuk guru: RememberingMengingat, lowrendah difficultyaras lowrendah, standard 3.1.1

TextbookBuku teks p.ms. 62

QuestionSoalan 2

Binary search hanya boleh dilakukan jika item dalam senarai

telah diisih dalam urutan menaik
kurang daripada sepuluh item
belum diisih
mempunyai nilai yang sama

Show answerTunjuk jawapanHide answerSembunyi jawapan

Sebelum binary search, item dalam senarai perlu diisih dalam urutan menaik supaya separuh senarai boleh diabaikan dengan selamat (ms. 65).

For the teacherUntuk guru: RememberingMengingat, lowrendah difficultyaras lowrendah, standard 3.1.1

TextbookBuku teks p.ms. 65

QuestionSoalan 3

Pasangan teknik yang manakah sesuai digunakan untuk senarai yang mempunyai item yang sedikit?

Binary search dan bucket sort
Binary search dan bubble sort
Linear search dan bubble sort
Linear search dan bucket sort

Show answerTunjuk jawapanHide answerSembunyi jawapan

Linear search dan bubble sort sesuai untuk senarai yang sedikit item. Binary search dan bucket sort sesuai untuk senarai yang banyak item (Rajah 3.1, ms. 72).

For the teacherUntuk guru: RememberingMengingat, lowrendah difficultyaras lowrendah, standard 3.1.1

TextbookBuku teks p.ms. 72

QuestionSoalan 4

Dalam bubble sort untuk urutan menaik, dua item bersebelahan bertukar tempat apabila

item pertama lebih kecil daripada item kedua
item pertama sama dengan item kedua
item kedua ialah item yang terakhir
item pertama lebih besar daripada item kedua

Show answerTunjuk jawapanHide answerSembunyi jawapan

Untuk urutan menaik, item pertama bertukar dengan item kedua jika item pertama lebih besar (ms. 69). Jika dua item sama, tiada pertukaran.

For the teacherUntuk guru: UnderstandingMemahami, lowrendah difficultyaras lowrendah, standard 3.1.1

TextbookBuku teks p.ms. 69

QuestionSoalan 5

Antara berikut, yang manakah menerangkan bucket sort dengan betul?

Item carian dibandingkan dengan item tengah dan separuh senarai diabaikan
Item dimasukkan ke dalam baldi mengikut julat, item dalam setiap baldi diisih, kemudian dicantumkan semula
Setiap item disemak satu demi satu bermula dengan item pertama
Dua item bersebelahan dibandingkan dan ditukar berulang kali

Show answerTunjuk jawapanHide answerSembunyi jawapan

Bucket sort mengisih item mengikut kategori (julat baldi), mengisih item dalam setiap baldi, kemudian mencantumkannya semula (ms. 86). A ialah binary search, C ialah linear search dan D ialah bubble sort.

For the teacherUntuk guru: UnderstandingMemahami, lowrendah difficultyaras lowrendah, standard 3.1.3

TextbookBuku teks p.ms. 86

QuestionSoalan 6

Rajah 1 menunjukkan keadaan senarai semasa binary search. Item di indeks 0 hingga 3 telah diabaikan. i = 4 dan j = 6. Apakah item pertengahan yang seterusnya dibandingkan?

Senarai 5, 10, 15, 20, 25, 30, 35 dengan indeks 0 hingga 3 berwarna kelabu; i menunjuk indeks 4 dan j menunjuk indeks 6 — Rajah 1

Show answerTunjuk jawapanHide answerSembunyi jawapan

m = (4 + 6) / 2 = 5. Item pada indeks 5 ialah 30.

For the teacherUntuk guru: ApplyingMengaplikasi, lowrendah difficultyaras lowrendah, standard 3.1.2

TextbookBuku teks p.ms. 66

QuestionSoalan 7

Linear search digunakan untuk mencari nombor 40 dalam senarai 14, 7, 31, 22, 9, 40, 18. Berapakah bilangan semakan sehingga 40 dijumpai?

Show answerTunjuk jawapanHide answerSembunyi jawapan

Item disemak satu demi satu: 14, 7, 31, 22, 9, 40. Nombor 40 berada pada indeks 5, iaitu semakan ke-6.

For the teacherUntuk guru: ApplyingMengaplikasi, mediumsederhana difficultyaras mediumsederhana, standard 3.1.2

TextbookBuku teks p.ms. 73

QuestionSoalan 8

Senarai 9, 4, 7, 2, 6 diisih dalam urutan menaik dengan bubble sort. Apakah senarai selepas lelaran pertama?

4, 7, 9, 2, 6
2, 4, 6, 7, 9
4, 2, 6, 7, 9
4, 7, 2, 6, 9

Show answerTunjuk jawapanHide answerSembunyi jawapan

Lelaran 1: 9 > 4 tukar (4, 9, 7, 2, 6); 9 > 7 tukar (4, 7, 9, 2, 6); 9 > 2 tukar (4, 7, 2, 9, 6); 9 > 6 tukar (4, 7, 2, 6, 9). Item terbesar, 9, berada di hujung. C ialah senarai selepas lelaran 2 dan B ialah senarai akhir.

For the teacherUntuk guru: ApplyingMengaplikasi, mediumsederhana difficultyaras mediumsederhana, standard 3.1.3

TextbookBuku teks p.ms. 83

QuestionSoalan 9

Senarai 3, 8, 12, 17, 21, 26, 30, 35, 41, 47, 52 mempunyai 11 item (indeks 0 hingga 10). Binary search digunakan untuk mencari 41. Apakah item pertengahan yang disemak, mengikut urutan?

17 dan 41
26 dan 35
26 dan 41
30 dan 41

Show answerTunjuk jawapanHide answerSembunyi jawapan

i = 0, j = 10: m = 5, item 26. 41 > 26, maka i = 6. m = (6 + 10) / 2 = 8, item 41. Dijumpai.

For the teacherUntuk guru: ApplyingMengaplikasi, mediumsederhana difficultyaras mediumsederhana, standard 3.1.2

TextbookBuku teks p.ms. 79

QuestionSoalan 10

Pseudokod bubble sort berikut menggunakan senarai L dengan n item. Baris 7.2 ditulis for j < n - i dan bukan for j < n - i - 1.

7 for i < n - 1
  7.1 Setkan j = 0
  7.2 for j < n - i
      7.2.1 Jika L[j] > L[j + 1]
            ... (pertukaran dengan temp)

Apakah akibatnya?

Senarai diisih dalam urutan menurun
Pada lelaran pertama, L[j + 1] merujuk item di luar senarai, maka ralat berlaku
Bubble sort berjalan dengan lebih pantas
Tiada perbezaan kerana n - i sama dengan n - i - 1

Show answerTunjuk jawapanHide answerSembunyi jawapan

Pada i = 0, j sampai n - 1, jadi L[j + 1] ialah L[n]. Senarai hanya ada indeks 0 hingga n - 1, maka L[n] tidak wujud (di luar julat). Gelung dalam mesti j < n - i - 1 supaya setiap pasangan bersebelahan wujud.

For the teacherUntuk guru: AnalysingMenganalisis, hightinggi difficultyaras hightinggi, standard 3.1.4

TextbookBuku teks p.ms. 83

QuestionSoalan 11

Sebuah klinik mempunyai 1 000 rekod pesakit yang belum diisih mengikut nombor kad pengenalan. Pembantu klinik perlu mencari banyak rekod dengan cepat. Gabungan teknik yang paling sesuai ialah

bucket sort, kemudian binary search
bubble sort, kemudian linear search
linear search, kemudian binary search
binary search, kemudian bubble sort

Show answerTunjuk jawapanHide answerSembunyi jawapan

Senarai mempunyai banyak item, maka bucket sort sesuai untuk mengisihnya dahulu. Selepas diisih, binary search sesuai untuk mencari dengan cepat dalam senarai yang banyak item (ms. 72, 102). Binary search tidak boleh dilakukan sebelum senarai diisih.

For the teacherUntuk guru: EvaluatingMenilai, hightinggi difficultyaras hightinggi, standard 3.1.6

TextbookBuku teks p.ms. 102

Bahagian B: soalan berstruktur

23 marksmarkah

Jawab semua soalan. Tunjukkan langkah kerja anda.

QuestionSoalan 12

Senarai yang telah diisih menaik: 4, 9, 15, 22, 28, 34, 41, 50, 57 (indeks 0 hingga 8). Binary search digunakan untuk mencari nombor 50. Pada mulanya i = 0 dan j = 8.

[2 marksmarkah] (a)Kira nilai m pada ulangan pertama dan nyatakan L[m]. Kemudian nyatakan nilai baharu bagi i atau j selepas membandingkan 50 dengan L[m].

You mark this one: open Show answerAnda tanda sendiri: buka Tunjuk jawapan

Show answerTunjuk jawapanHide answerSembunyi jawapan

m = 4, L[m] = 28; i = 5

m = (0 + 8) / 2 = 4; L[4] = 28 [1 mark]1
50 > 28, maka bahagian kiri diabaikan: i = m + 1 = 5 [1 mark]1

Tick each point you got.Tandakan setiap isi yang betul.

[1 markmarkah] (b)Berapakah bilangan ulangan sehingga 50 dijumpai?

Auto-checked: type a short answerSemakan automatik: taip jawapan pendek

Show answerTunjuk jawapanHide answerSembunyi jawapan

3 ulangan

3 ulangan. Ulangan 1: m = 4 (28). Ulangan 2: i = 5, j = 8, m = 6 (41), 50 > 41, i = 7. Ulangan 3: i = 7, j = 8, m = 7 (50), jumpa1

Tick each point you got.Tandakan setiap isi yang betul.

For the teacherUntuk guru: ApplyingMengaplikasi, mediumsederhana difficultyaras mediumsederhana, standard 3.1.2

TextbookBuku teks p.ms. 79

QuestionSoalan 13

Senarai 8, 3, 6, 1, 5 diisih dalam urutan menaik dengan bubble sort menggunakan pseudokod Rajah 3.10 (for i < n - 1 dan for j < n - i - 1).

[3 marksmarkah] (a)Tulis senarai selepas lelaran 1, lelaran 2 dan lelaran 3.

You mark this one: open Show answerAnda tanda sendiri: buka Tunjuk jawapan

Show answerTunjuk jawapanHide answerSembunyi jawapan

Lelaran 1: 3, 6, 1, 5, 8. Lelaran 2: 3, 1, 5, 6, 8. Lelaran 3: 1, 3, 5, 6, 8.

Lelaran 1: 3, 6, 1, 5, 8 (8 > 3, 8 > 6, 8 > 1, 8 > 5: semua tukar) [1 mark]1
Lelaran 2: 3, 1, 5, 6, 8 (3 > 6 tidak; 6 > 1 tukar; 6 > 5 tukar) [1 mark]1
Lelaran 3: 1, 3, 5, 6, 8 (3 > 1 tukar; 3 > 5 tidak) [1 mark]1

Tick each point you got.Tandakan setiap isi yang betul.

[1 markmarkah] (b)Berapakah jumlah perbandingan yang dibuat oleh pseudokod ini bagi 5 item?

Auto-checked: type a short answerSemakan automatik: taip jawapan pendek

Show answerTunjuk jawapanHide answerSembunyi jawapan

4 + 3 + 2 + 1 = 10 perbandingan (n(n - 1)/2 = 5 x 4 / 2)1

Tick each point you got.Tandakan setiap isi yang betul.

For the teacherUntuk guru: ApplyingMengaplikasi, lowrendah difficultyaras lowrendah, standard 3.1.3

TextbookBuku teks p.ms. 83

QuestionSoalan 14

Kamil menulis bahagian pertukaran dalam pseudokod bubble sort menaik seperti berikut.

7.2.1 Jika L[j] > L[j + 1]
      7.2.1.1 L[j] = L[j + 1]
      7.2.1.2 temp = L[j]
      7.2.1.3 L[j + 1] = temp
7.2.2 Tamat jika

[2 marksmarkah] (a)Nyatakan ralat dalam tiga baris pertukaran itu dan tulis tiga baris yang betul.

You mark this one: open Show answerAnda tanda sendiri: buka Tunjuk jawapan

Show answerTunjuk jawapanHide answerSembunyi jawapan

L[j] ditimpa sebelum disimpan dalam temp. Betul: temp = L[j], L[j] = L[j + 1], L[j + 1] = temp.

Urutan salah: L[j] diganti dengan L[j + 1] sebelum nilai asal L[j] disimpan dalam temp, jadi nilai asal L[j] hilang [1 mark]1
Betul: temp = L[j]; L[j] = L[j + 1]; L[j + 1] = temp [1 mark]1

Tick each point you got.Tandakan setiap isi yang betul.

[1 markmarkah] (b)Tulis senarai yang dihasilkan jika Kamil mengisih senarai 5, 2, 8 dengan pseudokod yang salah itu.

Auto-checked: type a short answerSemakan automatik: taip jawapan pendek

Show answerTunjuk jawapanHide answerSembunyi jawapan

2, 2, 8

2, 2, 8. Lelaran 1, j = 0: 5 > 2, L[0] = 2, temp = 2, L[1] = 2. Nilai 5 hilang1

Tick each point you got.Tandakan setiap isi yang betul.

For the teacherUntuk guru: AnalysingMenganalisis, mediumsederhana difficultyaras mediumsederhana, standard 3.1.4

TextbookBuku teks p.ms. 97

QuestionSoalan 15

Rajah 2 menunjukkan carta alir linear search bagi senarai L yang mempunyai 5 item. Carta alir ini mempunyai tiga bahagian yang tertinggal, P, Q dan R.

Rajah 2

[3 marksmarkah] Tulis nilai atau ungkapan bagi P, Q dan R.

You mark this one: open Show answerAnda tanda sendiri: buka Tunjuk jawapan

Show answerTunjuk jawapanHide answerSembunyi jawapan

P = 0, Q = T, R = i + 1

P = 0 (indeks item pertama) [1 mark]1
Q = T (nilai carian) [1 mark]1
R = i + 1 (indeks bertambah 1 untuk menyemak item seterusnya) [1 mark]1

Tick each point you got.Tandakan setiap isi yang betul.

For the teacherUntuk guru: UnderstandingMemahami, lowrendah difficultyaras lowrendah, standard 3.1.2

TextbookBuku teks p.ms. 75

QuestionSoalan 16

Markah 10 orang murid ialah 47, 12, 85, 33, 91, 5, 68, 29, 54, 76. Markah ini diisih menaik dengan bucket sort menggunakan 4 baldi: Baldi 1 (0 hingga 24), Baldi 2 (25 hingga 49), Baldi 3 (50 hingga 74) dan Baldi 4 (75 hingga 100). Item dalam setiap baldi diisih menaik.

[2 marksmarkah] (a)Tulis item dalam setiap baldi selepas diisih.

You mark this one: open Show answerAnda tanda sendiri: buka Tunjuk jawapan

Show answerTunjuk jawapanHide answerSembunyi jawapan

Baldi 1: 5, 12. Baldi 2: 29, 33, 47. Baldi 3: 54, 68. Baldi 4: 76, 85, 91.

Baldi 1: 5, 12; Baldi 2: 29, 33, 47 [1 mark]1
Baldi 3: 54, 68; Baldi 4: 76, 85, 91 [1 mark]1

Tick each point you got.Tandakan setiap isi yang betul.

[1 markmarkah] (b)Tulis senarai akhir selepas baldi dicantumkan.

Auto-checked: type a short answerSemakan automatik: taip jawapan pendek

Show answerTunjuk jawapanHide answerSembunyi jawapan

5, 12, 29, 33, 47, 54, 68, 76, 85, 91

5, 12, 29, 33, 47, 54, 68, 76, 85, 911

Tick each point you got.Tandakan setiap isi yang betul.

For the teacherUntuk guru: ApplyingMengaplikasi, lowrendah difficultyaras lowrendah, standard 3.1.3

TextbookBuku teks p.ms. 87

QuestionSoalan 17

Gunakan pengecaman corak untuk membandingkan linear search dengan binary search.

[3 marksmarkah] Nyatakan satu persamaan dan dua perbezaan.

You mark this one: open Show answerAnda tanda sendiri: buka Tunjuk jawapan

Show answerTunjuk jawapanHide answerSembunyi jawapan

Persamaan: kedua-duanya mencari item dalam senarai dan menggunakan gelung. Perbezaan: linear search menyemak satu demi satu dan tidak perlu diisih; binary search membandingkan dengan item tengah dan memerlukan senarai diisih menaik.

Persamaan (satu): kedua-duanya mencari item tertentu dalam senarai / menggunakan gelung / memerlukan satu nilai carian [1 mark]1
Perbezaan (mana-mana dua): linear search menyemak item satu demi satu, binary search membandingkan dengan item tengah dan mengabaikan separuh senarai; linear search tidak memerlukan senarai diisih, binary search memerlukan senarai diisih menaik; linear search sesuai untuk senarai yang sedikit item, binary search untuk senarai yang banyak item [2 marks]2

Tick each point you got.Tandakan setiap isi yang betul.

For the teacherUntuk guru: AnalysingMenganalisis, mediumsederhana difficultyaras mediumsederhana, standard 3.1.5

TextbookBuku teks p.ms. 101

QuestionSoalan 18

Sebuah kedai menyimpan 500 helai resit bernombor 1 hingga 900 yang bercampur-campur. Pemilik kedai perlu menyusun resit mengikut nombor menaik dahulu, kemudian mencari resit bernombor 633.

[2 marksmarkah] (a)Pilih satu teknik isihan dan satu teknik carian yang sesuai. Beri satu sebab bagi pilihan anda.

You mark this one: open Show answerAnda tanda sendiri: buka Tunjuk jawapan

Show answerTunjuk jawapanHide answerSembunyi jawapan

Bucket sort dan binary search, kerana senarai mempunyai banyak item dan binary search lebih pantas pada senarai yang sudah diisih.

Bucket sort untuk mengisih dan binary search untuk mencari [1 mark]1
Sebab: terdapat 500 item (banyak) dan selepas diisih, binary search tidak perlu menyemak setiap item [1 mark]1

Tick each point you got.Tandakan setiap isi yang betul.

[2 marksmarkah] (b)Tulis algoritma (dalam langkah-langkah ringkas) bagi gabungan teknik yang anda pilih.

You mark this one: open Show answerAnda tanda sendiri: buka Tunjuk jawapan

Show answerTunjuk jawapanHide answerSembunyi jawapan

1. Wujudkan baldi dan julat. 2. Masukkan resit ke dalam baldi. 3. Isih setiap baldi. 4. Cantum semula. 5. Binary search: bandingkan 633 dengan resit tengah, abaikan separuh, ulang sehingga dijumpai.

Isihan: wujudkan baldi dan tetapkan julat, masukkan setiap resit ke dalam baldi, isih resit dalam setiap baldi, cantumkan semula baldi mengikut urutan menaik [1 mark]1
Carian: lihat resit di tengah senarai, bandingkan 633 dengan nombor resit itu, abaikan separuh yang tidak mengandungi 633, ulang sehingga resit 633 dijumpai atau tiada lagi item [1 mark]1

Tick each point you got.Tandakan setiap isi yang betul.

For the teacherUntuk guru: CreatingMencipta, hightinggi difficultyaras hightinggi, standard 3.1.6

TextbookBuku teks p.ms. 102

Back to notesKembali ke nota Bab 4 questionssoalan Model papersKertas model