Font size
WorksheetsTrắc Nghiệm Tìm Kiếm Tuyến Tính
Total questions: 60
Worksheet time: 38mins
Xét mảng A sau và phần tử cần tìm kiếm là X. Cần bao nhiêu phép so sánh để tìm kiếm phần tử X trong mảng A. Biết A=[25,45,87,21,18,49,13,115,83,65], X=83.
7
8
9
10
Câu nào sau đây là đúng về tìm kiếm trong cấu trúc dữ liệu mảng có N phần tử?
Cả 2 ý đều đúng
Chỉ có 1 đúng
Chỉ có 2 đúng
Cả 2 ý đều sai.
Trường hợp tốt nhất cho tìm kiếm tuyến tính là gì?
O(nlogn)
O(logn)
O(n)
O(1)
Trường hợp tệ nhất của tìm kiếm tuyến tính là gì?
O(nlogn)
O(logn)
O(n)
O(1)
Độ phức tạp trong trường hợp tốt nhất và xấu nhất của tìm kiếm tuyến tính có thứ tự là bao nhiêu?
Độ phức tạp trong trường hợp tốt nhất và xấu nhất của tìm kiếm tuyến tính có thứ tự là bao nhiêu?
O(nlogn), O(logn)
O(logn), O(nlogn)
O(n), O(1)
O(1), O(n)
Điểm nào sau đây là nhược điểm của tìm kiếm tuyến tính?
Cần nhiều không gian hơn
Độ phức tạp về thời gian lớn hơn so với các thuật toán tìm kiếm khác
Không dễ hiểu
Không dễ triển khai
Thuật toán tìm kiếm nhảy yêu cầu điều kiện nào sau đây là đúng?
mảng phải được sắp xếp
mảng không được sắp xếp
mảng phải có ít hơn 64 phần tử
mảng phải được sắp xếp một phần
Các bước nhảy được thực hiện trong thuật toán tìm kiếm nhảy cho đến khi ___________
phần tử có giá trị nhỏ hơn giá trị của phần tử cần tìm được
phần tử có giá trị bằng giá trị trung vị của các giá trị trong mảng được tìm thấy
phần tử có giá trị lớn hơn giá trị của phần tử cần tìm được
phần tử ở giữa được tìm thấy bằng với phần tử đang được tìm kiếm
Bước nào sau đây được thực hiện sau khi tìm thấy một phần tử có giá trị lớn hơn phần tử đang được tìm kiếm?
Tìm kiếm tuyến tính diễn ra theo hướng thuận
Tìm kiếm tuyến tính diễn ra theo hướng ngược
Tìm kiếm nhị phân diễn ra theo hướng thuận
Tìm kiếm nhị phân diễn ra theo hướng ngược
Có bao nhiêu lần nhảy sẽ được thực hiện trong trường hợp tệ nhất của tìm kiếm nhảy (cho khối nhảy = k)?
n * k
n / k
k / n
n + k
Số lượng so sánh tối đa có thể thực hiện trong thuật toán tìm kiếm nhảy là bao nhiêu (giả sử k là các khối đã nhảy)?
k
n/k
k-1
k-1
Giá trị của bước nhảy được thực hiện để đạt hiệu quả tối đa khi triển khai tìm kiếm nhảy là bao nhiêu?
n/2
n2
n1/2
log n
của bước nhảy được thực hiện để đạt hiệu quả tối đa khi triển khai tìm kiếm nhảy là bao nhiêu?
n/2
n2
n1/2
log n
Thuật toán tìm kiếm nào sau đây là nhanh nhất?
tìm kiếm nhảy
tìm kiếm nhị phân
tìm kiếm tuyến tính
tất cả đều nhanh như nhau
Trong trường hợp nào sau đây, tìm kiếm nhảy sẽ được ưu tiên hơn tìm kiếm nhị phân?
nhảy ngược mất nhiều thời gian hơn đáng kể so với nhảy tiến
nhảy tiến mất nhiều thời gian hơn đáng kể so với nhảy lùi
khi mảng cho trước có kích thước rất lớn
khi mảng cho trước có kích thước rất nhỏ
Trường hợp tốt nhất của tìm kiếm nhảy sẽ có độ phức tạp thời gian là _________
O(1)
O(n)
O(logn)
O(nlogn)
Điều kiện nào sau đây là mong muốn nhất cho tìm kiếm nội suy?
Điều kiện nào sau đây là mong muốn nhất cho tìm kiếm nội suy?
mảng phải được sắp xếp
mảng không được sắp xếp nhưng các giá trị phải được phân bổ đều
mảng phải có ít hơn 64 phần tử
mảng phải được sắp xếp và các giá trị phải được phân bổ đều
Tìm kiếm nội suy là một biến thể của?
Tìm kiếm tuyến tính
Tìm kiếm nhị phân
Tìm kiếm nhảy
Tìm kiếm mũ
Tìm kiếm nội suy thực hiện tốt hơn tìm kiếm nhị phân khi nào?
Mảng có các giá trị phân bố đều nhưng không được sắp xếp
Mảng được sắp xếp và có các giá trị phân bố đều
Mảng được sắp xếp nhưng các giá trị không được phân bố đều
Mảng không được sắp xếp
Trong trường hợp nào sau đây, tìm kiếm nhảy thực hiện tốt hơn tìm kiếm nội suy?
Khi mảng có các giá trị phân phối đều nhưng không được sắp xếp
Khi mảng được sắp xếp và có phân phối đồng đều các giá trị
Khi mảng được sắp xếp nhưng các giá trị tăng theo cấp số nhân
Khi mảng không được sắp xếp
Độ phức tạp thời gian của tìm kiếm nội suy là bao nhiêu khi mảng đầu vào có các giá trị phân bố đều và được sắp xếp?
O(n)
O(log log n)
O(n log n)
O(log n)
Thuật toán tìm kiếm nào sau đây là nhanh nhất khi mảng đầu vào được sắp xếp và có các giá trị phân phối đều?
tìm kiếm nhảy
tìm kiếm mũ
tìm kiếm nhị phân
tìm kiếm nội suy
Thuật toán tìm kiếm nào sau đây là nhanh nhất khi mảng đầu vào được sắp xếp nhưng có các giá trị phân phối không đồng đều?
tìm kiếm nhảy
tìm kiếm tuyến tính
tìm kiếm nhị phân
tìm kiếm nội suy
Thuật toán tìm kiếm nào sau đây là nhanh nhất khi mảng đầu vào không được sắp xếp nhưng có các giá trị phân bố đều?
tìm kiếm nhảy
tìm kiếm tuyến tính
tìm kiếm nhị phân
tìm kiếm nội suy
Công thức nào được sử dụng để tính vị trí trong tìm kiếm nội suy?
((x - A[low]) * (high - low)) / (A[high] - A[low])
high + ((x - A[low]) * (high - low)) / (A[high] - A[low])
low + ((x - A[low]) * (high - low)) / (A[high] - A[low])
x + ((x - A[low]) * (high - low)) / (A[high] - A[low])
Giá trị cập nhật của high và low trong mảng là bao nhiêu nếu phần tử đang được tìm kiếm lớn hơn giá trị tại chỉ số được tính toán trong tìm kiếm nội suy? (pos = vị trí hiện tại)
low = pos + 1, high không đổi
high = pos - 1, low không đổi
low = low +1, high = high - 1
low = pos +1, high = pos - 1
Giá trị cập nhật của high và low trong mảng là bao nhiêu nếu phần tử đang được tìm kiếm thấp hơn giá trị tại chỉ mục được tính toán trong tìm kiếm nội suy? (pos = vị trí hiện tại)
low = pos + 1, high không đổi
high = pos - 1, low không đổi
low = low +1, high = high - 1
low = pos +1, high = pos - 1
Thuật toán tìm kiếm nào sau đây là nhanh nhất?
tìm kiếm nhị phân
tìm kiếm tuyến tính
tìm kiếm nhảy
tất cả đều nhanh như nhau
Tìm kiếm tuyến tính được sử dụng ở đâu?
Được sử dụng mọi lúc
Khi danh sách chỉ có một vài phần tử
Khi thực hiện một tìm kiếm duy nhất trong danh sách không có thứ tự
Khi danh sách chỉ có một vài phần tử và Khi thực hiện một tìm kiếm duy nhất trong danh sách không có thứ tự
Làm thế nào để cải thiện Jump Search?
Kích thước bước phải khác sqrt(n)
Không thể cải thiện
Bắt đầu từ mục thứ k, trong đó k là kích thước bước
Bắt đầu tìm kiếm từ cuối
Thuật toán tìm kiếm nào sau đây được sử dụng với sắp xếp theo cấp số nhân sau khi tìm thấy phạm vi thích hợp?
Tìm kiếm nhảy
Tìm kiếm Fibonacci
Tìm kiếm tuyến tính
Tìm kiếm nhị phân
Thuật toán tìm kiếm nào sau đây là nhanh nhất khi mảng đầu vào không được sắp xếp nhưng có các giá trị phân bố đều?
tìm kiếm tuyến tính
tìm kiếm nhảy
tìm kiếm nội suy
tìm kiếm nhị phân
Độ phức tạp thời gian của thuật toán Z để tìm kiếm mẫu là bao nhiêu (m = độ dài của văn bản, n = độ dài của mẫu)?
O(n)
O(m)
O(n + m)
O(m * n)
Trong trường hợp nào thì tìm kiếm nhị phân thống nhất không hiệu quả so với tìm kiếm nhị phân?
Trong trường hợp nào thì tìm kiếm nhị phân thống nhất không hiệu quả so với tìm kiếm nhị phân?
Độ phức tạp của mã
Nhiều tìm kiếm sẽ được thực hiện trên một số mảng có cùng độ dài
Nhiều tìm kiếm sẽ được thực hiện trên cùng một mảng
Tra cứu bảng thường nhanh hơn phép cộng và phép dịch chuyển
Tìm kiếm nội suy là một biến thể của?
Tìm kiếm theo hàm mũ
Tìm kiếm tuyến tính
Tìm kiếm nhị phân
Tìm kiếm nhảy
Ứng dụng nào sau đây không phải là ứng dụng của tìm kiếm nhị phân?
Tìm kiếm trong danh sách không có thứ tự
Gỡ lỗi
Hợp các khoảng
Tìm giới hạn dưới/trên trong một chuỗi có thứ tự
Bước nào sau đây được thực hiện sau khi tìm thấy một phần tử có giá trị lớn hơn phần tử đang được tìm kiếm?
Tìm kiếm nhị phân diễn ra theo hướng thuận
Tìm kiếm nhị phân diễn ra theo hướng ngược
Tìm kiếm tuyến tính diễn ra theo hướng thuận
Tìm kiếm tuyến tính diễn ra theo hướng ngược
Câu nào sau đây không phải là ưu điểm của Tìm kiếm Fibonacci?
Khi phần tử đang được tìm kiếm có bộ nhớ truy cập không đồng nhất
Có thể áp dụng hiệu quả trên các mảng chưa được sắp xếp
Có thể sử dụng cho các mảng lớn không vừa với bộ nhớ đệm CPU hoặc RAM
Có thể sử dụng trong băng từ
Trong trường hợp nào sau đây, tìm kiếm nhảy sẽ được ưu tiên hơn tìm kiếm theo cấp số nhân?
khi mảng cho trước có kích thước rất nhỏ
khi mảng cho trước có kích thước rất lớn
nhảy ngược lại mất nhiều thời gian hơn đáng kể so với nhảy về phía trước
nhảy về phía trước mất nhiều thời gian hơn đáng kể so với nhảy về phía sau
Trong trường hợp nào tìm kiếm nhảy sẽ không hiệu quả?
Khi mảng có kích thước rất lớn
Khi mảng không được sắp xếp
Khi mảng có các giá trị phân bố không đồng đều
Khi mảng được sắp xếp
Độ phức tạp thời gian của tìm kiếm nhị phân là gì khi mảng đã được sắp xếp?
O(n)
O(log n)
O(n log n)
O(1)
Điều kiện nào sau đây là cần thiết để áp dụng tìm kiếm nhảy?
Mảng phải được sắp xếp
Mảng không được sắp xếp
Các giá trị trong mảng phải phân bố ngẫu nhiên
Mảng phải có ít hơn 100 phần tử
Trong thuật toán tìm kiếm nhị phân, điều kiện nào là cần thiết để thuật toán hoạt động hiệu quả?
Mảng phải được sắp xếp
Mảng không được sắp xếp
Các giá trị trong mảng phải phân bố ngẫu nhiên
Mảng phải có ít hơn 50 phần tử
Độ phức tạp thời gian của tìm kiếm nhảy trong trường hợp tệ nhất là gì?
O(n)
O(log n)
O(n log n)
O(1)
Trong trường hợp nào tìm kiếm nhị phân sẽ không hoạt động hiệu quả?
Khi mảng không được sắp xếp
Khi mảng có kích thước rất nhỏ
Khi mảng có các giá trị phân bố đều
Khi mảng được sắp xếp
Tìm kiếm nhảy có thể được cải thiện bằng cách nào?
Giảm kích thước bước
Tăng kích thước bước
Thay đổi cách sắp xếp mảng
Không có cách nào
Điều kiện nào là cần thiết để áp dụng tìm kiếm nội suy?
Mảng phải được sắp xếp và có các giá trị phân bố đều
Mảng không được sắp xếp
Các giá trị trong mảng phải phân bố ngẫu nhiên
Mảng phải có ít hơn 100 phần tử
Độ phức tạp thời gian của tìm kiếm nhảy trong trường hợp xấu nhất là bao nhiêu?
O(n)
O(log n)
O(n^2)
O(1)
Trong trường hợp nào tìm kiếm nhảy sẽ không hiệu quả?
Khi mảng đã được sắp xếp
Khi mảng có kích thước rất lớn
Khi mảng có nhiều phần tử trùng lặp
Khi mảng có ít hơn 10 phần tử
Độ phức tạp thời gian của tìm kiếm nhị phân trong trường hợp tốt nhất là gì?
O(n)
O(log n)
O(1)
O(n log n)
Điều kiện nào là cần thiết để áp dụng tìm kiếm nhảy một cách hiệu quả?
Mảng phải được sắp xếp
Mảng không được sắp xếp
Các giá trị trong mảng phải phân bố ngẫu nhiên
Mảng phải có ít hơn 100 phần tử
Trong thuật toán tìm kiếm nhảy, kích thước bước tối ưu nên được xác định như thế nào?
Phụ thuộc vào kích thước của mảng
Luôn là một hằng số cố định
Phụ thuộc vào độ phân bố của các giá trị trong mảng
Không cần thiết phải xác định
Để cải thiện hiệu suất của tìm kiếm nhị phân, điều gì là cần thiết?
Giảm kích thước mảng
Đảm bảo mảng được sắp xếp
Thay đổi thuật toán tìm kiếm
Thêm nhiều phần tử vào mảng
Trong trường hợp nào tìm kiếm nội suy sẽ hoạt động kém hiệu quả?
Khi mảng có các giá trị phân bố không đồng đều
Khi mảng được sắp xếp
Khi mảng có kích thước nhỏ
Khi mảng có các giá trị phân bố đều
Trong thuật toán tìm kiếm nhị phân, số lần so sánh tối đa cần thiết để tìm kiếm một phần tử trong mảng có n phần tử là bao nhiêu?
O(n)
O(log n)
O(n log n)
O(1)
Điều kiện nào sau đây không cần thiết cho thuật toán tìm kiếm nhị phân?
Mảng phải được sắp xếp
Các phần tử trong mảng phải là số nguyên
Mảng không được chứa giá trị trùng lặp
Mảng phải có ít nhất một phần tử
Trong trường hợp nào tìm kiếm nhảy sẽ hoạt động hiệu quả nhất?
Khi mảng có kích thước nhỏ
Khi mảng có kích thước lớn và được sắp xếp
Khi mảng không được sắp xếp
Khi mảng có các giá trị phân bố ngẫu nhiên
