tailieunhanh - Cấu trúc dữ liệu và giải thuật I - BÀI TẬP BÀI TẬP LÝ THUYẾT

Bài 1. Phân tích ưu, khuyết điểm của xâu liên kết so với mảng. Tổng quát hóa các trường hợp nên dùng xâu liên kết. Bài 2. Xây dựng một cấu trúc dữ liệu thích hợp để biễu diễn đa thức P(x) có dạng : P(x) = c1xn1 + c2xn2 +.+ckxnk Biết rằng: Các thao tác xử lý trên đa thức bao gồm : thêm một phần tử vào cuối đa thức in danh sách các phần tử trong đa thức theo : thứ tự nhập vào ngược với thứ tự nhập vào hủy một phần tử bất kỳ. | BÀI TẬP cho các bài 7 8 9 10 BÀI TẬP LÝ THUYẾT -UBài 1. Phân tích ưu khuyết điểm của xâu liên kết so với mảng. Tổng quát hóa các trường hợp nên dùng xâu liên kết. ỠBài 2. Xây dựng một cấu trúc dữ liệu thích hợp để biễu diễn đa thức P x có dạng P x C1xn1 c2xn2 . ckxnk Biết rằng ŨCác thao tác xử lý trên đa thức bao gồm thêm một phần tử vào cuối đa thức in danh sách các phần tử trong đa thức theo thứ tự nhập vào ngược với thứ tự nhập vào hủy một phần tử bất kỳ trong danh sách Số lượng các phần tử không hạn chế Chỉ có nhu cầu xử lý đa thức trong bộ nhớ chính. a Giải thích lý do chọn CTDL đã định nghĩa. b Viết chương trình con ước lượng giá trị của đa thức P x khi biết x. c Viết chương trình con rút gọn biểu thức gộp các phần tử cùng số mũ . ỠBài 3. Xét đoạn chương trình tạo một xâu đơn gồm 4 phần tử không quan tâm dữ liệu sau đây Dx NULL p Dx Dx new NODE for i 0 i 4 i p p- next p new NODE p- next NULL Đoạn chương trình có thực hiện được thao tác tạo nêu trên không Tại sao Nếu không thì có thể sửa lại như thế nào cho đúng ỠBài 4. Một ma trận chỉ chứa rất ít phần tử với giá trị có nghĩa ví dụ phần tử 0 được gọi là ma trận thưa. Ví dụ r0 0 0 3 0 o1 1 0 0 0 2 0 L0 0 4 0 0 0 Dùng cấu trúc xâu liên kết để tổ chức biễu diễn một ma trận thưa sao cho tiết kiệm nhất chỉ lưu trữ các phần tử có nghĩa . a Viết chương trình cho phép nhập xuất ma trận. b Viết chương trình con cho phép cộng hai ma trận. ỠBài 5. Bài toán Josephus có N người đã quyết định tự sát tập thể bằng cách đứng trong vòng tròn và giết người thứ M quanh vòng tròn thu hẹp hàng ngũ lại khi từng người lần lượt ngã khỏi vòng tròn. Vấn đề là tìm ra thứ tự từng người bị giết. Ví dụ N 9 M 5 thì thứ tự là 5 1 7 4 3 6 9 2 8 Hãy viết chương trình giải quyết bài toán Josephus xử dụng cấu trúc xâu liên kết. ỠBài 6. Hãy cho biết nội dung của stack sau mỗi thao tác trong dãy EAS Y QUE ST I ON Với một chữ cái tượng trưng cho thao tác thêm chữ cái tương ứng vào stack dấu tượng trưng cho thao tác lấy nội dung một phần tử trong .