Câu hỏi và bài tập môn cấu trúc dữ liệu và giải thuật - Trường ĐH Công nghệ Thông tin

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

69
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tập hợp các Câu hỏi và Bài tập các chương: Chương Bảng băm Chương Danh sách liên kết; B-Tree; Chương Stack – Queue và các bài tập thực hành khác Mời các bạn xem nội dung chi tiết để bạn hệ thống lại kiến thức và ôn tập hiệu quả.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Câu hỏi và bài tập môn cấu trúc dữ liệu và giải thuật - Trường ĐH Công nghệ Thông tin

BÀI THỰC HÀNH Dùng danh sách liên kết đơn để quản lý một lớp học. Biết rằng mỗi sinh viên bao gồm các thông tin sau: Tên (chuỗi ký tự), Mã số sinh viên (chuỗi ký tự), Điểm trung bình. Hãy viết hàm thực hiện các yêu cầu sau: a. In danh sách sinh viên ra màn hình b. Liệt kê 5 sinh viên có điểm trung bình cao nhất trong lớp học. c. Cho biết số tổng số sinh viên có điểm trung bình
Câu hỏi & Bài tập Chương Bảng băm Phần câu hỏi ôn kiến thức: 1.Hãy trình bày ưu điểm và hạn chế của cấu trúc bảng băm và cho ví dụ minh họa cụ thể ? Bài tập : 1.Cho bảng A kích thước 11 ô và tập khóa K = {7, 20, 16, 24, 12, 40, 15}, ta cần nạp các giá trị khóa K vào bảng A sử dụng hàm băm H(k) = k % 11. om Hãy vẽ bảng A sau khi tất cả các giá trị khóa trong tập K được lưu trữ trong bảng A, sử dụng kỹ .c thuật danh sách liên kết để xử lý xung đột. ng 2. Cho bảng A kích thước 11 ô và tập khóa K = {30, 10, 56, 14, 22, 60, 15}, ta cần nạp các giá trị co khóa K vào bảng A sử dụng hàm băm H(k) = k % 7. Hãy vẽ bảng A sau khi tất cả các giá trị khóa trong tập K được lưu trữ vào bảng A, sử dụng kỹ an thuật dò tuyến tính để xử lý xung đột. th 3. Cho bảng A kích thước 11 ô và tập khóa K = {23, 12, 65, 27, 8, 50, 58}, ta cần nạp các giá trị ng khóa K vào bảng A sử dụng hàm băm H(k) = k % 10. o Hãy vẽ bảng A sau khi tất cả các giá trị khóa trong tập K được lưu trữ vào bảng A, sử dụng kỹ du thuật dò toàn phương để xử lý xung đột. u cu 4.Cho bảng A kích thước 11 ô và tập khóa K = {7, 20, 16, 24, 12, 40, 15}, ta cần nạp các giá trị khóa K vào bảng A sử dụng hàm băm H(k) = k % 11. Hãy vẽ bảng A sau khi tất cả các giá trị khóa trong tập K được lưu trữ vào bảng A, sử dụng kỹ thuật băm kép để xử lý xung đột, với hàm băm kép thứ 2 tự định nghĩa. 5.Viết chương trình minh hoạ bảng băm dùng phương pháp nối kết trong các trường hợp sau : a. Dữ liệu lưu trữ là số nguyên (khoá tìm kiếm là số nguyên). b. Dữ liệu lưu trữ là thông tin học sinh, bao gồm: họ tên học sinh, lớp, tên trường (khoá tìm kiếm là tên lớp). CuuDuongThanCong.com https://fb.com/tailieudientucntt
6.Viết chương trình minh hoạ bảng băm dùng phương pháp dò tuyến tính trong các trường hợp sau: a. Dữ liệu lưu trữ là số nguyên (khoá tìm kiếm là số nguyên). b. Dữ liệu lưu trữ là thông tin học sinh, bao gồm: họ tên học sinh, lớp, tên trường (khoá tìm kiếm là tên lớp). 3.Giả sử kích thước của bảng băm là SIZE = s và d1, d2, …, ds-1 là hoán vị ngẫu nhiên của các số 1, 2, …, s-1. Dãy thăm dò ứng với khoá k được xác định như sau: om i = i = h(k) 0 .c i = (i + d ) % SIZE , 1 ≤m≤s –1 m i ng Hãy cài đặt hàm thăm dò theo phương pháp trên. co Bài tập áp dụng: an 1. Viết chương trình cho phép tạo, tra cứu từ điển Anh-Việt sử dụng cấu trúc bảng băm 2. Viết chương trình cho phép tạo, tra cứu sách trong thư viện sử dụng cấu trúc bảng băm th 3. Các bài tập khác do Giảng viên đề nghị o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Câu hỏi & Bài tập B-Tree Phần câu hỏi ôn kiến thức: 1. Trình bày định nghĩa và các tính chất của cây B-Tree. 2. Cài đặt tất cả các thao trên cây B-Tree. 3. Cho B-tree bậc 5 gồm các khóa sau (chèn vào theo thứ tự): 3, 7, 9, 23, 45, 1, 5, 14, 25, 24, 13, 11, 8, 19, 4, 31, 35, 56 Thực hiện các yêu cầu sau: - Thêm các khóa: 2, 6,12 - Xóa khóa: 4, 5, 7, 3, 14 4. Khởi tạo B Tree bậc 7 với các thao tác Insert: 34, 12, 55, 21, 6, 84, 5, 33, 15, 74, 54, 28, 10, 19. Hãy thực hiện các chuỗi thao tác sau và cho biết kết quả qua từng thao tác: - Insert(11) - Delete(15) - Delete(6) - Insert(98) - Delete(34) - Delete(5) Bài tập : 1. Viết chương trình cài đặt các thao tác trên B tree. 2. Các bài tập khác do Giảng viên đề nghị
Câu hỏi & Bài tập Chương Danh sách liên kết Phầ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 đơn 2. Trình bày từng bước các thao tác trên danh sách liên kết đôi 3.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 ta muố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ành mộ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ác nú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ủa cá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ặc biệt như: đơn ánh, toàn ánh, song ánh 6. 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ác phầ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ên duy 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ập và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à đảm bả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ên float hesoluong ; // lưu thông tin hệ số lương float luongcoban ; // lưu thông tin lương cơ bản struct 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êm và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ác ngắ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ác thông tin: - Tên mặt hàng
- Giá mặt hàng - Số lượng còn trong kho Hã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ùng giá 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
Thông tin trên phiếu đăng ký bao gồm: họ tên người mua vé, số chứng minh nhân dân, địa chỉ, số lượng vé đăng ký mua. Nếu người nào đó thực hiện việc đăng ký hai lần thì phiếu đăng ký lần hai sẽ bị loại bỏ. Hãy viết chương trình cho phép: a. Thực hiện duyệt bán vé theo yêu cầu trên khi ban tổ chức phát ra 10.000 vé đăng ký, biết rằng số ghế ngồi là 15.000 ghế, chương trình sẽ chỉ còn giải quyết duyệt bán vé khi còn ghế trống. b. Hiển thị lên màn hình danh sách người mua vé và số vé tương ứng được mua. 16. Giả sử tại một trường học X, người ta có một tập tin dữ liệu, lưu thông tin tất cả các học sinh trong trường. Tập tin bao gồm nhiều bản ghi (record), trong đó mỗi bản ghi lưu thông tin: họ và tên học sinh, mã lớp (ví dụ :7a, 7b, 8c, 9a), điểm trung bình. Hãy thực hiện các yêu cầu sau : a. Tạo ra cho mỗi lớp một danh sách liên kết lưu thông tin tất cả học sinh của lớp ấy. b.Sắp xếp danh sách các lớp trong câu a theo họ và tên học sinh c. Hiển thị lên màn hình danh sách các lớp trong câu b. 17.Giả sử người ta phải xây dựng một chương trình soạn thảo văn bản, hãy chọn cấu trúc dữ liệu thích hợp để lưu trữ văn bản trong quá trình soạn thảo. Biết rằng: - Số dòng văn bản không hạn chế. - Mỗi dòng văn bản có chiều dài tối đa 80 ký tự. - Các thao tác yêu cầu gồm: Di chuyển trong văn bản (lên, xuống, qua trái, qua phải) Thêm, xóa, sửa ký tự trong một dòng Thêm, xóa một dòng trong văn bản Đánh dấu, sao chép khối. 18. Giả sử theo quy tắc tổ chức quản lý nhân viên của một công ty, thông tin về một nhân viên bao gồm lý lịch và bảng chấm công: + Lý lịch nhân viên: - Mã nhân viên: chuỗi 8 ký tự
- Tên nhân viên: chuỗi 20 ký tự - Tình trạng gia đình: 1 ký tự (M = Married, S = Single) - Số con: số nguyên ≤ 20 - Trình độ văn hóa: chuỗi 2 ký tự (C1 = cấp 1; C2 = cấp 2; C3 = cấp 3; ĐH = đại học; CH = cao học) - Lương căn bản: số ≤ 1000000 + Chấm công nhân viên: - Số ngày nghỉ có phép trong tháng: số ≤ 28 - Số ngày nghỉ không phép trong tháng: số ≤ 28 - Số ngày làm thêm trong tháng: số ≤ 28 - Kết quả công việc: chuỗi 2 ký tự (T = Tốt; TB = Đạt; K = Kém) - Lương thực lĩnh trong tháng: số ≤ 2000000 + Quy tắc tính lương: Lương thực lĩnh = Lương căn bản + Phụ trội trong đó nếu: - Số con > 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ên Hã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ương trì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 Anh Việ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.
Câu hỏi & Bài tập Chương Stack - Queue Phần câu hỏi ôn kiến thức: 1. 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 stack in lên màn hình. Hãy cho biết sau khi hoàn tất chuỗi thao tác, những gì xuất hiện trên màn hình? 2. Cài đặt chương trình cho phép thực hiện các phép tính +,-,*,/ trên các số có tối đa 30 chữ số, có chức năng nhớ (M+, M-, MC, MR). 3. Viết chương trình thực hiện các thao tác trên đa thức. 4.Giả sử cho hàm push(a) là hàm thực hiện nạp a vào ngăn xếp và hàm pop() là hàm lấy phần tử ra khỏi ngăn xếp. Giả sử cho dãy thao tác sau đây, biết rằng ngăn xếp ban đầu được khởi tạo rỗng : push(5), push(3), pop(), push(2), push(8), pop(), pop(), pop(), push(9), push(1), pop(), push(7), push(6), pop(), pop(), push(4), pop(), pop(). Hãy viết ra dãy phần tử của danh của ngăn xếp (chỉ rõ vị trí đầu ngăn xếp) sau khi thực hiện mỗi thao tác. 5.Giả sử cho hàm enq(a) là hàm thực hiện nạp a vào hàng đợi và hàm deq() là hàm thực hiện lấy phần tử ra khỏi hàng đợi. Giả sử cho dãy các thao tác sau đây, biết rằng hàng đợi ban đầu được khởi tạo rỗng: enq(5), enq(3), deq(), enq(2), enq(8), deq(), enq(9), enq(1), deq(), enq(7), enq(6), deq(), deq(). enq(4), deq(), deq(). Hãy viết ra dãy các phần tử của hàng đợi (chỉ rõ vị trí đầu và cuối của hàng đợi) sau khi thực hiện mỗi thao tác. 6.Hãy trình bày cách sử dụng ngăn xếp để chuyển biểu thức dạng trung tố sau đây về dạng biểu thức hậu tố:
a. a – b * c ^ d + f b. 1 + 2 + 3 * 4 + 5 – 6 * 7 + 8 7.Hãy trình bày cách tính giá trị của biểu thức hậu tố sau đây nhờ sử dụng ngăn xếp: a. 1 2 + 3 1 + * 1 1 + 1 + / b. 3 4 + 3 5 + * 7 + 8 * Bài tập: 1. Viết chương trình nhập vào một số nguyên không âm bất kỳ, sau đó hiển thị lên màn hình số đảo ngược thứ tự của số nguyên vừa nhập vào (ví dụ: nếu nhập số 12567, hiển thị lên màn hình số 76521) bằng cách: a. Sử dụng ngăn xếp b. Sử dụng hàng đợi 2. Viết chương trình chuyển đổi một số nguyên N trong hệ thập phân (hệ 10) sang biểu diễn ở các hệ sau, sử dụng ngăn xếp: a. Hệ nhị phân (hệ 2) b. Hệ thập lục phân (hệ 16) c. Hệ bát phân (hệ 8) 3.Hãy viết chương trình mô phỏng cho bài toán “Tháp Hà Nội” bằng cách sử dụng ngăn xếp. 4.Hãy viết chương trình tính toán cho biểu thức số học bằng cách sử dụng ngăn xếp. 5.Hãy viết chương trình tìm tất cả các cặp dấu ngoặc tương ứng trong một chương trình viết bằng ngôn ngữ C/C++.