CHƯƠNG 6: KỸ THUẬT LẬP TRÌNH

BÀI 30: THIẾT LẬP THƯ VIỆN CHO CHƯƠNG TRÌNH

(14 câu)

1. NHẬN BIẾT (5 câu)

Câu 1: math là gì?

Trả lời:

math là một thư viện các hàm chuẩn của Python liên quan đến các tính toán toán học.

Câu 2: Nêu cách thiết lập một thư viện.

Trả lời:

Cách thiết lập một thư viện: đưa các hàm chuẩn vào một tệp chương trình và đặt tên của tệp này chính là thư viện muốn lưu trữ.

Câu 3: Khái niệm thư viện chương trình.

Trả lời:

Thư viện chương trình là tập hợp các hàm được đặt trong các mô đun độc lập để dùng chung cho nhiều chương trình khác nhau. Các thư viện này có thể được dùng nhiều lần và có thể cập nhật, nâng cấp bất cứ lúc nào.

Câu 4: Mỗi danh sách liên kết bao gồm mấy cấu trúc dữ liệu?

Trả lời:

Mỗi danh sách liên kết bao gồm hai cấu trúc dữ liệu:

-       Cấu trúc Node mô tả các phần tử độc lập của danh sách. Tối thiểu mỗi node cần có thông tin dữ liệu key (khóa) và thuộc tính next dùng để kết nối sang phần tử tiếp theo trong danh sách.

-       Cấu trúc LL (linked list) sẽ có thông tin head (đầu) sẽ luôn chỉ vào node đầu tiên của danh sách liên kết.

Câu 5: Nêu cấu trúc dữ liệu của danh sách liên kết và các thao tác dữ liệu cơ bản trên danh sách liên kết.

Trả lời:

Danh sách liên kết là cấu trúc dữ liệu bao gồm:

●        Cấu trúc note mô tả các phần tử của danh sách. Mỗi node sẽ có dữ liệu khóa (key) là thông tin chính và thông tin next để kết nối sang phần tử tiếp theo của danh sách.

●        Cấu trúc head là đầu của mỗi danh sách liên kết. Head luôn chỉ vào node đầu tiên của danh sách.

●        Node cuối cùng của danh sách sẽ có thông tin next=None (dữ liệu rỗng). Có thể thiết lập các hàm tìm kiếm, bổ sung hoặc xóa thông tin trên danh sách liên kết.

2. THÔNG HIỂU (5 câu)

Câu 1: Kể tên một số lệnh, thao tác chính với kiểu dữ liệu danh sách liên kết.

Trả lời:

-       Khởi tạo một danh sách liên kết mới.

-       Bổ sung một phần tử với khóa k cho trước vào danh sách.

-       Tìm kiếm phần tử có khóa k trong danh sách cho trước.

-       Xóa phần tử có khóa k trong danh sách.

Câu 2: Viết chương trình của hàm delete_first (L).

Trả lời:

Câu 3: Vì sao lại cần thư viện chương trình?

Trả lời:

Các thư viện này có thể được dùng nhiều lần và có thể cập nhật, nâng cấp bất cứ lúc nào.

Câu 4: Ý nghĩa của các hàm trong thư viện chương trình là gì?

Trả lời:

Có chức năng đưa thư viện vào bộ nhớ để sẵn sàng sử dụng.

Câu 5: Những câu nào sau đây là đúng về ý nghĩa của việc sử dụng thư viện khi viết chương trình?

A. Chương trình sẽ ngắn hơn.

B. Các hàm thư viện được viết một lần và sử dụng nhiều lần.

C. Chương trình sẵn sàng, dễ hiểu hơn.

D. Chương trình sẽ chạy nhanh hơn.

Trả lời:

Câu đúng về ý nghĩa của việc sử dụng thư viện khi viết chương trình: A, B, C

3. VẬN DỤNG (4 câu)

Câu 1: Đoạn hàm sau thực hiện công việc gì?

Trả lời:

●        Đoạn mã trên sử dụng thư viện LinkedList và tạo một đối tượng danh sách liên kết mới (gọi là L) bằng cách gọi hàm khởi tạo LL().

Sau đó, thực hiện hai lần gọi hàm insert(L,10) và insert(L,20) để chèn các giá trị 10 và 20 vào danh sách liên kết L.

Cuối cùng, gọi hàm show(L) để hiển thị nội dung của danh sách liên kết L sau khi đã chèn các giá trị 10 và 20 vào trong đó.

Vậy đoạn mã này thực hiện việc tạo danh sách liên kết mới, chèn các giá trị 10 và 20 vào danh sách, và hiển thị danh sách liên kết đó.

Câu 2: Viết đoạn chương trình ngắn sử dụng thư viện LinkedList đề thiết lập một danh sách liên kết L và bổ sung các tên "Bình", "Hoa", "Hà" vào danh sách này.

Trả lời:

from LinkedList import *

# Tạo danh sách liên kết mới

L = LL()

# Thêm các tên vào danh sách liên kết

insert(L, "Bình")

insert(L, "Hoa")

insert(L, "Hà")

# Hiển thị nội dung của danh sách liên kết

show(L)

4. VẬN DỤNG CAO (2 câu)

Câu 1: Viết hàm delete_Jast(L) có chức năng xoá phần tử cuối cùng của danh sách liên kết L.

Trả lời:

Để xoá phần tử cuối cùng của danh sách liên kết ta cần duyệt từ đầu danh sách đến nút cuối cùng sau đó xoá nút cuối cùng và cập nhật con trỏ next của nút trước nó. Nếu danh sách rỗng hoặc chỉ có một phần tử thì ta chỉ cần xoá phần tử đó và trả về danh sách. Mã nguồn Python cho hàm delete_last() như sau:

def delete_last(L):
   # Nếu danh sách rỗng, trả về None
   if L is None:
       return None
   
   # Nếu danh sách chỉ có một phần tử, xoá phần tử đó và trả về danh sách
   if L.next is None:
       del L
       return None
   
   # Tìm nút cuối cùng và nút trước nó
   prev_node = None
   curr_node = L
   while curr_node.next is not None:
       prev_node = curr_node
       curr_node = curr_node.next
   
   # Xoá nút cuối cùng và cập nhật con trỏ next của nút trước nó
   prev_node.next = None
   del curr_node
   
   # Trả về danh sách đã được xoá phần tử cuối cùng
   return L

Câu 2: Cho trước danh sách liên kết L với cấu trúc như đã mô tả trong bài học, muốn lấy ra khoá của node đầu tiên của danh sách thì dùng lệnh nào?

Trả lời:

#include <stdio.h>

#include <stdlib.h>

struct Node

{

//khai bao thanh phan du lieu co kieu int

int data;

//khai bao con tro next co kieu Node

Node *next;

};

typedef struct Node NODE;

struct list{

//thanh phan dau danh sach

NODE *pHead;

//thanh phan cuoi danh sach

NODE *pTail;

};

typedef struct list LIST;

void KhoiTao(LIST &ds){

//dat dia chi dau danh sach bang NULL

ds.pHead = NULL;

//dat dia chi cuoi danh sach bang NULL

ds.pTail = NULL;

}

int KiemTraRong(LIST ds){

//neu phan tu dau danh sach NULL

if (ds.pHead == NULL){

//tra ve 1 la co NULL

return 1;

}

//truong hop nguoc lai tra ve khong null

return 0;

}

printf("\nDU LIEU TRONG DANH SACH LIEN KET DON\n");

Xuat(ds);

}