NEW
Font size
WorksheetsCấu trúc dữ liệu và Giải thuật 1
Total questions: 40
Worksheet time: 20mins
Hãy cho biết thuật toán không có tính chất nào dưới đây:
Tính đúng
Tính phổ dụng
Tính dừng
Tính tối ưu
Hãy cho biết trong các bước giải bài toán trong tin học, bước nào người lập trình cần mô tả được input và output của bài toán.
Lập trình
Xác định bài toán
Tìm cấu trúc dữ liệu biểu diễn bài toán
Xác định thuật toán
Hãy lựa chọn đáp án không phải là quy tắc để xác định độ phức tạp của giải thuật.
Quy tắc cộng
Quy tắc nhân
Quy tắc hằng số
Quy tắc bỏ hằng
Khi thiết kế giải thuật đệ quy, bước đầu tiên ta phải:
Xác định điều kiện dừng đệ quy và lời giải ứng với trường hợp này
Xác định trường hợp đệ quy
Xây dựng công thức đệ quy
Tìm cách khử đệ quy
Trường hợp suy biến (neo) của giải thuật tính n! là:
n=0
n=1
n=2
n>2
Câu lệnh nào dưới đây sẽ khai báo và tạo một mảng chứa được tối đa 10 số nguyên:
A= new int[10];
int[] A= new int[10];
int[] A= new int[9];
int[] A= new int[11];
Định nghĩa nào là đúng với danh sách liên kết:
Danh sách liên kết là cấu trúc dữ liệu dạng cây
Danh sách liên kết là cấu trúc dữ liệu tự định nghĩa
Danh sách liên kết là tập hợp các phần tử mà giữa chúng có một sự nối kết với nhau thông qua vùng liên kết của chúng
Danh sách liên kết là tập hợp các phần tử mà đặt kề cạnh nhau trong vùng nhớ
Cây nhị phân là cây mà mỗi nút trên cây có ………..
Hai cây con
Tối thiểu hai cây con
Tối đa hai cây con
Có một hoặc hai cây con
Trong thuật toán tìm kiếm 1 phần tử x trên cây nhị phân tìm kiếm; thì giá trị của x được so sánh với nút nào trên cây đầu tiên.
Nút gốc
Nút lá bên trái nhất
Nút lá bên phải nhất
Nút nhánh là con trái của nút gốc
Hãy cho biết để kiểm thử chương trình bậc 2; thì chúng ta cần tạo các bộ test nào dưới đây:
1 bộ test ứng với trường hợp có nghiệm
1 bộ test ứng với trường hợp có nghiệm, 1 bộ test ứng với trường hợp vô nghiệm
1 bộ test ứng với trường hợp có 2 nghiệm phân biệt, 1 bộ test ứng với trường hợp vô nghiệm, 1 bộ test ứng với trường hợp có nghiệm kép
Không cần tạo bộ test, chỉ cần chương trình chạy là được
Cho T(n)=n3+3n2+3n+10 . Độ phức tạp của thuật toán được biểu diễn dưới hàm O-lớn là:
T(n)=O(n3)
T(n)=O(3n2)
T(n)=O(n2)
T(n)=O(10)
Cho T(n)=3n+100 . Độ phức tạp của thuật toán được biểu diễn dưới hàm O-lớn là:
T(n)=O(3n)
T(n)=O(n)
T(n)=O(100)
T(n)=O(1)
Cho giải thuật int F(int n) { if (n<2) return 1; else return F(n-2) + F(n-1); } Hãy cho biết giá trị của biến S sau khi thực hiện câu lệnh sau: S= F(3)
2
3
4
1
Hãy chọn đáp án đúng để điền vào phần còn thiếu ở giải thuật trên.
B2.1: Q.pNext = P.pNext; B2.2: Q.pNext = P;
B2.1: P.pNext = Q.pNext; B2.2: Q.pNext = P;
B2.1: Q.pNext = P.pNext; B2.2: P.pNext = Q;
B2.1: P.pNext = Q.pNext; B2.2: P = Q.pNext;
Cho Stack có các phép toán: push(X): Thêm phần tử X vào Stack; pop(): Lấy một phần tử ra khỏi Stack. Hãy xác định giá trị phần tử ở đỉnh Stack sau khi tuần tự thực hiện: push(5); push(3); pop(); push(4); push(6); pop().
3
4
5
6
Trong thuật toán tìm kiếm nhị phân, điều kiện dừng là gì?
Tìm thấy phần tử cần tìm hoặc khoảng tìm kiếm trở nên rỗng.
Đã duyệt qua hết tất cả phần tử của dãy.
Đã duyệt hết các phần tử trong khoảng tìm kiếm bất kể đã tìm thấy hay chưa.
Chỉ khi tìm thấy phần tử cần tìm thì thuật toán mới dừng.
Trong thuật toán Euclid tìm ước số chung lớn nhất của hai số nguyên, dữ liệu vào của thuật toán là gì?
Hai số bất kỳ.
Hai số nguyên.
Hai số thực.
Ba số nguyên.
Cho hàm: int F(int n){ if (n < 2) return 1; else return F(n-2) + F(n-1); } Khi thực hiện lệnh S = F(3), chương trình thực hiện bao nhiêu lần gọi đệ quy?
1
2
3
4
-1
0
1
2
Cho danh sách liên kết được định nghĩa và sử dụng như sau: class Node{ public int info; public Node pNext; } class LinkList{ public Node pHead; public LinkList(){ pHead = null; } public void Them(int x){ Node P = new Node(); P.info = x; P.pNext = pHead; pHead = P; } public Node Tim(int x){ Node P = pHead; while (pHead != null){ if (P.info == x) break; P = P.pNext; } return P; } } Đoạn chương trình: LinkList L = new LinkList(); for (int i=2; i<=10; i=i+2) L.Them(i); Console.Write(L.Tim(3)); Kết quả hiển thị trên màn hình là gì?
Thông báo lỗi tại câu lệnh Console.Write(L.Tim(3)).
null
Địa chỉ của một vùng nhớ.
0
Ngăn xếp được ứng dụng trong thuật toán chuyển đổi một biểu thức toán học ở dạng trung tố sang hậu tố. Hãy cho biết biểu thức hậu tố nhận được khi áp dụng thuật toán này cho biểu thức: 2 + 3 * 4 - 5
2 3 + * 4 5 -
2 3 4 5 * + -
2 3 4 * 5 + -
2 3 4 * + 5 -
Q là nút gốc
Q là nút có đủ 2 con
Q là nút lá
Q là nút lá hoặc nút nửa lá (chỉ có một con trái hoặc con phải)
Sau khi thực hiện 3 lượt (vòng lặp) của giải thuật sắp xếp lựa chọn (selection sort) để sắp xếp dãy số theo thứ tự tăng dần cho dãy ban đầu: 1 12 21 24 -9 8 7 5 Hãy cho biết dãy số thu được sau 3 lượt là gì
-9 12 21 24 1 8 7 5
-9 1 21 24 12 8 7 5
-9 1 5 24 12 8 7 21
-9 5 7 24 1 8 21 12
Cho danh sách liên kết được định nghĩa như sau: class Node{ public int info; public Node pNext; } class LinkList{ public Node pHead; // pHead trỏ vào phần tử đầu danh sách public LinkList(){ pHead = null; } // Thêm một node mới vào danh sách: public void Them(int x){ Node P = new Node(); P.info = x; P.pNext = pHead; pHead = P; } // Tìm phần tử có giá trị x trong danh sách public Node Tim(int x){ Node P = pHead; while (pHead != null) { if (P.info == x) break; P = P.pNext; } return P; } } Hãy cho biết kết quả hiển thị trên màn hình sau khi thực hiện đoạn chương trình sau: LinkList L = new LinkList(); for (int i = 2; i <= 10; i = i + 2) L.Them(i); Console.WriteLine(L.Tim(7));
Thông báo lỗi tại câu lệnh Console.WriteLine(L.Tim(3));
null
Địa chỉ của một vùng nhớ
0
Cho giải thuật sau: int gt(int[] A){ int d = 0; for (int i = 0; i < A.Length; i++) if (A[i] > 0) d = d + 1; return d; } Hãy cho biết giá trị của biến T sau khi thực hiện câu lệnh: int T = gt(new int[] {2,3,4,5,6,7,8});
5
6
7
8
Cho giải thuật sau: int gt(int[] A){ int S = 0; for (int i = 0; i < A.Length; i++) if (A[i] % 2 == 0) S = S + A[i]; return S; } Hãy cho biết giá trị của biến T sau khi thực hiện câu lệnh: int T = gt(new int[] {1,3,5,7,8});
4
8
7
15
Cho giải thuật sau: int gt(int[] A, int x){ for (int i = 0; i < A.Length; i++) if (A[i] == x) return i; return -1; } Hãy cho biết giá trị của biến T sau khi thực hiện câu lệnh: int T = gt(new int[] {2,4,5,6,7,8}, 3);
-1
0
1
2
Cho giải thuật: int F(int n){ if (n < 2) return 1; else return F(n - 2) + F(n - 1); } Hãy cho biết giá trị của biến S sau khi thực hiện câu lệnh: S = F(4)
2
3
5
8
Cho giải thuật: int F(int n){ if (n < 2) return 1; else return F(n-2) + F(n-1); } Hãy cho biết để thực hiện câu lệnh: S = F( 2 ) thì chương trình cần gọi đệ quy mấy lần?
1
2
3
4
Ngăn xếp được ứng dụng trong thuật toán chuyển đổi một biểu thức toán học ở dạng Trung tố sang Hậu tố. Hãy cho biết biểu thức hậu tố nhận được sau khi chạy thuật toán chuyển biểu thức từ trung tố sang hậu tố với input: 1 + 2 * ( 4 + 5 ).
1 2 + * 4 5 +
1 2 4 5 * + +
1 2 4 5 + * +
1 2 4 * 5 + +
Ngăn xếp được ứng dụng trong thuật toán Tính giá trị của một biểu thức hậu tố. Hãy cho biết giá trị tại đỉnh của ngăn xếp sau khi thực hiện thuật toán tính giá trị của một biểu thức hậu tố với input: 2 1 4 * + 5 -.
1
3
2
4
Cho Queue có các phép toán: EnQueue(X): Thêm phần tử X vào Queue; DeQueue(): Lấy 1 phần tử ra khỏi Queue. Hãy cho biết phần tử ở đầu của Queue có giá trị là ký tự nào sau khi thực hiện thuật toán sau với input là: “This**is***Queue**”. Thuật toán: đọc lần lượt từng ký tự từ trái qua phải của xâu S; nếu ký tự đọc được là '*' thì lấy 1 phần tử ra khỏi Queue, ngược lại thì thêm phần tử đọc được vào Queue.
T
h
u
Q
Cho Stack có các phép toán: push(X): Thêm phần tử X vào Stack; pop(): Lấy 1 phần tử ra khỏi Stack. Hãy cho biết phần tử ở đỉnh của Stack có giá trị là ký tự nào sau khi thực hiện thuật toán sau với input là: “This**is***Stack**”. Thuật toán: đọc lần lượt từng ký tự từ trái qua phải của xâu S; nếu ký tự đọc được là '*' thì lấy 1 phần tử ra khỏi Stack, ngược lại thì thêm phần tử đọc được vào Stack.
T
S
a
k
Cho khai báo một nút trên cây nhị phân tìm kiếm: class Node { public int info; public Node left, right; } Hãy cho biết đoạn lệnh sau thực hiện việc xoá nút nào trên cây nhị phân tìm kiếm: static void Del(ref Node Q) // xoá nút Q trên cây { Node P = Q; if (P.left == null) Q = P.right; else if (P.right == null) Q = P.left; }
Q là nút gốc
Q là nút có đủ 2 con
Q là nút lá
Q là nút lá hoặc nút nửa lá (chỉ có một con trái hoặc con phải)
Một cây T có 9 nút. Phép duyệt cây đó theo thứ tự giữa và thứ tự trước cho kết quả: - Thứ tự giữa (Inorder): E A C K M H D B G - Thứ tự trước (Preorder): M A E K C D H G B Chọn cây T dựng được theo mô tả trên (chọn một trong bốn sơ đồ).
Sơ đồ A
Sơ đồ A
Sơ đồ B
Sơ đồ B
Sơ đồ C
Sơ đồ C
Sơ đồ D
Sơ đồ D
Thứ tự nào sau đây mô tả đúng phép duyệt đệ quy cây nhị phân theo thứ tự sau (postorder)?
Duyệt cây con trái theo thứ tự sau -> thăm gốc -> duyệt cây con phải theo thứ tự sau
Thăm gốc -> duyệt cây con trái theo thứ tự sau -> duyệt cây con phải theo thứ tự sau
Thăm gốc -> duyệt cây con phải theo thứ tự sau -> duyệt cây con trái theo thứ tự sau
Duyệt cây con trái theo thứ tự sau -> duyệt cây con phải theo thứ tự sau -> thăm gốc
Chọn đáp án thích hợp điền vào chỗ ... trong phát biểu: Đối với thuật toán Bubble Sort (Nổi bọt) áp dụng sắp xếp tăng dần cho dãy số: 12 23 74 11 65 58 94 36 6 87. Cần thực hiện ... lượt (vòng lặp) để phần tử 6 được đưa vào đúng vị trí của dãy kết quả.
1
2
8
9
Sau khi thực hiện 3 lượt (vòng lặp), áp dụng giải thuật sắp xếp Chèn (insertion sort) để sắp xếp dãy số sau tăng dần: 10 1 21 24 -9 8 7 5. Thì dãy số thu được là:
1 10 21 24 -9 8 7 5
-9 1 21 24 10 8 7 5
-9 1 5 24 10 8 7 21
1 5 21 24 -9 8 7 10
Hãy lựa chọn giải thuật đúng để thực hiện hoán vị 2 số nguyên.
void HoanVi(ref int a, ref int b){ int c = a; a=b; b=c; }
void HoanVi(int a, ref int b){ int c = a; a=b; b=c; }
void HoanVi(ref int a, out int b){ int c = a; a=b; b=c; }
void HoanVi(int a, int b){ int c = a; a=b; b=c; }
Cho L là danh sách liên kết; pHead là con trỏ để lưu địa chỉ của phần tử đầu tiên của danh sách L. Khi pHead có giá trị != null thì danh sách L có số phần tử là:
0
>=1
>1
Không xác định được số phần tử của danh sách
