Nội dung bài viết

    Xem thêm

    Chuyên đề Tin học 12 Bài 1 (Cánh diều): Giới thiệu cây nhị phân

    Với giải bài tập Chuyên đề Tin học 12 Bài 1: Giới thiệu cây nhị phân sách Cánh diều 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 1.

    1 113 12/08/2024
    Trang trước
    Chia sẻ
    Trang sau  

    Giải Chuyên đề Tin học 12 Bài 1: Giới thiệu cây nhị phân

    Khởi động trang 29 Chuyên đề Tin học 12: Em hãy quan sát một nhánh cây phả hệ ở Hình 1 và cho biết Bình phải xưng hô với An như thế nào?

    Em hãy quan sát một nhánh cây phả hệ ở Hình 1 và cho biết Bình phải xưng hô với An như thế nào

    Lời giải:

    Sau khi quan sát một nhánh cây phả hệ ở Hình 1 ta thấy Bình phải xưng hô với An là bác bởi vì Bình là con của chú Hiền và chú hiền là em của bố An.

    Hoạt động 2 trang 31 Chuyên đề Tin học 12: Đội tuyển Argentina đã giành chức vô địch World Cup 2022. Dựa vào hình minh hoạ ở Hình 6, em hãy vẽ cây trong tin học biểu diễn kết quả thi đấu World Cup 2022 các trận đấu từ vòng đấu loại 1:16 đến hết trận chung kết với cấu trúc như sau

    - Gốc của cây là đội vô địch.

    - Mỗi nút ngoại trừ các nút lá có đúng hai nút con tương ứng với hai đội tham gia trận đấu loại trực tiếp. Khoá của các nút trong là tên đội bóng giành chiến thắng. Khoá của các nút lá là tên các đội bóng ghép đấu với nhau ở vòng 1:16.

    Đội tuyển Argentina đã giành chức vô địch World Cup 2022. Dựa vào hình minh hoạ ở Hình 6

    Lời giải:

    Đội tuyển Argentina đã giành chức vô địch World Cup 2022. Để biểu diễn kết quả thi đấu World Cup 2022 từ vòng 1:16 đến trận chung kết dưới dạng cây, ta sẽ vẽ cây nhị phân với gốc là đội vô địch. Mỗi nút trong của cây sẽ có hai con, tương ứng với hai đội đã đấu với nhau trong một trận loại trực tiếp. Tên của các nút trong là đội thắng trận, còn tên các nút lá là các đội tham gia từ vòng 1:16.

    Các đội được ký hiệu bằng các chữ cái tương ứng với mỗi nút:

    A: Argentina

    M: Morocco

    P: Portugal

    E: England

    J: Japan

    N: Netherlands

    B: Brazil

    C: Croatia

    F: France

    K: South Korea

    S: Spain

    D: Senegal

    U: USA

    R: Australia

    W: Switzerland

    L: Poland

    Cây biểu diễn kết quả World Cup 2022 từ vòng 1:16 đến chung kết như sau:

    Đội tuyển Argentina đã giành chức vô địch World Cup 2022. Dựa vào hình minh hoạ ở Hình 6

    Vận dụng trang 36 Chuyên đề Tin học 12: Em hãy đưa ra danh sách các thành viên gia đình có mối quan hệ được biểu diễn dưới dạng cây trong Hình 17 (còn được gọi là cây phả hệ ngược) theo các thứ tự trước, sau và giữa.

    Em hãy đưa ra danh sách các thành viên gia đình có mối quan hệ được biểu diễn dưới dạng cây

    Lời giải:

    Danh sách các thành viên gia đình có mối quan hệ được biểu diễn dưới dạng cây trong Hình 17 (còn được gọi là cây phả hệ ngược) theo các thứ tự trước, sau và giữa:

    Trước: Ổng nội, bà nội, ông ngoại, bà ngoại

    Giữa: Bố Thái, mẹ Trà

    Sau: Bé Tũn

    Câu hỏi tự kiểm tra 1 trang 36 Chuyên đề Tin học 12: Trong các câu sau, những câu nào SAI?

    a) Nút trong của cây có ít nhất một nút con.

    b) Nút lá của cây là nút không có nút con.

    c) Sử dụng các cách duyệt cây khác nhau trên cùng một cây sẽ cho cùng một dãy kết quả.

    d) Số lượng nút giả cần bổ sung thêm trong trường hợp tồi nhất khi dùng mảng một chiều để biểu diễn cây nhị phân có chiều cao h là Trong các câu sau, những câu nào SAI trang 36 Chuyên đề Tin học 12 - h - 2 nút.

    Lời giải:

    Các câu sai là: c và d, vì:

    c) Cách duyệt cây bằng các cách khác nhau sẽ cho ra các dãy kết quả khác nhau. (duyệt trước, duyệt giữa, duyệt sau, duyệt theo mức)

    d) Công thức được đưa ra trong câu này là sai. Công thức cho số lượng nút giả cần bổ sung để biểu diễn một cây nhị phân hoàn chỉnh trong một mảng một chiều thường là 2h+1 - 1 - n, với nnn là số lượng nút thực tế trong cây, không phải 2h+1 - h - 2.

    Câu hỏi tự kiểm tra 2 trang 36 Chuyên đề Tin học 12: Tổng số nút của một cây nhị phân hoàn hảo chiều cao 3 là bao nhiêu?

    A.7.

    B. 8.

    C. 15.

    D. 16.

    Lời giải:

    Đáp án đúng là C. 15, vì:

    Muốn tính tổng số nút của một cây nhị phân hoàn hảo chiều cao 3 ta sử dụng công thức tổng quát:

    Tổng số nút = 2chiều cao+1 -1

    Trong trường hợp này, chiều cao của cây là 3, vì vậy ta có:

    Tổng số nút = 23+1-1=24-1=16-1=15

    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 113 12/08/2024
    Trang trước
    Chia sẻ
    Trang sau  

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