Đề ôn tập Tree Cấu trúc dữ liệu và giải thuật | Trường Đại học CNTT Thành Phố Hồ Chí Minh

Đề ôn tập Tree Cấu trúc dữ liệu và giải thuật | Trường Đại học CNTT Thành Phố Hồ Chí Minh được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!

47 24 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu và giải thuật (IT003)

Trường: Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh

Thông tin:

3 trang 5 tháng trước

Tác giả:

Profile Mai Nguyệt
Cho biết cây B-Tree bậc 3 là một cây thỏa mãn các tính chất sau:
➔ Tất cả node lá nằm trên cùng một mức
➔ Tất cả các node, trừ node gốc và node lá, có 2 node con.*tối thiểu*
➔ Tất cả các node có 3 con*tối đa*
➔ Tất cả các node, trừ node gốc , có từ 1 cho đến 2 khóa (keys)
➔ Một node không phải lá và có n khóa thì phải có n+1 node con.
Hãy thực hiện các yêu cầu sau:
1. Cho dãy số: 27, 19, 23, 9, 1, 3, 11, 21, 5, 13, 17, 15, 29, 25. Hỏi khi lần lượt thêm các
số trong dãy vào một cây B-Tree bậc 3 rỗng thì:
a. Các khóa nào khi thêm vào sẽ làm phát sinh thao tác split node? (0.5đ)
b. Vẽ cây B-Tree trước và sau khi thêm các khóa trên. (1đ)
2. Cho cây B-Tree bậc 3 như hình sau:
_____________{11,21}______________
____{3,7}____ ____{15}_____ ____{25}_____
{1} {5} {9} {13} {17,19} {23} {27,29}
a. Lần lượt tiến hành xóa các khóa sau khỏi cây B-Tree: 11, 21, 13 và Vẽ cây
B-Tree trước sau khi xóa mỗi khóa trên. (0.5đ)
Lưu ý:
i. Khi khóa cần xóa (gọi là x) không nằm ở node lá, chọn khóa thế mạng là
khóa có giá trị lớn nhất mà nhỏ hơn x.
ii. Thao tác underflow sẽ được thực hiện khi hai node liền kề có tổng số
khóa >= 2. Khi có một node không còn đáp ứng đủ số lượng khóa tối
thiểu, luôn ưu tiên thực hiện underflow thay cho catenation vì thao tác
này không làm thay đổi số khóa của node cha.
iii. Khi có 02 lựa chọn node liền kể để thực hiện catenation, ưu tiên chọn
catenate giữa node bị thiếu khóa với node liền trước
Đáp án:
1a. Các khóa làm phát sinh thao tác split node là : 23, 1, 21, 5, 17, 25,
1b.
Khó
a
trước
Sau
23
{19,27}
___{23}___
{19} {27}
1
____{23}____
{9,19} {27}
____{9,23}_____
{1} {19} {27}
21
_______{9,23}_______
{1,3} {11,19} {27}
______{19}______
____{9}____ ___{23}___
{1,3} {11} {21} {27}
5
______{19}______
____{9}____ ___{23}___
{1,3} {11} {21} {27}
_______{19}________
____{3,9}_____ ___{23}___
{1} {5} {11} {21} {27}
17
________{19}________
______{3,9}______ ___{23}___
{1} {5} {11,13} {21} {27}
__________{9,19}___________
__{3}___ ___{13}___ ___{23}___
{1} {5} {11} {17} {21} {27}
25
____________{9,19}_____________
__{3}___ ____{13}_____ ____{23}_____
{1} {5} {11} {15,17} {21} {27,29}
______________{9,19}______________
__{3}___ ____{13}_____ ____{23,27}_____
{1} {5} {11} {15,17} {21} {25} {29}
2.
Xóa 11: Swap 11 và 9 sau đó xóa tại lá và thực hiện catenate (chỉ có 1 lựa chọn để catenate)
_____________{9,21}_____________
___{3}____ ____{15}_____ ____{25}_____
{1} {5,7} {13} {17,19} {23} {27,29}
Xóa 21 - Swap 21 và 19 xóa tại lá và không cần thực hiện điều chỉnh
___________{9,19}____________
___{3}____ ___{15}___ ____{25}_____
{1} {5,7} {13} {17} {23} {27,29}
Xóa 13 trực tiếp tại lá, thực hiện catenate, lan truyền quá trình catenate lên node con ở giữa của gốc, tại mức này ưu tiên catenate với node
liền trước là {3} node gốc làm gốc bị giảm số khóa.
______{19}___________
_______{3,9}_______ ____{25}_____
{1} {5,7} {15,17} {23} {27,29}
| 1/3
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

Cho biết cây B-Tree bậc 3 là một cây thỏa mãn các tính chất sau:
➔ Tất cả node lá nằm trên cùng một mức
➔ Tất cả các node, trừ node gốc và node lá, có *tối thiểu* 2 node con.
➔ Tất cả các node có *tối đa* 3 con
➔ Tất cả các node, trừ node gốc , có từ 1 cho đến 2 khóa (keys)
➔ Một node không phải lá và có n khóa thì phải có n+1 node con.
Hãy thực hiện các yêu cầu sau:
1. Cho dãy số: 27, 19, 23, 9, 1, 3, 11, 21, 5, 13, 17, 15, 29, 25. Hỏi khi lần lượt thêm các
số trong dãy vào một cây B-Tree bậc 3 rỗng thì:
a. Các khóa nào khi thêm vào sẽ làm phát sinh thao tác split node? (0.5đ)
b. Vẽ cây B-Tree trước và sau khi thêm các khóa trên. (1đ)
2. Cho cây B-Tree bậc 3 như hình sau:
_____________{11,21}______________
____{3,7}____ ____{15}_____ ____{25}_____
{1} {5} {9} {13} {17,19} {23} {27,29}
a. Lần lượt tiến hành xóa các khóa sau khỏi cây B-Tree: 11, 21, 13 và Vẽ cây
B-Tree trước sau khi xóa mỗi khóa trên. (0.5đ) Lưu ý: i.
Khi khóa cần xóa (gọi là x) không nằm ở node lá, chọn khóa thế mạng là
khóa có giá trị lớn nhất mà nhỏ hơn x. ii.
Thao tác underflow sẽ được thực hiện khi hai node liền kề có tổng số
khóa >= 2. Khi có một node không còn đáp ứng đủ số lượng khóa tối
thiểu, luôn ưu tiên thực hiện underflow thay cho catenation vì thao tác
này không làm thay đổi số khóa của node cha. iii.
Khi có 02 lựa chọn node liền kể để thực hiện catenation, ưu tiên chọn
catenate giữa node bị thiếu khóa với node liền trước Đáp án:
1a. Các khóa làm phát sinh thao tác split node là : 23, 1, 21, 5, 17, 25, 1b. Khó trước Sau a 23 {19,27} ___{23}___ {19} {27} 1 ____{23}____ ____{9,23}_____ {9,19} {27} {1} {19} {27} 21 _______{9,23}_______ ______{19}______ {1,3} {11,19} {27} ____{9}____ ___{23}___ {1,3} {11} {21} {27} 5 ______{19}______ _______{19}________ ____{9}____ ___{23}___ ____{3,9}_____ ___{23}___ {1,3} {11} {21} {27} {1} {5} {11} {21} {27} 17 ________{19}________ __________{9,19}___________ ______{3,9}______ ___{23}___ __{3}___ ___{13}___ ___{23}___ {1} {5} {11,13} {21} {27} {1} {5} {11} {17} {21} {27} 25
____________{9,19}_____________
______________{9,19}______________
__{3}___ ____{13}_____ ____{23}_____
__{3}___ ____{13}_____ ____{23,27}_____
{1} {5} {11} {15,17} {21} {27,29}
{1} {5} {11} {15,17} {21} {25} {29} 2.
Xóa 11: Swap 11 và 9 sau đó xóa tại lá và thực hiện catenate (chỉ có 1 lựa chọn để catenate)
_____________{9,21}_____________
___{3}____ ____{15}_____ ____{25}_____
{1} {5,7} {13} {17,19} {23} {27,29}
Xóa 21 - Swap 21 và 19 xóa tại lá và không cần thực hiện điều chỉnh ___________{9,19}____________
___{3}____ ___{15}___ ____{25}_____
{1} {5,7} {13} {17} {23} {27,29}
Xóa 13 trực tiếp tại lá, thực hiện catenate, lan truyền quá trình catenate lên node con ở giữa của gốc, tại mức này ưu tiên catenate với node
liền trước là {3} node gốc làm gốc bị giảm số khóa. ______{19}___________
_______{3,9}_______ ____{25}_____ {1} {5,7} {15,17} {23} {27,29}