SPM KMK 2216: Struktur data: tatasusunan dan senarai

Domain Struktur data: tatasusunan dan senarai menguji cara menyimpan banyak nilai berkaitan di bawah satu nama, mengaksesnya dengan indeks, dan memprosesnya dengan gelung. Soalan biasanya berbentuk penjejakan: berapa nilai akhir pemboleh ubah selepas satu gelung melalui tatasusunan, atau di manakah sesuatu item dijumpai.

Tatasusunan (array)

• Saiz tetap semasa pengisytiharan, semua elemen jenis sama, disimpan dalam blok memori berturutan.
• Indeks bermula dari 0 dalam kebanyakan bahasa (nilai[0] hingga nilai[n-1]); sesetengah pseudocode bermula dari 1 - tentukan konvensyen yang digunakan oleh soalan.
• Tatasusunan 2D: grid[baris][lajur]; baris disebut dahulu, lajur kemudian.

Senarai (list)

Saiz boleh berubah semasa program berjalan. Operasi asas: tambah di hujung, sisip pada kedudukan, hapus, dan jelajah. Berbanding tatasusunan, senarai lebih fleksibel tetapi akses rawak lebih perlahan.

Operasi lazim

Jumlah, purata, maksimum/minimum, kiraan, carian linear, carian binari (hanya untuk data tersusun), dan isihan gelembung.

Contoh berperingkat

Diberi nilai = [4, 9, 2, 7], cari nilai 7.

cari = 7
jumpa = -1
for i = 0 to 3
    if nilai[i] = cari then
        jumpa = i
    endif
next i

• i=0: 4 ≠ 7, tidak berubah.
• i=1: 9 ≠ 7, tidak berubah.
• i=2: 2 ≠ 7, tidak berubah.
• i=3: 7 = 7 → jumpa = 3. Keputusan 3 ialah indeks, bukan nilai. Jika tiada padanan, jumpa kekal −1, nilai sentinel yang tidak boleh dikelirukan dengan indeks sah kerana indeks bermula dari 0.

Perangkap yang menghilangkan markah

• Indeks luar julat: gelung sehingga n dan bukan n-1.
• Mengelirukan nilai elemen dengan indeks elemen.
• Menjalankan carian binari pada senarai yang belum diisih.
• Meletakkan pengumpul di dalam gelung lalu menetapkannya semula kepada 0 setiap pusingan.
• Menghapuskan item senarai semasa sedang menjelajah, lalu indeks bergeser dan item tertinggal.
• Menukar urutan baris dan lajur bagi tatasusunan 2D.