Hướng dẫn giải nhanh Tin học 11 định hướng Khoa học máy tính Cánh diều 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

Câu 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ách, thêm nút vào giữa danh sách.

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

Hướng dẫn trả lời:

Thời gian thực hiện các phép toán sau của danh sách liên kết để đảm bảo chúng đều có thời gian O(1):

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

- Để thêm nút vào cuối danh sách, chúng ta chỉ cần cập nhật liên kết từ nút cuối cùng của danh sách đến nút mới. Thời gian thực hiện là O(1).

- Để thêm nút vào giữa danh sách, chúng ta cần cập nhật liên kết của nút mới để trỏ đến nút liền trước và liền sau của nó. Cả hai thao tác này đều có thời gian O(1) vì chúng ta chỉ cần thay đổi một số liên kết.

b) Gỡ bỏ nút ở cuối danh sách và ở đầu danh sách:

- Để gỡ bỏ nút ở cuối danh sách, chúng ta chỉ cần cập nhật liên kết của nút trước nút cuối cùng để trỏ đến null hoặc None (tùy theo ngôn ngữ lập trình). Thời gian thực hiện là O(1).

- Để gỡ bỏ nút ở đầu danh sách, chúng ta chỉ cần cập nhật liên kết của nút đầu danh sách để trỏ đến nút kế tiếp của nó. Thời gian thực hiện là O(1).

VẬN DỤNG

Câu 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ì:

a) 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?

b) 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.

Hướng dẫn trả lời:

a) Một số hàm thao tác với danh sách và ví dụ:

- cmp(list1, list2): So sánh các phần tử của hai danh sách.

- len(list): Trả về độ dài của danh sách.

- sum(list): Tính tổng giá trị của các phần tử trong danh sách (chỉ áp dụng cho kiểu số).

- max(list): Tìm phần tử có giá trị lớn nhất trong danh sách.

- min(list): Tìm phần tử có giá trị nhỏ nhất trong danh sách.

- list(seq): Chuyển đổi một tuple thành danh sách.

b) Các phép toán số học và logic, cùng với ví dụ:

- Phép toán số học bao gồm phép cộng (+), phép trừ (-), phép nhân (*), phép chia (/), phép chia lấy phần dư (%), và phép lũy thừa (**).

  Ví dụ: a + b, c * d, x / y.

- Phép so sánh bao gồm phép so sánh bằng (==), phép so sánh khác (!=), phép so sánh lớn hơn (>), phép so sánh nhỏ hơn (<), phép so sánh lớn hơn hoặc bằng (>=), và phép so sánh nhỏ hơn hoặc bằng (<=).

  Ví dụ: a == b, x > y, c <= d.

- Phép logic bao gồm phép AND logic (and), phép OR logic (or), và phép NOT logic (not).

  Ví dụ: a and b, x or y, not c.

- Phép gán giá trị bao gồm phép gán giá trị (=), phép gán giá trị tăng lên (+=), phép gán giá trị giảm đi (-=), và phép gán giá trị nhân với (*=).

  Ví dụ: a = 10, b += 5, x -= 3.

- Phép chuyển đổi kiểu dữ liệu bao gồm các phép chuyển đổi kiểu số nguyên (int), kiểu số thập phân (float), kiểu chuỗi (str), và kiểu boolean (bool).

  Ví dụ: int(x), float(y), str(z), bool(w).

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

Câu 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).

Hướng dẫn trả lời:

Các phép toán danh sách liên kết có thời gian thực hiện O(n) bao gồm:

- Tìm kiếm một phần tử: Để tìm kiếm một phần tử trong danh sách liên kết, ta phải duyệt qua từng nút của danh sách một cách tuần tự để tìm kiếm phần tử cần tìm. Thời gian thực hiện của phép toán này là O(n).

- Chèn một phần tử vào cuối danh sách: Để chèn một phần tử vào cuối danh sách, ta phải duyệt qua từng nút của danh sách để đến cuối danh sách và thực hiện thêm phần tử vào cuối danh sách. Thời gian thực hiện của phép toán này cũng là O(n).

- Xóa một phần tử khỏi danh sách: Để xóa một phần tử khỏi danh sách, ta phải tìm kiếm phần tử đó trong danh sách, sau đó thực hiện xóa phần tử đó bằng cách điều chỉnh các liên kết giữa các nút trong danh sách. Tương tự như tìm kiếm một phần tử, thời gian thực hiện của phép toán này là O(n).

- Đảo ngược danh sách: Để đảo ngược danh sách, ta phải duyệt qua từng nút của danh sách, thay đổi liên kết giữa các nút để đảo ngược danh sách. Vì vậy, thời gian thực hiện của phép toán này là O(n).

Câu 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).

Hướng dẫn trả lời:

Các phép toán với danh sách liên kết có độ phức tạp O(n) bao gồm:

- Tìm kiếm một phần tử: Để tìm kiếm một phần tử trong danh sách liên kết, ta phải duyệt qua từng nút của danh sách một cách tuần tự để tìm kiếm phần tử cần tìm. Thời gian thực hiện của phép toán này là O(n).

- Chèn một phần tử vào cuối danh sách: Để chèn một phần tử vào cuối danh sách, ta phải duyệt qua từng nút của danh sách để đến cuối danh sách và thực hiện thêm phần tử vào cuối danh sách. Thời gian thực hiện của phép toán này cũng là O(n).

- Xóa một phần tử khỏi danh sách: Để xóa một phần tử khỏi danh sách, ta phải tìm kiếm phần tử đó trong danh sách, sau đó thực hiện xóa phần tử đó bằng cách điều chỉnh các liên kết giữa các nút trong danh sách. Tương tự như tìm kiếm một phần tử, thời gian thực hiện của phép toán này là O(n).

- Đảo ngược danh sách: Để đảo ngược danh sách, ta phải duyệt qua từng nút của danh sách, thay đổi liên kết giữa các nút để đảo ngược danh sách. Vì vậy, thời gian thực hiện của phép toán này là O(n).

Câu 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.

Hướng dẫn trả lời:

Để truy cập nút chứa dữ liệu X trong danh sách liên kết, chúng ta cần thực hiện việc duyệt qua tất cả các nút của danh sách từ đầu đến cuối. Trong quá trình duyệt, chúng ta kiểm tra giá trị của mỗi nút để xác định xem nút đó có chứa dữ liệu X hay không. Sau khi tìm thấy nút chứa dữ liệu X, chúng ta có thể thực hiện các thao tác khác với nút đó, như việc xoá nút đó khỏi danh sách.

Do phải duyệt qua toàn bộ danh sách, thời gian thực hiện của việc truy cập nút chứa dữ liệu X là O(n), với n là số lượng nút trong danh sách. Trong trường hợp danh sách là danh sách liên kết kép, thao tác truy cập cũng có thể được thực hiện theo chiều ngược lại với độ phức tạp tương tự.