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. CNod, kemudian subpokok kiri, kemudian subpokok kanan
  4. DPeringkat demi peringkat dari atas
2.Mudah

Struktur data manakah yang berfungsi mengikut prinsip "masuk terakhir, keluar dahulu"?

  1. AJadual cincang
  2. BTindanan (stack)
  3. CSenarai berpaut
  4. DBaris gilir (queue)
3.Mudah

Dalam senarai berpaut tunggal, apakah yang terkandung dalam penuding seterusnya nod terakhir?

  1. AAlamat nod sebelumnya
  2. BBilangan nod dalam senarai
  3. CNull (tiada nod)
  4. DAlamat nod pertama
4.Sederhana

Matriks bersebelahan bagi graf dengan V bucu menggunakan berapa banyak memori?

  1. AO(V²)
  2. BO(log V)
  3. CO(E)
  4. DO(V + E)
5.Sederhana

Pokok AVL dan pokok merah-hitam menjamin:

  1. AKunci disimpan mengikut susunan sisipan
  2. BTiada nod mempunyai dua anak
  3. CKetinggian O(log n) melalui pengimbangan semula
  4. DCarian masa malar dalam setiap kes
6.Sederhana

Berapa lamakah masa untuk menyemak sama ada sisi (u, v) wujud menggunakan matriks bersebelahan?

  1. AO(log V)
  2. BO(V)
  3. CO(1)
  4. DO(E)
7.Sukar

Pernyataan manakah tentang isihan timbunan (heapsort) yang betul?

  1. AIa berjalan dalam masa O(n) pada sebarang input
  2. BIa stabil dan memerlukan memori tambahan O(n)
  3. CIa mengisih di tempat dalam masa kes terburuk O(n log n) tetapi tidak stabil
  4. DIa memerlukan pokok carian binari sebagai storan tambahan, jadi ia menggunakan memori tambahan O(n)
8.Sukar

Struktur union-find (set tercerai) dengan penyatuan mengikut pangkat dan pemampatan laluan mempunyai kos teramortisasi setiap operasi sebanyak:

  1. AO(log n) tepat
  2. BO(n²)
  3. CO(n)
  4. DO(α(n)), fungsi songsang Ackermann, yang hampir malar secara praktikal

Kunci jawapan

  1. 1. C · Nod, kemudian subpokok kiri, kemudian subpokok kanan
  2. 2. B · Tindanan (stack)
  3. 3. C · Null (tiada nod)
  4. 4. A · O(V²)
  5. 5. C · Ketinggian O(log n) melalui pengimbangan semula
  6. 6. C · O(1)
  7. 7. C · Ia mengisih di tempat dalam masa kes terburuk O(n log n) tetapi tidak stabil
  8. 8. D · O(α(n)), fungsi songsang Ackermann, yang hampir malar secara praktikal

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