Struktur Data dan Algoritma: paket kilat

Lembar rumus, langkah-langkah metode utama untuk setiap topik, dan 6 soal latihan, dengan pembahasan lengkap di bagian belakang.

Soal baruKembali ke mata kuliah

Di jendela cetak, pilih “Simpan sebagai PDF” untuk menyimpan salinan di perangkat Anda.

1Rumus dan metode

Teori graf

Lema jabat tangan
Σ deg(v) = 2|E|
Graf lengkap
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Graf beraturan
|E| = n·k/2
Pohon dan hutan
|E| = n − 1, |E| = n − c
Daun pohon
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
sirkuit: semua derajat genap; lintasan: tepat 2 derajat ganjil
Sirkuit Hamilton di Kn
(n − 1)!/2
Pembaruan Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Jalan dengan panjang L
(Mᴸ)ij

Metode

  1. Tuliskan derajat setiap simpul; jumlah derajat sama dengan dua kali banyaknya sisi.
  2. Untuk soal Euler, periksa bahwa graf terhubung dan hitung simpul berderajat ganjil.
  3. Untuk pohon, gunakan n − 1 sisi dan lema jabat tangan.
  4. Untuk Dijkstra, buat tabel jarak sementara dan tetapkan simpul belum tetap dengan jarak terkecil di setiap putaran.
  5. Untuk pohon rentang minimum, urutkan sisi menurut bobot dan lewati setiap sisi yang membentuk siklus (Kruskal), atau tumbuhkan satu pohon dari simpul awal (Prim).

2Soal latihan

1.Algoritma & kompleksitasSedang

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

  1. AMerge sort sudah O(n)
  2. BMerge sort tidak memiliki struktur rekursif
  3. CSubmasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang
  4. DDynamic programming hanya bekerja pada masalah graf, bukan pada array
2.Algoritma & kompleksitasSulit

Bagaimana algoritma Bellman–Ford mendeteksi siklus berbobot negatif yang dapat dicapai dari sumber?

  1. ASetelah V − 1 putaran, algoritma memeriksa apakah masih ada sisi yang dapat direlaksasi
  2. BAlgoritma memeriksa apakah ada sisi berbobot negatif
  3. CAlgoritma menjalankan Dijkstra dua kali dan membandingkan kedua hasil jaraknya
  4. DAlgoritma menghitung siklus dengan depth-first search
3.Struktur dataSedang

Berapa biaya menyisipkan elemen di tengah array berisi n elemen?

  1. AO(n²), karena setiap elemen bergeser n kali
  2. BO(log n), karena binary search
  3. CO(n), karena elemen-elemen sesudahnya harus digeser
  4. DO(1), karena indeksnya diketahui
4.Struktur dataSulit

Bloom filter dapat menjawab pertanyaan "apakah elemen ini ada di dalam himpunan?" dengan:

  1. AKemungkinan negatif palsu, tetapi tanpa positif palsu
  2. BKemungkinan positif palsu, tetapi tanpa negatif palsu
  3. CJawaban yang selalu tepat
  4. DJawaban hanya untuk bilangan
5.Teori grafSedang

Sebuah pohon memiliki 4 simpul berderajat 3, 2 simpul berderajat 4, 2 simpul berderajat 2, dan semua simpul lainnya adalah daun (derajat 1). Berapa daun L yang dimilikinya?

4 × deg 32 × deg 42 × deg 2
L =
6.Teori grafSulit
ABCDE

Ada berapa jalan tertutup dengan panjang 3 yang dimulai dan berakhir di E? Jalan boleh mengulang simpul dan sisi. Sebut bilangan ini N.

M = matriks ketetanggaanL = 3
N =

3Larutan

1.Algoritma & kompleksitas

Jawaban: C · Submasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang

Mengapa ini jawabannya

Kedua bagian merge sort saling lepas dan masing-masing diselesaikan sekali; DP hanya membantu ketika submasalah berulang, seperti pada Fibonacci.

Jawaban

C · Submasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang
2.Algoritma & kompleksitas

Jawaban: A · Setelah V − 1 putaran, algoritma memeriksa apakah masih ada sisi yang dapat direlaksasi

Mengapa ini jawabannya

Semua jarak terpendek sebenarnya ditemukan dalam V − 1 putaran; jika suatu sisi masih dapat diperbaiki, pasti ada siklus negatif.

Jawaban

A · Setelah V − 1 putaran, algoritma memeriksa apakah masih ada sisi yang dapat direlaksasi
3.Struktur data

Jawaban: C · O(n), karena elemen-elemen sesudahnya harus digeser

Mengapa ini jawabannya

Semua elemen setelah titik penyisipan bergeser satu posisi ke kanan, yang memerlukan waktu sebanding dengan n.

Jawaban

C · O(n), karena elemen-elemen sesudahnya harus digeser
4.Struktur data

Jawaban: B · Kemungkinan positif palsu, tetapi tanpa negatif palsu

Mengapa ini jawabannya

Jika ada bit suatu elemen yang bernilai 0, elemen itu pasti tidak ada; jika semuanya 1, elemen itu kemungkinan ada. Bloom filter mengorbankan akurasi demi penggunaan memori yang sangat kecil.

Jawaban

B · Kemungkinan positif palsu, tetapi tanpa negatif palsu
5.Teori graf

Jawaban: L = 10

Euler, Hamilton, dan pohon: graf terhubung memiliki sirkuit Euler (setiap sisi sekali, kembali ke awal) jika setiap simpul berderajat genap, dan lintasan Euler yang bukan sirkuit jika tepat dua simpul berderajat ganjil; lintasan itu berjalan dari satu simpul ganjil ke simpul ganjil lainnya. Sirkuit Hamilton mengunjungi setiap simpul sekali; Kn memiliki (n − 1)!/2 sirkuit seperti itu. Pohon dengan n simpul memiliki n − 1 sisi, dan graf terhubung dengan m sisi masih memiliki pohon rentang setelah m − n + 1 sisi dihapus.

Lema jabat tangan untuk pohon

L + 24 = 2(L + 8) − 2
L = 10

Jawaban

L = 10

Jalan pintas: L = 2 + Σ (d − 2) atas simpul berderajat d ≥ 3.

6.Teori graf

Jawaban: N = 4

Derajat: derajat suatu simpul adalah banyaknya sisi yang bertemu di simpul itu. Setiap sisi memiliki dua ujung, jadi jumlah derajat sama dengan dua kali banyaknya sisi: Σ deg(v) = 2|E| (lema jabat tangan). Karena itu banyaknya simpul berderajat ganjil selalu genap. Kn memiliki n(n − 1)/2 sisi, graf beraturan-k dengan n simpul memiliki nk/2, dan pohon dengan n simpul memiliki n − 1 sisi.

Matriks ketetanggaan

A: 0 1 1 0 0
B: 1 0 1 1 1
C: 1 1 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0

Satu langkah lagi

(M³)EE = 2·0 + 2·1 + 1·1 + 1·1 + 3·0 = 4

Jawaban

N = 4

ExamProblems · examproblems.com/courses/data-structures-and-algorithms