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

Duyệt cây con trái theo thứ tự sau; Duyệt gốc; Duyệt cây con phải theo thứ tự sau

Duyệt gốc, cây trái, cây phải đồng thời theo thứ tự sau

Duyệt cây con trái theo thứ tự sau; Duyệt cây con phải theo thứ tự sau; Duyệt gốc

Duyệt gốc; Duyệt cây con trái theo thứ tự sau; Duyệt cây con phải theo thứ tự sau

Dữ liệu tốt, giải thuật đơn giản

Giải thuật có thời gian thực hiện nhanh nhất

Cấu trúc dữ liệu thích hợp, giải thuật xử lý hiệu quả

Cấu trúc dữ liệu tốt

1 byte

2 byte

4 byte

6 byte

Giải thuật hay còn gọi là thuật toán dùng để chỉ phương pháp hay cách thức giải quyết vấn đề( bao gồm một dãy các bước tính toán rõ ràng và chính xác)

Giải thuật là nòng cốt của chương trình

Giải thuật là một dãy hữu hạn các bước, tất cả các phép toán có mặt trong các bước của thuật toán phải đủ đơn giản

Giải thuật cần có một hoặc nhiều dữ liệu ra (output), dữ liệu vào (input)

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

Thời gian khi chạy chương trình cụ thể

Tính xác định

Độ phức tạp tính toán của giải thuật

Tính dừng

O(1), O(logn), O(n), O(nlogn)

O(1), O(nlogn), O(n), O(logn)

O(logn), O(n), O(nlogn), O(1)

O(nlogn), O(n), O(logn), O(1)

Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó

Sau mỗi lần có lời gọi đệ quy thì kích thước của bài toán được thu nhỏ hơn trước

Có một trường hợp đặc biệt, trường hợp suy biến. Khi trường hợp này xảy ra thì bài toán còn lại sẽ được giải quyết theo một cách khác

Tất cả các đáp án đều đúng

Chỉ việc xoá X, vì X không liên quan đến phần tử nào khác

Tìm nút chứa khoá lớn nhất trong cây con trái, đưa giá trị chứa trong đó sang nút X , rồi xoá X

Không thể xoá X ra khỏi cây nhị phân tìm kiếm

Tìm nút chứa khoá lớn nhất trong cây con phải, đưa giá trị chứa trong đó sang nút X , rồi xoá X

Sắp xếp nhanh(quick sort)

Sắp xếp vun đống(Heap sort)

Sắp xếp lựa chọn(selection sort)

Sắp xếp trộn(Merge sort)

Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và phép loại bỏ một phần tử khỏi ngăn xếp luôn luôn thực hiện ở một đầu gọi là đỉnh

Là một danh sách tuyến tính trong đó phép bổ sung sung một phần tử vào ngăn xếp được thực hiện ở một đầu, Và phép loại bỏ không thực hiện được

Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và phép loại bỏ một phần tử khỏi ngăn xếp luôn luôn thực hiện ở tại một vị trí bất kì trong danh sách

Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp được thực hiện ở một đầu , và phép loại bỏ được thực hiện ở đầu kia

LILO(last in last out)

LIFO(last in first out)

FIFO( first in first out)

FOLO(fisrt out last out)

Sắp xếp trộn (Merge sort) hoặc Sắp xếp đống(Heap sort)

Sắp xếp đống(Heap sort) hoặc Sắp xếp nhanh(quick sort)

Sắp xếp chọn(selection sort), sắp xếp chèn ( Insert sort)

Sắp xếp nổi bọt ( bubble sort) hoặc Sắp xếp chọn(selection sort)

Trong giải thuật của nó có lời gọi tới một giải thuật khác đã biết kết quả

Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi lớn hơn

Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi nhỏ hơn

Trong giải thuật của nó có lời gọi tới chính nó

T1(n) + T2(n) = O(Min(f(n),g(n)))

T1(n) + T2(n) = O(max(f(n),g(n)))

T1(n) + T2(n) = O((f(n) or g(n)))

T1(n) + T2(n) = O((f(n)+g(n)))

O(n^3)

O(nlogn)

O(n^2)

O(n^2)+ O(n^3) + O(nlogn)

T1(n)T2(n) = O(f(n)and g(n))

T1(n)T2(n) = O(f(n).g(n))

T1(n)T2(n) = O(f(n)+g(n))

T1(n)T2(n) = O(f(n)/g(n))

O(logn)

O(n)

O(2)

O(1)

POP(72), POP(23), POP(72)

POP(72), POP(23), PUSH(72)

POP(23), PUSH(23), POP(72)

POP(23), PUSH(72), POP(72)

Quick sort, Heap sort

Quick sort, Merge sort

Quick sort, Bubble sort

Quick sort, Insert sort