tailieunhanh - Đề thi giữa kì 1 môn: Cấu trúc dữ liệu và giải thuật

Ghi chú: đề thi gồm tất cả 7 câu. Sinh viên lớp KSTN làm hết 7 câu, thang điểm 12/12. Sinh viên lớp thường làm 6 câu (từ câu 1 đến câu 6), thang diểm 10/10. Câu 1 ( điểm): Tính toán big-O của các hàm dưới đây và sắp xếp chúng theo thứ tự từ nhỏ đến lớn theo big-O: Đáp áp: a) (1 điểm) Tính big-O a. 2 = O(2 ) b. n! = O(n!) c. = O() d. n + n2 + n3 = O(n3) e. 105 = O(1) f. 150,000 = O(1) g. nlog2(n) = O(nlog2(n)) n. | Trường ĐH Bách Khoa ĐÁP ÁN Khoa KH KT Máy tính Đề thi giữa kỳ HK1 2009 Môn Cấu trúc dữ liệu và Giải thuật Thời gian 60 phút Không sử dụng tài liệu Ghi chú đề thi gồm tất cả 7 câu. Sinh viên lớp KSTN làm hết 7 câu thang điểm 12 12. Sinh viên lớp thường làm 6 câu từ câu 1 đến câu 6 thang diểm 10 10. Câu 1 điểm Tính toán big-O của các hàm dưới đây và sắp xếp chúng theo thứ tự từ nhỏ đến lớn theo big-O Đáp áp a 1 điểm Tính big-O a. 2n O 2n b. n O n c. n3 5 O n35 d. n n2 n3 O n3 e. 105 O 1 f. 150 000 O 1 g. nlog2 n O nlog2 n b điểm Sắp xếp theo big-O 105 150 000 nlog2 n n n2 n3 n3-5 2n n Câu 2 điểm Cho một DSLK đơn gồm các số nguyên có cấu trúc như hình bên. Trong đó mỗi thành phần của DSLK đơn là một cấu trúc có data là số nguyên và con trỏ link trỏ đến phần tử kế tiếp. DSLK đơn chỉ dùng một con trỏ head để chỉ đến phần tử đầu tiên của danh sách. Nếu danh sách rỗng con trỏ head này là null. Viết một phương thức bằng pseudocode nhận vào một số nguyên tìm trong DSLK đơn và loại bỏ đi các phần tử có giá trị bằng hoặc hơn số nguyên này 1 hoặc 2. Lưu ý không dùng thêm bất kỳ phương phức hoặc hàm Node data int link pointer end Node Linked List head pointer end Linked List phụ trợ nào kể cả tự viết lại . Ví dụ với danh sách là 12 13 5 6 -8 9 7 -2 5 -1 6 -3 và số nguyên nhận được là 5 thì danh sách kết quả là 12 13 -8 9 -2 -1 -3 tức là các phần tử 5 6 7 bị xóa đi. Đáp áp algorithm remove_in_range val x int Post Các phần tử có data y sao cho y-x là 0 1 2 bị xóa đi 1. pre null tmp head 2. loop tmp is not null 1. if tmp- data x or tmp- data x 1 or tmp- data x 2 1. if pre is null delete first 1. head head- link 2. delete tmp 3. tmp head 2. else delete the element after pre 1. pre- next tmp- link 2. delete tmp 3. tmp pre- link 3. end if 2. else 1. pre tmp 2. tmp tmp- link 3. end if 3. end loop end remove_in_range Câu 3 2 điểm Viết một hàm toàn cục global function bằng pseudocode nhận vào một queue và đảo ngược queue đó. Giả sử rằng các phương thức của queue và .

• Cơ sở dữ liệu
• cấu trúc dữ liệu
• đề kiểm tra cấu trúc dữ liệu
• cấu trúc máy tính
• ôn tập cấu trúc dữ liệu
• ôn tập giải thuật
• ôn thi cấu trúc và giải thuật
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình 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
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp