Bai Tap Danh Sach Lien Ket - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.docx) (7 trang)

Trang chủ

Đề thi

Đề thi dành cho sinh viên

Bai tap danh sach lien ket

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (72.05 KB, 7 trang )

Câu hỏi & Bài tập Chương Danh sách liên kếtPhần câu hỏi ôn kiến thức:1. Trình bày từng bước các thao tác trên danh sách liên kết đơn2. Trình bày từng bước các thao tác trên danh sách liên kết đôi3.Giả sử cho một danh sách liên kết đơn có thành phần dữ liệu là các số nguyên dương, người tamuốn tách danh sách đã cho thành hai danh sách riêng biệt, trong đó một danh sách lưu số chẵn,một danh sách lưu số lẻ. Hãy trình bày giải thuật để tách danh sách đã cho sao cho hiệu quả nhất vềthời gian xử lý và bộ nhớ sử dụng, đặc biệt xét cả trong trường hợp danh sách đã cho bao gồm tất cảlà số chẵn hoặc số lẻ.4.Hãy trình bày giải thuật trộn hai danh sách liên kết đơn đã có thứ tự (tăng hoặc giảm dần) thànhmột danh sách có thứ tự sao cho tối ưu bộ nhớ nhất có thể.5.Cho danh sách liên kết được mô tả bởi cấu trúc dữ liệu trên C như sau:struct Node{ int info;struct Node *next;};Hãy viết thuật giải nhận đầu vào là danh sách liên kết với phân tử đầu tiên được trỏ bởi list,thực hiện sắp xếp lại các phần tử của danh sách đã cho, sao cho các nút chẵn đứng trước cácnút lẻ và trong trường hợp ngược lại, thứ tự tương đối ban đầu của các nút là không thay đổi.Một nút được gọi là nút chẵn hay lẻ nếu nó đứng ở vị trí chẵn hay lẻ trong danh sách (vị trí củacác nút trong danh sách được đánh số từ phần tử đầu tiên đến phần tử cuối cùng bắt đầu từ 0).Bài tập:1. Viết chương trình thực hiện việc sắp xếp danh sách liên kết đơn bao gồm các phần tử là sốnguyên.2. Viết chương trình cộng 2 đa thức được biểu diễn thông qua danh sách liên kết đơn.3. Hãy cài đặt chương trình cho phép nhập vào một biểu thức bao gồm: các số, các toán tử +,-, *, /, div (chia dư) và các hàm toán học sin, cos, tan, ln, ex, trong biểu thức có các dấu mở,đóng ngoặc "(", ")" và chương trình sẽ tính toán giá trị của biểu thức này.4. Định nghĩa cấu trúc dữ liệu “tập hợp các số nguyên” dựa trên DSLK đơn, viết thuật giải và càiđặt các xử lý cơ bản gồm: kiểm tra phần tử thuộc tập hợp, so sánh tập hợp, kiểm tra tập rỗng;tính giao, hội, hiệu.5. Định nghĩa CTDL cho một ánh xạ từ tập các số nguyên A vào A; thuật giải kiểm tra tính chất dặcbiệt như: đơn ánh, toàn ánh, song ánh6. Tích Descart của 2 tập hợp số nguyên A và B và một vài xử lý.7. Hãy viết chương trình cho phép thực hiện yêu cầu sau :a. Nhập vào từ bàn phím một dãy số nguyên và lưu trong một danh sách liên kết có thứ tựkhông giảm, bằng cách: với mỗi phần tử được nhập vào thì phải tìm vị trí thích hợp đểchèn vào sao cho đảm bảo danh sách có thứ tự không giảm.b. Nếu thay cấu trúc danh sách liên kết bằng mảng thì thời gian thực hiện trên mảng sẽnhư thế nào so với danh sách liên kết ?8.Hãy viết chương trình cho phép thực hiện yêu cầu sau :a. Giả sử cho một danh sách liên kết kép lưu các số nguyên, hãy viết chương trình xóa cácphần tử trùng nhau trên danh sách (với các số nguyên trùng nhau, giữ lại một số nguyênduy nhất).b. Nếu thay cấu trúc danh sách liên kết bằng mảng thì thời gian thực hiện trên mảng sẽ nhưthế nào so với danh sách liên kết ?9. Giả sử cho một danh sách liên kết kép lưu các số nguyên, hãy viết chương trình cho phép nhậpvào danh sách các số nguyên, sao cho mỗi số nguyên chỉ xuất hiện một lần trên danh sách và đảmbảo danh sách luôn trong trạng thái là danh sách có thứ tự không giảm.10. Giả sử cho cấu trúc dữ liệu lưu trữ thông tin nhân sự như sau:struct NS{ int maso; // lưu thông tin mã số nhân sựchar * hoten ; // lưu thông tin họ và tên nhân sựint thamnien; // lưu thông tin số năm thâm niênfloat hesoluong ; // lưu thông tin hệ số lươngfloat luongcoban ; // lưu thông tin lương cơ bảnstruct Node *next;};Hãy viết chương trình thực hiện các yêu cầu sau:a. Tạo ra danh sách gồm 50 nhân sự bằng cách mỗi lần thêm vào một nhân sự sẽ thêmvào từ cuối danh sách.b. Sắp xếp danh sách theo thâm niên công tác giảm dần.c. Tính lương trung bình của các nhân sự trong câu a, biết rằng lương = hệ số lương *lương cơ bản.d. Hiển thị lên màn hình 5 nhân sự cho lương cao nhất, nhưng có thâm niên công tácngắn nhất và 5 nhân sự có lương thấp nhất, nhưng có thâm niên công tác lâu nhất.11. Giả sử cho một danh sách hàng hóa bao gồm nhiều mặt hàng, trong đó mỗi mặt hàng có cácthông tin:- Tên mặt hàng- Giá mặt hàng- Số lượng còn trong khoHãy thực hiện các yêu cầu sau:a. Khai báo danh dách liên kết lưu danh sách các mặt hàng theo thông tin như mô tảtrên.b. Viết hàm sắp xếp danh sách mặt hàng ở câu a theo giá mặt hàng tăng dần, nếu cùnggiá thì sắp xếp theo tên mặt hàng và hiển thị lên màn hình.c. Viết hàm nhập vào 2 số nguyên x, y (x 2 : Phụ trội = +5% Lương căn bản-Trình độ văn hóa = CH: Phụ trội = +10% Lương căn bản-Làm thêm: Phụ trội = +4% Lương căn bản/ngày-Nghỉ không phép : Phụ trội = -5% Lương căn bản/ngày+ Chức năng yêu cầu:-Cập nhật lý lịch, bảng chấm công cho nhân viên (thêm, xóa, sửa)-Xem bảng lương hàng tháng-Tìm thông tin của một nhân viênHãy khai báo cấu trúc dữ liệu thích hợp để biểu diễn các thông tin trên và cài đặt chươngtrình theo các chức năng đã mô tả ở trên.Bài tập áp dụng :1. Xây dựng cấu trúc dữ liệu và thuật giải và viết chương trình quản lý và tra từ trong tự điển AnhViệt khoảng 3000 từ dùng danh sách liên kết.2.Xây dựng cấu trúc dữ liệu và thuật giải và viết chương trình quản lý thông tin về sách trong thưviện điện tử từ dùng danh sách liên kết.