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 ciri penentu set sebagai jenis data abstrak?

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

Dalam graf, apakah kitaran?

  1. ALaluan yang bermula dan berakhir pada bucu yang sama
  2. BSisi dengan pemberat sifar
  3. CBucu tanpa sisi
  4. DLaluan yang melawat setiap bucu
3.Mudah

Dalam perwakilan senarai bersebelahan bagi graf, apakah yang disimpan untuk setiap bucu?

  1. ASenarai bucu jirannya
  2. BLaluan terpendek ke setiap bucu lain
  3. CSatu baris V nilai Boolean
  4. DJumlah bilangan sisi dalam graf
4.Sederhana

Berapa banyak memori yang digunakan oleh senarai bersebelahan bagi graf dengan V bucu dan E sisi?

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

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

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

Trie (pokok awalan) amat cekap untuk:

  1. AMenyimpan matriks
  2. BMengisih nombor
  3. CMencari laluan terpendek
  4. DCarian awalan seperti autolengkap
7.Sukar

Memadam nod dengan dua anak daripada pokok carian binari biasanya dilakukan dengan:

  1. AMenggantikannya dengan pengganti in-order (atau pendahulu) dan memadam nod itu
  2. BMenukarkannya dengan akar
  3. CMembuang seluruh subpokok
  4. DMembina semula subpokok di bawahnya dari awal dan menyisip semula setiap kunci yang dikandunginya
8.Sukar

Tanpa penyatuan mengikut pangkat atau pemampatan laluan, apakah kos kes terburuk satu find dalam struktur union-find dengan n elemen?

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

Kunci jawapan

  1. 1. A · Ia menyimpan elemen tanpa pendua
  2. 2. A · Laluan yang bermula dan berakhir pada bucu yang sama
  3. 3. A · Senarai bucu jirannya
  4. 4. C · O(V + E)
  5. 5. B · Elemen tatasusunan bersebelahan, jadi ia menggunakan cache CPU dengan baik
  6. 6. D · Carian awalan seperti autolengkap
  7. 7. A · Menggantikannya dengan pengganti in-order (atau pendahulu) dan memadam nod itu
  8. 8. C · O(n)

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