WorksheetsCấu trúc dữ liệu và Giải thuật
Total questions: 84
Worksheet time: 42mins
Cấu trúc dữ liệu (Data Structure) là gì?
Là phần cứng máy tính dùng để lưu trữ dữ liệu.
Là cách tổ chức và lưu trữ dữ liệu trong máy tính để có thể truy xuất và xử lý dễ dàng.
Là một ngôn ngữ lập trình.
Là quy trình phát triển phần mềm.
Đâu là ví dụ của kiểu dữ liệu sơ cấp (Primitive Data Type)?
Mảng (Array).
Danh sách liên kết.
Số nguyên (Integer), Ký tự (Character).
Cây (Tree).
Cấu trúc dữ liệu nào sau đây thuộc loại Tuyến tính (Linear)?
Cây (Tree).
Đồ thị (Graph).
Mảng (Array), Danh sách liên kết, Hàng đợi.
Bảng băm.
Giải thuật (Algorithm) là gì?
Là một chương trình máy tính đã biên dịch.
Là một chuỗi hữu hạn các thao tác để giải một bài toán nào đó.
Là phần cứng xử lý thông tin.
Là dữ liệu đầu vào.
Tính chất "Hữu hạn" của giải thuật nghĩa là gì?
Giải thuật phải giải quyết được mọi bài toán.
Giải thuật phải luôn kết thúc sau một số hữu hạn bước.
Giải thuật tốn ít bộ nhớ nhất.
Các bước thực hiện không cần rõ ràng.
Tính chất "Xác định" của giải thuật đòi hỏi điều gì?
Mỗi bước phải được xác định rõ ràng, thực hiện chính xác và có mục đích nhất định.
Giải thuật phải viết bằng tiếng Anh.
Giải thuật phải chạy nhanh nhất.
Giải thuật phải xử lý được vô hạn dữ liệu.
Phương pháp biểu diễn giải thuật nào sử dụng các hình khối để mô tả?
Ngôn ngữ tự nhiên.
Mã giả (Pseudocode).
Lưu đồ (Sơ đồ khối).
Ngôn ngữ lập trình C++.
Trong sơ đồ khối, hình thoi thường được dùng để biểu diễn thao tác nào?
Bắt đầu/Kết thúc.
Nhập/Xuất dữ liệu.
Điều kiện rẽ nhánh (So sánh).
Tính toán xử lý.
Độ phức tạp thời gian của giải thuật phụ thuộc chủ yếu vào yếu tố nào?
Số lượng bước thực hiện.
Dung lượng bộ nhớ sử dụng.
Số lượng phép toán thực hiện.
Tốc độ xử lý của máy tính.
Ngôn ngữ lập trình sử dụng, tốc độ của máy tính, khối lượng (kích thước) của dữ liệu đầu vào, và trình biên dịch, yếu tố nào ảnh hưởng đến độ phức tạp của thuật toán?
Ngôn ngữ lập trình sử dụng.
Tốc độ của máy tính.
Khối lượng (kích thước) của dữ liệu đầu vào.
Trình biên dịch.
Ký hiệu Big-O (O) dùng để đánh giá điều gì của giải thuật?
Độ chính xác của kết quả.
Thời gian chạy lâu nhất (trường hợp xấu nhất) của thuật toán theo kích thước dữ liệu đầu vào.
Số lượng dòng code.
Dung lượng ổ cứng cần thiết.
Độ phức tạp $O(1)$ có ý nghĩa gì?
Số phép tính tăng tuyến tính theo n.
Số phép tính là hằng số, không phụ thuộc vào khối lượng dữ liệu đầu vào.
Số phép tính tăng theo hàm logarit.
Số phép tính tăng theo hàm mũ.
Giải thuật có độ phức tạp thường gặp trong trường hợp nào?
Tìm kiếm nhị phân.
Các vòng lặp lồng nhau (ví dụ: sắp xếp nổi bọt).
Truy xuất phần tử mảng theo chỉ số.
Tính giai thừa.
Tiêu chuẩn nào sau đây KHÔNG phải là tiêu chuẩn chính để lựa chọn cấu trúc dữ liệu?
Tốc độ truy xuất dữ liệu.
Dễ dàng cài đặt.
Dung lượng bộ nhớ.
Độ phức tạp của thuật toán.
Bước đầu tiên trong quy trình làm phần mềm (theo mô hình thác nước) là gì?
Viết code (Cài đặt).
Kiểm thử (Testing).
Ý tưởng (Concept) và Xác định yêu cầu.
Bảo trì.
Mã giả (Pseudocode) có đặc điểm gì?
Máy tính có thể chạy trực tiếp được.
Sử dụng ngôn ngữ tựa ngôn ngữ lập trình để diễn đạt giải thuật, dễ công kênh hơn so đồ khối.
Rất trực quan nhờ các hình vẽ.
Phụ thuộc chặt chẽ vào phần cứng.
Yếu tố nào sau đây KHÔNG ảnh hưởng trực tiếp đến thời gian chạy thực tế của giải thuật trên máy?
Tốc độ thực thi lệnh của máy.
Chất lượng mã máy do trình dịch tạo ra.
Màu sắc của giao diện phần mềm.
Độ phức tạp về thời gian của thuật toán.
Độ phức tạp thường thấy ở các thuật toán nào?
Bubble Sort.
Merge Sort.
Selection Sort.
Insertion Sort.
Chương trình máy tính là gì?
Là phần cứng CPU.
Là một hình thức của thuật toán được viết bằng ngôn ngữ lập trình để máy tính hiểu và thực hiện.
Là sơ đồ khối trên giấy.
Là kết quả đầu ra (Output).
Cấu trúc dữ liệu dạng Cây (Tree) có đặc điểm gì?
Các phần tử liên kết tuần tự nối tiếp nhau.
Mỗi phần tử có thể liên kết với nhiều phần tử khác theo phân cấp (từng mức).
Sử dụng hàm băm để ánh xạ.
Lưu trữ dữ liệu dưới dạng bảng.
Tính "Phổ biến" của giải thuật nghĩa là gì?
Giải thuật phải giải quyết được một lớp các vấn đề tương tự.
Ai cũng biết giải thuật đó.
Giải thuật phải chạy trên mọi hệ điều hành.
Giải thuật phải ngắn gọn.
Mục tiêu của bài toán tìm kiếm là gì?
Tìm kiếm phần tử trong một danh sách.
Sắp xếp các phần tử theo thứ tự.
Tìm giá trị lớn nhất trong danh sách.
Tìm giá trị nhỏ nhất trong danh sách.
Hoạt động nào được thực hiện để tìm bản ghi có khóa X trong một khối thông tin lưu trữ?
Sắp xếp lại dữ liệu.
Tìm bản ghi có khóa X cho trước trong một khối thông tin lưu trữ.
Xóa dữ liệu trùng lặp.
Mã hóa dữ liệu.
Tìm kiếm tuyến tính (Linear Search) được thực hiện như thế nào?
Chia đôi mảng liên tục.
Duyệt từ đầu đến cuối mảng và so sánh từng phần tử với khóa cần tìm.
Dựa vào hàm băm để tính địa chỉ.
Sắp xếp mảng trước rồi mới tìm.
Điều kiện để áp dụng Tìm kiếm nhị phân (Binary Search) là gì?
Mảng phải có kích thước chẵn.
Mảng phải chứa số nguyên.
Mảng đã được sắp xếp thứ tự.
Mảng chưa được sắp xếp.
Độ phức tạp trong trường hợp xấu nhất của Tìm kiếm tuyến tính là bao nhiêu?
$O(1)$.
.
$O(n)$.
O(n2) .
Độ phức tạp trong trường hợp xấu nhất của Tìm kiếm nhị phân là bao nhiêu?
$O(n)$.
.
.
$O(1)$.
Trong tìm kiếm nhị phân, tại mỗi bước, không gian tìm kiếm thay đổi như thế nào?
Giảm đi 1 phần tử.
Giảm đi một nửa ($1/2$).
Tăng lên gấp đôi.
Không thay đổi.
Trường hợp tốt nhất của Tìm kiếm tuyến tính xảy ra khi nào?
Phần tử cần tìm nằm ở cuối mảng.
Phần tử cần tìm nằm ở vị trí đầu tiên của mảng.
Không tìm thấy phần tử.
Mảng đã sắp xếp.
Nếu mảng có 1000 phần tử, tìm kiếm tuyến tính trong trường hợp xấu nhất cần so sánh bao nhiêu lần?
1 lần.
10 lần.
500 lần.
1000 lần.
Công thức tính vị trí giữa (mid) trong tìm kiếm nhị phân thường dùng là gì?
$mid = (left + right) / 2$.
$mid = left + right$.
$mid = left - right$.
$mid = (left * right) / 2$.
Trong tìm kiếm nhị phân trên mảng tăng dần, nếu $A[mid] < X$, ta tìm tiếp ở đâu?
Dừng tìm kiếm.
Tìm ở nửa bên trái (từ left đến mid-1).
Tìm ở nửa bên phải (từ mid+1 đến right).
Trả về kết quả không tìm thấy.
Ưu điểm của tìm kiếm tuyến tính so với tìm kiếm nhị phân là gì?
Tốc độ nhanh hơn nhiều.
Không yêu cầu mảng phải được sắp xếp trước.
Tiết kiệm bộ nhớ hơn.
Code phức tạp hơn.
Hàm tìm kiếm thường trả về giá trị -1 khi nào?
Khi tìm thấy phần tử ở vị trí đầu tiên.
Khi mảng bị lỗi.
Khi không tìm thấy phần tử thỏa mãn yêu cầu.
Khi tìm thấy phần tử ở cuối cùng.
Tìm kiếm nhị phân có phù hợp với danh sách liên kết đơn không?
Rất phù hợp.
Không, vì không thể truy cập ngẫu nhiên phần tử giữa tức thời (truy cập tuần tự).
Có, vì danh sách liên kết luôn sắp xếp.
Phù hợp nếu danh sách liên kết có kích thước nhỏ.
Trong đoạn code tìm kiếm tuyến tính while ((i
Chỉ khi tìm thấy x.
Chỉ khi duyệt hết mảng.
Khi tìm thấy x HOẶC đã duyệt hết mảng.
Khi $i > n$.
Độ phức tạp trung bình của tìm kiếm tuyến tính là bao nhiêu?
$O(1)$.
$O((N+1)/2)$.
O(logN) .
O(N2) .
Nếu dữ liệu thường xuyên thay đổi (thêm/xóa), giải thuật tìm kiếm nào thường bị ảnh hưởng hiệu suất do phải sắp xếp lại?
Tìm kiếm tuyến tính.
Tìm kiếm nhị phân.
Cả hai đều không ảnh hưởng.
Tìm kiếm ngẫu nhiên.
Với mảng $A = [2, 6, 8, 9, 11, 10, 32, 18]$, tìm X = 10 bằng tìm kiếm tuyến tính. Số lần so sánh là bao nhiêu?
1.
4.
638.
8.
Cho mảng đã sắp xếp $A = [1, 2, 4, 5, 7, 8, 9, 11, 15, 17]$. Tìm X = 8 bằng nhị phân. Giá trị Mid đầu tiên là bao nhiêu?
5
739
8
4
Trong tìm kiếm nhị phân, điều kiện lặp thường là gì?
left < right
left <= right
left != right
left > right
Giải thuật tìm kiếm tuyến tính phù hợp nhất khi nào?
Dữ liệu cực lớn
Cần tốc độ tìm kiếm nhanh nhất
Danh sách nhỏ hoặc chưa sắp xếp
Danh sách đã sắp xếp
Sắp xếp trong (Internal Sorting) là gì?
Sắp xếp dữ liệu lưu trên bộ nhớ ngoài (ổ cứng).
Sắp xếp dữ liệu khi kích thước quá lớn không đủ bộ nhớ RAM.
Sắp xếp dữ liệu được lưu đầy đủ trong bộ nhớ trong (RAM).
Sắp xếp thông qua các con trỏ gián tiếp.
Độ phức tạp thời gian trung bình của thuật toán Interchange Sort là bao nhiêu?
$O(n)$
O(nlogn)
$O(1)$
Thuật toán nào sau đây luôn có độ phức tạp trong mọi trường hợp (tốt nhất, xấu nhất, trung bình)?
Quick Sort
Interchange Sort & Selection Sort
Merge Sort
Heap Sort
Ý tưởng chính của thuật toán Selection Sort là gì?
Đổi chỗ các cặp nghịch thế liên tiếp.
Chia dãy thành hai nửa rồi trộn lại.
Chọn phần tử nhỏ nhất trong dãy chưa sắp xếp và đưa về vị trí đúng đầu tiên.
Chèn phần tử đang xét vào vị trí thích hợp trong dãy con đã sắp xếp trước đó.
Trong thuật toán Insertion Sort, nếu dãy ban đầu đã được sắp xếp đúng thứ tự, độ phức tạp là bao nhiêu?
$O(n)$
O(nlogn)
Thuật toán Bubble Sort hoạt động theo nguyên tắc nào?
A. Chọn phần tử nhỏ nhất đưa về đầu.
B. Chia để trị.
C. Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận nếu chúng ngược thứ tự mong muốn.
D. Xây dựng cấu trúc Heap.
Thuật toán nào được xem là nhanh nhất trong các giải thuật sắp xếp và hoạt động theo chiến lược "Chia để trị"?
A. Bubble Sort
B. Quick Sort
C. Insertion Sort
D. Selection Sort
Trong Quick Sort, phần tử chốt (pivot) có vai trò gì?
A. Là phần tử nhỏ nhất của dãy.
B. Dùng để chia dãy thành 2 phần: phần nhỏ hơn pivot và phần lớn hơn pivot.
C. Là phần tử đứng cuối cùng sau khi sắp xếp.
D. Là phần tử trung vị của dãy.
Độ phức tạp thời gian xấu nhất của Quick Sort là bao nhiêu?
A. O(nlogn)
B. $O(n)$
C.
D.
Heap Sort sử dụng cấu trúc dữ liệu nào để sắp xếp?
Ngăn xếp (Stack)
Hàng đợi (Queue)
Cây nhị phân hoàn chỉnh (Heap)
Danh sách liên kết
Trong Heap Sort, giai đoạn 1 dùng để làm gì?
Sắp xếp dãy giảm dần.
Tạo Heap từ dãy ban đầu (vun đống).
Loại bỏ phần tử lớn nhất.
Chia dãy thành các phần tử nhỏ.
Shell Sort là biến thể cải tiến của thuật toán nào?
Bubble Sort
Selection Sort
Insertion Sort
Quick Sort
Shell Sort hoạt động dựa trên nguyên tắc nào?
Phân hoạch dãy thành các dãy con cách nhau $h$ vị trí và sắp xếp chèn trên các dãy con này.
Chia đôi dãy liên tục.
Sử dụng 2 vòng lặp lồng nhau để đổi chỗ trực tiếp.
Vun đống các phần tử.
Thuật toán Merge Sort có độ phức tạp thời gian là bao nhiêu trong trường hợp xấu nhất?
$O(n)$
Tính "ổn định" (stability) trong thuật toán sắp xếp nghĩa là gì?
Thuật toán luôn chạy với thời gian cố định.
Không làm thay đổi bộ nhớ.
Không làm thay đổi thứ tự tương đối của các phần tử có cùng giá trị khóa.
Không bị lỗi khi dữ liệu lớn.
Thuật toán nào sau đây KHÔNg cần bộ nhớ phụ đáng kể (in-place) nhưng vẫn đạt ?
Merge Sort
Heap Sort
Radix Sort
Counting Sort
Với danh sách có kích thước nhỏ, thuật toán nào thường được ưu tiên do cài đặt đơn giản?
Merge Sort
Quick Sort
Insertion Sort hoặc Bubble Sort
Heap Sort
Trong thuật toán Merge Sort, thao tác quan trọng nhất là gì?
Chọn phần tử chốt.
Vun đống.
Trộn (Merge) hai dãy con đã sắp xếp thành một dãy sắp xếp.
Đổi chỗ trực tiếp.
Nếu danh sách đã được sắp xếp một phần, thuật toán nào sẽ tận dụng tốt nhất điều này?
Selection Sort
Insertion Sort
Quick Sort
Heap Sort
Điều kiện dùng của thuật toán Quick Sort là gì?
Khi danh sách con có độ dài bằng 1 hoặc 0.
Khi không còn cặp nghịch thế nào.
Khi chiều cao cây bằng 0.
Khi số lần lặp đạt .
Đặc điểm chính của biến động (dynamic variable) là gì?
Có tên gọi tường minh và địa chỉ cố định.
Không có tên gọi tường minh, được cấp phát khi cần và giải phóng khi xong.
Chỉ tồn tại trong hàm main.
Kích thước cố định không đổi.
Trong C++, toán tử nào dùng để cấp phát bộ nhớ động?
malloc
alloc
new
create
Cấu trúc tự trỏ (Self-referential structure) là gì?
Cấu trúc chứa một biến nguyên trỏ đến chính nó.
Cấu trúc chứa ít nhất một con trỏ trỏ đến vùng dữ liệu có cùng kiểu cấu trúc.
Cấu trúc không chứa dữ liệu nào.
Cấu trúc chỉ chứa các con trỏ hàm.
Ưu điểm của Danh sách liên kết (Linked List) so với Mảng (Array) là gì?
Truy xuất phần tử ngẫu nhiên nhanh hơn ($O(1)$).
Sử dụng bộ nhớ hiệu quả và linh động về số lượng phần tử (không cần kích thước cố định).
Cài đặt đơn giản hơn mảng.
Không tốn bộ nhớ cho con trỏ liên kết.
Trong Danh sách liên kết đơn, mỗi nút (Node) gồm những thành phần nào?
Chỉ chứa dữ liệu (Data).
Chỉ chứa địa chỉ nút kế tiếp.
Thành phần dữ liệu (Data) và thành phần liên kết (con trỏ Next).
Dữ liệu và hai con trỏ (Next, Prev).
Để quản lý một DSLK đơn, ta thường cần ít nhất bao nhiêu con trỏ?
1 con trỏ (First) hoặc 2 con trỏ (First và Last).
Không cần con trỏ nào.
1 mảng các con trỏ.
Chỉ cần con trỏ Last.
Thao tác thêm một phần tử vào ĐẦU danh sách liên kết đơn có độ phức tạp là bao nhiêu?
$O(n)$
$O(1)$
Ngăn xếp (Stack) hoạt động theo nguyên tắc nào?
FIFO (Vào trước ra trước).
LIFO (Vào sau ra trước).
Ngẫu nhiên.
Ưu tiên (Priority).
Thao tác thêm một đối tượng vào Stack gọi là gì?
Pop
Push
Dequeue
Enqueue
Hàng đợi (Queue) hoạt động theo nguyên tắc nào?
LIFO (Vào sau ra trước).
FIFO (Vào trước ra trước).
Ngẫu nhiên.
Ưu tiên (Priority).
Trong Hàng đợi cài đặt bằng mảng, biến Front và Back dùng để làm gì?
Front quản lý phần tử cuối, Back quản lý phần tử đầu.
Front quản lý chỉ số phần tử đầu, Back quản lý chỉ số phần tử cuối.
Chỉ dùng để đếm số lượng phần tử.
Front trỏ tới phần tử giữa, Back trỏ tới phần tử cuối.
Nếu cài đặt Stack bằng DSLK đơn, đỉnh (Top) của Stack nên đặt ở đâu để tối ưu?
Cuối danh sách (Last).
Giữa danh sách.
Đầu danh sách (First).
Bất kỳ đâu.
Danh sách liên kết kép (Doubly Linked List) khác DSLK đơn ở điểm nào?
Mỗi nút có thêm con trỏ tới nút phía trước (Previous).
Nút cuối trỏ về nút đầu.
Chỉ đi được một chiều.
Không dùng con trỏ.
Danh sách liên kết vòng (Circular Linked List) có đặc điểm gì?
Không có phần tử đầu.
Nút cuối cùng liên kết với nút đầu tiên thay vì trỏ tới NULL.
Chỉ có một nút duy nhất.
Không có phần tử cuối.
Ứng dụng nào sau đây thường sử dụng Stack?
Quản lý hàng đợi in ấn.
Chuyển đổi biểu thức trung tố sang hậu tố và tính giá trị biểu thức.
Quản lý danh sách khách hàng chờ.
Sắp xếp file.
Khi xóa một nút P đứng sau nút Q trong DSLK đơn, ta cần làm gì?
Q->next = P->next; delete P;
P->next = Q->next; delete Q;
Q->next = NULL; delete P;
delete P;
Trong bài toán Tháp Hà Nội, việc khử đệ quy có thể sử dụng cấu trúc dữ liệu nào?
Queue
Array
Stack
Tree
Biểu thức hậu tố của biểu thức trung tố (A + B) * C là gì?
* + A B C
A B + C *
A B C + *
+ A B C
Khi thêm phần tử vào hàng đợi (Enqueue), vị trí thêm vào là ở đâu?
Đầu hàng đợi (Front).
Cuối hàng đợi (Back/Rear).
Giữa hàng đợi.
Bất kỳ vị trí nào trống.
Trong cài đặt DSLK đơn, con trỏ next của nút cuối cùng (Last) trỏ đi đâu?
Trỏ về nút đầu (First).
Trỏ về chính nó.
Trỏ tới NULL.
Không xác định.
Nút gốc (Root) của cây là gì?
Nút không có con.
Nút không có cha.
Nút có bậc lớn nhất.
Nút nằm ở mức cao nhất (mức n).
Bậc của một nút là gì?
Số lượng nút cha của nó.
Số lượng cây con (nhánh con) của nút đó.
Số lượng nút lá trong cây con của nó.
Số lượng nút cha và con của nó.
