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

Operasi manakah yang perlahan dalam tatasusunan tetapi pantas pada kepala senarai berpaut?

  1. AMenyisip di permulaan
  2. BMencari panjang tatasusunan tetap
  3. CMengakses elemen ke-5
  4. DMembaca elemen terakhir mengikut indeks
2.Mudah

Operasi manakah yang O(1) untuk tatasusunan tetapi O(n) untuk senarai berpaut tunggal?

  1. AMenyisip di kepala
  2. BMembuang elemen kepala
  3. CMembaca elemen pertama
  4. DMengakses elemen pada indeks i
3.Mudah

Apakah nama operasi tindanan yang menambah elemen di atas?

  1. APeek
  2. BPush
  3. CPop
  4. DEnqueue
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

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 2 5 1 3
  2. B5 4 3 2 1
  3. C4 5 2 3 1
  4. D1 2 4 5 3
6.Sederhana

Aplikasi memerlukan carian pantas dan juga perlu menyenaraikan kunci dalam susunan tersusun dan menjawab pertanyaan julat. Struktur manakah yang paling sesuai?

  1. ATindanan
  2. BJadual cincang
  3. CPokok carian binari seimbang
  4. DSenarai berpaut tidak tersusun
7.Sukar

Algoritma Kahn untuk isihan topologi berulang kali membuang bucu dengan darjah masuk 0. Struktur manakah yang menyimpan bucu tersebut?

  1. ATindanan semua sisi yang dilawati
  2. BBaris gilir (atau sebarang koleksi) bucu yang darjah masuknya 0
  3. CTimbunan maks yang disusun mengikut darjah keluar
  4. DMatriks bersebelahan yang merekodkan bucu mana yang sudah dibuang
8.Sukar

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

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

Kunci jawapan

  1. 1. A · Menyisip di permulaan
  2. 2. D · Mengakses elemen pada indeks i
  3. 3. B · Push
  4. 4. D · O(1)
  5. 5. C · 4 5 2 3 1
  6. 6. C · Pokok carian binari seimbang
  7. 7. B · Baris gilir (atau sebarang koleksi) bucu yang darjah masuknya 0
  8. 8. B · O(α(n)), fungsi songsang Ackermann, yang hampir malar secara praktikal

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