1. Trang chủ
  2. Lớp 12
  3. Tin học
  4. Giải chuyên đề Tin 12 KNTT Bài 11: Khái niệm đồ thị có đáp án

Giải chuyên đề Tin 12 KNTT Bài 11: Khái niệm đồ thị có đáp án

Giải chuyên đề Tin 12 KNTT Bài 11: Khái niệm đồ thị có đáp án

  • 30 lượt xem

  • 14 câu hỏi


Câu 1:

Năm 1736, nhà bác học Euler đưa ra bài toán, được gọi là bài toán 7 cây cầu ở Königsberg. Tại thành phố cổ Königsberg của nước Phổ cũ (nay thuộc nước Nga) có dòng sông Pregel vắt ngang qua, chia thành phố thành các vùng riêng biệt. Bài toán Euler đặt ra là làm sao đi qua tất cả 7 cây cầu này, mỗi cầu chỉ được phép đi qua đúng một lần.

Em hãy giải bài toán trên.

Có thể dùng mô hình dữ liệu nào để mô phỏng bài toán này?

Câu 2:

1. Trao đổi, thảo luận về mô hình đồ thị, các khái niệm cơ bản của đồ thị và trả lời câu hỏi: Bài toán trong phần khởi động có thể biểu diễn được bằng mô hình đồ thị không?

2. Em hãy tìm một số bài toán thực tế khác có thể biểu diễn được bằng đồ thị.

Câu 3:

Cây, cây nhị phân và cây tìm kiếm nhị phân có là mô hình đồ thị không?

Câu 4:

Vẽ đồ thị vô hướng G = (V, E) sau:

V = [0, 1, 2, 3, 4]

E = [{0,1}, {0,4}, {1,2}, {1,3}, {2,4}] 

Câu 5:

Mô tả tập hợp đỉnh V và tập hợp cạnh E của đồ thị vô hướng trong Hình 11.7.

Mô tả tập hợp đỉnh V và tập hợp cạnh E của đồ thị vô hướng trong Hình 11.7. (ảnh 1)

Câu 6:

Đọc, trao đổi và thảo luận các khái niệm, định nghĩa liên quan đến đồ thị. Quan sát đồ thị ở Hình 11.8 và thực hiện các yêu cầu sau:

1. Kể tên các đỉnh kề với D.

2. Hãy cho biết bậc của đỉnh A.

3. Liệt kê một vài đường đi từ đỉnh A đến đỉnh E.

Đọc, trao đổi và thảo luận các khái niệm, định nghĩa liên quan đến đồ thị. Quan sát đồ thị ở Hình 11.8 và thực hiện các yêu cầu sau: (ảnh 1)

Câu 7:

Khi nào một đỉnh của đồ thị có bậc bằng 0?

Câu 8:

Xác định ma trận kề và danh sách kề của các đồ thị ở Hình 11.11.

Xác định ma trận kề và danh sách kề của các đồ thị ở Hình 11.11. (ảnh 1)

Câu 9:

Tìm hiểu một số cách biểu diễn dữ liệu đồ thị trên máy tính. Thảo luận xem cách nào là hợp lí nhất. Hãy biểu diễn dữ liệu của các đồ thị ở Hình 11.12.

Tìm hiểu một số cách biểu diễn dữ liệu đồ thị trên máy tính. Thảo luận xem cách nào là hợp lí nhất. Hãy biểu diễn dữ liệu của các đồ thị ở Hình 11.12. (ảnh 1)

Câu 10:

Thiết lập bộ dữ liệu biểu diễn gồm (n, V, E, A, Adj) cho các đồ thị sau:

Thiết lập bộ dữ liệu biểu diễn gồm (n, V, E, A, Adj) cho các đồ thị sau: (ảnh 1)

Câu 11:

Đồ thị ứng với mô hình bài toán 7 cây cầu ở Königsberg có phải là đơn đồ thị không? Tính bậc của các đỉnh của đồ thị đó.

Câu 12:

Cho đồ thị G vô hướng với ma trận kề như hình bên. Hãy vẽ đồ thị trên.

Cho đồ thị G vô hướng với ma trận kề như hình bên. Hãy vẽ đồ thị trên. (ảnh 1)

Câu 13:

Đồ thị vô hướng G được gọi là đầy đủ nếu giữa hai đỉnh bất kì (khác nhau) đều có cạnh nối. Hãy vẽ và thiết lập ma trận kề của đồ thị đầy đủ với số đỉnh n = 2, 3, 4. 

Câu 14:

Đồ thị trong Hình 11.17 có bao nhiêu thành phần liên thông?

Đồ thị trong Hình 11.17 có bao nhiêu thành phần liên thông? (ảnh 1)

Các bài thi hot trong chương:

0

Đánh giá trung bình

0%

0%

0%

0%

0%

Bình luận


Bình luận
CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK
Giấy chứng nhận ĐKKD số: 0108307822 do Sở KH & ĐT TP Hà Nội cấp lần đầu ngày 04/06/2018
© 2017 Vietjack72. All Rights Reserved.

Đăng ký

Bạn đã có tài khoản? Đăng nhập