Đ I H C THÁI NGUYÊNẠ Ọ
KHOA CÔNG NGH THÔNGỆ TIN
………………
Câu 1( 1 đi m)ể
Nêu khái ni m đ quy, gi i thu t đ quy, Cho ví d v m t gi i thu t đ quy?ệ ệ ả ậ ệ ụ ề ộ ả ậ ệ
Câu 2( 3 đi m )ể
Hàm Ackermann là hàm hai đ i s v i giá tr c a đ i s là s nguyên không âm. Nóố ố ớ ị ủ ố ố ố
đ c đ nh nghĩa nh sau:ượ ị ư
Acker(m,n) =
a) Hãy xác đ nh xem đây “tiêu chu n g c” ( ng v i tr ng h p suy bi n) là gì?ị ở ẩ ố ứ ớ ườ ợ ế
b) Hãy tính Acker(1, 3), gi i thích t i sao? .ả ạ
c) Vi t gi i thu t đ tính giá tr Acker(n,m), v i m, n là các s nguyên đ c nh p t bànế ả ậ ể ị ớ ố ượ ậ ừ
phím
Câu 3( 4 đi m )ể
H c sinh kh i 12 d thi h t h c kỳ các môn: toán, lý, hóa, ngo i ng . M i thí sinh c nọ ố ự ế ọ ạ ữ ỗ ầ
qu n lý các thông tin S báo danh, h tên, l pả ố ọ ớ
1. Hãy s d ng c u trúc d li u danh sách liên k t đ n đ l u tr các thông tin c aử ụ ấ ữ ệ ế ơ ể ư ữ ủ
các thí sinh d thi. Vi t d ng cài đ t t ng ng c a c u trúc trênự ế ạ ặ ươ ứ ủ ấ
2. Xây d ng các ch ng trình con th c hi n các nhi m v sau:ự ươ ự ệ ệ ụ
- Nh p thông tin v các thí sinh d thi (đi u ki n d ng là nh p SBD = r ng)ậ ề ự ề ệ ừ ậ ỗ
- Hi n th các thí sinh d thi theo l p ể ị ự ớ
- Lo i b các thí sinh có đi m trung bình < 5 ra kh i danh sách (đi m trung bìnhạ ỏ ể ỏ ể
= (toan+ly+hoa+ngoaingu)/4)
- Tìm ki m thí sinh theo s báo danh nh p vàoế ố ậ
……………………H t……………………….ế
Thí sinh không đ c s d ng tài li u, không ghi vào đ thiượ ử ụ ệ ề
CB coi thi không gi i thích gì thêm và n p l i đ thi cho phòng ch c năng theo quy ch c a bả ộ ạ ề ứ ế ủ ộ
Mã đ thi: 07ề
Đ THI H T H C PH NỀ Ế Ọ Ầ
Đ THI H T H C PH NỀ Ế Ọ Ầ
Môn thi: C u trúc d li u và gi i thu t; H : Chính quyấ ữ ệ ả ậ ệ
Th i gian chu n b : 45 phút, không k th i gian giao đờ ẩ ị ể ờ ề
{
n+1 n u m=0ế
Acker(m-1,1) n u m ≠ 0, n=0ế
Acker(m-1, Acker(m, n-1)) n u m ≠ 0 và n ≠ 0ế