Nội dung câu trắc nghiệm
1. Cho danh sách đặc có 10 phần tử. Khi thêm phần tử vào vị trí 4 trong danh sách, vòng lặp dịch
chuyển tịnh tiến nội dung các phần tử L->Elements[i]=L->Elements[i+1] sẽ thực hiện
a. 4 lần b. 5 lần c. 6 lần d. Tất cả đều sai
2. Cho danh sách đặc có 10 phần tử. Khi xóa phần tử ở vị trí 4 trong danh sách, vòng lặp dịch chuyển
tịnh tiến nội dung các phần tử L->Elements[i]=L->Elements[i+1]
a. 4 lần b. 5 lần c. 6 lần d. Tất cả đều sai
3. Cho biểu thức a+b*((c-d)*e+f/h). Danh sách duyệt tiền tự của biểu thức đã cho là:
a. + * a b + * - c d e / f h
b. + a * b + * - c d e / f h
c. + a b * * e - c d + / f h
d. + * a + b – c d * e / f h
4. Danh sách duyệt hậu tự của biểu thức trong câu 3 là:
a. a c d - * e b * + f h / +
b. a b c d - e * + f h / * +
c. a b c d - e * f h / + * +
d. a b e c d * - f h / + * +
5. Danh sách duyệt theo mức của biểu thức đã cho trong câu 3 là:
a. + a * b + * / - e f h c d
b. a b + * + / - c d e f h *
c. + * a + b – c d * e / f h
d. + * a b + * - c d e / f h
6. Giá trị của biểu thức /, +, 2, *, 3, 4, –, 5, 7 là:
a. -7 b. 5 c. 7 d.14
7. Giá trị của biểu thức 2, 3, 4, *, -, 5, 7, +, / là:
a. -7 b. 5 c. 7 d. Một giá trị khác
8. Khi thêm phần tử đầu tiên vào danh sách liên kết có ô đầu mục L thì
a. L luôn luôn thay đổi.
b. L có thể thay đổi.
c. L luôn luôn không đổi.
9. Khi thêm phần tử vào hàng cài đặt bằng mảng vòng thì
a. Front luôn luôn không đổi, Rear luôn luôn thay đổi
b. Front luôn luôn không đổi, Rear có thể thay đổi
c. Front có thể thay đổi, Rear luôn luôn thay đổi
d. Front có thể thay đổi, Rear có thể thay đổi
10. Chiều cao của cây tìm kiếm nhị phân cho bởi danh sách: 10, 15, 8, 4, 20, 5, 1, 3, 14, 15 là
a. 2 b. 3 c. 4 d. 5
11. Danh sách duyệt tiền tự của cây trên là
a. 15, 14, 10, 8, 5, 3, 1, 4, 20
b. 10, 8, 5, 4, 1, 3, 15, 14, 20
c. 10, 8, 4, 1, 5, 3, 15,14, 15, 20
d. 10, 8, 4, 1, 3, 5, 15, 14, 20
12. Danh sách duyệt hậu tự của cây trên là:
a. 3, 1, 5, 4, 8, 14, 20,15, 15, 10
b. 3, 1, 5, 4, 8, 14, 20, 15, 10
ĐỀ 1
c. 1, 3, 4, 5, 8, 14, 20, 15, 10
d. 1, 3, 5, 4, 8, 14, 20, 15, 10
13. Danh sách duyệt trung tự tổng quát của cây tìm kiếm nhị phân trên là:
a. 3, 1, 4, 5, 8, 10, 14, 15, 20
b. 1, 3, 4, 5, 8, 10, 14, 15, 20
c. 3, 1, 4, 5, 8, 10, 15, 14, 20
d. 1, 3, 5, 4, 8, 10, 14, 15, 20
14. Khi xóa nút 10 ra khỏi cây, ta thực hiện như sau:
a. Thay nút 10 bằng nút 8 và quay về xóa nút 8.
b. Thay nút 10 bằng nút 20 và quay về xóa nút 20
c. Thay nút 10 bằng nút 15 và quay về xóa nút 15
d. Cho con trái của nút 10 trỏ xuống nút 4
15. Khi thêm nút 9 vào cây ta sẽ cho
a. Nút 9 là con trái của nút 14
b. Nút 9 là con phải của nút 5
c. Nút 9 là con phải của nút 8
d. Nút 9 là con phải của nút 3
16. Khi xóa nút 8 ra khỏi cây, ta thực hiện :
a. Thay nút 8 bằng nút 4 và quay về xóa nút 4
b. Thay nút 8 bằng nút 5 và quay về xóa nút 5
c. Thay nút 8 bằng nút 10 và quay về xóa nút 10
d. Cho con trái của nút 10 trỏ xuống nút 4
17. Khi thêm phần tử vào hàng cài đặt bằng mảng vòng không đầy thì
a. Front luôn luôn không đổi, Rear luôn luôn thay đổi
b. Front luôn luôn không đổi, Rear có thể thay đổi
c. Front có thể thay đổi, Rear luôn luôn thay đổi
d. Front có thể thay đổi, Rear có thể thay đổi
18. Khi xóa phần tử vào hàng cài đặt bằng mảng vòng không rỗng thì
a. Front luôn luôn không đổi, Rear luôn luôn thay đổi
b. Front luôn luôn không đổi, Rear có thể thay đổi
c. Front có thể thay đổi, Rear luôn luôn thay đổi
d. Front có thể thay đổi, Rear có thể thay đổi
19. Hàm Endlist (L) trong danh sách là
a. Hàm kiểm tra xem danh sách có đầy không
b. Hàm kiểm tra xem danh sách kết thúc chưa
c. Hàm trả về vị trí của phần tử cuối trong danh sách
d. Hàm trả về vị trí sau phần tử cuối trong danh sách
20. Trong các phát biểu sau, phát biểu nào đúng?
a. Giá trị hàm EndList(L) và hàm FirstList(L) luôn luôn bằng nhau khi danh sách rỗng.
b. Giá trị hàm EndList(L) và hàm FirstList(L) luôn luôn khác nhau.
c. Giá trị hàm EndList(L) và hàm FirstList(L) bằng nhau hay không tùy thuộc vào phương
pháp cài đặt danh sách.
d. Tất cả đều sai
21. Kết quả biểu thức : -, *, +, 2, 3, 4, /, 5, 1, +, 7, 8 là
a. 9 b. 15 c. 19 d. Một giá trị khác
22. Kết quả biểu thức: 2,-,3,4,*,1,5,*,7,8,-,/,- là
a. Biểu thức đã cho không hợp lệ b. 15
c.25 d. Một giá trị khác
23. Trong danh sách liên kết kép DL không có ô đầu mục, khi thêm phần tử vào vị trí FirstList(DL)
trong danh sách thì:
a. DL luôn luôn thay đổi
b. DL có thể thay đổi
c. DL luôn luôn không đổi
24. Khi xóa phần tử cuối ra khỏi danh sách ta thực hiện lời gọi hàm:
a. Delete_List(Endlist(L),L);
b. Delete_List(Endlist(L),&L);
c. Delete_List(Endlist(*L), &L);
d. Tất cả đều sai.
25. Cho cây tổng quát cài đặt bằng mảng như sau:
T.MaxNode-1
Chỉ số mảng 0 1 2 3 4 5 6 7 8 9 10 11 …
Parent -1 0 0 2 2 0 5 6 7 6 6 6
Label A B C E F D G H I K J L
Bậc của cây là:
a. 2 b. 3 c. 4 d. 5
26. Nút C có bậc là :
a. 0 b. 1 c. 2 d. 3
27. Con của nút G theo thứ tự là
a. H, K, J, L b. H, I, K, L
c. H, J, K, L d. I, H, K, L
28. Nút sâu nhất trong cây là nút :
a. Nút B b. Nút H
c. Nút I d. Tất cả đều sai
29. Chiều cao của cây là
a. 2 b. 3 c. 4 d. 5
30. Nút I nằm bên trái của nút J
a. Đúng b. Sai
31. Cho hai danh sách duyệt nhị phân như sau :
NLR : D, C, B, A, H, E, I, K, J, F, G
LNR: A, B, H, C, D, K, I, J, E, F, G
Danh sách duyệt LRN của cây nhị phân dựng nên bởi cặp danh sách trên là:
a. A, H, B, C, D, K, J, I, G, F, E
b. A, H, B, C, D, K,J, I, F, G, E
c. A, H, B, C, K, J, I, G, F, E, D
d. A, H, B, C, K, J, I, F, G, E,D
32. Danh sách duyệt trung tự tổng quát của cây nhị phân trên là:
a. A, B, H, C, D, K, I, J, E, G, F
b. A, B, H, C, D, K, I, J, E, F, G
c. A, H, B, C, D, K, J, I, E, F, G
d. A, H, B, C, D, K, J, I, E, G, F
33. Danh sách duyệt theo mức của cây trên là
a. D, C, B, A, H, E, I, F, K, J, G
b. D, C, E, B, I, F, A, H, K, J, G
c. D, C, E, H, I, F, A, B, K, J, G
d. D, C, B, A, H, E ,I, K, J ,F, G
34. Nút F trên cây là
a. Nút lá
b. Nút có 1 con phải
c. Nút có 1 con trái
d. Nút có 2 con
35. Nút I có bậc là
a. 0 b. 1 c. 2
36. Hàm băm mở được xem là hiệu quả về mặt thời gian thực hiện khi:
a. Các phần tử tập trung trên một lớp (bucket).
b. Các phần tử nằm rãi đều trên các lớp.
c. Số lớp càng lớn thì càng hiệu quả
d. Cả b và c đều đúng
37. Cho danh sách liên kết như sau:
p=First(L) ;
q=Next(Next(Next(Next(p,L),L),L),L);
Printf(“%c”, Retrieve(q,L));
Delete_List(q,L);
Kết quả của danh sách sau khi thực hiện đoạn lệnh trên là:
a. Đoạn lệnh bị lỗi.
b.
c.
d. Tất cả đều sai
38. Lệnh Printf tron câu 37 sẽ cho kết quả trên màn hình là:
a. C b. K c. Y d. Đoạn lệnh trên bị sai
39. Cho bảng băm đóng với hàm băm H(x)=x %10 và phương pháp giải quyết đụng độ là băm lại
tuyến tính. Kết quả bảng băm sau khi thực hiện các thao tác thêm 33, 14, 15, 25, 35, 18, 45,20, 22,
xóa 18, xóa 25, xóa 22 là :
Empty
20
Deleted
33
14
15
Deleted
35
Deleted
45
a. Các giá trị lưu trữ trong bảng băm là hoàn toàn hợp lệ.
b. Lỗi lưu trữ tại vị trí có giá trị 20.
c. Lỗi lưu trữ tại vị trí 35
d. Lỗi lưu trữ tại vị trí 45
L U
K
C
L
Y
L U
K
C
L
L U Y C
L
40. Từ bảng băm ban đầu đã cho, tiếp tục thực hiện dãy thao tác thêm 20, 40, 25, xóa 14, thêm 55 với
hàm băm H(x)= (x+i) %10 (với i=0..9), ta có kết quả như sau :
20 20 20 20 20
Empty 20 40 40 40
Deleted 40 Deleted Deleted Deleted
33 33 33 33 33
14 Deleted Deleted 24 Deleted
24 24 24 25 24
Deleted 25 25 55 25
Empty 55 Empty Empty 55
Deleted Deleted 55 Deleted Deleted
49 49 49 49 49
Bảng băm
ban đầu
a. b. c. d.
PHẦN TỰ LUẬN : (3 điểm)
Câu 1 : 0.75 điểm
- Vẽ đúng cấu trúc cây TÌM KIẾM NHỊ PHÂN CÂN BẰNG
Câu 2 : 1.25 điểm
- Thực hiện các thao tác theo đúng thứ tự đã cho và có cây kết quả đúng.
Câu 3 : 1 điểm
- Viết đúng cấu trúc danh sách liên kết
- Thực hiện tìm được vị trí PHẦN TỬ CUỐI CÓ NỘI DUNG X TRONG DANH SÁCH
- Trả hàm về vị trí Endlist nếu không có phần tử x trong danh sách ;
- Ngược lại, trả hàm về vị trí phần tử X sau cùng.