Hãy cho biết đâu là đặc trưng của thuật toán trong các phương án sau?

Mỗi thuật toán có bộ dữ liệu vào, ra tương ứng

Mỗi bước của thuật toán cần phải được mô tả một các chính xác

Thuật toán phải dừng lại sau một số hữu hạn các bước cần thực hiện

Tất cả các đặc trưng đã nêu

Trả lời:

Đáp án đúng: D

Câu hỏi yêu cầu xác định đặc trưng của thuật toán. - Phương án 1: "Mỗi thuật toán có bộ dữ liệu vào, ra tương ứng" là đúng. Thuật toán nhận dữ liệu đầu vào và tạo ra kết quả đầu ra. - Phương án 2: "Mỗi bước của thuật toán cần phải được mô tả một các chính xác" là đúng. Tính xác định là một đặc trưng quan trọng của thuật toán. - Phương án 3: "Thuật toán phải dừng lại sau một số hữu hạn các bước cần thực hiện" là đúng. Tính hữu hạn là một đặc trưng bắt buộc của thuật toán. Vì cả ba phương án đều đúng, phương án "Tất cả các đặc trưng đã nêu" là đáp án chính xác nhất.

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

Đề 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 17:

Với dữ liệu đầu vào (n) lớn, ta nên sử dụng phương pháp sắp xếp nào sau đây?

Lời giải:

Đáp án đúng: B

Khi kích thước dữ liệu (n) lớn, các thuật toán sắp xếp có độ phức tạp thời gian trung bình hoặc tốt nhất là O(n log n) thường được ưu tiên hơn vì chúng có hiệu suất tốt hơn so với các thuật toán có độ phức tạp O(n^2).

Sắp xếp trộn (Merge sort) và Sắp xếp đống (Heap sort) đều có độ phức tạp thời gian O(n log n) trong trường hợp xấu nhất, trung bình và tốt nhất, làm cho chúng phù hợp với dữ liệu lớn. Sắp xếp nhanh (Quick sort) cũng có độ phức tạp trung bình là O(n log n), nhưng trong trường hợp xấu nhất (ví dụ: khi dữ liệu đã được sắp xếp), nó có thể xuống đến O(n^2).

Sắp xếp chọn (Selection sort), sắp xếp chèn (Insert sort) và sắp xếp nổi bọt (Bubble sort) đều có độ phức tạp thời gian O(n^2), do đó không hiệu quả với dữ liệu lớn.

Vậy nên đáp án chính xác nhất là "Sắp xếp trộn (Merge sort) hoặc Sắp xếp đống(Heap sort)"

Câu 18:

Trong một chương trình có 3 bước thực hiện, mà thời gian thực hiện từng bước lần lượt là O(n^2), O(n^3) và O(nlogn). Cho biết thời gian thực hiện của chương trình là bao nhiêu trong các phương án sau?

Lời giải:

Đáp án đúng: A

Thời gian thực hiện của chương trình là tổng thời gian thực hiện của các bước. Trong trường hợp này, chúng ta có ba bước với thời gian thực hiện lần lượt là O(n^2), O(n^3) và O(nlogn). Khi tính tổng độ phức tạp, chúng ta chỉ giữ lại thành phần có tốc độ tăng trưởng lớn nhất khi n tiến tới vô cùng. Trong ba thành phần trên, O(n^3) có tốc độ tăng trưởng lớn nhất. Do đó, thời gian thực hiện của chương trình là O(n^3).

Câu 19:

Nếu tương ứng với P1 và P2 là T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện P1 và P2 lồng nhau sẽ là bao nhiêu trong các phương án sau?

Lời giải:

Đáp án đúng: B

Khi hai đoạn chương trình P1 và P2 lồng nhau, thời gian thực hiện sẽ là tích của thời gian thực hiện của mỗi đoạn. Vì T1(n) = O(f(n)) và T2(n) = O(g(n)), nên thời gian thực hiện lồng nhau sẽ là T1(n) * T2(n) = O(f(n) * g(n)).

Câu 20:

Hãy cho biết ý tưởng nào sau đây nói về tưởng phương pháp sắp xếp Trộn (Merge sort)?

Lời giải:

Đáp án đúng: D

Phương pháp sắp xếp trộn (Merge Sort) là một thuật toán sắp xếp dựa trên kỹ thuật chia để trị. Ý tưởng chính của thuật toán là chia dãy ban đầu thành các dãy con nhỏ hơn, sau đó sắp xếp các dãy con này và cuối cùng trộn các dãy con đã sắp xếp lại với nhau để tạo thành một dãy đã được sắp xếp hoàn chỉnh. Vì vậy, đáp án đúng là phương án mô tả việc phân đoạn dãy thành nhiều dãy con và trộn chúng lại.

Câu 21:

Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp vun đống (Heap sort)?

Lời giải:

Đáp án đúng: D

Heap sort là một thuật toán sắp xếp dựa trên cấu trúc dữ liệu Heap (đống). Ý tưởng chính của Heap sort là xây dựng một max-heap (đống mà phần tử gốc lớn nhất) từ dãy các phần tử cần sắp xếp, sau đó liên tục loại bỏ phần tử gốc (phần tử lớn nhất) và đưa nó vào dãy kết quả, đồng thời tái cấu trúc lại heap. Vì vậy, đáp án đúng phải mô tả quá trình tạo đống và loại phần tử gốc để sắp xếp. Phương án 4 mô tả chính xác ý tưởng này: "Lần lượt tạo đống cho cây nhị phân (phần tử gốc có giá trị lớn nhất) và loại phần tử gốc ra khỏi cây đưa vào dãy sắp xếp".

Câu 22:

Trong giải thuật sắp xếp vun đống, ta có 4 thủ tục con (Insert - thêm 1 phần tử vào cây; Downheap - vun đống lại sau khi loại một phần tử khỏi Heap, Upheap- vun đống sau khi thêm một phần tử vào cây; Remove - loại 1 phần tử khỏi cây nhị phân). Để sắp xếp các phần tử trong dãy theo phương pháp vun đống, ta thực hiện 4 thủ tục trên theo thứ tự như thế nào sau đây?

Lời giải: