CHỦ ĐỀ F^CS: GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH

BÀI 15 CẤU TRÚC DỮ LIỆU DANH SÁCH LIÊN KẾT VÀ ỨNG DỤNG

LUYỆN TẬP

CH 1: Dựa trên hình minh hoạ, mô tả các bước thực hiện các phép toán sau của danh sách liên kết để minh hoạ chúng đều có thời gian là O(1).

a) Thêm nút vào cuối danh sánh, thêm nút vào giữa danh sách.

b) Gỡ bỏ nút ở cuối danh sánh, ở đầu danh sách.

Đáp án chuẩn:

Gợi ý: Mô tả các bước thực hiện các phép toán sau của danh sách liên kết để minh hoạ chúng đều có thời gian là O(1).

VẬN DỤNG

CH 1: Phân tích yêu cầu ứng dụng của một danh sách nhóm đứng đầu top X và cho biết, nếu dùng kiểu danh sách của Python để thực hiện thì:

1. Những thao tác cần làm với danh sách top X sẽ thực hiện qua các phép toán danh sách Python như thế nào?

2. Kể tên một vài phép toán danh sách của Python không cần dùng đến cho trường hợp này.

Đáp án chuẩn:

a) Gợi ý: Một số hàm thao tác với list thông dụng khác:

• cmp(list1, list2): so sánh các phần tử của 2 list

• len(list): lấy về chiều dài của list

• sum(): Trả về tổng giá trị của các phần tử trong list.

• max(list): Trả về phần tử có giá trị lớn nhất trong list

• min(list): Trả về phần tử có giá trị nhỏ nhất trong list

• list(seq): Chuyển đổi một tuple thành list

b) Gợi ý:

• Phép toán số học: phép cộng, trừ, nhân, chia, chia lấy phần dư, lũy thừa.

• Phép so sánh: phép so sánh bằng, so sánh khác, so sánh lớn hơn, so sánh nhỏ hơn, so sánh lớn hơn hoặc bằng và so sánh nhỏ hơn hoặc bằng.

• Phép logic: phép and logic and, or logic or và not logic not.

• Phép gán giá trị: phép gán giá trị, gán giá trị tăng lên, gán giá trị giảm đi và phép gán trị nhân với.

• Phép chuyển đổi kiểu dữ liệu: phép chuyển đổi kiểu số, thập phân, chuỗi và boolean bool.

CÂU HỎI TỰ KIỂM TRA

CH 1: Hãy nêu các phép toán danh sách liên kết có thời gian thực hiện (1).

Đáp án chuẩn:

Truy cập phần tử đầu tiên (head) và phần tử cuối cùng (tail) của danh sách liên kết, thêm phần tử vào đầu danh sách và cuối danh sách, xóa phần tử đầu danh sách và cuối danh sách.

CH 2: Hãy nêu các phép toán danh sách liên kết có thời gian thực hiện O(n).

Đáp án chuẩn:

Tìm kiếm một phần tử, chèn một phần tử vào cuối danh sách, xóa một phần tử khỏi danh sách, đảo ngược danh sách.

CH 3: Nếu muốn truy cập nút chứa dữ liệu X thì phải làm gì? Ước lượng thời gian thực hiện.

Đáp án chuẩn:

Ta phải duyệt toàn bộ các nút của danh sách từ đầu đến cuối, kiểm tra giá trị của mỗi nút để tìm nút chứa dữ liệu X. Thời gian thực hiện là O(n), với n là số lượng nút trong danh sách.