TAILIEUCHUNG - Đề thi hết môn học kỳ I năm học 2016-2017 môn Cấu trúc dữ liệu và giải thuật - ĐH Công nghệ

Đề thi hết môn học kỳ I năm học 2016-2017 môn Cấu trúc dữ liệu và giải thuật giúp cho các bạn sinh viên nắm bắt được cấu trúc đề thi, dạng đề thi chính để có kế hoạch ôn thi một cách tốt hơn. Tài liệu hữu ích cho các các bạn sinh viên đang theo học chuyên ngành Công nghệ thông tin và những ai quan tâm đến môn học này dùng làm tài liệu tham khảo. | Đề thi CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Học kỳ I 2016-2017 Thời gian 100 phút Lưu ý Đề thi có 02 trang. Sinh viên không được sử dụng tài liệu. Câu 1 1 điểm a. Sắp xếp độ phức tạp tính toán ký hiệu O theo thứ tự tăng dần O n O 1 O 2n O O n2 O log2n O n3 . b. Tìm độ phức tạp tính toán cho hàm count dưới đây int count int n int result 0 while n 0 result 1 n 2 return result Câu 2 1 điểm Giả sử có ngăn xếp stack S gồm các giá trị 1 2 3 trong đó 3 ở đầu ngăn xếp bên phải và có một hàng đợi queue Q rỗng với đầu hàng đợi ở bên phải và đuôi ở bên trái . Chỉ sử dụng S Q và thêm một biến duy nhất nếu cần không được sử dụng thêm bất kỳ cấu trúc dữ liệu nào khác hãy liệt kê các thao tác để có được ngăn xếp S như sau a. 1 3 b. 3 2 1 Câu 3 1 5 điểm Theo ký hiệu O hãy cho biết a. Thời gian tìm kiếm trung bình một phần tử trong mảng array của n phần tử đã được sắp xếp là bao nhiêu b. Thời gian tìm kiếm trung bình một phần tử trong danh sách liên kết đơn single linked-list của n phần tử đã được sắp xếp là bao nhiêu c. Thời gian tìm kiếm trung bình một phần tử trong bảng băm hash table có n phần tử là bao nhiêu d. Thời gian tìm kiếm xấu nhất một phần tử trong cây tìm kiếm nhị phân binary search tree có n đỉnh là bao nhiêu e. Thời gian tìm kiếm xấu nhất một phần tử trong cây cân bằng AVL có n đỉnh là bao nhiêu g. Thời gian tìm kiếm xấu nhất một phần tử trong cây thứ tự bộ phận heap có n đỉnh là bao nhiêu Câu 4 1 5 điểm a. Hãy sắp xếp mảng các số 1 4 10 9 6 5 3 7 2 8 theo thứ tự tăng dần bằng thuật toán Sắp xếp hòa trộn Merge sort . b. Cho biết độ phức tạp tính toán trung bình và xấu nhất của Sắp xếp hòa trộn c. Thế nào là thuật toán sắp xếp ổn định stable sort Sắp xếp hòa trộn có phải là thuật toán sắp xếp ổn định không 1 Câu 5 2 điểm Cho cây tìm kiếm nhị phân binary search tree - BST T như trong hình vẽ ở dưới bên trái . a. Cho biết thứ tự các đỉnh khi duyệt cây T theo thứ tự trong inorder và theo thứ tự trước preorder . b. Trình bày các bước để .

• Cơ sở dữ liệu
• Đề thi học kỳ
• Cấu trúc dữ liệu và giải thuật
• Đề thi Cấu trúc dữ liệu và giải thuật
• Bài tập Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Đề thi cuối học kỳ hè
• Đề thi học kỳ 1 môn Lý
• Đề thi học kỳ 1 lớp 8
• Đề thi học kỳ 1
• Đề thi học kỳ Vật lý 8
• Đề thi học kỳ Vật lý
• Đề thi học kỳ lớp 8
• Đề thi học kỳ 2
• Đề kiểm tra học kỳ
• Đề kiểm tra học kỳ 2 lớp 7
• Đề thi học kỳ Mĩ thuật 7
• Đề thi học kỳ môn Mĩ thuật
• Đề thi học kỳ lớp 7
• Đề kiểm tra học kỳ 1 lớp 8
• Đề thi học kỳ Mĩ thuật 8
• Đề kiểm tra học kỳ 2 lớp 9
• Đề thi học kỳ Mĩ thuật 9
• Đề thi học kỳ lớp 9
• Đề kiểm tra học kỳ 1 lớp 7