Tiêu đề Giải đề cuối kì HK211.docx ✅

Câu 1. Cho đồ thị như hình vẽ bên dưới Hãy chọn các thứ tự nào sau đây của các đỉnh là một thứ tự topo? a. 10, 17, 13, 2, 3, 0, 14, 7, 8, 11, 1, 4, 5, 9, 6, 12, 16, 15 b. 10, 17, 13, 2, 3, 0, 14, 7, 8, 11, 1, 4, 5, 6, 9, 12, 16, 15 c. 10, 17, 13, 2, 3, 0, 14, 7, 12, 11, 1, 4, 5, 6, 9, 8, 16, 15 d. 10, 17, 13, 2, 3, 0, 14, 7, 8, 11, 1, 4, 5, 6, 9, 16, 12, 15 Giải: Bài này mình sẽ giải bằng phương pháp DFS. Chi tiết xem tại: https://www.youtube.com/watch?v=eL- KzMXSXXI Đầu tiên, ta xác định xem những node nào có indegree = 0. Ta có node 0, 10, 2 Theo pp DFS, nếu bắt đầu từ Node 10 thì phần tử cuối cùng của thứ tự topo phải là 17 hoặc 16 . Node 2 thì là 3 hoặc 16 -> 4 đáp án bắt đầu từ node 0. Xét đáp án A theo chiều xuôi. Ta nhận thấy 9 đc duyệt trước 6, trong khi 6 là điều kiện tiên quyết để 9 đc duyệt -> A sai. Xét đáp án B , ta nhận thấy thứ tự đều hợp lý, đảm bảo đc điều kiện tiên quyết -> B đúng. Xét đáp án C, theo chiều xuôi, ta nhận thấy 12 đc duyệt trước các điều kiện tiên quyết là 9,8,11 -> C sai. Xét đáp án D, theo chiều xuôi, ta nhận thấy 16 đc duyệt trước đk của nó (12) -> D sai. Câu 2. Trong các hình dưới đây, hình nào là một max-heap? Chọn một hoặc nhiều hơn:
a. C b. D c. A d. B D sai vì node 10 > node (8) - vốn là parent của nó. C sai vì node 8 lớn hơn node parent của nó (node 5). A sai vì đây không phải là một cây nearly complete / complete tree. Câu 3. Cho một đồ thị như hình vẽ: Hãy viết một thứ tự (cách nhau bởi dấu phẩy, không có khoảng trắng trong đáp án) của các đỉnh được viếng thăm trong phương pháp duyệt ưu tiên theo chiều rộng (các đỉnh liền kề của một đỉnh được thêm vào một hàng đợi theo thứ tự abc). Biết rằng đỉnh đầu tiên được chọn là đỉnh g.
Giải: Từ đỉnh g, ta có đường đi trực tiếp tới f,e,c -> queue: f->e->c. Order: g. Xét front queue f, ta thấy f đi đc trực tiếp tới a,d -> queue e->c->a->d. Order: g->f. Xét front queue e, ta thấy e đi đc trực tiếp tới b -> queue: c->a->d->b. Order: g->f->e. Từ c trở đi, ta thấy các node đều đã đc thăm. Queue: Empty. Order: g->f->e->c->a->d->b Câu 5. Cho cây AVL được trình bày dưới dạng liệt kê bằng dấu ngoặc như sau: 67(51(47(44,N),56(N,63)),71(69,82(73,86))) với N là NULL. Lần lượt thêm các nút 79 và 68 vào cây AVL trên, tổng các khóa trên nút lá sau khi thêm là Đầu tiên, ta build cây AVL. Thêm 79 vào cây này, ta có: Điền balanceFactor = left – right lên các node. Ta nhận thấy cây mất cân bằng ở 71. (balanceFactor_71 = 2). Nguyên nhân nằm ở cây con bên phải. Ta có 71->right = 82_balanceFactor = -1 -> mất cân bằng theo case left of Right. Đầu tiên, ta xoay phải node 82.
RotateRight() Tmp = 82->left. 82->left = tmp->right. Tmp->right = 82. Return tmp. Sau đó, xoay node 71 qua trái. Rotateleft() Tmp = 71->right 71->right = tmp->left Tmp->left = 71. Sau khi xoay Node 71 qua trái, ta có cây sau.