Font size
WorksheetsCâu hỏi trắc nghiệm về cấu trúc dữ liệu
Total questions: 59
Worksheet time: 37mins
Phát biểu nào sau đây là đúng khi nói về đường đi từ đỉnh 2 về đỉnh 0?
Có đường đi độ dài 2
Nếu x ≡ y, (x,y) gọi là vòng
Tồn tại duy nhất một đường đi
Không có đường đi nào
Phát biểu nào sau đây là đúng khi nói về hàng đợi (Queue)?
Chỉ có thể cài đặt bằng danh sách liên kết
Hoạt động theo nguyên tắc LIFO (Last-In, First-Out)
Có thể cài đặt bằng cấu trúc dữ liệu mảng
Không thể thêm phần tử khi hàng đợi đã đầy
Phát biểu nào sau đây là đúng khi nói về cấu trúc dữ liệu cây?
Cây là một cấu trúc dữ liệu động
Cây là một cấu trúc dữ liệu trừu tượng
Có thể cài đặt bằng mảng
Cả ba câu đều đúng
Phát biểu nào sau đây là đúng khi nói về đặc điểm của danh sách?
Các phần tử được lưu trữ liền kề trong bộ nhớ
Chỉ có thể truy cập phần tử đầu tiên
Cả hai đều đúng
Cả hai đều sai
Phát biểu nào sau đây là đúng khi nói về danh sách liên kết kép?
Mỗi phần tử chỉ có một mối liên kết.
Thành phần liên kết có 2 mối liên kết với 2 phần tử khác trong danh sách.
Chỉ có thể duyệt danh sách theo một chiều.
Việc thêm/xóa phần tử rất phức tạp.
Phát biểu nào sau đây là đúng khi nói về thuật toán đệ quy quay lui?
Tìm lời giải bằng phương pháp thử - sai
Phải ghi nhận trạng thái để quay lui
Là một dạng bài toán vét cạn
Cả ba câu đều đúng
Phát biểu nào sau đây là đúng về danh sách liên kết?
Phát biểu nào sau đây là đúng về danh sách liên kết?
Kích thước của danh sách là cố định.
Các phần tử phải được lưu trữ liền kề nhau trong bộ nhớ.
Danh sách liên kết có thể thêm, xóa phần tử tại vị trí bất kỳ.
Truy cập một phần tử bất kỳ có độ phức tạp là O(1).
Phát biểu nào sau đây là đúng với cây nhị phân có chiều cao là h?
Số nút tối thiểu là h.
Số nút tối đa có thể có trong cây là 2^h - 1.
Số nút tối đa có thể có trong cây là 2^(h-1).
Số nút lá luôn bằng số nút trong.
Phát biểu nào sau đây là đúng?
Danh sách liên kết khó khăn khi thêm/bớt phần tử.
Danh sách đặc dễ dàng thêm/bớt phần tử ở giữa.
Danh sách liên kết dễ dàng thêm/bớt phần tử vào danh sách.
Danh sách đặc có kích thước linh động.
Phát biểu nào sau đây là đúng?
Có thể tồn tại nhiều đường đi từ gốc đến một nút bất kỳ trong cây.
Luôn tồn tại một đường đi duy nhất từ gốc đến một nút bất kỳ trong cây.
Cây không có khái niệm đường đi.
Một số nút trong cây không thể đến được từ gốc.
Phát biểu nào sau đây là đúng?
Cây nhị phân hoàn chỉnh không phải là cây nhị phân đầy đủ.
Cây nhị phân đầy đủ là cây nhị phân hoàn chỉnh.
Cây nhị phân đầy đủ không có nút lá.
Cây nhị phân hoàn chỉnh luôn cân bằng.
Phát biểu nào sau đây là sai?
Cài đặt theo đệ quy thường dễ hiểu và sáng sủa.
Cài đặt theo đệ q
Phát biểu nào sau đây là sai?
Cài đặt theo đệ quy thường dễ hiểu và sáng sủa.
Cài đặt theo đệ quy làm cho chương trình ít tốn bộ nhớ.
Đệ quy có thể dẫn đến tràn bộ nhớ stack.
Mọi bài toán đệ quy đều có thể khử đệ quy.
Phát biểu nào sau đây là sai đối với dãy A, n phần tử được gọi là Heap (Max Heap)?
A[i] >= A[2*i+1] (nếu có).
A[i] >= A[2*i+2] (nếu có).
Phần tử đầu dãy là phần tử lớn nhất.
Phần tử đầu dãy là phần tử nhỏ nhất.
Phát biểu nào sau đây là sai khi chọn để điền vào dấu '...' trong phát biểu sau: 'Thuật toán là một dãy hữu hạn các thao tác, trong đó...'?
các thao tác được xác định rõ ràng.
sau một số hữu hạn bước sẽ cho ra kết quả.
thứ tự thao tác không quan trọng.
có dữ liệu đầu vào và đầu ra.
Phát biểu nào sau đây là sai khi nói về ngăn xếp (Stack)?
Có thể cài đặt ngăn xếp bằng mảng.
Có thể cài đặt ngăn xếp bằng danh sách liên kết.
Ngăn xếp là kiểu tổ chức dữ liệu theo kiểu FIFO (First-In, First-Out).
Cả ba câu đều sai.
Phát biểu nào sau đây là sai về cây nhị phân?
Một cây nhị phân có thể rỗng.
Mỗi nút có tối đa hai cây con.
Tất cả các cây nhị phân đều phải có ít nhất một nút.
Cây con bên trái và cây con bên phải là hai cây nhị phân.
Phát biểu nào sau đây là sai về cây nhị phân?
Một cây nhị phân có thể rỗng.
Mỗi nút có tối đa hai cây con.
Tất cả các cây nhị phân đều phải có ít nhất một nút.
Cây con bên trái và cây con bên phải là hai cây nhị phân phân biệt.
Phát biểu nào sau đây là sai về danh sách đặc (mảng)?
Kích thước thường cố định.
Truy cập phần tử bất kỳ nhanh (O(1)).
Không thể thêm, xóa phần tử trong danh sách đặc.
Chèn/xóa ở giữa danh sách tốn thời gian (O(n)).
Phát biểu nào sau đây là sai về danh sách liên kết?
Việc lưu trữ các phần tử trong danh sách liên kết khác với lưu trữ các phần tử trong mảng.
Các phần tử trong danh sách liên kết không cần phải lưu trữ liền kề trong bộ nhớ.
Danh sách liên kết là tập hợp các nút, bao gồm 2 phần, phần thông tin và phần liên kết đến nút kế tiếp trong danh sách.
Cả ba câu trên đều đúng.
Phát biểu nào sau đây là sai?
Danh sách đặc có thể thêm phần tử vào cuối.
Danh sách đặc có thể xóa phần tử.
Danh sách đặc chỉ được phép bổ sung phần tử.
Kích thước của danh sách đặc cần được khai báo trước.
Phát biểu nào sau đây là sai?
Hàm đệ quy có thể trả về kiểu void.
Hàm đệ quy phải có trường hợp cơ sở (điểm dừng).
Hàm đệ quy phải trả về kiểu int.
Phát biểu nào sau đây là sai?
A. Hàm đệ quy có thể trả về kiểu void.
B. Hàm đệ quy phải có trường hợp cơ sở (điểm dừng).
C. Hàm đệ quy phải trả về kiểu int.
D. Hàm đệ quy gọi lại chính nó.
Phát biểu nào sau đây là sai?
A. Độ phức tạp của thuật toán thêm/bớt một phần tử vào cuối danh sách đặc là O(1) (nếu chưa đầy).
B. Độ phức tạp của thuật toán thêm/bớt một phần tử vào đầu danh sách đặc là O(n).
C. Độ phức tạp của thuật toán thêm/bớt một phần tử trong danh sách đặc tương đương O(1).
D. Độ phức tạp truy cập phần tử trong danh sách đặc là O(1).
Phát biểu nào sau đây là sai?
A. Một số bài toán giải bằng đệ quy có thể có độ phức tạp lớn.
B. Cùng một bài toán, thuật toán lặp có thể hiệu quả hơn thuật toán đệ quy.
C. Thuật toán đệ quy luôn có độ phức tạp lớn hơn so với độ phức tạp của các thuật toán khác khi cùng giải quyết một bài toán.
D. Thuật toán QuickSort đệ quy có độ phức tạp trung bình là O(n log n).
Phát biểu nào sau đây sai đối với đồ thị vô hướng G có n đỉnh?
A. Số cạnh tối đa là n*(n-1)/2.
B. Một đồ thị có thể không có cạnh nào.
C. Giữa 2 đỉnh bất kỳ thuộc G, luôn tồn tại đường đi.
D. Một đỉnh có thể không được kết nối với đỉnh nào khác.
Phát biểu nào sau đây sai khi nói về danh sách liên kết?
Phát biểu nào sau đây sai khi nói về danh sách liên kết?
A. Danh sách liên kết là một cấu trúc dữ liệu động.
B. Danh sách liên kết là một tập hợp các phần tử nằm liên tiếp nhau trong bộ nhớ.
C. Việc chèn/xóa phần tử trong danh sách liên kết (khi biết vị trí) là nhanh chóng.
D. Các phần tử của danh sách liên kết được gọi là các nút (node).
Phát biểu nào sau đây sai?
A. O(n) có độ phức tạp nhỏ hơn O(n^2).
B. O(log n) có độ phức tạp nhỏ hơn O(n).
C. O(2n) có độ phức tạp nhỏ hơn O(3n+5).
D. O(n!) có độ phức tạp lớn hơn O(2^n).
Phương pháp nào sau đây không được dùng để biểu diễn cây?
A. Mảng
B. Con trỏ (Danh sách liên kết)
C. Hình vẽ
D. Cả A và B đều được dùng
Phương pháp sắp xếp nhanh (Quick Sort) chính là phương pháp?
A. Chọn
B. Chèn
C. Phân đoạn
D. Trộn
Sắp xếp theo thứ tự tăng dần của cấp thời gian thực hiện chương trình.
A. O(1), O(n), O(log₂n), O(nlog₂n)
B. O(1), O(log₂n), O(n), O(nlog₂n)
C. O(log₂n), O(1), O(n), O(nlog₂n)
D. O(1), O(l
Sắp xếp theo thứ tự tăng dần của cấp thời gian thực hiện chương trình.
A. O(1), O(n), O(log₂n), O(nlog₂n)
B. O(1), O(log₂n), O(n), O(nlog₂n)
C. O(log₂n), O(1), O(n), O(nlog₂n)
D. O(1), O(log₂n), O(nlog₂n), O(n)
Sau một số ... bước thực hiện giải thuật cho chúng ta đạt được kết quả mong muốn.
A. Vô hạn
B. Hữu hạn
C. Tối thiểu
D. Tối đa
Số nút tối đa ở mức 5 trong cây nhị phân là bao nhiêu? (Giả sử mức gốc là mức 1)
A. 8
B. 16
C. 31
D. 32
Số nút tối đa trong cây nhị phân có chiều cao bằng 5 là bao nhiêu?
A. 16
B. 25
C. 31
D. 32
Thao tác nào dưới đây thực hiện được trên Ngăn xếp (Stack)?
A. Thêm và loại bỏ phần tử tại vị trí bất kỳ.
B. Thêm ở đầu và loại bỏ ở cuối.
C. Thêm và loại bỏ phần tử luôn thực hiện tại vị trí đỉnh (top).
D. Chỉ cho phép xem phần tử ở đáy.
Thao tác Push và Pop đề cập tới cấu trúc dữ liệu nào sau đây?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Cây (Tree)
D. Danh sách (List)
Thao tác thêm phần tử (insert/enqueue) và lấy phần tử (remove/dequeue) thường đề cập tới cấu trúc dữ liệu nào?
A. Ngăn xếp (Stack)
B. Đồ thị (Graph)
C. Cây (Tree)
D. Hàng đợi (Queue)
Thời gian thực hiện của một thuật toán được tính toán ra kết quả là
Thời gian thực hiện của một thuật toán được tính toán ra kết quả là t(n) = 2*n + n*log(n). Ký hiệu O của độ phức tạp thuật toán trên là gì?
O(n)
O(log n)
O(n log n)
O(n²)
Thời gian thực hiện thuật toán để thêm một nút vào sau nút p (nút cuối của một danh sách liên kết đơn, có con trỏ tail) là bao nhiêu?
O(1)
O(n)
O(log n)
O(n²)
Thời gian thực hiện thuật toán tìm kiếm 1 phần tử trong danh sách liên kết có chiều dài n trong trường hợp xấu nhất là bao nhiêu?
O(1)
O(log n)
O(n)
O(n²)
Thuật ngữ nào dưới đây được sử dụng để mô tả một thuật toán có độ phức tạp là O(n)?
Độ phức tạp hằng số
Độ phức tạp tuyến tính
Độ phức tạp toàn phương
Độ phức tạp logarit
Thuật toán sắp xếp nào sau đây sử dụng chiến thuật "chia để trị"?
Sắp xếp chèn (Insertion Sort)
Sắp xếp nhanh (Quick Sort)
Sắp xếp nổi bọt (Bubble Sort)
Sắp xếp chọn (Selection Sort)
Thuật toán sắp xếp nào sau đây, có thời gian thực hiện trong trường hợp xấu nhất không phải là O(n²)?
Quick Sort
Bubble Sort
Insertion Sort
Heap Sort
Thuật toán tìm kiếm nhị phân được áp dụng cho cấu trúc dữ liệu nào dưới đây?
Một danh sách liên kết bất kỳ.
Một mảng các phần tử đã sắp xếp.
Một h
Thuật toán tìm kiếm nhị phân được áp dụng cho cấu trúc dữ liệu nào dưới đây?
Một danh sách liên kết bất kỳ.
Một mảng các phần tử đã sắp xếp.
Một hàng đợi.
Một cây nhị phân bất kỳ.
Tìm từ trong từ điển dựa trên phương pháp tìm kiếm nào phù hợp nhất?
Tuyến tính
Nhị phân
Theo chiều sâu
Ngẫu nhiên
Tổ chức lưu trữ cây nhị phân sử dụng mảng một chiều thì có hiệu quả đối với loại cây nhị phân nào nhất?
Cây nhị phân lệch trái.
Cây nhị phân tìm kiếm.
Cây nhị phân hoàn chỉnh.
Cây nhị phân bất kỳ.
Trong phép duyệt cây nhị phân có 15 nút theo thứ tự LRN (duyệt sau), nút gốc có thứ tự duyệt là bao nhiêu?
1
8
14
15
Tư tưởng của giải thuật tìm kiếm nhị phân là:
So sánh lần lượt từng phần tử của dãy.
Tại mỗi bước so sánh X với phần tử ở giữa dãy để giới hạn phạm vi tìm kiếm.
Chia dãy thành nhiều phần và tìm kiếm trên từng phần.
Bắt đầu tìm từ cuối dãy.
Ưu điểm của danh sách liên kết so với danh sách đặc là gì?
Truy cập ngẫu nhiên phần tử nhanh hơn.
Ít tốn bộ nhớ hơn.
Chèn/xóa một phần tử ở giữa danh sách dễ dàng.
Dễ cài đặt hơn.
Ưu điểm của thuật toán đệ quy là gì?
Luôn chạy nhanh hơn thuật toán không đệ quy.
Luôn tốn ít
Ưu điểm của thuật toán đệ quy là gì?
Luôn chạy nhanh hơn thuật toán không đệ quy.
Luôn tốn ít bộ nhớ hơn.
Sáng sủa, dễ hiểu, nêu rõ bản chất vấn đề.
Không bao giờ bị lỗi tràn bộ nhớ.
Ý tưởng phương pháp sắp xếp chèn (Insertion Sort) là:
Tìm phần tử nhỏ nhất và đưa về đầu dãy.
Lần lượt đưa các phần tử lớn nhất về cuối dãy.
Chia dãy thành hai nửa và sắp xếp đệ quy.
Lần lượt lấy phần tử chưa sắp xếp chèn vào vị trí đúng trong dãy đã sắp xếp.
Ý tưởng phương pháp sắp xếp chọn tăng dần (Selection Sort) là:
Lần lượt chọn phần tử nhỏ nhất trong dãy chưa sắp xếp và đưa vào vị trí đúng ở dãy đã sắp xếp.
So sánh hai phần tử liền kề và đổi chỗ nếu sai thứ tự.
Lấy một phần tử làm chốt và phân hoạch dãy.
Chèn từng phần tử vào đúng vị trí của nó.
Yếu tố thời gian khi xem xét tính hiệu quả của một thuật toán được xác định phụ thuộc bởi đại lượng nào?
Tốc độ của máy tính.
Ngôn ngữ lập trình được sử dụng.
Số các phép tính cơ bản khi thực hiện thuật toán.
Kinh nghiệm của lập trình viên.
