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 pokok carian binari, nilai dalam subpokok kiri bagi sesuatu nod adalah:

  1. ALebih besar daripada nilai nod
  2. BDalam susunan rawak
  3. CLebih kecil daripada nilai nod
  4. DSama dengan nilai nod
2.Mudah

Struktur data manakah yang paling sesuai untuk ciri "buat asal" (undo) dalam editor teks?

  1. ABaris gilir (queue)
  2. BGraf
  3. CTindanan (stack)
  4. DSet cincang
3.Mudah

Apakah ciri penentu set sebagai jenis data abstrak?

  1. AIa menyimpan elemen dalam susunan tersusun
  2. BIa membenarkan akses hanya di satu hujung
  3. CIa menyimpan pasangan kunci-nilai
  4. DIa menyimpan elemen tanpa pendua
4.Sederhana

Apakah kos menyisip elemen di tengah tatasusunan dengan n elemen?

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

Mengapakah timbunan binari boleh disimpan dalam tatasusunan tanpa sebarang penuding?

  1. ATatasusunan secara automatik mengekalkan kunci dalam susunan tersusun, jadi tiada penuding diperlukan
  2. BTimbunan tidak pernah mengandungi lebih daripada 100 elemen
  3. CSemua kunci dalam timbunan adalah sama
  4. DIa pokok binari lengkap, jadi kedudukan mengikut formula indeks yang mudah
6.Sederhana

Jenis data abstrak manakah yang digunakan oleh algoritma Dijkstra untuk memilih bucu seterusnya untuk diproses?

  1. ASet tanpa susunan
  2. BTindanan
  3. CBaris gilir FIFO
  4. DBaris gilir keutamaan min
7.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)), fungsi songsang Ackermann, yang hampir malar secara praktikal
  3. CO(n)
  4. DO(n²)
8.Sukar

Kunci 5, 3, 8, 1 disisip mengikut susunan ini ke dalam timbunan min binari berasaskan tatasusunan yang kosong. Apakah tatasusunan akhir?

  1. A[1, 3, 5, 8]
  2. B[1, 3, 8, 5]
  3. C[3, 1, 8, 5]
  4. D[1, 5, 8, 3]

Kunci jawapan

  1. 1. C · Lebih kecil daripada nilai nod
  2. 2. C · Tindanan (stack)
  3. 3. D · Ia menyimpan elemen tanpa pendua
  4. 4. C · O(n), kerana elemen kemudian mesti dianjak
  5. 5. D · Ia pokok binari lengkap, jadi kedudukan mengikut formula indeks yang mudah
  6. 6. D · Baris gilir keutamaan min
  7. 7. B · O(α(n)), fungsi songsang Ackermann, yang hampir malar secara praktikal
  8. 8. B · [1, 3, 8, 5]

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