Đề thi Cấu trúc dữ liệu và giải thuật - Đề 3 | Trường Đại học CNTT Thành Phố Hồ Chí Minh

Đề thi Cấu trúc dữ liệu và giải thuật - Đề 3 | Trường Đại học CNTT Thành Phố Hồ Chí Minh được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!

71 36 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu và giải thuật (IT003)

Trường: Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh

Thông tin:

1 trang 7 tháng trước

Tác giả:

Profile Mai Nguyệt
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
ĐỀ Ệ THI CUỐI KỲ MÔN CẤU TRÚC DỮ LI U VÀ GIẢI THUẬT
Thời gian: 90 phút
(Không s d ng tài li ử ụ ệu)
Câu 1 ( m) 3 điể : Cho dãy s 17 72 99 32 58 70 44 12 23 ố ban đầu như sau :
Hãy th n các yêu c u sau: ực hiệ ầ
a. Hãy trình bày các bướ .5 đc thực hiện thuật toán ch n tr p ọ ực tiế (1 )
b. Vẽ hình t c th c hi n c a thu t toán ừng bướ ự ệ ủ ậ trên để s p x p dãy s theo th t ắ ế ố ứ ự
giảm dần (không c n l p trình) (1 ) ầ ậ .5 đ
Câu 2 (4 m) điể : Cho dãy các ký t ự như sau : A B C D E F W Z U T K
Hãy th n các yêu c u sau: ực hiệ ầ
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 t các ký t sau vào cây N, G, H , M , L ần lượ ự để hình thành cây nhị phân
tìm ki i, vếm mớ ẽ hình cây khi thêm t ng ký t vào cây (1 ) ừ ự đ
c. Trình bày dãy k t k t q t cây theo th t NRL, LRN ỹ ự ế ủa khi duyệ ứ ứ (1 đ)
d. Vẽ hình cây khi xóa l W, E, H, C ần lượt các ký tự (1 đ)
Lưu ý : trong qúa trình b xung hay xóa m t nút trên cây, n u có x y ra m t cân b ng thì ổ ộ ế ả ấ ằ
cho biết trường h p m ng là lo i gì và n hành cân b ng l cây. ợ ất cân bằ ạ tiế ằ ại
Câu 3 (2 m) : điể Cho m t danh sách liên k s n ph m trong mộ ết đôi đã lưu thông tin về ả ẩ ột
công ty, bao gồm:
1.Mã s n ph m (ki u s nguyên) ả ẩ ể ố
2.Tên sản ph m (ki u chu ẩ ể ỗi)
3.Chủng lo ng Gi y, b ng Kim lo i, b ng Nh a) ại (bằ ấ ằ ạ ằ ự
4.N kiăm sản xuất ( ểu s nguyên) ố
5.Số năm bảo hành (kiểu số nguyên)
Hai con trỏ Head, Tail đang trỏ đến ph n t u tiên và cu i cùng trong danh sách trên. ầ ử đầ ố
Hãy th n các yêu c u sau : ực hiệ ầ
a. Viết hàm s p x p các s n ph m theo mã s n ph m gi m d n (1 ) ắ ế ả ẩ ả ẩ ả ầ đ
b. s Viết hàm xóa các ản ph t h n b o hành ra kh i danh sách khi thẩm đã hế ạ ả ỏ ỏa điều
kiện : Năm sả năm bảo hành > Năm hiện xuất + Số n tại (1 đ)
Câu 4 (1 m) : điể Trình bày ng n g ng v b t bắ ọn ý tưở ề ảng băm. Cho biế ảng băm tối ưu
hơn các cấ ệu đã họu trúc dữ li c nào và cho một ví dụ ọ minh h a.
HẾT
| 1/1
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
ĐỀ THI CUỐI KỲ MÔN CẤU TRÚC DỮ L Ệ
I U VÀ GIẢI THUẬT
Thời gian: 90 phút
(Không sử dụng tài liệu )
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 thực hiện các yêu cầu sau:
a. Hãy trình bày các bước thực hiện thuật toán chọn trực tiếp (1.5 đ)
b. Vẽ hình từng bước thực hiện của thuật toán trên để sắp xếp dãy số theo thứ tự
giảm dần (không cần lập trình) (1.5 đ)
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 thực hiện các yêu cầu 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 mới, vẽ hình cây khi thêm từng ký tự vào cây (1 đ)
c. Trình bày dãy kỹ tự kết qủa khi duyệt 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 một nút trên cây, nếu có xảy ra mất cân bằng thì
cho biết trường hợp mất cân bằng là loại gì và tiến hành cân bằng lại c ây.
Câu 3 (2 điểm) : Cho một danh sách liên kết đôi đã lưu thông tin về sản phẩm trong một công ty, bao gồm:
1.Mã sản phẩm (kiểu số nguyên)
2.Tên sản phẩm (kiểu chuỗi )
3.Chủng loại (bằng Giấy, bằng Kim loại, bằng Nhựa) 4.Năm sản xuất k ( iểu số nguyên)
5.Số năm bảo hành (kiểu số nguyên)
Hai con trỏ Head, Tail đang trỏ đến phần tử đầu tiên và cuối cùng trong danh sách trên.
Hãy thực hiện các yêu cầu sau :
a. Viết hàm sắp xếp các sản phẩm theo mã sản phẩm giảm dần (1 đ)
b. Viết hàm xóa các sản phẩm đã hết hạn bảo hành ra khỏi danh sách khi thỏa điều
kiện : Năm sản xuất + Số năm bảo hành > Năm hiện tại (1 đ)
Câu 4 (1 điểm) : Trình bày ngắn 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ữ liệu đã học nào và cho một ví dụ minh họa. HẾT