Trong biểu diễn dữ liệu dưới dạng cây, nút có cấp bằng 0 gọi là nút gì trong các phương án sau?

Là nút lá

Là phần tử cuối cùng trong cây

Là nút gố

Là phần tử đầu cùng trong cây

Trả lời:

Đáp án đúng: A

Trong cây, cấp của một nút là số cạnh trên đường đi từ nút gốc đến nút đó. Do đó, nút có cấp bằng 0 chính là nút gốc của cây. Các nút lá là các nút không có nút con.

220 câu trắc nghiệm Cấu trúc dữ liệu và giải thuật có đáp án - Phần 5

Đề cương ôn thi với 220 câu trắc nghiệm Cấu trúc dữ liệu và giải thuật có đáp án được chọn lọc và chia sẻ dưới đây, nhằm giúp bạn sinh viên hệ thống kiến thức chuẩn bị cho kì thi sắp diễn ra.

20 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 17:

Hàng đợi còn được gọi là danh sách kiểu:

Lời giải:

Đáp án đúng: B

Hàng đợi (queue) là một cấu trúc dữ liệu hoạt động theo nguyên tắc "First In, First Out" (FIFO), nghĩa là phần tử nào được thêm vào trước sẽ được lấy ra trước. Các lựa chọn khác không đúng vì:
- LOLO không phải là thuật ngữ liên quan đến hàng đợi.
- FILO là viết tắt của "First In, Last Out", nguyên tắc hoạt động của ngăn xếp (stack), không phải hàng đợi.
- LIFO là viết tắt của "Last In, First Out", cũng là nguyên tắc hoạt động của ngăn xếp (stack), không phải hàng đợi.

Câu 18:

Cho dãy số {6 1 3 0 5 7 9 2 8 4}. áp dụng phương pháp sắp xếp lựa chọn (Select sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ ba là:

Lời giải:

Đáp án đúng: A

Giải thuật sắp xếp lựa chọn (Selection Sort) hoạt động bằng cách tìm phần tử nhỏ nhất trong dãy chưa được sắp xếp và đổi chỗ nó với phần tử ở vị trí đầu tiên của dãy chưa sắp xếp đó. Sau mỗi lần lặp, một phần tử sẽ được đưa về đúng vị trí của nó.

Sau lần lặp đầu tiên, dãy số là: {0 1 3 6 5 7 9 2 8 4}

- Lần lặp thứ hai: Tìm phần tử nhỏ nhất trong dãy {1 3 6 5 7 9 2 8 4}. Phần tử nhỏ nhất là 1, nó đã ở đúng vị trí nên không cần đổi chỗ. Dãy số vẫn là {0 1 3 6 5 7 9 2 8 4}

- Lần lặp thứ ba: Tìm phần tử nhỏ nhất trong dãy {3 6 5 7 9 2 8 4}. Phần tử nhỏ nhất là 2, đổi chỗ 2 với 3. Dãy số trở thành {0 1 2 6 5 7 9 3 8 4}

Câu 19:

Bước tổng quát của Phương pháp sắp xếp kiểu lựa chọn (selection sort):

Lời giải:

Đáp án đúng: a

Phương pháp sắp xếp kiểu lựa chọn (Selection Sort) hoạt động bằng cách tìm phần tử nhỏ nhất trong đoạn chưa được sắp xếp của mảng và hoán đổi nó với phần tử đầu tiên của đoạn đó. Bước tổng quát của thuật toán này là chọn phần tử có khóa nhỏ nhất trong `n-i+1` phần tử từ `a[i]` đến `a[n]` và hoán vị nó với `a[i]`. Các phương án khác mô tả các thuật toán sắp xếp khác (ví dụ, phương án 1 liên quan đến sắp xếp chèn, phương án 2 liên quan đến sắp xếp nổi bọt).

Câu 20:

Dùng phương pháp lưu trữ liên tiếp để lưu trữ một ma trận ( mảng hai chiều) có nhược điểm lớn nhất là:

Lời giải:

Đáp án đúng: B

Phương pháp lưu trữ liên tiếp cho ma trận, đặc biệt là ma trận thưa (sparse matrix), có nhược điểm lớn nhất là lãng phí bộ nhớ. Ma trận thưa là ma trận mà phần lớn các phần tử có giá trị bằng 0. Khi lưu trữ liên tiếp, chúng ta vẫn phải cấp phát bộ nhớ cho tất cả các phần tử, kể cả các phần tử có giá trị 0, dẫn đến lãng phí không gian lưu trữ đáng kể.

Câu 1:

Chọn câu đúng nhất để mô tả thuật toán sắp xếp nổi bọt (Bubble Sort) trên mảng M có N phần tử:

Lời giải:

Đáp án đúng: A

Thuật toán sắp xếp nổi bọt (Bubble Sort) hoạt động bằng cách lặp đi lặp lại qua danh sách, so sánh các cặp phần tử liền kề và hoán đổi chúng nếu chúng không đúng thứ tự. Trong mỗi lần lặp, phần tử lớn nhất "nổi" lên vị trí cuối cùng (hoặc đầu tiên, tùy thuộc vào cách triển khai) của danh sách chưa được sắp xếp.

Phương án 1 mô tả chính xác cách hoạt động của thuật toán Bubble Sort: đi từ cuối mảng về đầu mảng, so sánh các phần tử liền kề và đổi chỗ nếu cần để đưa phần tử lớn hơn "nổi" lên. Sau N-1 lần lặp, mảng sẽ được sắp xếp.

Phương án 2 sai vì Bubble Sort cần N-1 lần lặp, không phải N lần.

Phương án 3 sai vì Bubble Sort cần N-1 lần lặp, không phải N lần.

Phương án 4 sai vì có một đáp án đúng (phương án 1).

Câu 2:

Lựa chọn định nghĩa về danh sách đúng nhất?

Lời giải: