Tiêu đề Cau_truc_de_IT003.docx ✅

LÝ THUYẾT THI TỰ LUẬN Làm trực tiếp trên đề - Không tham khảo tài liệu Phần 1. - Chạy từng bước các thuật toán tìm kiếm, sắp xếp. - Viết code trên giấy => viết hàm. Phân tích input và output Nội dung thi lý thuyết: - D/s liên kết đơn => data là cấu trúc - Stack, queue - Hashtable - Cây nhị phân tìm kiếm - Thuật toán tìm kiếm, sắp xếp Ví dụ: Trình bày chạy từng bước thuật toán tìm kiếm tuyến tính: i 0 1 2 3 4 16 78 50 66 38 Minh họa tìm kiếm 66: Bước i = 0: 16 khác 66 => chưa tìm thấy Bước i = 1: 78 khác 66 => chưa tìm thấy Bước i = 2: 50 khác 66 => chưa tìm thấy Bước i = 3: 66 bằng 66 => Đã tìm thấy. Kết thúc quá trình tìm kiếm. Ví dụ: Trình bày chạy từng bước thuật toán tìm kiếm nhị phân: i 0 1 2 3 4 16 23 31 56 62 Tìm kiếm giá trị 56 Bước 1: L = 0 R = 4 => mid = (0+4)/2 = 2 => 31 != 56 chưa tìm thấy
Bước 2: L = 2+1=3 R = 4 => mid = (3+4)/2=3 => 56 = 56 tìm thấy. Kết thúc. Ví dụ: Trình bày chạy từng bước thuật toán chọn trực tiếp: i 0 1 2 3 4 3 2 5 1 4 Bước i = 0: (Vị trí min = 3). Hoán vị 1, 3. Kết quả: 1 2 5 3 4 Bước i = 1: (Vị trí min = 1). Hoán vị 2, 2. Kết quả: 1 2 5 3 4 Bước i = 2: (Vị trí min = 3). Hoán vị 3, 5. Kết quả: 1 2 3 5 4 Bước i = 3: (Vị trí min = 4). Hoán vị 4, 5. Kết quả: 1 2 3 4 5 Phần 2. - Đọc code ghi kết quả. Cấp phát động, tất cả các kiểu dữ liệu cấp phát động - Xem lại cấp phát động trong slide bài giảng Buổi 1 - Ví dụ Chương trình Kết quả #include <iostream> using namespace std; int main() { int a[] = {1,3,5,7,9,2,4,6,8}; cout << *(a + 3) + *(a + 7); return 0; } Chương trình Kết quả #include <iostream> using namespace std; int main() { int a = 102, b, *p; p = &a; b = (*p)++; cout << a << " _ " << b; return 0;
}
ÔN TẬP THỰC HÀNH Nội dung: - D/s liên kết đơn => data là cấu trúc - Stack, queue - Hashtable - Cây nhị phân tìm kiếm