Trong các ứng dụng thực tế, chẳng hạn trong mạng lưới giao thông đường bộ, đường thủy hoặc đường hàng không, người ta không chỉ quan tâm đến việc tìm đường đi giữa hai địa điểm mà còn phải lựa chọn một hành trình tiết kiệm nhất (theo tiêu chuẩn không gian, thời gian hay chi phí). Vấn đề này có thể được mô hình hóa thành một bài toán trên đồ thị, trong đó mỗi địa điểm được biểu diễn bởi một đỉnh, cạnh nối hai đỉnh biểu diễn cho “đường đi trực tiếp” giữa hai địa điểm (tức không đi qua địa điểm trung gian) và trọng số của cạnh là khoảng cách giữa hai địa điểm.

Bài toán có thể phát biểu dưới dạng tổng quát như sau: Cho một đơn đồ thị có hướng và có trọng số dương G=(V,E), trong đó V là tập đỉnh, E là tập cạnh (cung) và các cạnh đều có trọng số, hãy tìm một đường đi (không có đỉnh lặp lại) ngắn nhất từ đỉnh xuất phát S thuộc V đến đỉnh đích F thuộc V. Giả sử thông tin đầu vào của bài toán (Input) được nhập vào chương trình như sau:

Input	Giải thích
7 A B 1 B E 3 E D 3 C B 4 A D 7 E C 2 C D 1 A E	- Dòng đầu tiên chứa một số nguyên dương e cho biết số cạnh của đồ thị - Với e dòng tiếp theo, mỗi dòng chứa hai chuỗi u, i và một số nguyên dương x, thể hiện thông tin có một cạnh nối từ đỉnh u sang đỉnh i trong đồ thị với độ dài (trọng số) là x - Dòng cuối cùng chứa hai chuỗi s và f, đây là đỉnh bắt đầu và đỉnh kết thúc của đường đi cần tìm Lưu ý: không biết trước số đỉnh và danh sách các đỉnh.

Hãy thực hiện các yêu cầu sau:

a. Xây dựng các cấu trúc dữ liệu phù hợp nhất có thể để biểu diễn đồ thị trên máy tính theo input đã cho.

Cấu trúc được xem là tốt nếu đạt được các tiêu chuẩn sau: Tiết kiệm tài nguyên; Hỗ trợ một số thao tác cơ bản như “Kiểm tra hai đỉnh có kề nhau không”, “Tìm danh sách
các đỉnh kề với một đỉnh cho trước” với ràng buộc là không phải duyệt qua danh sách tất cả các cạnh của đồ thị.

b. Viết hàm nhập theo Input ở đầu bài và lưu trữ thông tin của đồ thị vào cấu trúc dữ liệu đã đề xuất ở câu a.

** KHÔNG YÊU CẦU tìm cách giải cho bài toán này. Sinh viên ĐƯỢC PHÉP sử dụng Standard Template Library-STL với những cấu trúc dữ liệu (vector, stack, queue, list, map, set, pair, …) cũng như giải thuật được xây dựng sẵn.

Hãy cho biết độ phức tạp của thuật toán Insertion sort (chèn trực tiếp) theo định nghĩa Big-O (O lớn).

b. Viết hàm sắp xếp mảng 1 chiều gồm N phần tử giảm dần với thuật toán Insertion sort.

c. Hãy cho biết dãy số sẽ thay đổi qua từng bước như thế nào khi áp dụng thuật toán ở câu 1b, biết rằng dãy số cho như sau: 3, 8, 4, 5, 9, 1, 2, 6.

Cho dãy ký tự như sau: R, E, T, A, V, X, L, G, S, I

Hãy thực hiện các yêu cầu sau:

a. Vẽ cây nhị phân tìm kiếm bằng cách thêm lần lượt từng ký tự vào cây theo thứ tự từ trái qua phải của dãy ký tự trên, biết rằng giá trị của từng ký tự tương ứng theo thứ tự xuất
hiện của ký tự trong từ điển.

b. Cho biết kết qủa duyệt cây theo RNL, NRL.

c. Huỷ lần lượt từng nút L, T, E, R trên cây, mỗi lần huỷ 1 nút vẽ lại cây nối tiếp theo như thứ tự huỷ.
 

Cho biết cây B-Tree bậc 3 là một cây thỏa mãn các tính chất sau:

• Tất cả node lá nằm trên cùng một mức
• Tất cả các node, trừ node gốc và node lá, có *tối thiểu* 2 node con.
• Tất cả các node có *tối đa* 3 con
• Tất cả các node, trừ node gốc, có từ 1 cho đến 2 khóa (keys)
• Một node không phải lá và có n khóa thì phải có n+1 node con.

Hãy thực hiện các yêu cầu sau:

3.1 Cho dãy số: 12, 17, 20, 23, 15, 11, 24, 13, 19, 22, 18, 21, 16. Hỏi khi lần lượt thêm các số trong dãy theo thứ tự từ trái qua phải vào một cây B-Tree bậc 3 rỗng thì:

a. Các khóa nào khi thêm vào cây sẽ làm phát sinh thao tác tách (split) node? (0.5 điểm)

b. Vẽ cây B-Tree trước và sau khi thêm các khóa ở câu a (1 điểm)

3.2 Cho cây B-Tree bậc 3 như hình sau:

Hãy lần lượt tiến hành xóa các khóa sau khỏi cây: 13, 24, 19 và vẽ cây B-Tree trước và sau khi xóa mỗi khóa trên (0.5 điểm)

Lưu ý khi xoá:

- Khi khóa cần xóa (gọi là x) không nằm ở node lá, chọn khóa thế mạng là khóa có giá trị lớn nhất mà nhỏ hơn x.

- Thao tác nhường khoá (underflow) sẽ được thực hiện khi hai node liền kề có tổng số khóa >= 2. Khi có một node không còn đáp ứng đủ số lượng khóa tối thiểu, ưu tiên thực hiện underflow thay cho catenation (hợp) vì thao tác này không làm thay đổi số khóa của node cha.

- Khi có 02 lựa chọn node liền kể để thực hiện catenation, ưu tiên chọn catenation giữa node bị thiếu khóa với node liền trước.

Để việc tìm kiếm thông tin mặt hàng được nhanh chóng, người ta dùng một bảng băm theo phương pháp thăm dò, làm việc trên mã quản lý của mặt hàng. Mã quản lý này là một con số nguyên. Bảng băm có:

- Hàm băm: h(key) = (key % M)

- Hàm băm lại (hàm thăm dò): prob(key, i) = (h(key) + i*i + i) % M

Trong đó:

- key là giá trị khóa.

- i là một số nguyên cho biết lần băm lại (thăm dò) thứ i.

- M là kích thước bảng băm.

Giả sử M = 7, cho trường hợp T của bảng băm đã chứa dữ liệu như bên dưới. Biết “-” là ký hiệu vị trí trống trong bảng băm.

a. Trình bày từng bước việc tìm mã quản lý 23 trong bảng băm T.

b. Trình bày từng bước việc thêm các mã quản lý sau vào bảng băm T theo đúng thứ tự liệt kê là 11, 20, 27.