Tổng hợp câu hỏi phỏng vấn về cấu trúc dữ liệu và giải thuật
Câu 1: Độ phức tạp của thuật toán sắp xếp nổi bọt?
A. N
B. 2N
C. N * Log(N)
Câu 2: Độ phức tạp của thuật toán sắp xếp Quicksort
a. N
b. 2N
c. N * Log(N)
Câu 3: Cấu trúc dữ liệu nào hỗ trợ nhanh nhất việc kiểm tra một phần tử có nằm trong danh sách hay không?
A. ArrayList
B. HashSet
C. TreeMap
Câu 4: Giải thuật đệ quy là?
A. 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
B. Trong giải thuật của nó có lời gọi tới chính nó
C. 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ả
D. 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
Câu 5: Ngăn xếp làm việc theo nguyên tắc
A. LILO ( last in last out)
B. LIFO ( last in first out)
c. FOLO (first out last out)
d. FIFO ( first in first out)
Câu 6: Định nghĩa danh sách tuyến tính hàng đợi:
A. Là một danh sách tuyến tính trong đó phép bổ sung một phần tử và phép loại bỏ một phần tử được thực hiện ở tại một vị trí bất kì trong danh sách.
B. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử được thực hiện ở một đầu, gọi là lối sau (rear) hay lối trước (front). Phép loại bỏ không thực hiện được.
C. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử hay loại bỏ được thực hiện ở một đầu danh sách gọi là đỉnh (Top)
D. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung phần tử ở một đầu, gọi là lối sau (rear) và phép loại bỏ phần tử được thực hiện ở đầu kia, gọi là lối trước (front).
Câu 7: Độ phức tạp của việc tìm kiếm 1 số trong 1 mảng số nguyên đã sắp xếp là bao nhiêu?
A. N
B. N * Log(N)
C. Log(N)
D. N
Câu 8: Tạo một file ignore.txt gồm 500 nghìn phần tử random từ 1-> 2triệu. Tạo một file data.txt có 1,5 triệu phần tử. Các phần tử tăng dần từ 1 đến 2 triệu và loại trừ các phần tử trong file ignore yêu cầu: Có thể dùng bất kỳ ngôn ngữ gì để thực hiện.
Áp dụng các kiến thức về cấu trúc dữ liệu giải thuật sao cho code tối ưu và thời gian thực thi ngắn nhất có thể.
Bài nộp bao gồm code và thời gian thực thi đoạn code đó. Không bao gồm các file dữ liệu.
Câu 9: A là một sinh viên CNTT, làm thêm việc shipper hàng ngày. A nhận ra, mỗi ngày mình chỉ có thể chở tổng cộng 100kg. Nên giờ A cần tìm một thuật toán để tối ưu giá trị thu lại của mình. Vì vậy A lên danh sách các đơn hàng mỗi ngày. Trong ngày hôm nay, A có danh sách như sau:
Cân nặng = [20, 30, 40, 50]
Giá trị = [10, 40, 10, 20]
Theo danh sách trên, A sẽ trở món hàng ở vị trí 0, 1, 3 - tổng cân nặng là 20 + 30 + 50 = 100kg và có tổng giá trị là 10 + 40 + 20 = 70 là lớn nhất.
Yếu cầu: viết hàm với đầu vào là 2 danh sách, danh sách cân nặng và giá trị theo thứ tự tương ứng của từng mặt hàng, tính ra phương án cho A chọn những mặt hàng nào để tối ưu giá trị nhận được.
Input:
Cân nặng = [20,30,40,50]
Giá trị = [10,40,10,20]
Output:
[0, 1, 3],100,70
Câu 10: Ai là người nổi tiếng:
Người nổi tiếng trong một nhóm là người không biết ai trong nhóm đó, nhưng tất cả mọi người trong nhóm đó đều biết anh ta.
Ví dụ 1: Cho một nhóm người, dưới dạng ma trận như sau:
| A | B | C | |
|---|---|---|---|
| A | 0 | 0 | 0 |
| B | 1 | 0 | 1 |
| C | 1 | 0 | 0 |
Ví dụ 2:
| A | B | C | |
|---|---|---|---|
| A | 0 | 1 | 0 |
| B | 1 | 0 | 1 |
| C | 1 | 1 | 0 |
