Pseudo-code Drills: Cấu trúc dữ liệu cơ bản

91%

Quảng cáo • Advertisement

📢 Sponsor Ad

Google AdSense

🎯 Làm quen với Giả mã (Pseudo-code) Part B

Đề thi FE dùng một ngôn ngữ giả mã riêng (tương tự C/Java nhưng đơn giản hơn). Bạn phải đọc hiểu nó.

📝 Cú pháp Giả mã FE cần nhớ:

a <- 5: Gán 5 cho a.
a, b: Khai báo nhiều biến.
if (điều kiện) then ... else ... endif
while (điều kiện) do ... endwhile
for (i from 1 to 10 step 1) ... endfor
Mảng[i]: Truy cập phần tử thứ i (Cẩn thận: Index có thể bắt đầu từ 0 hoặc 1 tùy đề).

1. Stack (Ngăn xếp) & Queue (Hàng đợi)


// Stack: LIFO
push(stack, 5)
push(stack, 10)
val = pop(stack) // val = 10

// Queue: FIFO
enqueue(queue, 5)
enqueue(queue, 10)
val = dequeue(queue) // val = 5

Bài tập điển hình: Cho một chuỗi thao tác push/pop. Hỏi trạng thái cuối cùng của Stack?

🧮 Thử thách Ba Lan (Reverse Polish Notation):

Tính biểu thức: 5 1 2 + 4 * + 3 -

Push 5. Stack: [5]
Push 1. Stack: [5, 1]
Push 2. Stack: [5, 1, 2]
Gặp +: Pop 2, Pop 1. Tính 1+2=3. Push 3. Stack: [5, 3]
Push 4. Stack: [5, 3, 4]
Gặp *: Pop 4, Pop 3. Tính 3*4=12. Push 12. Stack: [5, 12]
Gặp +: Pop 12, Pop 5. Tính 5+12=17. Push 17. Stack: [17]
Push 3. Stack: [17, 3]
Gặp -: Pop 3, Pop 17. Tính 17-3=14. -> Đáp án: 14.

📝 Luyện tập Part B (Exam Drills):

Câu hỏi: Cho Stack rỗng. Thực hiện: push(5), push(3), pop(), push(7), pop(). Giá trị còn lại trong Stack?
Đáp án
Số 5. Giải thích: [5] -> [5, 3] -> [5] -> [5, 7] -> [5].
Câu hỏi: Tại sao Queue lại phù hợp để quản lý hàng đợi in ấn (Printer Queue)?
Đáp án
Vì nó tuân thủ nguyên tắc FIFO (vô trước ra trước), đảm bảo công bằng cho người gửi lệnh in trước.

2. Linked List (Danh sách liên kết)


Node {
    data: int
    next: Node
}
// Thêm node mới vào sau node p
new_node.next = p.next
p.next = new_node

// Xóa node sau node p
p.next = p.next.next

Mẹo: Luôn vẽ hình ra giấy nháp để không bị rối các mũi tên.

3. Linked List Reversal (Đảo ngược danh sách)

Bài toán: Input: 1 -> 2 -> 3 -> null. Output: 3 -> 2 -> 1 -> null.


prev = null
curr = head
while curr != null:
    next_node = curr.next  // Lưu thằng đằng sau
    curr.next = prev       // Quay xe: Trỏ ngược về đằng trước
    prev = curr            // Bước tiếp: Prev tiến lên
    curr = next_node       // Curr tiến lên
head = prev // Head mới là thằng cuối cùng (3) (Lúc này curr đã nhảy ra null)

graph LR A((1)) -.-> B((2)) B -.-> C((3)) B --> A C --> B style B stroke:red style C stroke:red

DAY 91🇯🇵 アルゴリズム (Stack/Queue)