Nội dung bài viết

    Xem thêm

    Chuyên đề Tin học 12 Bài 2.1 (Chân trời sáng tạo): Cây và cây nhị phân

    Với giải bài tập Chuyên đề Tin học 12 Bài 2.1: Cây và cây nhị phân sách Chân trời sáng tạo hay nhất, chi tiết giúp học sinh dễ dàng làm bài tập Chuyên đề học tập Tin học 12 Bài 2.1.

    1 212 24/07/2025
    Trang trước
    Chia sẻ
    Trang sau  

    Giải Chuyên đề Tin học 12 Bài 2.1: Cây và cây nhị phân

    Khởi động trang 26 Chuyên đề Tin học 12: Quan sát sơ đồ tổ chức của một công ty ở Hình 1 và cho biết các phòng ban chức năng trong công ty được tổ chức như thế nào.

    Quan sát sơ đồ tổ chức của một công ty ở Hình 1 và cho biết

    Lời giải:

    Quan sát sơ đồ tổ chức của một công ty ở Hình 1 ta thấy các phòng ban chức năng trong công ty được tổ chức theo hình cây. Có gốc là nút “giám đốc” và cá nút con như “Phòng tổ chức”, “Phòng kinh doanh”, “Phòng kế toán”.

    1. Giới thiệu cây, cây nhị phân

    Câu hỏi trang 28 Chuyên đề Tin học 12: Cho các cây như ở Hình 3. Cho biết:

    a) Nút gốc, nút nhánh, nút lá ở Hình 3a:

    b) Mức và chiều cao của cây trong Hình 3b

    Lời giải:

    a) Nút gốc, nút nhánh, nút lá ở Hình 3a:

    - Nút gốc là: 2

    - Nút nhánh là: 24, 11, 20, 8.

    - Nút lá là: 83, 3, 10, 15, 9.

    Cho các cây như ở Hình 3. Cho biết: Nút gốc, nút nhánh, nút lá ở Hình 3a

    b) Mức và chiều cao của cây trong Hình 3b

    Mức của cây là: 1, nút gốc ở mức 0.

    Chiều cao của cây là: 3

    Câu hỏi trang 29 Chuyên đề Tin học 12: Cho biết cây nào ở Hình 3 là cây nhị phân.

    Lời giải:

    Hình 3b là cây nhị phân. Vì mỗi nút của cây có tối đa hai cây con (cây con trái và cây con phải).

    2. Biểu diễn cây nhị phân

    Câu hỏi trang 31 Chuyên đề Tin học 12: Xây dựng mảng một chiều biểu diễn cây ở Hình 7.

    Xây dựng mảng một chiều biểu diễn cây ở Hình 7 trang 31 Chuyên đề Tin học 12

    Lời giải:

    Xây dựng mảng một chiều biểu diễn cây ở Hình 7 như sau: [20, 24, 12, 2, 4, 11, 13, 38, 8, 9]. Trong đó 20 là nút gốc. Mảng được duyệt theo chiều rộng của cây, từ trên xuống dưới, từ trái sang phải.

    Luyện tập 1 trang 31 Chuyên đề Tin học 12: Biểu diễn cấu trúc các tập bao lồng nhau trong Hình 8 dưới dạng cây. Cho biết cây vừa nêu có mấy nút lá.

    Biểu diễn cấu trúc các tập bao lồng nhau trong Hình 8 dưới dạng cây

    Lời giải:

    Biểu diễn cấu trúc các tập bao lồng nhau trong Hình 8 dưới dạng cây như sau:

    Biểu diễn cấu trúc các tập bao lồng nhau trong Hình 8 dưới dạng cây

    Cây vừa nêu có 2 mấy nút lá là: C, D, E, F.

    Luyện tập 2 trang 31 Chuyên đề Tin học 12: Hãy vẽ một cây nhị phân có chiều cao là 4; sau đó, xây dựng mảng một chiều để biểu diễn cây này.

    Lời giải:

    a) Vẽ một cây nhị phân có chiều cao là 4 như sau:

    Hãy vẽ một cây nhị phân có chiều cao là 4; sau đó, xây dựng mảng một chiều để biểu diễn

    b) Xây dựng mảng một chiều để biểu diễn cây này:

    [A, B, C, D, E, F, G, H, I, K, N, M, L, O, P]

    Vận dụng trang 31 Chuyên đề Tin học 12: Cho mảng một chiều A biểu diễn cho một cây nhị phân hoàn chỉnh như sau:

    2

    24

    11

    8

    3

    8

    9

    1

    2

    3

    4

    Chỉ ra các nút con của rút có giá trị là 11.

    Lời giải:

    Mảng biểu diễn cây nhị phân như sau:

    Mảng

    2

    24

    11

    8

    3

    8

    9

    1

    2

    3

    4

    Thứ tự

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    Ta thấy nút có giá trị là 11 nằm ở vị trí thứ 3 trong mảng.

    Xác định các nút con của nút tại vị trí 3

    - Nút con trái của nút tại vị trí i hay còn gọi là vị trí số 3 sẽ nằm ở vị trí 2*i = 2*3=6

    - Nút con phải của nút tại vị trí i hay còn gọi là vị trí số 3 sẽ nằm ở vị trí 2*i + 1=2*3+1=7

    Giá trị của các nút con tại vị trí 6 có giá trị là 8. Nút tại vị trí 7 có giá trị là 9.

    Vậy, các nút con của nút có giá trị 11 là: Nút con trái: 8. Nút con phải: 9

    Xem thêm các bài giải Chuyên đề Tin học 12 sách Chân trời sáng tạo hay, chi tiết khác:

    Bài 2.2: Các phép toán duyệt cây nhị phân

    Bài 2.3: Cây tìm kiếm nhị phân

    Bài 2.4: Thực hành cây tìm kiếm nhị phân

    Bài 3.1: Các khái niệm cơ bản của đồ thị

    Bài 3.2: Biểu diễn đồ thị

    Tham khảo các loạt bài Tin học 12 khác:

    Bài viết cùng lớp mới nhất

    Xem thêm
    1 212 24/07/2025
    Trang trước
    Chia sẻ
    Trang sau  

    Xem thêm các chương trình khác: