• Đề thi Cấu trúc dữ liệu và giải thuật - Mã đề CD 2011 - 01 - Đại học Bách khoa Hà NộiĐề thi Cấu trúc dữ liệu và giải thuật - Mã đề CD 2011 - 01 - Đại học Bách khoa Hà Nội

    Bài 3. a) Cho cây nhị phân tìm kiếm ban đầu như hình thêm lần lượt dãy khóa 43, 12, 36, 78, 29, 16, 9, 65, 27, 32. Hãy vẽ cây nhị phân kết quả thu được cuối cùng (không cần trình bày các bước trung gian). b) Với cây nhị phân tìm kiếm thu được ở phần a, thực hiện xóa lần lượt khóa 18 và 36. Hãy vẽ cây kết quả thu được sau mỗi lần xóa Chú ý: ch...

    pdf2 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 524 | Lượt tải: 1

  • Đề thi Cấu trúc dữ liệu và giải thuật - Mã đề CD 2012 - 03 - Đại học Bách khoa Hà NộiĐề thi Cấu trúc dữ liệu và giải thuật - Mã đề CD 2012 - 03 - Đại học Bách khoa Hà Nội

    Bài 2. Cho cây biểu thức sau a.Duyệt cây biểu thức để đưa ra biểu thức dạng tiền tố, hậu tố b.Với a=36 và b=5, hãy minh họa thuật toán định giá biểu thức hậu tố trên biểu thức hậu tố thu được từ phần a Chú ý: √ là ký hiệu của toán tử căn bậc hai Bài 3. Cây nhị phân tìm kiếm a) Thêm lần lượt các nút 25, 32, 14, 21, 19, 17, 23, 5, 9 vào cây nhị...

    pdf2 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 592 | Lượt tải: 1

  • Bài giảng Cấu trúc dữ liệu và giải thuật - Chương: Các thuật toán nén dữ liệu - Bùi Tiến LênBài giảng Cấu trúc dữ liệu và giải thuật - Chương: Các thuật toán nén dữ liệu - Bùi Tiến Lên

    Thuật toán nén RLE (cont.) Ví dụ 1 Hãy nén chuỗi sau bằng RLE AAABBCCAAADE Sẽ được mã hóa thành 3A2B2C3A1D1E Đánh giá thuật toán RLE Đơn giản, dễ cài đặt Dùng để nén các dữ liệu có nhiều đoạn lặp lại Thích hợp cho dữ liệu ảnh Hiệu suất nén không cao Thuật toán nén LZW Giới thiệu Được đề xuất bởi Ziv and Lempel và cải tiến bởi Welch [L...

    pdf76 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 675 | Lượt tải: 1

  • Bài giảng Cấu trúc dữ liệu và giải thuật - Chương: Bảng băm - Bùi Tiến LênBài giảng Cấu trúc dữ liệu và giải thuật - Chương: Bảng băm - Bùi Tiến Lên

    Các khái niệm Định nghĩa 1 Cho số nguyên dương n 2 N, hai số nguyên a; b 2 Z được gọi là đồng dư theo mô-đun n nếu cả hai có cùng số dư khi chia cho n. Được ký hiệu a ≡ b (modn) Ví dụ 1 Ta có 11 ≡ 8 (mod3) (vì 11 và 8 chia cho 3 đều có số dư là 2) −2 ≡ 5 (mod7) (vì -2 và 5 chia cho 7 đều có số dư là 5) Một số tính chất Tính chất Quan hệ...

    pdf51 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 570 | Lượt tải: 1

  • Bài giảng Cấu trúc dữ liệu và giải thuật - Chương: Cấu trúc dữ liệu cây - Bùi Tiến LênBài giảng Cấu trúc dữ liệu và giải thuật - Chương: Cấu trúc dữ liệu cây - Bùi Tiến Lên

    Ứng dụng của kiểu dữ liệu cây Kiểu dữ liệu cây thể hiện tính “phân cấp”, “kế thừa”. Do đó có thể biểu diễn được những cấu trúc như Cây gia phả (trong các dòng họ) Cây phân cấp các loài (trong sinh học) Cây thư mục (trong máy tính) Ứng dụng của kiểu dữ liệu cây (cont.) Biểu thức toán học có thể được biểu diễn bằng cây. Ví dụ cây dưới đây dùn...

    pdf68 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 536 | Lượt tải: 1

  • Bài giảng Cấu trúc dữ liệu và giải thuật - Chương: Cấu trúc dữ liệu ngăn xếp với hàng đợi - Bùi Tiến LênBài giảng Cấu trúc dữ liệu và giải thuật - Chương: Cấu trúc dữ liệu ngăn xếp với hàng đợi - Bùi Tiến Lên

    Ngăn xếp Định nghĩa 1 Ngăn xếp (stack) là một cấu trúc dữ liệu dùng để lưu trữ một tập hợp các phần tử Hoạt động theo cơ chế “vào sau - ra trước” (last in, first out - LIFO); nghĩa là, ta chỉ thấy và truy cập của đỉnh của ngăn xếp Cấu trúc dữ liệu này được đề xuất bởi hai nhà khoa học người Đức [Bauer and Samelson, 2001] Ngăn xếp (cont.) M...

    pdf33 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 587 | Lượt tải: 1

  • Bài giảng Cấu trúc dữ liệu và giải thuật - Chương: Cấu trúc dữ liệu - Cây đỏ đen - Bùi Tiến LênBài giảng Cấu trúc dữ liệu và giải thuật - Chương: Cấu trúc dữ liệu - Cây đỏ đen - Bùi Tiến Lên

    Cây đỏ đen Định nghĩa 1 Cây đỏ đen (red black tree) được Rudolf Bayer phát minh và là một cây nhị phân tìm kiếm có các đặc điểm sau 1. Mọi nút phải là nút đỏ hoặc nút đen 2. Nút gốc là nút đen 3. Nếu một nút là nút đỏ, thì con của nó phải nút đen 4. Tất cả các đường đi từ nút gốc đến nút-0 (không có con) hoặc nút-1 (có 1 con) phải có cùng s...

    pdf25 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 537 | Lượt tải: 1

  • Bài giảng Cấu trúc dữ liệu và giải thuật - Chương: Hàng đợi ưu tiên - Bùi Tiến LênBài giảng Cấu trúc dữ liệu và giải thuật - Chương: Hàng đợi ưu tiên - Bùi Tiến Lên

    Dẫn nhập Một số ứng dụng kiểu hàng đợi thông thường không thể giải quyết được như Sắp hàng mua vé: thường sẽ ưu tiên cho người già, phụ nữ có thai, người tàn tật Trạm thu phí: thường ưu tiên sẽ cứu thương, xe cứu hỏa Hàng đợi ưu tiên Định nghĩa 1 Hàng đợi ưu tiên (priority queue) là một hàng đợi trong đó mỗi phần tử được gắn với một con số...

    pdf24 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 647 | Lượt tải: 1

  • Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Cấu trúc dữ liệu cây M-nhánh vs B cây - Bùi Tiến LênBài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Cấu trúc dữ liệu cây M-nhánh vs B cây - Bùi Tiến Lên

    Các thao tác trên cây m-nhánh Đối với cây m-nhánh có các thao tác cơ bản trên cây Duyệt từng khóa của cây Tìm một khóa trong cây Thêm một khóa vào cây Xóa một khóa khỏi cây Thao tác duyệt cây Ta có thể xem cây như một đồ thị tổng quát và áp dụng các thuật toán duyệt của đồ thị để duyệt cây. Có hai thuật toán duyệt cơ bản Duyệt theo chiều ...

    pdf55 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 703 | Lượt tải: 1

  • Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 7: Cấu trúc dữ liệu cây AVL - Bùi Tiến LênBài giảng Cấu trúc dữ liệu và giải thuật - Chương 7: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên

    Cây nhị phân tìm kiếm cân bằng (cont.) Ý tưởng Có hai chiến lược cân bằng: Cân bằng theo chu kỳ hoạt động Cân bằng theo thao tác cập nhật Đa số kỹ thuật sử dụng biến đổi xoay để cân bằng lại Các phép biến đổi Để duy trì được sự cân bằng trong cây T, các nhà lập trình thường sử dụng các phép biến đổi sau Phép xoay trái (left rotation) Ph...

    pdf38 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 717 | Lượt tải: 1