Tài liệu Đề thi tham khảo môn cấu trúc dữ liệu và giải thuật 17

ĐẠI HỌC THÁI NGUYÊN ĐỀ THI HẾT HỌC PHẦN KHOA CÔNG NGHỆ THÔNG TIN 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 đề Mã đề thi: 17 Câu 1( 3 điểm) Trình bày một phương pháp cài đặt cây nhị phân tìm kiếm. Dựng một cây nhị phân tìm kiếm có 13 nút, các đỉnh nhận giá trị là các số chẵn 2, 4, 6, … Viết thuật toán thêm một đỉnh mới x = 13 vào cây nhị phân tìm kiếm với cách cài đặt trên và minh hoạ trên cây vừa dựng. Kết quả của từng phép duỵệt cây theo thứ tự trước, giữa, sau Câu 2( 3 điểm ) Anh (chi) hãy viết dạng cài đặt từ điển bởi bảng băm đóng. Nếu thêm một từ vào từ điển cài đặt bởi bảng băm đóng thì khi nào xảy ra hiện tượng đụng khóa, ví dụ minh họa. Khi nào cần băm lại, Hãy trình bày các phương pháp băm lại. Câu 3 (2 điểm) Nêu các cách cài đặt danh sách? viết dạng cài đặt tương ứng? ưu nhược điểm của từng cách cài đặt. ……………………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ộ Câu 1 + Có thể cài đặt cây NPTK bởi con trỏ như sau: (0.5 đ) Dạng cài đặt cây: Type TreeBSearch = ^Nut; Nut = Record Infor: Integer; Left, Right: TreeBSearch; End; Var T : TreeBSearch; + Dựng một cây NPTK có 13 nút, lưu các số nguyên chẵn, cây sau khi thêm đỉnh 13 như hình vẽ: (0.5 đ) 26 14 8 2 40 16 10 13 30 36 42 32 38 34 + Thủ tục thêm đỉnh x= 13 vào cây T: Insert(x, T): (1 đ) * Sử dụng con trỏ phụ M chứa địa chỉ của nút cần thêm * Xin MT cấp phát ô nhớ cho M * Đổ dữ liệu cần thêm vào ô nhớ có địa chỉ M * Gắn M vào cây: Nếu Cây rỗng (T = nil): T := M Nếu cây không rỗng: Xác định vị trí thêm M: If (xT^.info) then Insert(x, T^.right); else thông báo x đã có trên cây + Kết quả duyệt cây theo thứ tự trước, giữa, sau: (1 đ) - Trước: 26 14 8 2 10 13 16 40 36 32 30 34 28 42 - Giữa: 2 8 10 13 14 16 26 30 32 34 36 38 40 42 - Sau: 2 13 10 8 16 14 30 34 32 38 36 42 40 26 Câu 2 + Dạng cài đặt từ điển bởi bảng băm đóng: (0.5 đ) type Dictionary = array[0..N-1] of keytype; var T: dictionary; + Đụng khóa, giải quyết đụng khóa(1 đ) - Dụng khóa xảy ra khi thêm một phần tử vào từ điển: Giả sử muồn thêm phần tử có khóa x và từ điển T, ta muốn đặt khóa x vào thành phần T[h(x)] của mảng, như ở vị trí đó đã lưu giữ một giá trị khóa khác, hoàn cảnh này còn gọi là sự va chạm (đụng khóa) Ví dụ: N=10, các khóa a,b,c,d,e có các giá trị băm như sau: h(a)=7, h(b)=1, h(c)=4, h(d)=3, h(e)=3, Giả sử ban đầu bảng rỗng, tức là tất cả các thành phần của bảng đều chứa giá trị rỗng.ta đưa lần lượt các giá trị khóa a,b,c,d,e vào bảng, khi đó a,b,c,d lần lượt được đặt vào vị trí 7,1,4,3. Vì h(e)=3,ta tìm đến vị trí thứ 3 của mảng, ta thấy vị trí này đã chứa d => xẩy ra hiện tượng đụng khóa khi thêm e vào bảng. - Khi xảy ra hiện tượng đụng khóa ta cần băm lại: ta lần lượt xét các vị trí h1(x), h2(x),…..hi(x) – băm lại lần thứ i cho đến khi nào tìm thấy vị trí trống để đặt x vào. Nếu không tìm được vị trí trống, ta nói bảng đã đầy không thể thêm x được nữa , + Một số phương pháp băm lại: (1.5 đ) a) Băm lại tuyến tính Các hàm hi(x) được xác định như sau: hi(x) = (h(x) = i ) mod N Tức ta xem mảng là mảng vòng tròn và lần lượt xét đến các vị trí h(x)+1, h(x)+2, …… b) Băm lại bình phương hi(x) = (h(x) + i2) mod N Câu 3 Tương tự câu 3 mã đề 04