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

Apakah nama operasi tindanan yang menambah elemen di atas?

  1. APeek
  2. BEnqueue
  3. CPop
  4. DPush
2.Mudah

Struktur data manakah yang digunakan untuk melakukan traversal peringkat demi peringkat pada pokok?

  1. ABaris gilir (queue)
  2. BBaris gilir keutamaan
  3. CJadual cincang
  4. DTindanan (stack)
3.Mudah

Apakah deque (baris gilir dua hujung)?

  1. ADua baris gilir berasingan yang berkongsi satu tatasusunan
  2. BBaris gilir yang hanya membenarkan pembuangan di belakang
  3. CBaris gilir yang disusun mengikut keutamaan
  4. DStruktur yang membenarkan sisipan dan pembuangan di kedua-dua hujung
4.Sederhana

Pokok binari mempunyai akar 1 dengan anak kiri 2 dan anak kanan 3; nod 2 mempunyai anak 4 (kiri) dan 5 (kanan). Apakah traversal postorder?

  1. A4 5 2 3 1
  2. B4 2 5 1 3
  3. C5 4 3 2 1
  4. D1 2 4 5 3
5.Sederhana

Apakah kos menyisip elemen di tengah tatasusunan dengan n elemen?

  1. AO(log n), kerana carian binari
  2. BO(1), kerana indeks diketahui
  3. CO(n²), kerana setiap elemen bergerak n kali
  4. DO(n), kerana elemen kemudian mesti dianjak
6.Sederhana

Apakah kerumitan masa mencari kunci dalam pokok carian binari yang seimbang?

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

Bagaimanakah anda boleh mengesan sama ada senarai berpaut tunggal mengandungi kitaran menggunakan memori tambahan O(1)?

  1. AKira nod sehingga bilangan melebihi medan panjang senarai
  2. BGerakkan satu penuding satu langkah dan satu lagi dua langkah dan semak sama ada mereka bertemu
  3. CSimpan setiap nod yang dilawati dalam set cincang
  4. DIsih senarai dan cari pendua
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)), fungsi songsang Ackermann, yang hampir malar secara praktikal
  4. DO(n²)

Kunci jawapan

  1. 1. D · Push
  2. 2. A · Baris gilir (queue)
  3. 3. D · Struktur yang membenarkan sisipan dan pembuangan di kedua-dua hujung
  4. 4. A · 4 5 2 3 1
  5. 5. D · O(n), kerana elemen kemudian mesti dianjak
  6. 6. D · O(log n)
  7. 7. B · Gerakkan satu penuding satu langkah dan satu lagi dua langkah dan semak sama ada mereka bertemu
  8. 8. C · O(α(n)), fungsi songsang Ackermann, yang hampir malar secara praktikal

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