Title Giải đề cuối kì 202_Dự thính.docx ✅

Từ mảng ban đầu ta có cây sau. Ta nhận thấy các phần tử trong mảng đều đã thoả điều kiện trở thành một Max-Heap (Cây nhị phần gần đầy đủ, các node con đều nhỏ hơn node cha). Vậy ta không cần thực hiện bất kì hoán đổi nào. Giải:
Open addressing (địa chỉ mở): Hash table là một Array<LinkedList>. Phần tử đc hash xong sẽ đc thêm vào linked list tương ứng vs ô đã đc hash. Closed addressing (địa chỉ đóng): Hash Table là một Array<Int>, với int là khoá tương ứng. Phần tử đc hash xong sẽ đc thêm vào ô nhớ tương ứng vs kq hash. Nếu gặp collision (đụng độ), phần tử sẽ đc xem xét thêm vào ô kế tiếp ô đã xảy ra đụng độ. Cứ làm vậy cho đến khi hết các phần tử. Tham khảo thêm: https://stackoverflow.com/questions/9124331/meaning-of-open-hashing-and- closed-hashing A. Đúng. (3*8 + 4) % 7 = 0. Do bị đụng độ nên 8 sẽ ở index 1. Sau đó, 10 cũng bị đụng độ tại vị trí 6 -> 10 ở index 2. B sai. Giải thích ở trên. C sai. 8 và 10 bị đụng độ ở 0 và 6. Mà 8 được thêm vào trước 10 -> 8 ở index 1, 10 ở index 2. D sai. Ta nhận thấy (3*1 + 4) mod 7 = 0 và (3*3 + 4) mod 7 = 6 -> 1 và 3 ở index 0 và 6. (3*8 + 4) mod 7 = 0 và (3*10 + 4) mod 7 = 6. Giải: Chọn C. Ở đây, ta thấy có 2 vòng lặp lồng nhau. Vòng lặp đầu tiên có Time complexity là O(n). Vòng lặp lồng trong vòng lặp đầu tiên có Time complexity cao nhất là O(n) (Trường hợp I = 0). Vậy độ phức tạp của giải thuật trên là O(n^2).
Giải: Ta có: kA mod 1 = 123456*0.618033 mod 1 = 0.88205 (một số thập phân chia lấy dư cho 1 sẽ ra phần dư là phần thập phân của số đó). h(123456) = floor( 100 * (kA mod 1)) = floor(100*0.88205) = 88. (floor(x) là hàm sàn. Nó trả về kq là phần nguyên của số thập phân). Chọn C. Giải: Giải thích code ở một vài chỗ. If (!(list) || !list->next) return; // Nếu danh sách có một phần tử hoặc ko có phần tử nào thì quay về . Code trong vòng while có nhiệm vụ đưa phần tử đầu của list xuống cuối. Dừng thực thi khi p->next == NULL. Nó thực hiện điều này bằng cách swap(p,q), trong đó q = p->next.
Lần lặp đầu tiên, ta có. Kết quả: list = 2-1-3-4-5-6-7-8-9 Lần lặp thứ 2, ta có. Sau khi kết thúc lặp, ta có: list = 2-3-1-4-5-6-7-8-9. Làm vậy cho đến khi p->next = NULL. Ta có list = 2-3-4-5-6-7-8-9-1. Chọn C. Ta có max-Heap như sau. Sau khi thực hiện delete lần 1, ta swap root vs nút cuối trong heap. Sau đó ta xoá nút cuối đi. Sau đó ta swap root với phần tử lớn thứ nhì trong heap. Sau khi thực hiện delete lần 2, ta thay thế node theo cách tương tự lần trước. Chọn B.