Cho dãy số sau: 40 25 75 15 65 55 90 30 95 85. Áp dụng phương pháp sắp xếp hòa nhập (Merge_Sort) trực tiếp, sau lượt 1 dãy sẽ được sắp xếp lại như thế nào?

[15 40] [30 25] [55 65] [75 85] [90 95]

[40 25] [55 15] [30 65] [75 90] [85 95]

[15 25] [40 75] [30 55] [65 90] [85 95]

[25 40] [15 75] [55 65] [30 90] [85 95]

Trả lời:

Đáp án đúng: D

Phương pháp sắp xếp hòa nhập (Merge Sort) là một thuật toán sắp xếp chia để trị. Trong lượt đầu tiên (lượt 1), thuật toán chia dãy số thành các cặp phần tử liền kề và sắp xếp từng cặp đó.

Dãy số ban đầu: 40 25 75 15 65 55 90 30 95 85

Sau lượt 1, các cặp được sắp xếp như sau:

Cặp 1: 40 và 25 -> 25 40
Cặp 2: 75 và 15 -> 15 75
Cặp 3: 65 và 55 -> 55 65
Cặp 4: 90 và 30 -> 30 90
Cặp 5: 95 và 85 -> 85 95

Vậy dãy số sau lượt 1 sẽ là: [25 40] [15 75] [55 65] [30 90] [85 95]

Đáp án phù hợp nhất là phương án 4.

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

Đề 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.

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 38:

Cho dãy số sau: 14 32 10 43 57 87 55 36 97 11. Áp dụng phương pháp tìm kiếm tuần tự, sau bao nhiều lần thực hiện phép so sánh ta sẽ tìm thấy số 43?

Lời giải:

Đáp án đúng: C

Phương pháp tìm kiếm tuần tự duyệt qua từng phần tử của dãy số từ đầu đến khi tìm thấy phần tử cần tìm. Trong trường hợp này, ta có dãy số: 14, 32, 10, 43, 57, 87, 55, 36, 97, 11.

1. So sánh 14 với 43 (không trùng khớp).
2. So sánh 32 với 43 (không trùng khớp).
3. So sánh 10 với 43 (không trùng khớp).
4. So sánh 43 với 43 (trùng khớp).

Vậy, sau 4 lần so sánh, ta tìm thấy số 43.

Câu 39:

Để viết chương trình chỉ để sử dụng một số ít lần và cái giá của thời gian viết chương trình vượt xa cái giá của chạy chương trình thì ta chọn thuật toán:

Lời giải:

Đáp án đúng: B

Trong trường hợp cần viết chương trình chỉ sử dụng một vài lần và chi phí thời gian viết chương trình lớn hơn chi phí chạy chương trình, thì việc ưu tiên một thuật toán đơn giản, dễ hiểu và dễ cài đặt là hợp lý nhất. Điều này giúp giảm thiểu thời gian và công sức cần thiết để phát triển chương trình, ngay cả khi nó không tối ưu về hiệu suất. Thuật toán sử dụng ít tài nguyên và chạy nhanh nhất chỉ quan trọng khi chương trình được sử dụng thường xuyên và hiệu suất là yếu tố then chốt.

Câu 40:

Thế nào là sắp xếp ngoài?

Lời giải:

Đáp án đúng: D

Sắp xếp ngoài (External sorting) là thuật toán sắp xếp được sử dụng khi dữ liệu cần sắp xếp quá lớn để chứa hết trong bộ nhớ trong (RAM). Thay vào đó, dữ liệu được lưu trữ trên các thiết bị lưu trữ ngoài như ổ cứng, SSD. Quá trình sắp xếp sẽ bao gồm việc đọc các phần dữ liệu từ thiết bị lưu trữ ngoài vào bộ nhớ trong, sắp xếp chúng, và sau đó ghi kết quả trở lại thiết bị lưu trữ ngoài. Vì vậy, đáp án đúng là đáp án 1.

Câu 41:

Đâu là phương pháp sắp xếp trong, trong các phương pháp sau:

Lời giải:

Đáp án đúng: A

Sắp xếp trong (internal sorting) là các thuật toán sắp xếp mà dữ liệu được sắp xếp nằm hoàn toàn trong bộ nhớ chính (RAM) của máy tính. Điều này cho phép truy cập ngẫu nhiên vào dữ liệu. Các phương pháp nổi bọt (Bubble sort), sắp xếp chèn (Insertion sort), và sắp xếp chọn (Selection sort) đều là các thuật toán sắp xếp trong, vì chúng thực hiện sắp xếp trực tiếp trên dữ liệu trong bộ nhớ. Tuy nhiên, câu hỏi liệt kê "Phương pháp sắp xếp chèn (selection sort)" và "Phương pháp sắp xếp chọn (insertion sort)" bị ngược tên. Do đó, không có đáp án nào đúng trong các phương án đã cho.

Câu 42:

Đâu là phương pháp sắp xếp ngoài, trong các phương pháp sau:

Lời giải:

Đáp án đúng: D

Sắp xếp ngoài (external sort) là các thuật toán sắp xếp có thể xử lý lượng dữ liệu lớn. Thông thường, các thuật toán sắp xếp ngoài được sử dụng khi dữ liệu quá lớn để phù hợp với bộ nhớ chính (RAM) của máy tính. Do đó, dữ liệu được lưu trữ trên các thiết bị lưu trữ chậm hơn, chẳng hạn như ổ cứng. Các thuật toán sắp xếp chèn (insertion sort), sắp xếp chọn (selection sort) và nổi bọt (bubble sort) là các thuật toán sắp xếp trong (internal sort), tức là chúng yêu cầu toàn bộ dữ liệu cần sắp xếp phải nằm trong bộ nhớ chính. Vì vậy, không có đáp án đúng trong các lựa chọn trên. Tuy nhiên, theo ngữ cảnh thông thường, các thuật toán sắp xếp được đề cập (insertion sort, selection sort, bubble sort) thường được coi là các thuật toán sắp xếp trong. Do đó, không có đáp án nào chính xác trong trường hợp này.

Câu 43:

Thế nào là ngôn ngữ giả?

Lời giải: