Bài Tập Tổng Hợp 3 - Thuật Toán và Cấu Trúc Dữ Liệu. Môn Cấu trúc dữ liệu và thuật toán (Phenika) | Đại học Trường Đại học Phenika.
Bài Tập Tổng Hợp 3 - Thuật Toán và Cấu Trúc Dữ Liệu. Môn Cấu trúc dữ liệu và thuật toán (Phenika) | Đại học Trường Đại học Phenika.
Tài liệu gồm 1 trang giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem!
Môn: Cấu trúc dữ liệu và thuật toán (Phenika) 11 tài liệu
Trường: Đại học Phenika 889 tài liệu
Tác giả:
Preview text:
BÀI TẬP TỔNG HỢP 3 Câu 1:
Hãy cho biết các phát biểu sau úng hay sai:
a. Các phần tử trong cấu trúc dữ liệu Stack ược thực hiện theo nguyên tắc vào
trước ra trước(first in first out).
b. Độ phức tạp(complexity) của hai thuật toán sắp xếp nổi bọt và merge-sort là như nhau.
c. Thuật toán Dijkstra cho phép tìm ường i ngắn ngất từ một ỉnh ến tất cả các
ỉnh còn lại của ồ thị
d. Đỉnh gốc sẽ ược thăm ầu tiên nếu chúng ta tiến hành duyệt theo thứ tự
sau(post order) trên một cây.
e. Một ồ thị ơn vô hướng, liên thông có số cạnh nhiều hơn số ỉnh.
Câu 2: Hãy mô tả thuật toán ệ quy(recursive) dưới dạng pseudo code ể tìm số phần tử
có giá trị bằng phần tử ầu tiên trong một dãy danh sách liên kết ơn(singly-linked list).
Câu 3: Vẽ cây nhị phân tìm kiếm cân bằng cho dãy sau: 1 9 6 2 4 7
Câu 4: Mô tả thuật toán kiểm tra xem 1 phần tử có giá trị bằng k có nằm trong cây
nhị phân tìm kiếm hay không bằng pseudo-code.
Câu 5: Hãy mô tả thuật toán liệt kê tất cả các hoán vị của n phần tử dưới dạng
pseudocode. Hãy cho biết ộ phức tạp của thuật toán dưới dạng O().
Câu 6: Trình bày ngắn gọn phương pháp giải quyết va chạm trong cấu trúc dữ liệu bảng băm (Hash table).