Struktur Data dan Algoritma: soalan latihan dan soalan peperiksaan

Notasi Big-O, masa larian algoritma biasa dan pertukaran antara tatasusunan, senarai terpaut, pokok, jadual cincangan dan graf.

Berlatih kursus ini secara percumaBerlatih kursus iniAmbil peperiksaan percubaan5 soalan percuma setiap hari. Tiada kad diperlukan.

Pek ulang kaji kilat (PDF)Lembaran formula, langkah kaedah dan soalan latihan dengan penyelesaian penuh, sedia untuk dicetak.

Topik dalam kursus ini

  1. Algoritma & kerumitanistilah dan fakta utama · menggunakan konsep · kes dan analisisaneka pilihan
  2. Struktur dataistilah dan fakta utama · menggunakan konsep · kes dan analisisaneka pilihan
  3. Teori grafdarjah dan sisi · laluan Euler dan pokok · laluan terpendek dan pokok rentangpengiraan

Tip peperiksaan untuk Struktur Data dan Algoritma

  • Untuk gelung bersarang, darabkan bilangan lelaran; untuk gelung berturutan, kekalkan sebutan yang lebih besar.
  • Ketahui kos carian, sisipan dan pemadaman bagi setiap struktur data.
  • Membahagi dua input pada setiap langkah memberikan masa logaritma.

Contoh penyelesaian

Algoritma & kerumitanMudah

Notasi manakah yang menerangkan batas atas pertumbuhan?

  1. ABig Omega
  2. BOmega kecil
  3. CBig O
  4. DBig Theta
Tunjukkan petunjuk
  1. "Paling banyak".
  2. Dua jawapan salah kini telah dipangkah. Satu daripada dua yang tinggal adalah betul.
Tunjukkan jawapan dan penerangan

Mengapa ini jawapannya

O memberikan batas atas, Ω batas bawah dan Θ batas ketat.

Jawapan

C · Big O
Struktur dataSederhana

Bagaimanakah extract-min berfungsi dalam timbunan min binari?

  1. ABuang elemen terakhir tatasusunan
  2. BPindahkan elemen terakhir ke akar dan gerakkannya ke bawah
  3. CBuang akar dan anjakkan semua elemen satu tempat ke kiri
  4. DCari semua daun untuk minimum baharu
Tunjukkan petunjuk
  1. Kekalkan pokok lengkap, kemudian betulkan susunan.
  2. Dua jawapan salah kini telah dipangkah. Satu daripada dua yang tinggal adalah betul.
Tunjukkan jawapan dan penerangan

Mengapa ini jawapannya

Elemen terakhir mengisi lubang di akar dan ditukar dengan anaknya yang lebih kecil sehingga sifat timbunan dipenuhi, mengambil O(log n).

Jawapan

B · Pindahkan elemen terakhir ke akar dan gerakkannya ke bawah

Cara latihan berfungsi

  • “Berlatih kursus ini” mencampurkan soalan daripada semua topiknya, seperti peperiksaan sebenar.
  • Setiap soalan mempunyai nilai baharu, jadi anda mempelajari kaedah dan bukannya jawapan.
  • Buntu? Buka petunjuk kecil dahulu, dan penerangan penuh hanya apabila anda memerlukannya.
  • Peperiksaan percubaan adalah bermasa dan tanpa petunjuk, dan anda mendapat skor serta semakan penuh pada akhirnya.

Kursus berkaitan

Asas Sains KomputerMatematik DiskretRangkaian Komputer
Berlatih kursus ini secara percumaBerlatih kursus iniAmbil peperiksaan percubaan5 soalan percuma setiap hari. Tiada kad diperlukan.