TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
ĐỀ THI CUI K MÔN CU TRÚC D LIU VÀ GII THUT
Thi gian: 90 phút
(Không s dng tài liu)
Câu 1 (3 điểm) : Cho dãy s ban đầu như sau : 17 72 99 32 58 70 44 12 23
Hãy thc hin các yêu cu sau:
a. Hãy trình bày các bước thc hin thut toán chn trc tiếp (1.5 đ)
b. V hình từng bước thc hin ca thut toán trên để sp xếp y s theo th t
gim dn (không cn lp trình) (1.5 đ)
Gi ý đáp án:
a. Sinh viên trình bày lý thuyết đúng thuật toán (1,5 điểm)
c 1: i = 0;
c 2: Tìm phn t a[min] nh nht trong dãy hin hành t a[i] đến a[N-1]
c 3 : Hoán v a[min] và a[i]
c 4 : Nếu i < N-2 thì i = i+1; Lp lại Bước 2
Ngưc li: Dng. //N-1 phn t đã nằm đúng v trí.
b. Viết đúng các bước đưa từng phn t nh/ln nhất lên trước (1,5 điểm). Nếu SV
làm sai phương pháp thì không tính đim.
Nếu SV l nhm sai 1-2 trường hp thì ch cho 1.0 điểm
Câu 2 (4 điểm) : Cho dãy các ký t như sau : A B C D E F W Z U T K
Hãy thc hin các yêu cu sau:
a. Hãy v cây nh phân tìm kiếm t dãy ký t trên (1 đ)
b. B xung lần lượt các ký t sau vào cây N, G, H , M , L để hình thành cây nh phân
tìm kiếm mi, v hình cây khi thêm tng ký t vào cây (1 đ)
c. Trình bày dãy k t kết qa khi duyt cây theo th t NRL, LRN (1 đ)
d. V hình cây khi xóa lần lượt các ký t W, E, H, C (1 đ)
Lưu ý : trong qúa trình b xung hay xóa mt nút trêny, nếu có xy ra mt cân bng thì
cho biết trưng hp mt cân bng là loi gì và tiến hành cân bng li cây.
Câu 3 (2 điểm) : Cho mt danh sách liên kết đôi đã lưu thông tin v sn phm trong mt
công ty, bao gm:
1.Mã sn phm (kiu s nguyên)
2.Tên sn phm (kiu chui)
3.Chng loi (bng Giy, bng Kim loi, bng Nha)
4.Năm sản xut (kiu s nguyên)
5.S năm bảo hành (kiu s nguyên)
Hai con tr Head, Tail đang tr đến phn t đầu tiên và cui cùng trong danh sách trên.
Hãy thc hin các yêu cu sau :
a. Viết hàm sp xếp các sn phm theo mã sn phm gim dn (1 đ)
b. Viết hàm xóa các sn phm đã hết hn bo hành ra khi danh sách khi thỏa điều
kiện : Năm sản xut + S năm bảo hành > Năm hiện tại (1 đ)
Gi ý đáp án:
a.
b.
Câu 4 (1 điểm) : Trình y ngn gọn ý tưởng v bảng băm. Cho biết bảng băm tối ưu
hơn các cấu trúc d liu đã học nào và cho mt ví d minh ha.
Gi ý đáp án:
- Nêu đưc bảng băm phục v cho vic tìm kiếm (0.25 điểm)
- Nêu đưc cách s dụng hàm băm trong việc phân b giá tr (0.25 điểm)
- Nêu được ưu việt ca tìm kiếm trên bảng băm so vi tìm kiếm tun t hay nh
phân (0.25 điểm)
- Cho ví d minh ha đưc (0.25 đim)
HT