Free Printable Câu hỏi trắc nghiệm về độ phức tạp và đệ qui

Worksheets

Câu hỏi trắc nghiệm về độ phức tạp và đệ qui

Total questions: 108

Worksheet time: 54mins

Name

Class

Date

Thời gian thực hiện chương trình được xác định dựa vào …

trường hợp tốt nhất.

trường hợp xấu nhất.

trường hợp tổng quát.

trường hợp trung bình.

Tỷ suất tăng của hàm $T(n)$ là $(2n + 1)^2$ . Chọn phương án đúng về bậc tăng trưởng.

$4n^2 + 4n + 1$

$4n^2 + 4n$

$4n^2$

$n^2$

Phương pháp đoán nghiệm đúng để giải phương trình đệ qui sử dụng phương pháp chứng minh … để chứng tỏ nghiệm đoán là đúng.

tổ hợp

phản chứng

qui nạp

trực tiếp

Phát biểu nào sau đây là sai? Khi tính độ phức tạp của giải thuật …

qui tắc cộng được áp dụng cho các đoạn chương trình nối tiếp nhau.

qui tắc nhân được áp dụng cho các đoạn chương trình lồng nhau.

các lệnh gán, nhập, xuất, có thời gian là $O(1)$ .

thời gian thực hiện một chuỗi tuần tự các lệnh là tổng thời gian thực hiện của các lệnh trong chuỗi lệnh đó.

Phát biểu nào sau đây là sai?

Thời gian thực hiện vòng lặp là tổng thời gian thực hiện thân vòng lặp.

Nếu hai vòng lặp lồng nhau thì ta áp dụng qui tắc nhân để tính thời gian thực hiện của chúng.

Thời gian thực hiện vòng lặp là tổng của số lần lặp với thời gian thực hiện thân vòng lặp nếu thân vòng lặp có thời gian thực hiện không đổi.

Nếu số lần lặp của vòng lặp là không xác định thì ta lấy số lần lặp trong trường hợp xấu nhất để tính thời gian thực hiện cho vòng lặp đó.

Giải phương trình đệ qui dưới đây. Ta có nghiệm là …

$O(n\cdot \log n)$

$O(n)$

$O(\log^n)$

$O(n^2)$

Khi giải phương trình đệ qui, nếu $d(n)$ là hàm nhân và $a < d(b)$ thì nghiệm của phương trình là …

$O(n^{\log_a b})$

$O(n^{\log_b a})$

$O(n^{\log_a b}\cdot \log n)$

$O(n^{\log_b d(b)})$

Giả sử có sơ đồ gọi thực hiện các chương trình con không đệ qui như sau: Chương trình A gọi B và C; B lần lượt gọi B1 và B2; B2 gọi B12. Phát biểu nào sau đây là đúng?

Chương trình con B phải được đánh giá sau chương trình con B1 và B2.

Chương trình con B1 phải được đánh giá trước chương trình con B2.

Chương trình con C phải được đánh giá trước chương trình con B.

Chương trình con B12 phải được đánh giá đầu tiên.

Xét đoạn mã: return Func(a-1, N-1) + Func(a, N-1); Hỏi: Hàm Func trên có độ phức tạp là gì?

$O(N!)$

$O(N\log N)$

$O(2^N)$

$O(N^2)$

10.

Cho hàm sắp xếp như sau: void Sort (int M[], int N) { for (int i = 0; i < N-1; i++) for (int j = N-1; j > i; j--) if (M[j] < M[j-1]) { int Temp = M[j]; M[j] = M[j-1]; M[j-1] = Temp; } } Hỏi: Hàm Sort trên được viết dựa vào giải thuật nào?

Quick Sort

Bubble Sort

Heap Sort

Insertion Sort

11.

Cho thuật toán: B1: k = 1; B2: IF (M[k] ≠ X && k ≤ N) { B2.1: k++; B2.2: Lặp lại B2 } B3: IF k ≤ N thì "Tìm thấy tại vị trí k"; B4: ELSE "Không tìm thấy phần tử có giá trị X"; Bkt: Kết thúc. Thuật toán trên là thuật toán gì?

sắp xếp chọn trực tiếp

sắp xếp chèn nhị phân

12.

Giải thuật sắp xếp chèn nhị phân có độ phức tạp là …

$O(N\log N)$

$O(N)$

$O(N^2)$

$O(\log N)$

13.

Shaker Sort còn có tên gọi khác là …

Ring Sort

Fruit Sort

Cocktail Sort

Shake-man Sort

14.

Cho mảng M như sau: Hàm QuickSort(M, 6) gọi hàm PartitionSort(M, 0, 5), hàm PartitionSort(M, 0, 5) sau khi thực hiện sẽ gọi đệ qui hai hàm là gì?

PartitionSort(M, 0, 1); và PartitionSort(M, 2, 5);

PartitionSort(M, 0, 3); và PartitionSort(M, 4, 5);

PartitionSort(M, 0, 2); và PartitionSort(M, 3, 5);

PartitionSort(M, 0, 2); và PartitionSort(M, 2, 5);

15.

Phát biểu nào sau đây là sai?

Giải thuật sắp xếp Bubble Sort chỉ tận dụng được chiều nổi lên mà chưa tận dụng được chiều chìm xuống.

Giải thuật sắp xếp Heap Sort có thời gian thực hiện tỷ lệ nghịch với chiều sâu của cây nhị phân biểu diễn Heap.

Giải thuật sắp xếp Quick Sort sẽ đạt hiệu quả nhất khi chốt được chọn phân hoạch đều các dãy con.

Giải thuật sắp xếp Quick Sort ít được sử dụng trên thực tế vì nó thuộc nhóm non in-place.

16.

Kỹ thuật thiết kế giải thuật nào có thể không trả về phương án tối ưu?

Chia để trị.

Tìm kiếm địa phương.

Qui hoạch động.

Tham ăn.

17.

Bài toán nào sau đây thường không sử dụng kỹ thuật chia để trị trong thiết kế giải thuật?

Sắp xếp QuickSort

Xếp lịch thi đấu

Nhân số nguyên lớn

Rút tiền từ ATM

18.

Kỹ thuật quy hoạch động có tên tiếng Anh là gì?

dynamic programming

dynamic scheme

static technology

static programming

19.

Phát biểu nào sau đây là sai về cây biểu thức trong biểu diễn trung gian của biểu thức số học?

Một trong các cách biểu diễn trung gian cho biểu thức số học chính là cây biểu thức

Trong cây biểu thức nút lá biểu diễn cho các toán hạng

Trong cây biểu thức nút trong biểu diễn cho các toán tử

Cây biểu thức biểu diễn biểu thức số học là một cây nhị phân tìm kiếm

20.

Cho bài toán xếp lịch thi đấu, nếu có 3 đấu thủ thì lịch thi đấu nào sau đây là sai? Các ma trận lịch thi đấu cho 3 đấu thủ (nhãn 1, 2, 3) được cho trong bốn hình A, B, C, D.

Hình A

Hình B

Hình C

Hình D

21.

Xét bài toán cái ba lô có trọng lượng là 37 và 4 loại đồ vật với số lượng không hạn chế; bảng cho biết trọng lượng và giá trị tương ứng của mỗi loại. Áp dụng kỹ thuật tham ăn, ta chọn được số lượng các đồ vật đựng vào ba lô là phương án nào?

0 : A; 3 : B; 1 : C; 1 : D

1 : A; 2 : B; 1 : C; 1 : D

1 : A; 3 : B; 1 : C; 0 : D

0 : A; 2 : B; 2 : C; 1 : D

22.

Dựa vào bảng giá trị F[k, V] và X[k, V] được lập theo công thức truy hồi trong hình, giá trị F5 trong bảng trên là bao nhiêu?

23.

Hãy chọn ba bước đúng khi áp dụng kỹ thuật tìm kiếm địa phương vào một bài toán.

B1: Xuất phát từ một phương án nào đó. B2: Áp dụng một phép biến đổi lên phương án hiện hành để được một phương án mới tốt hơn phương án đã có. B3: Lặp lại việc áp dụng phép biến đổi lên phương án hiện hành cho đến khi không còn có thể cải thiện được phương án nữa.

B1: Xuất phát từ một phương án nào đó. B2: Áp dụng một phép biến đổi lên phương án hiện hành để được một phương án mới tốt hơn phương án đã có. B3: Lặp lại B1 cho đến khi không còn có thể cải thiện được phương án nữa.

B1: Xuất phát từ một phương án nào đó. B2: Áp dụng một phép biến đổi lên phương án hiện hành để được một phương án mới tốt hơn phương án đã có. B3: Lặp lại B2 cho đến khi không còn có thể cải thiện được phương án nữa.

B1: Xuất phát từ một phương án nào đó. B2: Áp dụng một phép biến đổi lên phương án hiện hành để được một phương án mới tốt hơn phương án đã có. B3: Lặp lại 2 bước trên cho đến khi không còn có thể cải thiện được phương án nữa.

24.

Phát biểu nào sau đây là sai?

Bộ nhớ ngoài có dung lượng lớn hơn nhiều so với bộ nhớ trong.

Bộ nhớ đệm là vùng nhớ của bộ nhớ ngoài dành riêng để giao tiếp với bộ nhớ trong.

Bộ nhớ đệm là vùng nhớ của bộ nhớ trong dành riêng để giao tiếp với bộ nhớ ngoài.

Bộ nhớ trong có tốc độ truy xuất nhanh hơn nhiều so với bộ nhớ ngoài.

25.

Phát biểu nào sau đây là sai? B-cây bậc m là cây tìm kiếm m-phân cân bằng có tính chất ...

Nút gốc hoặc là lá hoặc có ít nhất hai nút con.

Mỗi nút, trừ nút gốc và nút lá, có từ $\left\lfloor \frac{m}{2} \right\rfloor$ đến m nút con.

Các đường đi từ gốc tới lá có cùng độ dài.

26.

Để tìm mẫu tin có khóa là $29$ thì giải thuật phải xét bao nhiêu khối? Giả sử tập tin F gồm 24 mẫu tin với giá trị khóa là các số nguyên cho trước; tập tin được tổ chức vào danh sách liên kết, mỗi khối chứa tối đa 3 mẫu tin như sơ đồ khối minh họa.

27.

Phát biểu nào sau đây là đúng?

Cấu trúc tập tin chỉ mục bao gồm hai tập tin là tập tin chính gồm nhiều khối lưu các mẫu tin theo thứ tự bất kỳ và tập tin chỉ mục dày gồm khối chứa các cặp (x, p) với x là khóa của mẫu tin đầu tiên trong khối còn p là con trỏ đến khối.

Cấu trúc tập tin chỉ mục bao gồm hai tập tin là tập tin chính gồm nhiều khối lưu các mẫu tin được sắp xếp theo khóa và tập tin chỉ mục thưa gồm các khối chứa các cặp (x, p) với x là khóa của mẫu tin đầu tiên trong khối còn p là con trỏ đến khối.

Cấu trúc tập tin chỉ mục là một tập tin gồm nhiều khối lưu các mẫu tin được sắp xếp giảm dần theo khóa của nó.

Cấu trúc tập tin chỉ mục là một tập tin chỉ mục thưa gồm các khối chứa các cặp (x, p) với x là khóa của mẫu tin đầu tiên trong khối còn p là con trỏ trỏ đến khối.

28.

Phát biểu nào sau đây là sai?

Tổ chức tập tin B-cây là cây m-phân, trong đó các nút lưu trữ các mẫu tin của tập tin và mỗi nút trong lưu trữ m con trỏ trỏ tới m nút con.

Tổ chức tập tin băm là một bảng có m phần tử, trong đó mỗi phần tử là một con trỏ trỏ tới phần tử đầu tiên của danh sách liên kết các khối.

Tổ chức tập tin tuần tự là một danh sách liên kết trong đó mỗi phần tử là một mẫu tin của tập tin.

Tổ chức tập tin chỉ mục gồm 2 tập tin, được gọi là tập tin chính và tập tin chỉ mục.

29.

Sau khi trộn các đường có độ dài 1 của F1 và F2 thành các đường có độ dài 2 rồi ghi luân phiên vào hai tập tin G1 và G2, kết quả đúng là lựa chọn nào dưới đây? Mô tả hình: các dãy số của F1 và F2 được hiển thị ở trên; bên dưới là bốn phương án A, B, C, D biểu diễn nội dung hai tập tin G1 và G2 sau khi trộn, mỗi phương án gồm hai hàng nhãn G1 và G2 chứa các dãy số liên tiếp.

Phương án A: bố trí G1/G2 như hình A

Phương án B: bố trí G1/G2 như hình B

Phương án C: bố trí G1/G2 như hình C

Phương án D: bố trí G1/G2 như hình D

30.

Cho tập tin có 24 mẫu tin với các khóa: 3, 5, 12, 65, 34, 20, 21, 17, 56, 1, 16, 2, 78, 94, 38, 15, 23, 14, 10, 29, 19, 6, 45, 36. Tổ chức vào bảng băm gồm 7 phần tử, mỗi khối chứa tối đa 3 mẫu tin, hàm băm h(x) = x % 7. Bảng băm thu được đúng với phương án nào dưới đây? Mô tả hình: có bốn phương án A, B, C, D, mỗi phương án là sơ đồ 7 danh sách B[0]..B[6] với các khối tối đa 3 ô chứa khóa theo thứ tự chèn.

Phương án A

Phương án B

Phương án C

Phương án D

31.

Cho tập tin có 24 mẫu tin với các khóa: 3, 5, 12, 65, 34, 20, 21, 17, 56, 1, 16, 2, 78, 94, 38, 15, 23, 14, 10, 29, 19, 6, 45, 36. Tổ chức vào bảng băm gồm 5 phần tử, mỗi khối chứa tối đa 4 mẫu tin, hàm băm h(x) = x % 5. Dựa trên sơ đồ bảng băm minh họa, phát biểu nào sau đây là sai?

Ta không thể xóa mẫu tin có khóa 22.

Khi xóa mẫu tin có khóa 6 thì khối thứ hai trong danh sách B[1] sẽ giảm một mẫu tin.

Khi xóa mẫu tin có khóa 23 thì số khối và số mẫu tin trong bảng băm không thay đổi.

Khi xóa mẫu tin có khóa 19 thì số khối trong bảng băm giảm xuống một.

32.

Sau khi thêm mẫu tin có khóa 47 vào tập tin B-cây như hình mô tả (các nút lá hiện tại chứa: B1: 3 5 8; B2: 10 11 16; B3: 23 25 27; B4: 28 31 38; B5: 42 46; B6: 48 52 60; các khóa chỉ mục hiển thị ở các nút trong như trên hình), cấu trúc tập tin sau khi chèn sẽ là phương án nào dưới đây? Chọn sơ đồ đúng.

Phương án A (xem sơ đồ A)

Phương án B (xem sơ đồ B)

Phương án C (xem sơ đồ C)

Phương án D (xem sơ đồ D)

33.

Sau khi thêm mẫu tin có khóa 9 vào tập tin B-cây như hình mô tả ở phần trên (Root chứa 18; các nút lá: L1: 4 6 8; L2: 10 12; L3: 14 16; L4: 18 20; L5: 22 24 26; L6: 28 30 32; L7: 34 36; L8: 38 40 42), cấu trúc tập tin sau khi chèn sẽ là phương án nào dưới đây? Chọn sơ đồ đúng.

Phương án A (xem sơ đồ A)

Phương án B (xem sơ đồ B)

Phương án C (xem sơ đồ C)

Phương án D (xem sơ đồ D)

34.

Khai báo nào sau đây không đúng cho hàm thực hiện chức năng tách danh sách liên kết L1 thành hai danh sách L2 và L3?

void Split(List L1, List &L2, List &L3);

List Split(List L1, List &L3);

List Split(List L1, List &L2);

void Split(List &L1, List L2, List L3);

35.

Các kiểu dữ liệu cơ bản là …

các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ ngôn ngữ tự nhiên

các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ máy tính

các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ ngôn ngữ lập trình

các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ người máy

36.

Đặc điểm nào sau đây không phải của hàm có tính đệ qui?

luôn có trường hợp cơ sở để đảm bảo dừng

có thể tự gọi lại chính nó (trực tiếp hoặc gián tiếp)

mỗi lần gọi làm bài toán tiến dần tới trường hợp cơ sở

luôn luôn tối ưu hơn giải pháp lặp

37.

Chọn phát biểu sai về các phép toán cơ bản trên hàng đợi.

Phép toán cơ bản trên hàng đợi là insertqueue

Phép toán cơ bản trên hàng đợi là dequeue

Phép toán cơ bản trên hàng đợi là emptyqueue

Phép toán cơ bản trên hàng đợi là enqueue

38.

Cho ngăn xếp S kiểu phần tử là char có các phép toán cơ bản MakeNullStack, EmptyStack, Push, Top, Pop. Thực hiện chuỗi thao tác: KH#OA#CON##GNGH#E##. Mỗi dấu # biểu thị thao tác lấy nội dung phần tử ở đỉnh ngăn xếp S, in ra màn hình rồi xóa phần tử đó. Chuỗi ký tự được in ra là gì?

HAONHEG

HAONEHF

HANOHEG

HANOEHG

39.

Xét đoạn mã hàm: long Func(int n, int x, int y) { if(n==0) return x*y; else if(n%2==0) return Func(n-1, x/2, y*2); else return Func(n-1, x*2, y/2); } Lời gọi hàm Func(5, 4, 3) sẽ trả về kết quả nào?

40.

Danh sách được cài đặt bằng mảng được gọi là gì?

danh sách liên kết vòng

danh sách liên kết

danh sách liên kết kép

danh sách đặc

41.

Để quản lý điểm trung bình tích lũy của các sinh viên trong một lớp (không quá 80 người), có thể khai báo cấu trúc dữ liệu theo hai cách: Cách 1: struct Sinhvien { char mssv[10]; float dtbtl; }; typedef Sinhvien sv[80]; Cách 2: struct Sinhvien { char mssv[10]; float dtbtl; }; typedef struct Node { Sinhvien Element; Node* Next; }; typedef Node* sv; Phát biểu nào sau đây là đúng?

Cách 2 luôn luôn tốt hơn cách 1

Dung lượng trong vùng nhớ của cách 1 không phụ thuộc vào số lượng sinh viên nhưng dung lượng trong vùng nhớ của cách 2 phụ thuộc vào số lượng sinh viên

Cách 1 luôn luôn tốt hơn cách 2

Nếu số lượng sinh viên trong một lớp là 65 thì ta nên chọn cách 1 để khai báo

42.

Cho khai báo: struct DateOfBirth { int nam; int thang; int ngay; } dob = {9, 7, 8}; Giá trị lần lượt của các trường ngay, thang và nam của biến dob là gì?

9, 7, 8

7, 8, 9

8, 7, 9

8, 9, 7

43.

Hàm nào sau đây thực hiện đúng chức năng thêm một phần tử vào đầu danh sách liên kết?

void ThemDau(ElementType X, List &L) { Position Temp=new Node; Temp->Element=X; Temp->Next=L->Next; L->Next=Temp; }

void ThemDau(ElementType X, List L) { Position Temp=new Node; Temp->Next=X; Temp->Next=L->Next; L->Next=Temp; }

void ThemDau(ElementType X, List &L) { Position Temp=new Node; Temp->Element=X; L->Next=Temp->Next; L->Next=Temp; }

void ThemDau(ElementType X, List &L) { Position Temp=new Node; Temp->Element=X; L=Temp->Next; L->Next=Temp; }

44.

Trong ngôn ngữ lập trình C/C++ có các cấu trúc điều khiển nào?

Rẽ nhánh và lặp

Tuần tự và rẽ nhánh

Tuần tự, rẽ nhánh và lặp

Tuần tự và lặp

45.

Phát biểu nào sau đây là sai?

Biến con trỏ không cho phép chúng ta thâm nhập trực tiếp vào bộ nhớ

Địa chỉ của một biến là địa chỉ byte nhớ đầu tiên của biến đó

Để con trỏ p trỏ tới x ta phải gán địa chỉ của x cho p

Con trỏ là một biến chứa địa chỉ của biến khác

46.

Kiểu dữ liệu trừu tượng là gì?

Kiểu dữ liệu mà người lập trình phải tự xây dựng dựa trên các kiểu dữ liệu cơ bản được cung cấp từ ngôn ngữ lập trình

Kiểu dữ liệu mà người lập trình phải tự xây dựng dựa trên các kiểu dữ liệu không cơ bản được cung cấp từ ngôn ngữ lập trình

47.

Mối quan hệ giữa cấu trúc dữ liệu và giải thuật có thể minh họa bằng đẳng thức nào?

Giải thuật + Chương trình = Cấu trúc dữ liệu

Cấu trúc dữ liệu = Giải thuật

Cấu trúc dữ liệu + Chương trình = Giải thuật

Cấu trúc dữ liệu + Giải thuật = Chương trình

48.

Phát biểu nào sau đây là sai?

Trong danh sách liên kết đơn phần tử cuối cùng có trường liên kết trỏ đến NULL.

Trong danh sách liên kết đơn địa chỉ của phần tử đầu tiên được giữ bởi một con trỏ.

Trong danh sách liên kết đơn ta không thể xóa phần tử đầu tiên vì khi đó sẽ không còn con trỏ nào để giữ địa chỉ của danh sách đó.

Trong danh sách liên kết đơn để truy xuất đến phần tử thứ i thì phải duyệt qua lần lượt các phần tử từ đầu danh sách.

49.

Cho hàm thêm một phần tử X vào vị trí P trong danh sách L như sau (xem hình). Hai câu lệnh nào có thể ghép chung thành một?

(4) và (5)

(1) và (2)

(2) và (3)

(3) và (4)

50.

Lời gọi hàm Swap(5, 10); sẽ không báo lỗi đối với hàm nào sau đây?

void Swap(int *a, int *b) { int t = b; b = a; a = t; }

void Swap(int *a, int &b) { int t = a; t = b; b = a; }

void Swap(int &a, int &b) { int t = a; a = b; b = t; }

void Swap(int a, int b) { int t = a; b = t; a = b; }

51.

Hàm Func sau đây thực hiện chức năng gì trên danh sách liên kết?

Nối danh sách liên kết L vào sau danh sách liên kết R.

Sắp xếp danh sách liên kết L.

Sao chép danh sách liên kết L thành danh sách liên kết R.

Chuyển danh sách liên kết L thành danh sách liên kết R.

52.

Cho hàng đợi Q với kiểu phần tử là char đã có sẵn các phép toán cơ bản MakeNullQueue, EmptyQueue, EnQueue, FirstQueue, DeQueue; cho khối lệnh for (int i = 0; i < K; i++) EnQueue(DeQueue(Q), Q). Giả sử trong hàng đợi Q có chứa các ký tự: K, H, O, A, C, N, T, T. K nhận giá trị là bao nhiêu để sau khi thực hiện xong khối lệnh trên thì hàng đợi Q có kết quả như hình?

53.

Đánh giá độ phức tạp của giải thuật là việc xác định … và … mà giải thuật cần để thực hiện giải một bài toán.

độ khó, thời gian

dung lượng bộ nhớ, độ khó

thời gian, dung lượng bộ nhớ

tính đơn giản, thời gian

54.

Giải thuật đệ quy là:

Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi nhỏ hơn.

Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi lớn hơn.

55.

Đặc điểm của giải thuật đệ quy là gì?

Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó.

Sau mỗi lần có lời gọi đệ quy thì kích thước của bài toán được thu nhỏ hơn trước.

Có một trường hợp đặc biệt, trường hợp suy biến Khi trường hợp này xảy ra thì bài toán còn lại sẽ được giải quyết theo một cách khác.

Tất cả đều đúng.

56.

Danh sách tuyến tính là gì?

Danh sách mà quan hệ lân cận giữa các phần tử được xác định.

Danh sách dạng được lưu dưới dạng mảng.

Danh sách tuyến tính là một danh sách rỗng.

Danh sách tuyến tính là một danh sách có dạng (a1, a2, ..., an).

57.

Ưu điểm của việc cài đặt danh sách bằng mảng là gì?

Có thể bổ sung hoặc xóa một phần tử bất kỳ trong mảng.

Việc truy nhập vào phần tử của mảng được thực hiện trực tiếp vào địa chỉ tính được (chỉ số), nên tốc độ nhanh và đồng đều đối với mọi phần tử.

Có thể thay đổi số lượng phần tử theo ý muốn của người dùng.

Tất cả các ý trên đều đúng.

58.

Danh sách tuyến tính dạng ngăn xếp là gì?

Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp được thực hiện ở một đầu, và phép loại bỏ được thực hiện ở đầu kia.

Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và phép loại bỏ một phần tử khỏi ngăn xếp luôn luôn thực hiện ở một đầu gọi là đỉnh.

Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và phép loại bỏ một phần tử khỏi ngăn xếp luôn luôn thực hiện ở tại một vị trí bất kì trong danh sách.

Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp được thực hiện ở một đầu, Và phép loại bỏ không thực hiện được.

59.

Danh sách tuyến tính dạng ngăn xếp làm việc theo nguyên tắc nào?

FIFO (first in first out)

LILO (last in last out)

LIFO (last in first out)

FOLO (first out last out)

60.

Khi đổi một số nguyên từ hệ thập phân sang hệ nhị phân bằng phép chia liên tiếp cho 2 và lấy các số dư theo chiều ngược lại, cơ chế này tương ứng với cấu trúc dữ liệu nào?

Hàng đợi (Queue)

Mảng (array)

Bản ghi (Record)

Ngăn xếp (stack)

61.

Định nghĩa danh sách tuyến tính Hàng đợi (Queue) là gì?

Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử được thực hiện ở một đầu, gọi là lối sau (rear) hay lối trước (front). Phép loại bỏ không thực hiện được.

Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử ở một đầu, gọi là lối sau (rear) và phép loại bỏ phần tử được thực hiện ở đầu kia, gọi là lối trước (front).

Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử hay loại bỏ được thực hiện ở một đầu danh sách gọi là đỉnh (Top).

Là một danh sách tuyến tính trong đó phép bổ sung một phần tử và phép loại bỏ một phần tử được thực hiện ở tại một vị trí bất kì trong danh sách.

62.

Hàng đợi còn được gọi là danh sách kiểu gì?

FIFO (first in first out)

LILO (last in last out)

LIFO (last in first out)

FOLO (first out last out)

63.

Để thêm một đối tượng x bất kỳ vào Stack, thao tác thường dùng là gì?

POP(x)

EMPTY(x)

TOP(x)

PUSH(x)

64.

Để lấy loại bỏ một đối tượng ra khỏi Stack, thao tác thường dùng là gì?

PUSH(x)

POP(x)

EMPTY(x)

FULL(x)

65.

Để biểu diễn Stack, ta thường sử dụng kiểu dữ liệu nào sau đây?

Danh sách móc nối và mảng dữ liệu

Kiểu bản ghi

Mảng dữ liệu

Danh sách móc nối

66.

Thao tác POP(x) dùng trong Stack là để làm gì?

Xóa bỏ một dãy các phần tử ra khỏi Stack

Xóa bỏ một phần tử bất kì khỏi Stack

Lấy phần tử đầu tiên ra khỏi Stack

Lấy một phần tử cuối cùng ra khỏi đỉnh Stack

67.

Thao tác PUSH(x) dùng trong Stack là để làm gì?

Bổ sung một phần tử vào đầu Stack

Bổ sung một dãy các phần tử vào đỉnh Stack

Bổ sung một phần tử vào đỉnh Stack

Bổ sung một phần tử bất kì vào Stack

68.

Cho Stack gồm 5 phần tử {12, 5, 20, 23, 25}, trong đó 25 là phần tử ở đỉnh Stack. Để lấy ra phần tử thứ 3 trong Stack ta phải làm thế nào?

POP(25), POP(23), POP(20)

POP(25), POP(23), POP(20), PUSH(23), PUSH(25)

POP(25), POP(23), POP(20), PUSH(25), PUSH(23)

POP(25), POP(23), PUSH(20), PUSH(25), PUSH(23)

69.

Trong lưu trữ dữ liệu kiểu Queue (Q) dưới dạng mảng nối vòng, giả sử F là con trỏ trỏ tới lối trước của Q, R là con trỏ trỏ tới lối sau của Q. Điều kiện F=R=0 nghĩa là gì?

Queue rỗng

Kiểm tra chỉ số trước và chỉ số sau của Queue có bằng nhau không.

Queue tràn

Đặt phần tử đầu và phần tử cuối của Queue bằng 0

70.

Trong lưu trữ dữ liệu kiểu Queue (Q), giả sử F là con trỏ trỏ tới lối trước của Q, R là con trỏ trỏ tới lối sau của Q. Khi thêm một phần tử vào Queue, thì R và F thay đổi thế nào?

F=F-1, R không thay đổi

F không thay đổi, R=R-1

F=F+1, R không thay đổi

F không thay đổi, R=R+1

71.

Trong lưu trữ dữ liệu kiểu Queue (Q), giả sử F là con trỏ trỏ tới lối trước của Q, R là con trỏ trỏ tới lối sau của Q. Khi loại bỏ một phần tử vào Queue, thì R và F thay đổi thế nào?

F=F-1, R không thay đổi

F không thay đổi, R=R-1

F không thay đổi, R=R+1

F=F+1, R không thay đổi

72.

Trong biểu diễn dữ liệu dưới dạng cây, cấp của cây chính là gì?

Cấp cao nhất của nút lá

Cấp cao nhất của một nút trên cây

Tổng số nút trên cây

Cấp cao nhất của nút gốc

73.

Trong biểu diễn dữ liệu dưới dạng cây, nút có cấp bằng 0 gọi là gì?

Lá

Phần tử cuối cùng trong cây

Không có đáp án nào đúng

Gốc

74.

Mỗi nút trong cây có thể có tối đa bao nhiêu nút con?

1 nút con

Nhiều nút con

3 nút con

75.

Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là i thì vị trí của nút con trái là:

i-1

2*i

i+1

2*i + 1

76.

Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là i thì vị trí của nút con phải là:

i+1

2*i

2*i + 1

i-1

77.

Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là 3 thì vị trí tương ứng của nút con sẽ là:

6 và 7

78.

Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là 3 thì vị trí tương ứng của nút con trái sẽ là:

79.

Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là 3 thì vị trí tương ứng của nút con phải sẽ là:

80.

Duyệt cây nhị phân theo thứ tự trước được thực hiện theo thứ tự:

Duyệt cây con trái theo thứ tự trước, thăm gốc giữa, duyệt cây con phải theo thứ tự sau.

Duyệt cây con trái theo thứ tự sau, thăm gốc trước, duyệt cây con phải theo thứ tự sau.

Nút gốc, duyệt cây con trái theo thứ tự trước, duyệt cây con phải theo thứ tự trước.

Thăm gốc trước, duyệt cây con trái theo thứ tự giữa, duyệt cây con phải theo thứ tự sau.

81.

Duyệt cây nhị phân theo thứ tự giữa được thực hiện theo thứ tự:

Thăm gốc trước, duyệt cây con trái theo thứ tự giữa, duyệt cây con phải theo thứ tự sau.

Duyệt cây con theo thứ tự trước, thăm gốc giữa, duyệt cây con phải theo thứ tự sau.

Duyệt cây con trái theo thứ tự giữa, thăm gốc, duyệt cây con phải theo thứ tự giữa.

Thăm gốc, duyệt cây con trái theo thứ tự giữa, duyệt cây con phải theo thứ tự giữa.

82.

Duyệt cây nhị phân theo thứ tự sau được thực hiện theo thứ tự:

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.

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 trái theo thứ tự trước, thăm gốc giữa, duyệt cây con phải theo thứ tự sau.

Thăm gốc trước, duyệt cây con trái theo thứ tự giữa, duyệt cây con phải theo thứ tự sau.

83.

Ý tưởng phương pháp sắp xếp chọn tăng dần (select sort):

Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách dời chỗ phần tử bé nhất với phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai, ba...

Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.

Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy.

Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào bé hơn được đứng vị trí trên.

84.

Ý tưởng phương pháp sắp xếp nổi bọt (bubble sort) là:

Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào nhỏ hơn được đứng vị trí trên.

Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.

Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy.

85.

Ý tưởng phương pháp sắp xếp chèn (insertion sort) là:

Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.

Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào nhỏ hơn được đứng vị trí trên.

Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy bằng cách đẩy các phần tử lớn hơn xuống.

86.

Ý tưởng phương pháp sắp xếp nhanh (Quick sort) là:

Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khóa (dãy con trước khóa gồm các phần tử nhỏ hơn khóa và dãy còn lại gồm các phần tử lớn hơn khóa).

Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào nhỏ hơn được đứng vị trí trên.

Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.

87.

Phương pháp sắp xếp nhanh (Quick sort) chính là phương pháp:

Phân đoạn

Vun đống

Chèn

Trộn

88.

Ý tưởng phương pháp sắp xếp Trộn (Merge sort) là:

Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào nhỏ hơn được đứng vị trí trên.

Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.

89.

Ý tưởng của giải thuật tìm kiếm nhị phân:

So sánh X lần lượt với các phần tử thứ nhất, thứ hai,... của dãy cho đến khi gặp phần tử có khóa cần tìm.

Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy, Dựa vào bước so sánh này quyết định giới hạn dãy tìm kiếm nằm ở nửa trên, hay nửa dưới của dãy hiện hành.

Lần lượt chia dãy thành hai dãy con dựa vào phần tử khóa, sau đó thực hiện việc tìm kiếm trên hai đoạn đã chia.

Tìm kiếm dựa vào cây nhị tìm kiếm.

90.

Ý tưởng của giải thuật tìm kiếm tuần tự:

Lần lượt chia dãy thành hai dãy con dựa vào phần tử khóa, sau đó thực hiện việc tìm kiếm trên hai đoạn đã chia.

Tìm kiếm dựa vào cây nhị tìm kiếm: Nếu giá trị cần tìm nhỏ hơn gốc thì thực hiện tìm kiếm trên cây con trái, ngược lại ta việc tìm kiếm được thực hiện trên cây con phải.

91.

Tư tưởng của giải thuật tìm kiếm trên cây nhị phân tìm kiếm là gì?

So sánh X lần lượt với các phần tử thứ nhất, thứ hai,... của dãy cho đến khi gặp phần tử có khóa cần tìm.

Tìm kiếm dựa vào cây nhị tìm kiếm: nếu giá trị cần tìm nhỏ hơn gốc thì thực hiện tìm kiếm trên cây con trái, ngược lại thì việc tìm kiếm được thực hiện trên cây con phải.

Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy. Dựa vào bước so sánh này quyết định giới hạn dãy tìm kiếm nằm ở nửa trên hay nửa dưới của dãy hiện hành.

Lần lượt chia dãy thành hai dãy con dựa vào phần tử khóa, sau đó thực hiện việc tìm kiếm trên hai đoạn đã chia.

92.

Cây nhị phân tìm kiếm là:

Là cây nhị phân đầy đủ.

Cây nhị phân mà mỗi nút trong cây đều thỏa tính chất: giá trị của nút cha nhỏ hơn mọi nút trên cây con trái và lớn hơn mọi nút trên cây con phải của nó.

Cây nhị phân mà mỗi nút trong cây đều thỏa tính chất: giá trị của nút cha lớn hơn giá trị của hai nút con.

Cây nhị phân thỏa tính chất heap.

93.

Trong các giải thuật sắp xếp, giải thuật nào áp dụng phương pháp "Chia để trị"?

Quick sort, Heap sort

Quick sort, Bubble sort

Quick sort, Insert sort

Quick sort, Merge sort

94.

Cho dãy số {6 1 3 0 5 7 9 2 8 4}. Áp dụng phương pháp sắp xếp lựa chọn (Select sort). Dãy số thu được sau lần lặp thứ hai là:

{0 1 2 6 5 7 9 3 4 8}

{0 1 2 6 5 7 9 3 8 4}

{0 1 3 6 5 7 9 2 8 4}

{0 1 2 3 4 5 6 7 8 9}

95.

Cho dãy số {4 7 0 9 2 5 3 1 8 6}. Áp dụng phương pháp sắp xếp nổi bọt (Bubble sort). Dãy số thu được sau lần lặp thứ ba là:

{0 1 2 4 7 3 5 6 8}

{0 1 2 3 4 7 5 6 8}

{0 4 7 1 9 2 5 3 6 8}

{0 1 4 7 2 9 3 5 6 8}

96.

Cho dãy số {4 0 2 8 5 9 6 1 3 7}. Áp dụng phương pháp sắp xếp chèn (Insert sort). Dãy số thu được sau lần lặp thứ bốn là:

{0 1 2 3 5 9 6 4 8 7}

{0 4 2 8 5 9 6 1 3 7}

{0 1 2 8 5 9 6 4 3 7}

{0 2 4 5 8 9 6 1 3 7}

97.

Cho dãy số {3 1 6 0 5 4 8 2 9 7}. Áp dụng phương pháp sắp xếp nhanh (Quick sort). Dãy số thu được sau lần lặp thứ bốn là:

{0 1 2 3 (5 4 8 6 9 7)}

{0 1 (2 3) (5 4 8) (6 9 7)}

{(3) 1 (6 0) 5 (4 8) 2 (9 7)}

{(0) 1 (2 3) 4 (5 6) 7 (8 9)}

98.

Cho dãy số: 12 2 8 5 1 6 4 15 và các bước sắp xếp sau: Bước 1: 1 2 8 5 12 6 4 15 Bước 2: 1 2 8 5 12 6 4 15 Bước 3: 1 2 4 5 12 6 8 15 Bước 4: 1 2 4 5 12 6 8 15 Bước 5: 1 2 4 5 6 12 8 15 Bước 6: 1 2 4 5 6 8 12 15 Các bước trên dựa theo giải thuật sắp xếp nào?

Select sort

Quick sort

Insert sort

Bubble sort

99.

Cho dãy số: "4 7 0 9 2 5 3 1 8 6" và các bước sắp xếp sau: Bước 1: 0 4 7 1 9 2 5 3 6 8 Bước 2: 0 1 4 7 2 9 3 5 6 8 Bước 3: 0 1 2 4 7 3 9 5 6 8 Bước 4: 0 1 2 3 4 7 5 9 6 8 Bước 5: 0 1 2 3 4 5 7 6 9 8 Bước 6: 0 1 2 3 4 5 6 7 8 9 Các bước trên dựa theo giải thuật sắp xếp nào?

Bubble sort

Select sort

Quick sort

Insert sort

100.

Cho dãy số: "5 1 4 2 7 3" và các bước sắp xếp sau: Bước 1: 1 5 4 2 7 3 Bước 2: 1 4 5 2 7 3 Bước 3: 1 2 4 5 7 3 Bước 4: 1 2 4 5 7 3 Bước 5: 1 2 3 4 5 7 Các bước trên dựa theo giải thuật sắp xếp nào?

Select sort

Insert sort

Quick sort

Bubble sort

101.

Cho dãy số: 3 1 6 0 5 4 8 2 9 7 và các bước sắp xếp sau: Bước 1: 1 3 6 0 5 4 8 2 9 7 Bước 2: 1 3 6 0 5 4 8 2 9 7 Bước 3: 1 3 6 0 5 4 8 2 9 7 Bước 4: 0 1 3 5 6 4 8 2 9 7 Bước 5: 0 1 3 5 6 4 8 2 9 7 Bước 6: 0 1 3 5 6 2 4 8 9 7 Bước 7: 0 1 3 5 6 2 4 8 7 9 Bước 8: 0 1 3 5 6 2 4 7 8 9 Bước 9: 0 1 2 3 4 5 6 7 8 9 Các bước trên dựa theo giải thuật sắp xếp nào?

Quick sort

Select sort

Merge sort

Insert sort

102.

Cho dãy số sau: 10 11 14 32 36 43 55 57 87 97. Áp dụng phương pháp tìm kiếm nhị phân, sau bao nhiêu lần phân đoạn ta sẽ tìm thấy số 43?

2 lần

4 lần

3 lần

5 lần

103.

Tính chất nào sau đây là tính chất của cây nhị phân tìm kiếm:

Mọi khóa thuộc cây con trái nút đó đều lớn hơn khóa ứng với nút đó.

Đáp án A và C.

Mọi khóa thuộc cây con trái nút đó đều nhỏ hơn khóa ứng với nút đó.

Mọi khóa thuộc cây con trái nút đó đều lớn hơn khóa cây con phải nút đó.

104.

Chọn câu trả lời đúng nhất về thuật toán:

Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết vấn đề đặt ra.

Thuật toán là một dãy hữu hạn các bước, tất cả các phép toán có mặt trong các bước của thuật toán phải đủ đơn giản.

Thuật toán là nòng cốt của chương trình.

Thuật toán cần có một hoặc nhiều dữ liệu ra (output), dữ liệu vào (input).

105.

Giải thuật đệ quy là:

Nếu lời giải của một bài toán T được giải bằng lời giải của một bài toán T1 khác T, thì lời giải đó được gọi là lời giải đệ quy.

Nếu lời giải của một bài toán T được giải bằng lời giải của một bài toán T1, có dạng giống như T, thì lời giải đó được gọi là lời giải đệ quy.

Nếu lời giải của một bài toán T được giải bằng lời giải của một bài toán T1 mà T1 giải được thì lời giải đó được gọi là lời giải đệ quy.

Nếu lời giải của một bài toán T được giải bằng lời giải của một bài toán T1 mà T1 có độ phức tạp khác T, thì lời giải đó được gọi là lời giải đệ quy.

106.

Định nghĩa cấu trúc dữ liệu Stack:

Stack là một danh sách đặc biệt mà phép thêm vào được thực hiện ở một đầu, và phép loại bỏ được thực hiện ở phần kia của stack.

Stack là một danh sách đặc biệt mà phép thêm vào hoặc loại bỏ một phần tử chỉ thực hiện tại một đầu gọi là đỉnh (Top) của Stack.

Stack là danh sách kết nối.

Stack là cấu trúc dữ liệu được cài đặt bằng con trỏ.

107.

Để cài đặt Stack ta có thể dùng phương pháp nào sau đây:

Bằng con trỏ và bằng mảng

Bằng con trỏ

Bằng mảng

Tất cả đều sai

108.

Hãy cho biết hàm sau dùng để làm gì: Position ham (List L) { Position P; P = L; while (P->Next != NULL) P = P->Next; return P; }

Xác định phần tử đầu tiên.

Xác định phần tử cuối cùng.

Xác định phần tử đứng sau P.

Xác định phần tử đứng trước P.

100 %

Câu hỏi trắc nghiệm về độ phức tạp và đệ qui

Total questions: 108

Worksheet time: 54mins

Similar Resources on Wayground