ĐỀ KIỂM TRA TRẮC NGHIỆM
Thời gian 30 phút Số câu: 15
________________________________________
Kiến thức cơ bản
Câu 1: Cấu trúc dữ liệu nào sử dụng kiểu dữ liệu con trỏ để cài đặt?
A : List
B :Linked List
C : Queue
D Stack
________________________________________
Con trỏ
Câu 2: Phương án nào thực hiện đúng nhất thủ tục tạo mới danh sách liên kết đơn L rỗng?
A : New(L);
L := NIL;
B New(L);
L^.NEXT := L;
C : New(L);
L^.NEXT := NIL;
D: L:=NIL;
________________________________________
Độ phức tạp
Câu 3: Những thao tác nào trên danh sách có thời gian thực hiện O(n) nếu nó được cài đặt bằng mảng?
A : INSERT(X: ELEMENTTYPE; P: POSITION; VAR L: LIST);
DELETE(P: POSITION; VAR L: LIST);
B : NEXT(P: POSITION; L:LIST): POSITION;
LOCATE(X: ELEMENTTYPE; L: LIST):POSITION;
C : NEXT(P: POSITION; L:LIST): POSITION;
DELETE(P: POSITION; VAR L: LIST);
LOCATE(X: ELEMENTTYPE; L: LIST):POSITION;
PREVIOUS(P: POSITION; L:LIST): POSITION;
INSERT(X: ELEMENTTYPE; P: POSITION; VAR L: LIST);
PREVIOUS(P: POSITION; L:LIST): POSITION;
Câu 4: Phương án nào gồm hai thao tác có thời gian thực hiện khác nhau trên danh sách liên kết đơn? (hai phương án đúng)
A INSERT(X: ELEMENTTYPE; P: POSITION; VAR L: LIST);
DELETE(P: POSITION; VAR L: LIST);
B NEXT(P: POSITION; L:LIST): POSITION;
LOCATE(X: ELEMENTTYPE; L: LIST):POSITION;
C NEXT(P: POSITION; L:LIST): POSITION;
DELETE(P: POSITION; VAR L: LIST);
D LOCATE(X: ELEMENTTYPE; L: LIST):POSITION;
PREVIOUS(P: POSITION; L:LIST): POSITION;
E INSERT(X: ELEMENTTYPE; P: POSITION; VAR L: LIST);
PREVIOUS(P: POSITION; L:LIST): POSITION;
Chon Nhieu phuong an tuy y
________________________________________
Cài đặt DS liên kết
Câu 5: Đoạn mã nào thể hiện đúng nhất phép bổ sung phần tử X vào trước phần tử ở vị trí P danh sách liên kết đơn L?
a)
Đây là hình ảnh câu 5 các bác xem rùi hỗ trợ em cái
b)
c)
d)
Câu 6: Đoạn mã nào thể hiện đúng nhất phép bổ sung phần tử X vào sau phần tử ở vị trí P danh sách liên kết vòng L?
a)
b)
c)
d)
________________________________________
Stack
Câu 7: Trạng thái nào của stack xuất hiện trong quá trình chuyển biểu thức 12/(2+1)/3+5-2 về dạng RPN (Reverse Polish Notation)?
a)
b)
c)
d)
________________________________________
Tính giá trị biểu thức
Câu 8: Lựa chọn nào biểu thị dạng postfix của biểu thức 2*4+(17-5)/3/2?
a)
b)
c)
d)
________________________________________
Duyệt cây
Câu 9:
a)
b)
c)
d)
________________________________________
Mã Huffman
Câu 10: Độ dài mong đợi (Expected Length) khi mã hóa xâu "CU RUA NGHIN TUOI" theo phương pháp Huffman?
57
56
55
54
53
Câu 11: Độ dài mong đợi (Expected Length) khi mã hóa xâu "NUOC NON NGHIN DAM" theo phương pháp Huffman?
59
58
57
56
________________________________________
Cây tìm kiếm nhị phân
Câu 12: Thời gian chạy của phép bổ sung một phần tử vào Cây tìm kiếm nhị phân (BST) trong trường hợp tốt nhất là
O(1)
O(log(n))
O(n^2)
O(n)
________________________________________
heap
Câu 13: Mảng nào dưới đây là heap
(50, 38, 27, 49, 16)
(50, 16, 27, 38, 49)
(50, 38, 49, 16, 27)
(16, 27, 38, 49, 50)
________________________________________
Đường đi ngắn nhất
Câu 14:
a)
b)
c)
d)
________________________________________
Thời gian chạy
Câu 15: Thời gian chạy của giải thuật sắp xếp chọn (SELECTION SORT) là
O(1)
O(n.log(n))
O(n^2)
O(n)
