ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC SƯ PHẠM
KỲ THI KẾT THÚC HỌC PHẦN
HỌC KỲ 2 NĂM HỌC 2011-2012

Đề thi môn: Cấu trúc dữ liệu và giải thuật nâng cao
Dành cho: K6 – SP Tin học Đề số: 1
Thời gian làm bài: 90 phút (không kể thời gian phát đề)

Câu I (2 điểm):
Cho n loại tiền mệnh giá lần lượt v1,v2,v3, … vn. Mỗi loại tiền có k tờ. Cần mua 1 đồ vật có giá tiền s. Hỏi có mấy cách sử dụng các tờ tiền đã có để mua đồ vật đó. Liệt kê các cách?
Câu II (3.5 điểm):
Cho một DSLK đơn. Mỗi phần tử gồm info là một số nguyên và liên kết chỉ đến phần tử kế. a. Tạo 2 DSLK đơn mới (không phá huỷ DSLK đã cho). Một danh sách chứa các số lẻ của danh sách đã cho. Một danh sách chứa các số chẵn của danh sách đã cho. b. Viết chương trình in ra DSLK đã cho theo thứ tự ngược. (HD: Sử dụng đưa DSLK vào Stack). c. In ra các run tự nhiên từ DSLK đã cho: VÍ DỤ: DSLK ban đầu biểu diễn các số: 1 5 6 4 8 3 7  In ra các dãy số: 1 5 6 4 8  3 7  d. Sắp xếp tăng/giảm dần danh sách đã cho theo các phương pháp: chọn trực tiếp, nổi bọt, đổi chỗ trực tiếp
Câu III ( 2 điểm):
a) Cách sử dụng ngăn xếp để chuyển biểu thức dạng trung tố sau thành biểu thức dạng hậu tố: a-b*c^d-f
b) Hãy trình bày cách tính gia trị của biểu thức hậu tố sau đây nhờ sử dụng ngăn xếp
1 2 + 3 1 + * 1 1 + 1+/
Câu IV (2.5 điểm): Cho một cây nhị phân tìm kiếm. Mỗi node trên cây có info là một số nguyên và liên kết chỉ đến cây con trái và cây con phải. a. Tính số node, số node lá, số node nhánh trên cây. b. Nhập vào một số nguyên x. Viết thủ tục tìm x trên cây . Nếu tìm thấy hãy in ra màn hình giá trị của các node lớn hơn x.
-------------------------------------------Hết----------------------------------------
Ghi chú: + Thí sinh không được sử dụng tài liệu khi làm bài
+ Cán bộ coi thi không giải thích gì thêm.