Struktur data: soalan latihan dengan penerangan

1Apakah struktur data

Struktur data ialah cara menyusun data dalam memori supaya operasi tertentu menjadi pantas: mencari item, menambah satu, membuang satu.

Tiada struktur yang pantas dalam segala-galanya. Memilih satu bermakna memilih operasi mana yang patut murah. Kosnya ditulis dalam Big O, dengan n ialah bilangan item.

Dua blok binaan asas ialah tatasusunan dan senarai terpaut.

Tatasusunan menyimpan itemnya dalam satu blok memori, satu demi satu. Komputer boleh mengira di mana item i berada, maka membaca a[i] mengambil O(1). Menyisip di hadapan bermakna menganjakkan setiap item: O(n).

Senarai terpaut menyimpan setiap item dalam satu nod dengan penuding ke nod seterusnya. Penuding terakhir ialah null. Menyisip di kepala (h) hanya mengubah satu penuding: O(1). Tetapi untuk sampai ke item i anda mesti mengikut i penuding: O(n).

Senarai terpaut dua hala juga mempunyai penuding ke nod sebelumnya, maka anda boleh berjalan ke kedua-dua arah.

2Tindanan dan barisan gilir

Tindanan seperti longgokan pinggan: anda menambah dan membuang hanya di atas. Item yang masuk terakhir keluar dahulu: LIFO.

• push meletakkan item di atas, pop membuang item teratas, peek membaca item teratas tanpa membuangnya. Semuanya O(1).
• Kegunaan: fungsi buat asal (undo) dalam editor, tindanan panggilan sesebuah program, menyemak bahawa kurungan seimbang, carian kedalaman dahulu.

Barisan gilir seperti barisan di kaunter: anda menyertai di belakang dan keluar di hadapan. Item yang masuk pertama keluar dahulu: FIFO.

• enqueue menambah di belakang, dequeue membuang dari hadapan. Kedua-duanya O(1).
• Kegunaan: kerja cetakan, mesej yang menunggu untuk dikendalikan, carian keluasan dahulu.

Deque (barisan gilir dua hujung) membenarkan penambahan dan pembuangan di kedua-dua hujung. Barisan gilir keutamaan sentiasa membuang item dengan keutamaan tertinggi dahulu; ia biasanya dibina sebagai longgokan.

3Pokok, longgokan, jadual cincang dan graf

Pokok mempunyai satu nod teratas, iaitu akar. Setiap nod lain mempunyai tepat satu induk. Nod tanpa anak ialah daun. Pokok dengan n nod mempunyai n − 1 tepi.

Dalam pokok binari setiap nod mempunyai paling banyak dua anak. Pokok carian binari (BST) menambah satu peraturan: kunci dalam subpokok kiri lebih kecil daripada nod, kunci dalam subpokok kanan lebih besar.

Mencari dalam BST mengikut satu laluan ke bawah, maka kosnya O(ketinggian). Pokok seimbang (AVL, merah-hitam) mengekalkan ketinggian hampir log₂ n. Kunci yang disisip mengikut urutan terisih membentuk rantai berketinggian n.

Longgokan ialah pokok binari yang setiap induknya lebih kecil daripada anaknya (longgokan min) atau lebih besar (longgokan maks). Minimum atau maksimum berada di akar, dan sisip serta buang berkos O(log n).

Jadual cincang menyimpan pasangan kunci–nilai. Fungsi cincang menukar kunci kepada indeks, maka sisip dan carian mengambil O(1) secara purata. Dua kunci dengan indeks yang sama ialah perlanggaran, diselesaikan dengan perantaian (senarai bagi setiap slot) atau pengalamatan terbuka (cuba slot lain).

Graf mempunyai bucu yang disambung oleh tepi, yang mungkin mempunyai arah atau pemberat. Ia disimpan sebagai matriks kejiranan, memori O(V²), atau sebagai senarai kejiranan, O(V + E).

4Kaedah langkah demi langkah

Soalan sering menerangkan tugas dan bertanya struktur mana yang sesuai, atau bertanya bagaimana rupa sesuatu struktur selepas beberapa operasi.

1. Cari operasi yang mesti pantas: capaian mengikut kedudukan, mengikut kunci, item terbaharu, item paling lama, item terkecil, atau julat.
2. Padankan dengan struktur: indeks → tatasusunan, kunci → jadual cincang, terbaharu → tindanan, paling lama → barisan gilir, terkecil atau terbesar → longgokan, urutan terisih atau julat → pokok carian seimbang.
3. Semak kos operasi lain yang diperlukan tugas itu, dalam Big O.
4. Untuk soalan jejak, jalankan operasi satu demi satu dan tulis keadaan selepas setiap satu.
5. Semak keadaan akhir dengan peraturan struktur: LIFO, FIFO, susunan BST atau susunan longgokan.

5Contoh terselesai

Ikuti setiap langkah. Cuba ramalkan langkah seterusnya sebelum anda membukanya.

6Kesilapan lazim

• Mengelirukan LIFO dengan FIFO. Tindanan memulangkan item terbaharu, barisan gilir item paling lama.
• Menyangka senarai terpaut memberi capaian pantas mengikut indeks. Ia mesti berjalan dari kepala.
• Menganggap BST sentiasa O(log n). Hanya pokok seimbang yang begitu; sisipan terisih memberi O(n).
• Terlupa perlanggaran dalam jadual cincang. O(1) ialah purata, bukan kes terburuk.
• Mengelirukan traversal. Tertib-awal: nod dahulu. Tertib-dalam: nod di tengah. Tertib-akhir: nod terakhir.
• Menggunakan matriks kejiranan untuk graf besar yang jarang. Ia membazirkan memori O(V²).

7Rupa soalan peperiksaan

• Mudah: istilah dan fakta utama. LIFO dan FIFO, apakah nod, akar atau daun, peraturan BST, apa yang dilakukan oleh fungsi cincang.
• Sederhana: menerapkan konsep. Struktur mana yang sesuai untuk sesuatu tugas, hasil push dan pop atau sisipan BST, traversal pokok, jadual cincang dengan penyelakan linear, kos dalam Big O.
• Sukar: kes dan analisis. Pokok seimbang, longgokan dalam tatasusunan, pokok-B, trie, union-find, penapis Bloom dan reka bentuk seperti cache LRU.

Bagi longgokan yang disimpan dalam tatasusunan dari indeks 0, anak bagi indeks i berada pada 2i + 1 dan 2i + 2, dan induknya berada pada ⌊(i − 1) / 2⌋.