Cấu trúc dữ liệu và giải thuật

Bộ công nghiệp
Cộng hoà xã hội chủ nghĩa việt nam

Trường Trường ĐHCN Hà Nội
Độc lập - Tự do - Hạnh phúc

**************
***********

Phiếu thi
Kỳ thi: Học kỳ V
Môn thi: CTDL>
Hình thức: Thi viết
Thời gian: 120 phút

đề bài
Câu 1(2 điểm):
Cho hàm số f(m,n) với m,n là các đối số kiểu nguyên như sau:

a) Tính f(2,3), giải thích cách tính?
b) Viết giải thuật đệ qui và thủ tục đệ qui để tính giá trị hàm f. Để tính f(2,3) phải gọi thủ tục tính giá trị hàm f bao nhiêu lần?
Câu 2(3 điểm):
a) Cho dãy số S:3 0 -1 8 9 6 2 5. Hãy minh hoạ việc sắp xếp dãy số S đã cho theo chiều tăng dần bằng phương pháp chọn trực tiếp.
b) Viết chương trình nhập một dãy X có n số thực, sắp xếp dãy X theo chiều giảm dần bằng phương pháp nói trên rồi in kết quả ra màn hình.
c) Cho dãy số Y: -10 8 9 6 12 7. Minh hoạ việc tìm kiếm số k=15 trong dãy Y theo phương pháp tìm kiếm tuần tự.
Câu 3(3 điểm):
Cho danh sách thí sinh dự thi, mỗi thí sinh có các thông tin: Số báo danh, họ và tên, năm sinh, điểm toán, điểm lý, điểm hoá, tổng điểm (TĐ = ĐT + ĐL + ĐH).
a) Hãy biểu diễn CTDL của danh sách nói trên dưới dạng một danh sách liên kết đơn.
b) Dựa vào CTDL đã biểu diễn ở trên hãy viết các thủ tục thực hiện các yêu cầu sau:
+ Nhập danh sách n thí sinh (cho n là số nguyên dương).
+ Tìm và in ra những thí sinh có tổng điểm >= 20.
+ Loại bỏ những thí sinh có tổng điểm bằng 0.
Câu 4 (2 điểm):
Cho biểu thức (x-y+z)*t + u/v –x/z
a) Viết lại biểu thức dưới dạng tiền tố, hậu tố (vẽ cây nhị phân biểu diễn biểu thức).
b) Minh hoạ việc định giá biểu thức bằng ngăn xếp với biểu thức được viết ở dạng hậu tố với x=6, y=4, z=3, t=2, u=16, v=8.
Hà Nội, ngày tháng năm 200
Duyệt đề


Bộ công nghiệp
Cộng hoà xã hội chủ nghĩa việt nam

Trường Trường ĐHCN Hà Nội
Độc lập - Tự do - Hạnh phúc

**************
***********

Phiếu thi
Kỳ thi: Học kỳ V
Môn thi: CTDL>
Hình thức: Thi viết
Thời gian: 120 phút

đề bài
Câu 1(2 điểm):
Cho hàm số f(x,y) với x,y là các đối số kiểu nguyên như sau:

a) Tính f(3,2), giải thích cách tính?
b) Viết giải thuật đệ qui và thủ tục đệ qui để tính giá trị hàm f. Để tính f(3,2) phải gọi thủ tục tính giá trị hàm f bao nhiêu lần?
Câu 2(3 điểm):
a) Cho dãy số: 2 3 -1 8 0 9 6 5. Hãy minh hoạ việc sắp xếp dãy số trên theo chiều giảm dần bằng phương pháp chèn trực tiếp.
b) Viết chương trình nhập một dãy X có n số thực sắp xếp dãy X theo chiều tăng dần bằng phươ