Free Printable Cấu trúc dữ liệu và giải thuật

Worksheets

Cấu trúc dữ liệu và giải thuật – Bài tập trắc nghiệm

Total questions: 100

Worksheet time: 50mins

Name

Class

Date

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 gì?

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

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

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

Cấu trúc dữ liệu = Chương trình

Để đánh giá cấu trúc dữ liệu chúng ta dựa vào tiêu chí nào?

Cấu trúc dữ liệu phải tiết kiệm bộ nhớ trong

Cấu trúc dữ liệu phản ánh thực tế của bài toán

Cấu trúc dữ liệu phải giúp dễ dàng trong thao tác dữ liệu

Các phương án đều đúng

Tiêu chuẩn để đánh giá giải thuật tốt là gì?

Giải thuật đúng đắn

Giải thuật đơn giản

Giải thuật thực hiện nhanh

Tất cả các phương án đều đúng

Độ phức tạp thời gian trong trường hợp xấu nhất được gọi là gì?

Best-case complexity

Average-case complexity

Worst-case complexity

Time complexity

Độ phức tạp không gian của thuật toán liên quan đến yếu tố nào?

Bộ nhớ tạm thời cần thiết

Số lần lặp trong vòng lặp

Số lượng câu lệnh thực thi

Tốc độ xử lý của bộ vi xử lý

Danh sách là gì trong lập trình?

Một dãy số nguyên

Một cấu trúc dữ liệu lưu trữ các phần tử liền tiếp

Một phương thức sắp xếp dữ liệu

Một loại biến đặc biệt

Trong danh sách bổ mảng, cách truy cập vào phần tử có chỉ số là gì?

Dấu ngoặc vuông ([])

Dấu ngoặc tròn (())

Dấu ngoặc nhọn ({})

Dấu ngoặc kép (" ")

Đặc điểm quan trọng của danh sách là gì?

Các phần tử có thể thay đổi

Các phần tử không thể thay đổi

Chỉ chứa số nguyên

Chỉ chứa chuỗi ký tự

Stack là một cấu trúc dữ liệu có nguyên tắc gì?

FIFO (First In First Out)

LIFO (Last In First Out)

LILO (Last In Last Out)

FILO (First In Last Out)

10.

Phép toán chính trên stack là gì?

Push và Pop

Add và Remove

Enqueue và Dequeue

Insert và Delete

11.

Khi một phần tử được thêm vào stack, nó được thêm vào vị trí nào?

Ở đầu danh sách

Ở cuối danh sách

Ở giữa danh sách

Ở đỉnh của stack

12.

Queue hoạt động theo nguyên tắc nào?

LIFO (Last In First Out)

FIFO (First In First Out)

LILO (Last In Last Out)

FILO (First In Last Out)

13.

Phép toán chính trên queue là gì?

Push và Pop

Enqueue và Dequeue

Add và Remove

Insert và Delete

14.

Trong queue, phần tử mới được thêm vào ở đâu?

Ở đầu danh sách

Ở cuối danh sách

Ở giữa danh sách

Ở đỉnh của queue

15.

Khi một phần tử được loại bỏ khỏi stack, phép toán đó được gọi là gì?

Pop

Push

Peek

Empty

16.

Ngăn xếp có thể được triển khai bằng cách sử dụng gì?

Mảng

Danh sách liên kết

Cả mảng và danh sách liên kết

Cả mảng và danh sách liên kết và cây

17.

Danh sách liên kết đơn và danh sách liên kết kép có điểm khác biệt chính gì?

Số lượng phần tử

Khả năng tìm kiếm

Khả năng chèn và xóa

Không có sự khác biệt

18.

Trong giải thuật, bài toán liệt kê là:

Bài toán yêu cầu đưa ra danh sách các cấu hình

Bài toán phân tích đối tượng thành nhiều thành phần

Bài toán tính số tổ hợp chập k của n theo công thức truy hồi

Tất cả đều đúng

19.

Thuật toán đệ quy là:

Thuật toán có lời gọi đến một thuật toán khác

Thuật toán có lời gọi đến chính nó nhưng với kích thước lớn hơn

Thuật toán có lời gọi trực tiếp đến chính nó nhưng với kích thước nhỏ hơn

Thuật toán có lời gọi trực tiếp hoặc gián tiếp đến chính nó nhưng có kích thước nhỏ hơn

20.

Cơ chế thực hiện giải thuật đệ quy bao gồm:

Một giai đoạn chính là đi từ trên xuống

Một giai đoạn chính đi từ dưới lên

Hai giai đoạn chính: đi từ trên xuống và đi từ dưới lên

Tất cả các đáp án đều sai

21.

Cho hàm đệ quy sau: int factorial(int n) { if (n == 0) // Phần neo. return 1; else // Phần gọi đệ quy. return factorial(n - 1) * n; } Sau mỗi lần gọi đệ quy thì giá trị của biến n:

Tăng lên 1 đơn vị

Giảm xuống 1 đơn vị

n có giá trị bằng 0

n có giá trị bằng 1

22.

Một hàm đệ quy được định nghĩa bởi:

2 phần

3 phần

1 phần

Không chia thành các phần

23.

Số bước thực hiện thuật toán đệ quy cho bài toán Tháp Hà Nội với số lượng đĩa 3 là:

5 bước

6 bước

7 bước

8 bước

24.

Nhược điểm của thuật toán đệ quy là:

Tốn bộ nhớ

Tốn thời gian

Dễ gây tràn bộ nhớ

Tất cả các phương án đều đúng

25.

Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp lựa 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 đổ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 đổi chỗ cho phần tử thứ hai, cứ như vậy cho đến phần tử trước phần tử cuối cùn

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 cho lên 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

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

26.

Phương pháp nào sau đây chính là phương pháp sắp xếp nhanh (Quick sort)?

Phương pháp trộn

Phương pháp vun đống

Phương pháp chèn

Phương pháp phân đoạn

27.

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

Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổ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...

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 chia dãy phần tử thành hai dãy con bởi một phần tử khoá (dãy con trước khoá gồm các phần tử nhỏ hơn khoá và dãy còn lại gồm các phần tử lớn hơn khoá).

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.

28.

Ý 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.

29.

Cơ chế heap trong sắp xếp vun đống là:

Cây nhị phân đầy đủ với tính chất giá trị của nút cha luôn lớn hơn giá trị hai nút con.

Cây nhị phân đầy đủ với tính chất giá trị của nút cha luôn lớn hơn giá trị của nút trong cây con trái và nhỏ hơn giá trị các nút trong cây con phải.

Cây nhị phân hoàn chỉnh với tính chất giá trị nút cha lớn luôn lớn hơn giá trị các nút trong cây con trái và nhỏ hơn giá trị các nút trong cây con phải.

Cây nhị phân hoàn chỉnh với tính chất giá trị của nút cha luôn lớn hơn giá trị hai nút con.

30.

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

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.

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

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ó khoá cần tìm hoặc không thấy X trong dãy.

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.

31.

Thuật toán sắp xếp nhanh (Quick Sort) có độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?

$O(1)$

$O(n)$

$O(\log n)$

$O(n^2)$

32.

Cho thuật toán sắp xếp Bubble Sort, chọn câu đúng nhất cho hàm Swap: void BubbleSort(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]) Swap(M[J], M[J-1]); } return;}

void Swap(int &X, int &Y) { int Temp = X; X = Y; Y = Temp; return; }

void Swap(float X, float Y) { int Temp = X; X = Y; Y = Temp; return; }

void Swap(int *X, int *Y) { int Temp = X; X = Y; Y = Temp; return; }

void Swap(int X, intY) { int Temp = X; X = Y; Y = Temp; return; }

33.

Trong cây nhị phân tìm kiếm, nếu thực hiện thao tác tìm kiếm và giá trị không tồn tại trong cây, kết quả sẽ là gì?

Giá trị gần nhất

Null

Giá trị 0

Giá trị lớn nhất trong cây

34.

Trong cây nhị phân tìm kiếm, việc sắp xếp các nút theo thứ tự inorder được thực hiện bằng cách nào?

Sử dụng thuật toán sắp xếp nổi bọt

Sử dụng thuật toán quicksort

Sử dụng thuật toán mergesort

Thực hiện thao tác duyệt theo thứ tự inorder trên cây

35.

Trong cây nhị phân, nút trên cùng được gọi là gì?

Nút gốc

Nút lá

Nút cha

Nút con

36.

Đặc điểm nào mô tả cây nhị phân hoàn chỉnh?

Mỗi nút có tối đa một nút con trái và một nút con phải

Mỗi nút có thể có nhiều hơn một nút con trái và một nút con phải

Mỗi nút không có nút con trái hoặc phải

Mỗi nút có nhiều hơn hai nút con

37.

Trong quá trình duyệt cây nhị phân theo thứ tự trước (preorder), thứ tự duyệt nút là gì?

Nút cha trước, sau đó là nút con trái và nút con phải

Nút con trái trước, sau đó là nút cha và nút con phải

Nút con phải trước, sau đó là nút cha và nút con trái

Nút cha trước, sau đó là nút con phải và nút con trái

38.

Trong cây nhị phân tìm kiếm, khóa tìm kiếm của nút con phải, so với khóa tìm kiếm của nút cha và của nút con trái, có quan hệ như thế nào?

Lớn hơn

Nhỏ hơn

Bằng

Không có quy tắc cụ thể

39.

Cây nhị phân cân bằng là gì?

Cây mà mọi nút đều có hai nút con

Cây mà độ cao của cây là tối thiểu

Cây mà độ chênh lệch giữa độ cao của cây con trái và cây con phải của mọi nút là nhỏ hơn hoặc bằng một giá trị cho phép, thường là 1

Cây mà tỷ lệ giữa số nút lá và số nút trong cây là tối ưu

40.

Trong cây nhị phân tìm kiếm, thao tác chèn một giá trị mới thường được thực hiện ở đâu?

Nút lá đầu tiên mà gặp

Nút gốc

Nút lá cuối cùng

Nút lá gần giá trị cần chèn nhất

41.

Trong cây nhị phân tìm kiếm, thứ tự duyệt theo phương pháp inorder sẽ cho ra kết quả như thế nào?

Giá trị giảm dần

Giá trị tăng dần

Giá trị không theo thứ tự cụ thể

Giá trị không hiển thị

42.

Trong cây nhị phân tìm kiếm, thao tác xóa một nút thường yêu cầu làm gì với các nút con của nút cần xóa?

Chuyển tất cả các nút con sang cây con trái

Chuyển tất cả các nút con sang cây con phải

Giữ nguyên cấu trúc cây con trái và cây con phải

Xóa tất cả các nút con

43.

Cây nhị phân đầy đủ là gì?

Cây mà mọi nút đều có đúng hai nút con

Cây mà tất cả các nút đều có giá trị tăng dần

Cây mà tất cả các nút lá đều ở mức cuối cùng

Cây mà tất cả các nút đều có giá trị giảm dần

44.

Trong cây nhị phân tìm kiếm, thao tác xóa một nút yêu cầu xử lý phức tạp nhất khi nút cần xóa có bao nhiêu nút con?

45.

Trong đồ thị, liên thông có nghĩa là gì?

Tất cả các đỉnh đều kết nối

Một số đỉnh không kết nối

Tất cả các cạnh đều kết nối

Không có đỉnh nào kết nối

46.

Một đồ thị được gọi là đồ thị cây nếu:

Có nhiều nhánh nhất

Không có chu trình và liên thông

Có nhiều chu trình

Có nhiều đỉnh nhất

47.

Trong thuật toán DFS, các đỉnh được thăm theo thứ tự nào?

Theo thứ tự bậc tăng dần

Theo thứ tự bậc giảm dần

Theo thứ tự tìm thấy đầu tiên

Theo thứ tự tìm thấy cuối cùng

48.

Hãy cho biết quy tắc đúng của phép duyệt cây theo thứ tự sau trong các phương án sau?

Duyệt cây con trái theo thứ tự sau; Duyệt gốc; Duyệt cây con phải theo thứ tự sau

Duyệt gốc, cây trái, cây phải đồng thờ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; Duyệt gốc

Duyệt gốc; Duyệt cây con trái theo thứ tự sau; Duyệt cây con phải theo thứ tự sau

49.

Thời gian thực hiện chương trình là:

Một hàm của kích thước dữ liệu đầu vào, ký hiệu là T(n) trong đó n là kích thước (độ lớn) của dữ liệu đầu vào

Một hàm của độ dài dữ liệu đầu vào, ký hiệu là N(x) trong đó x là độ dài của dữ liệu đầu vào

Thời gian ngắn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n

Thời gian thực hiện chương trình trong trường hợp nhanh nhất trên dữ liệu đầu vào có kích thước n

50.

Phương pháp để xác định hiệu quả thời gian thực hiện của một giải thuật là:

Lập trình hoạt động trên một máy tính xác định đối với tập hợp được chọn lọc các dữ liệu vào

Đo lường thời gian thực hiện của hoạt động trên một máy tính xác định đối với tập hợp được chọn lọc các dữ liệu vào

Cả hai đáp án cụ thể đều sai

Cả hai đáp án cụ thể đều đúng

51.

Khi ta nói thời gian thực hiện của một chương trình là $T(n)=Cn$ thì có nghĩa là chương trình ấy:

Cận C chi thì thực thi

Cận T(n) chi thì thực thi

Cận n chi thì thực thi

Cận Cn chi thì thực thi

52.

Đơn vị đo thời gian thực hiện chương trình là:

Đơn vị đo thời gian bình thường giờ, phút, giây...

Không phải là đơn vị đo thời gian bình thường như giờ, phút, giây....

Được xác định bởi thời gian được thực hiện trong một máy tính lý tưởng

Tất cả đều sai

53.

Tìm mệnh đề sai trong các mệnh đề sau, một cấu trúc dữ liệu bao gồm:

Một tập hợp nào đó các dữ liệu thành phần

Các dữ liệu thành phần đặt sát nhau trong bộ nhớ

Kiểu dữ liệu là một tập hợp nào đó các phần tử dữ liệu cùng chung một thuộc tính

Tất cả đều là mệnh đề sai

54.

Cho Stack gồm 5 phần tử {12, 5, 20, 23, 72}, trong đó 72 là phần tử ở đỉnh Stack. Để lấy ra phần tử thứ 4 trong Stack ta phải thực hiện theo phương án nào?

POP(72), POP(23), POP(20), POP(5)

POP(72), POP(23), PUSH(20), POP(5)

POP(23), PUSH(23), POP(72), POP(5)

POP(23), PUSH(72), POP(20), POP(5)

55.

Lựa chọn định nghĩa về danh sách đúng nhất? Danh sách là tập hợp các phần tử có kiểu dữ liệu xác định và giữa chúng có một mối liên hệ nào đó

hệ nào đó

Số phần tử của danh sách gọi là chiều dài của danh sách

Một danh sách có chiều dài bằng 0 là một danh sách rỗng

Tất cả đều đúng

56.

Cấu trúc dữ liệu mảng có các ưu điểm nào?

Việc thêm, bớt các phần tử trong danh sách đặc có nhiều khó khăn do phải di dời các phần tử khác đi qua chỗ khác

Việc truy xuất và tìm kiếm các phần tử của mảng là dễ dàng vì các phần tử đứng liền nhau nên chúng ta chỉ cần sử dụng chỉ số để định vị vị trí các phần tử trong danh sách (định vị địa chỉ các phần tử)

Mật độ sử dụng bộ nhớ của mảng là tối ưu tuyệt đối

Tất cả đều đúng

57.

Lựa chọn câu đúng nhất về danh sách liên kết đôi (Doubly Linked List):

Mỗi phần tử trong danh sách liên đôi có 01 mối liên kết với 02 phần tử khác trong danh sách

Mỗi phần tử trong danh sách liên đôi có 01 mối liên kết với 02 phần tử trước và sau nó trong danh sách

Mỗi phần tử trong danh sách liên đôi có 02 mối liên kết với 02 phần tử trước và sau nó trong danh sách

Mỗi phần tử trong danh sách liên đôi có 02 mối liên kết với phần tử đầu và cuối của danh sách

58.

Định nghĩa cấu trúc dữ liệu của danh sách liên kết đơn được mô tả như sau: struct Node { int Key; Node * NextNode; } OneNode; Trong đó, khai báo Node * NextNode; dùng để mô tả

Con trỏ trỏ tới phần dữ liệu

Vùng liên kết quản lý địa chỉ phần tử kế tiếp

Con trỏ trỏ tới phần dữ liệu cuối của danh sách

Vùng liên kết quản lý địa chỉ phần tử kế tiếp của phần tử cuối

59.

Trong các danh sách tuyến tính sau đây, danh sách nào có dạng ngăn xếp?

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 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

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ỏ được thực hiện ở đầu kia

60.

Đoạn mã nguồn sau trả lại kết quả bằng bao nhiêu khi nhập n = 4: int sum(int n) { if (n != 0) // sum() function calls itself return n + sum(n-1); else return n; }

Kết quả là 9

Kết quả là 10

Kết quả là 11

Kết quả là 8

61.

Đoạn mã nguồn sau trả lại kết quả bằng bao nhiêu khi nhập n = 5: int fibonacci(int n) { if(n == 0){ return 0; } else if(n == 1) { return 1; } else { return (fibonacci(n-1) + fibonacci(n-2)); } }

Kết quả là 5

Kết quả là 8

Kết quả là 6

Kết quả là 9

62.

Tìm mô tả đúng nhất cho hàm TinhTong sau: int TinhTong(int N) { int so = 2; int tong = 0; int dem = 0; while (dem < N) { if (KiemTra(so) == 1) { tong = tong + so; dem ++; } so = so + 1; } return tong; } Trong đó int KiemTra(int so) { for (int i = 2; i < so; i++) if (so % i == 0) return 0; return 1; }

Tính tổng N số nguyên tố đầu tiên

Tính tổng các số nguyên tố không vượt quá N

Tính tổng các số chẵn từ 2 đến N

Tính tổng N số tự nhiên đầu tiên

63.

Hãy cho biết câu trả lời đúng nhất về đặc điểm của giải thuật đệ quy?

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ả các đáp án đều đúng

64.

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

Qucick sort, Insert sort

Quick sort, Bubble sort

Quick sort, Merge sort

65.

Thuật toán sắp xếp nào hoạt động bằng cách so sánh từng cặp phần tử liền kề nhau và đổi chỗ nếu cần thiết?

Sắp xếp nhanh (Quick Sort)

Sắp xếp nổi bọt (Bubble Sort)

Sắp xếp chèn (Insertion Sort)

Sắp xếp trộn (Merge Sort)

66.

Đối với thuật toán sắp xếp chọn trực tiếp cho dãy các phần tử sau: 16 60 2 25 15 45 5 30 33 20. Cần thực hiện bao nhiêu lần chọn lựa phần tử nhỏ nhất để sắp xếp mảng trên có thứ tự tăng dần.

7 lần

8 lần

9 lần

10 lần

67.

Với dữ liệu đầu vào (n) đủ nhỏ, ta nên sử dụng phương pháp sắp xếp nào sau đây?

Sắp xếp nhanh (quick sort)

Sắp xếp vun đống (Heap sort)

Sắp xếp lựa chọn (selection sort)

Sắp xếp trộn (Merge sort)

68.

Với dữ liệu đầu vào (n) lớn, ta nên sử dụng phương pháp sắp xếp nào sau đây?

Sắp xếp trộn (Merge sort) hoặc Sắp xếp đống (Heap sort)

Sắp xếp đống (Heap sort) hoặc Sắp xếp nhanh (quick sort)

Sắp xếp chọn (selection sort), sắp xếp chèn (Insert sort)

Sắp xếp nổi bọt (bubble sort) hoặc Sắp xếp chọn (selection sort)

69.

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) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ hai là:

{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}

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

70.

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) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ ba là:

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

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

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

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

71.

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, để tìm kiếm số 10, lần phân đoạn thứ nhất của dãy sẽ là:

[14 32 10 43 57]

[10 11 14 32 36]

[87 55 36 97 11]

[55 36 97 11]

72.

Trong cây nhị phân, giá trị ở nút con phải luôn lớn hơn giá trị ở nút cha và giá trị ở nút con trái luôn nhỏ hơn giá trị ở nút cha. Điều này đảm bảo gì?

Cây nhị phân hoàn chỉnh

Cây nhị phân đầy đủ

Thuật toán tìm kiếm hiệu quả

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

73.

Trong cây nhị phân tìm kiếm, thứ tự duyệt theo thứ tự inorder sẽ cho kết quả nào?

Tăng dần

Giảm dần

Ngẫu nhiên

Không xác định

74.

Đối với một cây nhị phân tìm kiếm, thao tác chèn một giá trị mới sẽ được thực hiện ở đâu?

Nút lá cuối cùng

Nút gốc

Nút lá đầu tiên mà gặp

Nút lá gần giá trị cần chèn nhất

75.

Cây nhị phân cân bằng là gì?

Cây mà tất cả các nút đều có đúng hai nút con

Cây mà độ chênh lệch giữa chiều cao của cây con trái và cây con phải của mọi nút là nhỏ nhất

Cây mà độ chênh lệch giữa số nút lá và số nút trong cây là nhỏ nhất

Cây mà độ chênh lệch giữa chiều cao của cây con trái và cây con phải của mọi nút là lớn nhất

76.

Trong cây nhị phân tìm kiếm, thao tác tìm kiếm một giá trị cụ thể có độ phức tạp thời gian là bao nhiêu trong trường hợp trung bình?

O(1)

O(log n)

O(n)

$O(n^2)$

77.

Khi xóa một nút trong cây nhị phân tìm kiếm, nếu nút đó có hai nút con, nút thay thế sẽ được chọn như thế nào?

Chỉ có thể chọn nút con trái

Chỉ có thể chọn nút con phải

Ta có thể chọn một trong hai nút con, nút con còn lại được đưa xuống làm con phù hợp của cây con nút thay thế

Xóa luôn hai nút con

78.

Đồ thị là gì?

Tập hợp các đỉnh và cạnh (hay cung)

Phương trình toán học

Tập hợp các hình học

Bảng số liệu

79.

Trong đồ thị vô hướng, mỗi cạnh nối bao nhiêu đỉnh?

2 đỉnh

3 đỉnh

4 đỉnh

5 đỉnh

80.

Hãy cho biết phương pháp nào sau đây để loại bỏ nút X trên cây nhị phân tìm kiếm, với X là một phần tử bất kỳ:

Chỉ việc xoá X, vì X không liên quan đến phần tử nào khác

Tìm nút chứa khoá lớn nhất trong cây con trái, đưa giá trị chứa trong đó sang nút X , rồi xoá X

Không thể xoá X ra khỏi cây nhị phân tìm kiếm

Tìm nút chứa khoá lớn nhất trong cây con phải, đưa giá trị chứa trong đó sang nút X, rồi xoá X

81.

Cho mảng 2 chiều: A={F(i j)}; i là chỉ số hàng, j là chỉ số cột. Mảng A có 8 hàng, 9 cột. Lưu trữ liên tiếp mảng A ưu tiên hàng. Nếu phần tử F(11) có địa chỉ 50, mỗi phần tử chiếm 3 ô thì phần tử F(57) có địa chỉ bằng bao nhiêu?

148

152

162

176

82.

Cho mảng 2 chiều A={F(i j)}: i là chỉ số hàng, j là chỉ số cột. Mảng A có 8 hàng, 9 cột. Lưu trữ liên tiếp mảng A ưu tiên cột. Nếu phần tử F(11) có địa chỉ 230, mỗi phần tử chiếm 3 ô thì phần tử F(37) có địa chỉ bằng bao nhiêu?

378

382

380

420

83.

Đoạn mã nguồn sau trả lại kết quả bằng bao nhiêu khi nhập base = 3, a = 4: int power(int base, int a) { if (a != 0) return (base * power(base, a - 1)); else return 1; }

84.

Số lần gọi đệ quy trong đoạn mã nguồn sau đây là bao nhiêu khi nhập n = 9: int display(int n) { if (n != 0) // sum() function calls itself return n + sum(n - 1); else return n; }

Thực hiện gọi đệ quy 8 lần

Thực hiện gọi đệ quy 7 lần

Thực hiện gọi đệ quy 9 lần

Thực hiện gọi đệ quy 10 lần

85.

Thuật toán: B1: k = 1 B2: IF M[k] == X AND k! = N B2.1: k++ B2.2: Lặp lại B2 B3: IF k < N Thông báo tìm thấy tại vị trí k B4: ELSE Không tìm thấy. B5: Kết thúc Thuật toán trên là gì?

Tìm nhị phân phần tử có giá trị X

Tìm phần tử nhỏ nhất của mảng M bao gồm N phần tử

Tìm tuyến tính phần tử có giá trị X

Tất cả đều sai

86.

Cho đoạn mã tìm kiếm nhị phân sau: int Mid = (First + Last)/2; if (X == M[Mid]) return(Mid); if (X < M[Mid]) Last = Mid - 1; else First = Mid + 1; } return(-1); } Chọn câu đúng nhất trong trường hợp tốt nhất khi phần tử ở giữa của mảng có giá trị bằng X.

Số phép gán: Gmin = 3; Số phép so sánh: Smin = 2

Số phép gán: Gmin = 2; Số phép so sánh: Smin = 3

Số phép gán: Gmin = 2; Số phép so sánh: Smin = 2

Số phép gán: Gmin = 0; Số phép so sánh: Smin = 2

87.

Trong giải thuật sắp xếp vun đống (Heap sort), ta có 4 thủ tục con: Insert (thêm 1 phần tử vào cây), Downheap (vun đống lại sau khi loại một phần tử khỏi Heap), Upheap (vun đống sau khi thêm một phần tử vào cây), Remove (loại 1 phần tử khỏi cây nhị phân). Để sắp xếp các phần tử trong dãy theo phương pháp vun đống, ta thực hiện 4 thủ tục trên theo thứ tự nào?

Insert – Upheap – Remove – Downheap

Remove – Downheap – Insert – Upheap

Insert – Upheap – Downheap – Remove

Upheap – Downheap – Remove – Insert

88.

Cho thuật toán sau: int LinearSearch (int M[], int N, int X) { int k = 0; while (M[k] != X && k < N) k++; if (k < N) return (k); return (-1); } Chọn câu đúng nhất trong trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X.

Số phép gán: Gmax = 1; Số phép so sánh: Smax = $2N+1$

Số phép gán: Gmax = 2; Số phép so sánh: Smax = $2N+1$

Số phép gán: Gmax = 1; Số phép so sánh: Smax = $2N+2$

Số phép gán: Gmax = 1; Số phép so sánh: Smax = $N+2$

89.

Một đồ thị có hướng có bao nhiêu đỉnh có thể kết nối với một đỉnh cụ thể?

Nhiều hơn 1

Tùy thuộc vào loại đồ thị

90.

Trong đồ thị có hướng, đỉnh có bậc là gì?

Số cạnh kết nối với đỉnh đó

Độ dài của đỉnh

Màu sắc của đỉnh

Tên của đỉnh

91.

Một chu trình trong đồ thị là gì?

Đỉnh không có cạnh

Tập hợp các đỉnh không kết nối

Đường đi đóng thành vòng

Các đỉnh có màu sắc giống nhau

92.

Đồ thị không chu trình được gọi là gì?

Đồ thị đầy đủ

Đồ thị vô hướng

Đồ thị cây

Đồ thị đồng dạng

93.

Trong đồ thị, đỉnh có bậc vào và bậc ra là bao nhiêu?

Bậc vào và bậc ra không liên quan

Chúng luôn bằng nhau

Chúng có thể bằng nhau hoặc khác nhau

Không có khái niệm bậc vào và ra

94.

Một đồ thị được gọi là đồ thị đầy đủ nếu:

Có nhiều đỉnh nhất

Mọi đỉnh đều kết nối với tất cả các đỉnh khác

Không có chu trình

Đỉnh và cạnh có màu sắc đẹp

95.

Trong đồ thị, đường đi ngắn nhất giữa hai đỉnh được gọi là:

Đường đi tối ưu

Đường đi ngắn nhất

Đường đi đẹp nhất

Đường đi tiện ích

96.

Đồ thị có trọng số là gì?

Mỗi đỉnh có một trọng số

Mỗi cạnh có một trọng số

Cả đỉnh và cạnh đều có trọng số

Không có trọng số

97.

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à bao nhiêu trong các phương án sau?

98.

Độ cao của cây là gì?

Số mức lớn nhất từ gốc đến một lá của cây

Số lượng cạnh của toàn bộ cây

Số lượng đỉnh trong cây

Chiều cao trung bình của các nút

99.

Thường ta coi T(n) là thời gian thực hiện chương trình trong trường hợp xấu nhất trên dữ liệu vào có kích thước n, tức T(n) là:

Thời gian nhỏ nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước T

Thời gian nhỏ nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n

Thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n

Thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước T

100.

Hãy chọn định nghĩa đúng nhất về danh sách kiểu hàng đợi (Queue)?

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ử hay loại bỏ được thực hiện ở một đầu danh sách gọi là đỉnh (Top)

Hàng đợi 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

Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung 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)

Reset

Cấu trúc dữ liệu và giải thuật – Bài tập trắc nghiệm

Total questions: 100

Worksheet time: 50mins

Similar Resources on Wayground