Lembaran kerja Struktur data dengan jawapan

Lembaran kerja Struktur data percuma untuk dicetak: 8 soalan dari mudah hingga tahap peperiksaan, dengan skema jawapan. Cetak atau simpan sebagai PDF.

Lembaran kerja baharuBerlatih dalam talian dengan petunjuk

Untuk pensyarah dan guru: percuma untuk dicetak, disalin dan digunakan di dalam kelas. Setiap lembaran kerja baharu mempunyai nilai baharu dan skema jawapannya sendiri. Pautan ke ExamProblems di halaman kursus anda amat dihargai.

Nama: ____________________   Tarikh: ____________

1.Mudah

Dalam susunan manakah traversal preorder pokok binari melawat nod?

  1. ASubpokok kiri, kemudian nod, kemudian subpokok kanan
  2. BSubpokok kiri, kemudian subpokok kanan, kemudian nod
  3. CPeringkat demi peringkat dari atas
  4. DNod, kemudian subpokok kiri, kemudian subpokok kanan
2.Mudah

Apakah graf berpemberat?

  1. AGraf yang mempunyai lebih banyak sisi daripada bucu
  2. BGraf yang sesetengah bucunya lebih berat daripada yang lain kerana mempunyai lebih banyak sisi
  3. CGraf yang disimpan pada cakera
  4. DGraf yang setiap sisinya mempunyai nilai berangka seperti kos atau jarak
3.Mudah

Apakah faktor beban jadual cincang?

  1. ABilangan elemen yang disimpan dibahagi dengan bilangan baldi
  2. BBilangan baldi dibahagi dengan purata panjang kunci yang disimpan
  3. CMasa yang diperlukan untuk memuatkan jadual dari cakera
  4. DBilangan perlanggaran setakat ini
4.Sederhana

Baris gilir dilaksanakan dengan dua tindanan: push ke tindanan "masuk", dan pop dari tindanan "keluar", mengisinya semula dari "masuk" apabila kosong. Apakah kos teramortisasi setiap operasi?

  1. AO(n²)
  2. BO(log n)
  3. CO(n)
  4. DO(1)
5.Sederhana

Mengapakah menyusuri tatasusunan selalunya jauh lebih pantas dalam praktik berbanding menyusuri senarai berpaut yang sama panjang?

  1. ATatasusunan menggunakan lebih sedikit arahan untuk membandingkan nilai
  2. BSenarai berpaut sentiasa menyimpan elemen pada cakera
  3. CElemen tatasusunan bersebelahan, jadi ia menggunakan cache CPU dengan baik
  4. DTraversal tatasusunan O(1) secara keseluruhan manakala traversal senarai berpaut O(n)
6.Sederhana

Apakah yang berlaku apabila jadual cincang dicincang semula selepas faktor bebannya melebihi ambang?

  1. AHanya kunci yang berlanggar dipindahkan ke senarai limpahan baharu di hujung jadual
  2. BKunci tertua dipadam untuk memberi ruang
  3. CJadual yang lebih besar diperuntukkan dan setiap kunci disisip semula
  4. DKunci sedia ada disusun di tempat
7.Sukar

Penapis Bloom boleh menjawab "adakah elemen ini dalam set?" dengan:

  1. AKemungkinan negatif palsu tetapi tiada positif palsu
  2. BJawapan tepat sentiasa
  3. CKemungkinan positif palsu tetapi tiada negatif palsu
  4. DJawapan untuk nombor sahaja
8.Sukar

Dalam jadual cincang yang menggunakan pengalamatan terbuka, mengapakah pemadaman sering dilakukan dengan penanda "batu nisan" (tombstone)?

  1. ABatu nisan mempercepat pencincangan
  2. BMengosongkan slot boleh memecahkan jujukan penyiasatan bagi kunci lain
  3. CIa menjadikan jadual tersusun
  4. DKunci yang dipadam mesti disimpan selama-lamanya demi keselamatan, jadi slot tidak boleh digunakan semula

Kunci jawapan

  1. 1. D · Nod, kemudian subpokok kiri, kemudian subpokok kanan
  2. 2. D · Graf yang setiap sisinya mempunyai nilai berangka seperti kos atau jarak
  3. 3. A · Bilangan elemen yang disimpan dibahagi dengan bilangan baldi
  4. 4. D · O(1)
  5. 5. C · Elemen tatasusunan bersebelahan, jadi ia menggunakan cache CPU dengan baik
  6. 6. C · Jadual yang lebih besar diperuntukkan dan setiap kunci disisip semula
  7. 7. C · Kemungkinan positif palsu tetapi tiada negatif palsu
  8. 8. B · Mengosongkan slot boleh memecahkan jujukan penyiasatan bagi kunci lain

Penyelesaian langkah demi langkah yang lengkap: berlatih topik ini di examproblems.com.