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

ĐẠ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: 16 Câu 1( 3 điểm) Tác dụng của hàm băm trong việc tạo một từ điển cài đặt bởi bảng băm, các tiêu chuẩn để lựa chọn một hàm băm. Trình bày các phương pháp băm gấp, băm cắt bỏ, băm lấy phần dư. Cho ví dụ minh họa. Câu 2( 5 điểm ) Cho một cây nhị phân tìm kiếm có các khóa là các số nguyên như hình vẽ. 25 20 15 Anh (chị) hãy: 39 30 21 31 40 35 1) Tạo cây 2) Viết dạng cài đặt cây trên bằng con trỏ. Root là con trỏ trỏ tới gốc của cây 3) Tìm đỉnh có khóa x trên cây 4) Nêu phương pháp để loại bỏ một đỉnh x = 39 trên cây, sao cho cây sau khi loại bỏ đỉnh đó vẫn là cây nhị phân tìm kiếm 5) Hủy cây ……………………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 + Tác dụng của hàm băm h(hash function) : Phân chia các phần tử của tập hợp vào trong các lớp. Nếu x là giá trị khóa của môt phần tử nào đó của tập hợp thì h(x) là chỉ số nào đó của mảng T, h(x) được gọi là giá trị băm của x, ta nói x thuộc lớp h(x); + Các tiêu chuẩn để lựa chọn một hàm băm: - (1 đ) (0.5 đ) Hàm băm phải cho phép tính được dễ dàng và nhanh chóng giá trị băm của mỗi khóa - Phân bố đều các khóa vào các lớp + Một số phương pháp băm: phương pháp băm gấp: (0.5 đ) Giả sử khóa là số nguyên, ta phân chia khóa thành một số phần, sau đoa kết hợp các phần lại bằng một phương pháp nào đó(có thể dùng phép cộng hoặc phép nhân) để nhận được giá trị băm Ví dụ: Nếu khóa là số nguyên gồm 10 chữ số, N= 1000, ta phân thành các nhóm 3,3,2,2 chữ số từ bên trái và công các nhòm lại, sau đó cắt cụt nếu cần thiết, ta sẽ nhận được giá trị băm 1229876087 được biến đổi thành: 122+987+60+87=1256, do ó ta có giá trị băm là: 256 Phương pháp băm cắt bỏ: (0.5 đ) Giả sử khóa là số nguyên ( nếu khóa không là số nguyên ta xét đến mã của chúng). Ta sẽ bỏ đi một phần nào đó của khóa và lấy phần còn lại làm giá trị băm của khóa Ví dụ:: Nếu khóa là số nguyên gồm 10 chữ số, N= 1000, ta lấy các chữ số thứ nhất, thứ 3, thứ 6 làm giá trị băm, giả sử khóa x= 1229876087 ta có h(x) = 126 là giá trị băm Phương pháp băm lấy phần dư(0.5 đ) Giả sử khóa là số nguyên, và giả sử ta muốn chia tập hợp các khóa thành N lớp. Ta chia khóa cho N, rồi lấy phần dư làm giá trị băm. Ví dụ: Viết một hàm băm để băm các khóa là các xâu ký tự có độ dài 10 thành các giá trị từ 0 đến N-1 Type keytype= string[10]; Function h(x: keytype): 0..N-1; Var I,sum:integer; Begin Sum:=0; For i:=1 to 10 do Sum:=Sum+ord(x[i]); H:= Sum mod N; End; Câu 2 + Dạng cài đặt cây: (1 đ) Type TreeBSearch = ^Nut; Nut = Record Infor: Integer; Left, Right: TreeBSearch; End; Var T : TreeBSearch; 1) Tạo cây nhị phân tìm kiếm: - (1 đ) Viết thủ tục thêm một đỉnh x vào cây T: Insert(x, T): * 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 - Trong khi điều kiện nhập chưa thỏa mãn tính dừng (x<>0):  Nhập dữ liệu mới cần thêm x,  Liên tiếp gọi thủ tục thêm đỉnh mới vào cây: Insert(x,T); 2) Tìm xem trên cây T có nút chứa thông tin = x không: Search(x, T) - Nhâp x = ? - Nếu cây rỗng (T = nil): Thông báo không tìm thấy - Nếu cây không rỗng: (1 đ) a) Sử dụng con trỏ phụ M di chuyển đến các đỉnh trên cây bắt đầu từ gốc: b) Nếu M^.info = x: thông báo tìm thấy(found := true), thoát c) Nếu (x - Xem thêm -