Ôn tập cấu trúc dữ liệu và giải thuật môn Cơ sở lập trình | Đại học Văn Lang

ÔN TẬP
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT HK183
CHƯƠNG 1: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
1) Tìm một số ví dụ minh hoạ mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Giải thích minh họa nếu cần. -
Ví dụ minh hoạ: Giả sử ta có một danh sách các trường đại học và cao đẳng trên cả
nước, mỗi trường có các thông tin sau: Tên trường, địa chỉ, số điện thoại phòng đào tạo.
Ta muốn viết một chương trình trên máy tính điện tử để khi cho biết “tên trường” máy sẽ
hiện ra màn hình cho ta: “địa chỉ” và “số điện thoại phòng đào tạo” của trường đó. -
Giải thích: Một cách đơn giản là cứ duyệt tuần tự các tên trường trong danh sách cho tới
khi tìm thấy tên trường cần tìm thì sẽ đối chiếu ra “địa chỉ” và “ số điện thoại phòng đào
tạo” của trường đó. Cách tìm tuần tự này rõ ràng chỉ chấp nhận được khi danh sách
ngắn còn danh sách dài thì rất mất thời gian.
Nếu ta biết tổ chức lại danh sách bằng cách sắp xếp theo thứ tự từ điển của tên trường thì có
thể áp dụng một giải thuật tìm kiếm khác tốt hơn, tương tự như ta vẫn thường làm khi tra từ
điển. Cách tìm này nhanh hơn cách trên rất nhiều nhưng không thể áp dụng được với dữ liệu chưa được sắp xếp.
Nếu lại biết tổ chức thêm một bảng mục lục chỉ dẫn theo chữ cái đầu tiên của tên trường, thì khi
tìm “địa chỉ” và “số điện thoại phòng đào tạo” của Hdkdh ta sẽ bỏ qua được các tên trường mà chữ cái đầu tiên.
2) Cho biết một số kiểu dữ liệu được định nghĩa sẵn trong một ngôn ngữ lập trình các
bạn thường sử dụng. Cho biết một số kiểu dữ liệu tiền định này có đủ để đáp ứng mọi
yêu cầu về tổ chức dữ liệu không ? -
Một số kiểu dữ liệu được định sẵn trong một ngôn ngữ lập trình thường sử dụng là:
+ integer: rất thông dụng, được dùng để biểu diễn các số nguyên
+ char: biểu diễn các ký tự đơn lẻ
+ string: biểu diễn chuỗi các ký tự, hay còn gọi là chuỗi, để tạo thành câu hay cụm từ -
Không đủ đáp ứng, vì còn phải xài nhiều kiểu dữ liệu khác ngoài kiểu dữ liệu định
nghĩa sẵn chẳng hạn như : mảng, con trỏ, kiểu dữ liệu người dùng tự định nghĩa ( struct & class) enumenum
3) Một ngôn ngữ lập trình có nên cho phép người sử dụng tự định nghĩa thêm các kiểu
dữ liệu có cấu trúc? Giải thích và cho ví dụ. -
Có, vì các kiểu dữ liệu được định nghĩa trước là không đủ để thỏa mãn nhiều yêu cầu khi lập trình -
VD: để lưu thông tin cá nhân về 1 nhân viên, ta cần tạo kiểu dữ liệu nvien gồm các
thuộc tính như tên, năm sinh, địa chỉ, cmnd,... mỗi thuộc tính lại có 1 kiểu dữ liệu khác
nhau chúng là thành phần của kiểu dữ liệu NhanVien trong tình huống trên chúng ta phải
tự định nghĩa ra kiểu NhanVien, chúng ta không thể dùng các kiểu dữ liệu đc định nghĩa
trc để thể hiện cho đối tượng nvien này
4) Cấu trúc dữ liệu và cấu trúc lưu trữ khác nhau những điểm nào? Một cấu trúc dữ liệu
có thể có nhiều cấu trúc lưu trữ được không? Ngược lại, một cấu trúc lưu trữ có thể
tương ứng với nhiều cấu trúc dữ liệu được không ? Cho ví dụ minh hoạ. -
VD: Cấu trúc lưu trữ kế tiếp (mảng) và cấu trúc lưu trữ móc nối đều có thể được dùng để cài
đặt cấu trúc dữ liệu ngăn xếp (stack). Mặt khác, các cấu trúc dữ liệu như: danh sách, ngăn xếp
và cây đều có thể cài đặt trên máy thông qua cấu trúc lưu trữ móc nối.
5) Giả sử có một bảng giờ tàu cho biết thông tin về các chuyến tàu khác nhau của mạng
đường sắt. Hãy biểu diễn các dữ liệu này bằng một cấu trúc dữ liệu thích hợp (file, array,
struct ...) sao cho dễ dàng truy xuất giờ khởi hành, giờ đến của một chuyến tàu bất kỳ tại một nhà ga bất kỳ.
6) Theo anh / chị, thế nào là cấu trúc dữ liệu động, cấu trúc dữ liệu tĩnh? Cho ví dụ minh họa. -
Cấu trúc dữ liệu động là những thứ có thể mở rộng hoặc thu lại tùy thuộc vào chương
trình, đồng thời các vị trí bộ nhớ liên quan của chúng sẽ có thể thay đổi.
Ví dụ: Danh sách liên kết được tạo ra bằng con trỏ -
Cấu trúc dữ liệu tĩnh là những cấu trúc và kích thước của các vị trí bộ nhớ được cố định lúc biên dịch. Ví dụ: Mảng - Array
7) Hãy đánh giá độ phức tạp của đoạn code chạy trên C++ như sau: ● Phép gán:
Lần thứ 0: thực hiện 1 lần
Lần thứ 1: thực hiện 2 lần
Lần thứ 2: thực hiện 3 lần …
Lần thứ k: thực hiện N + 1 lần => Độ phức tạp O(n) ● Phép so sánh:
Lần thứ 0: thực hiện 2 lần
Lần thứ 1: thực hiện 4 lần
Lần thứ 2: thực hiện 6 lần …
Lần thứ k: N = k thực hiện 2N + 2 lần => Độ phức tạp O(n)
8) Hãy đánh giá độ phức tạp của đoạn code chạy trên C++ như sau: -
Xét vòng lặp For bên trong sẽ lặp tối đa n lần
=> Vòng lặp For này có độ phức tạp thuộc lớp O(n) -
Xét vòng lặp For bên ngoài, ta thấy lặp tối đa n lần
=> Vòng lặp For này có độ phức tạp thuộc lớp O(n) -
Mà ta thấy 2 vòng lặp lồng vào nhau (tức là trong for có for)
=> Độ phức tạp tổng thể là O(n) * O(n) ~ O(n * n) ~ O(n^2)
=> Độ phức tạp của đoạn code trên thuộc lớp O(n^2)
9) Hãy đánh giá độ phức tạp của đoạn code chạy trên C++ như sau: ● Phép gán:
Lần thứ 0: 1 + 1 = 2 phép gán
Lần thứ 1: 1 + 1 + 1 + 1 = 4 phép gán
Lần thứ 2: 2 + 2 + 2 = 6 phép gán …
Lần thứ k: 2n + 2 phép gán => Độ phức tạp O(n)
10) Hãy đánh giá độ phức tạp của đoạn code chạy trên C++ như sau:
O(n^2); dòng (7 - 9), vòng for chạy n lần là O(n); dòng (9 - 12), 2 vòng for là O(n^2); 2 dòng for
độc lập, lấy max được O(n^2)
11) Hãy đếm số phép so sánh bằng trong đoạn code sau, từ đó đánh giá độ phức tạp của đoạn code
Lần thứ 0: thì ’so sánh’ thực hiện 2 lần
Lần thứ 1: thì ’so sánh’ thực hiện 5 lần
Lần thứ 2: thì ’so sánh’ thực hiện 8 lần …
Lần thứ k: thì ’so sánh’ thực hiện 2 + 3k lần
Lần thứ N: thì ‘so sánh’ thực hiện 2 + 3N lần => Độ phức tạp O(n)
12) Hãy đếm số phép gán trong đoạn code sau, từ đó đánh giá độ phức tạp của đoạn code
CHƯƠNG 2: MỘT SỐ CTDL CƠ BẢN 1) Anh / chị hãy:
(a) Định nghĩa DSLK kép DLIST với mui phần tử là các đối tượng PhanSo (gvm tử số và mwu số)
(b) Viết các hàm cần thiết để hàm main() sau thực thi
2) Giả sử có danh sách liên kết (DSLK) có cấu trúc như sau:
Viết hàm thực hiện việc:
(a) Nhập từ bàn phím vào thông tin của 10 sinh viên.
Thông tin này được đưa vào DLSK theo phương pháp thêm vào cuối.
(b) In ra danh sách những sinh viên có ĐTB <5.
(c) Giải phóng danh sách liên kết
(d) Viết hàm main để gọi các hàm trên
3) Cho một danh sách liên kết đôi đã lưu thông tin về sản phẩm trong một công ty, bao gvm:
1.Mã sản phẩm (kiểu số nguyên)
2.Tên sản phẩm (kiểu chuui)
3.Chủng loại (bằng Giấy, bằng Kim loại, bằng Nhựa)
4.Năm sản xuất (kiểu số nguyên)
5.Số năm bảo hành (kiểu số nguyên)
Hai con trỏ First, Last đang trỏ đến phần tử đầu tiên và cuối cùng trong danh sách trên.
Hãy thực hiện các yêu cầu sau :
(a) Viết hàm sắp xếp các sản phẩm theo mã sản phẩm giảm dần
(b) Viết hàm xóa các sản phẩm đã hết hạn bảo hành ra khỏi danh sách khi thỏa điều
kiện : Năm sản xuất + Số năm bảo hành > Năm hiện tại
4) Trình bày khái niệm của các loại danh sách? Ưu, nhược điểm và ứng dụng của mui loại danh sách? -
Danh sách đặc: là một danh sách mà các phần tử trong danh sách có cùng kiểu dữ liệu,
và được cấp phát liên tục trong bộ nhớ.
+ Ưu điểm: mật độ sử dụng danh sách là tối ưu tuyệt đối, truy cập, tìm kiếm các
phần tử ở mọi vị trí là dễ dàng vì vị trí các phần tử liền kề nhau trong bộ nhớ.