NEW
Font size
WorksheetsCâu hỏi về thuật toán và tìm kiếm CTDL
Total questions: 39
Worksheet time: 20mins
Câu 4: Đoạn mã giả dưới đây mô tả thuật toán gì?
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
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
Cả a, b, c đều sai
Câu 5: Cho hàm tim kiểm tuyến tính như sau: int TimKiem (int M[], int N, int X) { int k = 0; M[N] = X; while(M[k] != X) k++; if (k<N)
return (k);
return (-1); }
Chọn câu đúng nhất:
Hàm sẽ trả về 0 nếu không tìm thấy phần tử có giá trị là X
Hàm sẽ trả về 1 nếu tìm thấy phần tử có giá trị là X
Hàm sẽ trả về - 1 nếu không tìm thấy phần tử có giá trị là X
Hàm sẽ trả về 1 nếu không tìm thấy phần tử có giá trị là X
Câu 6: Xét thủ tục sau: int TimKiemNP (int M[], int First, int Last. int X)
{ if (First > Last)
return (-1);
int Mid (First + Last)/2;
if (X = M[Mid])
return (Mid);
if (X < M[Mid])
return(TimKiemNP (M, First, Mid-1, X));
else
return(TimKiemNP (M, Mid + 1, Last, X)); }
Lựa chọn câu đúng nhất để mô tả thủ tục trên:
Thủ tục hỗ trợ tìm kiếm phần tử có giá trị là X trên mảng các phần từ từ chỉ số từ First đến chỉ số Last
Thủ tục hỗ trợ tim kiểm đệ quy phần tử có giá t giá trị là X trên màng các phần từ từ chỉ số từ First đến chỉ số Last
Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần từ từ chỉ số từ Last đến chỉ số First
Thủ tục hỗ trợ tìm kiếm không đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ Last đến chỉ số First
Câu 13: Lựa chọn định nghĩa về danh sách đúng nhất?
A. Danh sách là tập hợp các phân tử có kiểu dữ liệu xác định và giữachúng có một mối liên hệ nào đó
B. Số phần tử của danh sách gọi là chiều dài của danh sách
C. Một danh sách có chiều dài bằng 0 là một danh sách rỗng
D. Cả a, b, c đều đúng
Câu 14: Tìm mô tả đúng cho hàm sau:
int SC (int M[], int Len, int CM[])
{ for (int i = 0; i < Len; i++)
CM[i] = M[i];
return (Len);}
A. Hàm thực hiện việc sao chép nội dung màng CM có chiều dài Len về mảng M có cùng chiều dài. Hàm trả về chiều dài của mảng M sau khi sao chép
B. Hàm thực hiện việc sao chép nội dung mảng M có chiều dài Len -1 về mảng CM có cùng chiều dài. Hàm trả về chiều dài của mảng CM sau khi sao chép
C. Hàm thực hiện việc sao chép nội dung màng CM có chiều dài Len -1 về mảng M có cùng chiều dài. Hàm trả về chiều dài của măng M sau khi sao chép
D. Hàm thực hiện việc sao chép nội dung màng M có chiều dài Len về mảng CM có cùng chiều dài. Hàm trả về chiều dài của màng CM sau khi sao chép
Câu 15: 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
Câu a, b, c đúng
Câu 16: Đị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ận với nhau trong vùng nhớ
Câu hỏi: Đị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:
typedef struct Node
{ int ElementType;
Node * Next;
} pNode;
Trong đó, khai báo Node * Next; 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 địa chỉ vùng nhớ của phần từ trước đó trong danh sách liên kết đơn
Con trỏ trỏ tới địa chỉ vùng nhớ của phần tử đầu tiên trong danh sách liên kết đơn
Câu 1: Cấu trúc dữ liệu nào tương ứng với LIFO/FILO?
Queue
Linked List
Tree
Stack
Câu 1.1: Cấu trúc dữ liệu nào tương ứng với FIFO/LILO?
Queue
Linked List
Tree
Stack
Câu 2: Lựa chọn câu đúng nhất về danh sách liên kết đôi (Doubly Linked List):
A. Vùng liên kết của một phần tử trong danh sách liên đôi có 02 mối liên kết với 01 phần tử khác trong danh sách
B. Vùng liên kết của một 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 I
C. Vùng liên kết của một phần tử trong danh sách liên đôi có 02 mối liên kết với 02 trước và sau nó trong danh sách
D. Vùng liên kết của một 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
Cho cây biểu thức sau:
Chọn biểu thức tương ứng với cây
(2*(4+ (5+3)))
(4* (2+(5+ 3)))
(2* (3+ (5+4)))
(2* (5+ (4+3)))
Câu 12: Chọn định nghĩa đúng nhất về hàng đợi (Queue):
A. Hàng đợi còn được gọi là danh sách FILO và cấu trúc dữ liệu này còn được gọi cấu trúc FILO (First In Last Out)
B. Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần từ vào trong danh sách được thực hiện 1 đầu này và lấy 1 phần tử trong danh sách lại thực hiện bởi đầu kia
C. Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần tử hay hủy một phần tử trong danh sách được thực hiện 1 đầu
D. Hàng đợi phải là một danh sách liên kết đơn
Câu 14: Chọn định nghĩa đúng nhất đối với cây nhị phân tìm kiếm:
A. Cây nhị phân tìm kiếm là cây nhị phân có thành phần khóa của mọi nút lớn hơn thành phần khóa của tất cả các nút trong cây con trái của nó và nhỏ hơn thành phần khóa của tất cả các nút trong cây con phải của nó
B. Cây nhị phân tìm kiếm là cây nhị phân có thành phần khóa của mọi nút nhỏ hơn thành phần khóa của tất cả các nút trong cây con trái của nó và nhỏ hơn thành phần khóa của tất cả các nút trong cây con phải của nó
C. Cây nhị phân tìm kiếm là cây nhị phân có thành phần khỏa của mọi nút lớn hơn thành phần khóa của tất cả các nút trong cây con trái của nó và lớn hơn thành phần khóa của tất cả các nút trong cây con phải của nó,
D. Cây nhị phân tìm kiếm chính là cây nhị phân
Câu 1: Hãy cho biết quy tắc đúng của phép duyệt cây theo thứ tự sau/hậu tự trong các phương án sau?
A. 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
B. Duyệt gốc, cây trái, cây phải đồng thời theo thứ tự sau
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 gốc
D. 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
Câu 1: Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp chọn tăng dần (select sort)?
A. 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. 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
C. 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 cho đến phần tử cuối cùng
D. 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
Câu 2: Yếu tố nào sau đây để xây dựng nên một chương trình hoàn chỉnh?
A. Dữ liệu tốt, giải thuật đơn giản
B. Giải thuật có thời gian thực hiện nhanh nhất
C. Cấu trúc dữ liệu thích hợp, giải thuật xử lý hiệu quả
D. Cấu trúc dữ liệu tốt
Câu 2: Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp nổi bọt (bubble sort)?
A. 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. 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
C. 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
D. 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 cho đến phần tử cuối cùng
Câu 3: Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp chèn (insertion sort)?
A. 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. 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
C. 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 cho đến phần tử cuối cùng
D. Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần nhau, nếu phần tử nào nhỏ hơn được đứng vị trí trên
Câu 4: Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp nhanh (Quick sort)?
A. 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 cho đến phần tử cuối cùng
B. 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ếpnh u, nếu phần tử nào nhỏ hơn được đứng vị trí trên
C. 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
D. 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á)
Câu 4: Hãy chọn Câu trả lời đúng nhất về giải thuật?
A. Giải thuật hay còn gọi là thuật toán dùng để chỉ phương pháp hay cách thức giải quyết vấn đề ( bao gồm một dây các bước tính toán rõ ràng và chính xác)
B. Giải thuật là nòng cốt của chương trình
C. Giải thuật 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
D. Giải thuật cần có một hoặc nhiều dữ liệu ra (output), dữ liệu vào (input)
Câu 5: Hãy cho biết đâu là đặc trưng của thuật toán trong các phương án sau?
A. Mỗi thuật toán có bộ dữ liệu vào, ra tương ứng
B. Mỗi bước của thuật toán cần phải được mô tả một các chính xác
C. Thuật toán phải dừng lại sau một số hữu hạn các bước cần thực hiện
D. Tất cả các đặc trưng đã nêu
Câu 6: Hãy cho biết ý tưởng nào sau đây nói về tưởng phương pháp sắp xếp Trộn (Merge sort)?
A. 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á)
B. 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
C. 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 cho đến phần tử cuối cùng
D. 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
Câu 6: Dựa vào yếu tố nào sau đây để đánh giá thời gian thực hiện của giải thuật?
Thời gian khi chạy chương trình cụ thể
Tính xác định
Độ phức tạp tính toán của giải thuật
Tính dừng
Câu 7: Hãy cho biết phương án đúng của để sắp xếp theo thứ tự tăng dần của cấp thời gian thực hiện chương trình?
A. O(1), O(logn), O(n), O(nlogn)
B. O(1), O(nlogn), O(n), O(logn)
C. O(logn), O(n), O(nlogn), O(1)
D. O(nlogn), O(n), O(logn), O(1)
Câu 7: Cho bài toán: cho trước n là một số tự nhiên, tính n!. Chỉ ra trường hợp suy biến
với n = 0
với n = 1
với n =0 hoặc n = 1
Câu 8: Hãy cho biết Câu trả lời đúng nhất về đặc điểm của giải thuật đệ quy?
A. Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó
B. 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. 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
D. Tất cả các đáp án đều đúng
Câu 8: Hãy chọn định nghĩa đúng nhất về danh sách kiểu hàng đợi (Queue)?
A. 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 cuối hàng (rear) hay lối trước/đầu hàng (front). Phép loại bỏ không thực hiện được
B. 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)
C. 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
D. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung/thêm phần tử ở một đầu, gọi là lối sau/cuối hàng (rear) (rear) và phép loại/xóa bỏ phần tử được thực hiện ở đầu kia, gọi là lối trước/đầu hàng (front)
Câu 9: 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ỳ?
A. Chỉ việc xoá X, vì X không liên quan đến phần tử nào khác
B. 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
C. Không thể xoá X ra khỏi cây nhị phân tìm kiếm
D. 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
Câu 9: Trong bốn kiểu ký hiệu sau đây, ký hiệu nào biểu thị cho danh sách kiểu hàng đợi?
FIFO
LIFO
FILO
LOLO
Câu 10: Để thêm một đối tượng x bất kỳ vào Stack, ta dùng hàm nào sau đây?
TOP(x)
EMPTY(x)
PUSH(x)
POP(x)
Câu 11: Để loại bỏ một đối tượng ra khỏi Stack, ta dùng hàm nào sau đây?
FULL(x)
POP(x)
EMPTY(x)
PUSH(x)
Câu 12: 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/đầu hàng của Q, R là con trò trỏ tới lối sau/cuối hàng của Q. Điều kiện F=R=0 nghĩa là gì trong các phương án sau?
A. Queue tràn
B. Queue rỗng
C. Kiểm tra chỉ số trước và chỉ số sau của Queue có bằng nhau hay không
D. Đặt phần tử đầu và phần từ cuối của Queue bằng 0
Câu 12: Hãy cho biết tính chất nào sau đây là của cây nhị phân tìm kiếm?
A. Cây nhị phân mà mỗi nút trong cây đều thoả tính chất: giá trị của nút cha lớn hơn giá trị của hai nút con
B. Là cây nhị phân đầy đủ
C. Cây nhị phân thoả tính chất heap
D. Cây nhị phân mà mỗi nút trong cây đều thoả 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âu 13: Trong lưu trữ dữ liệu kiểu Queue (Q), giả sử F là con trỏ trỏ tới lối trước/đầu hàng của Q, R là con trỏ trò tới lối sau/cuối hàng của Q. Khi thêm một phần tử vào Queue, thì R và F thay đổi thế nào trong các phương án sau?
A. F không thay đổi, R=R+1
B. F=F+1, R không thay đổi
C. F không thay đổi, R=R-1
D. F=F-1, R không thay đổi
Câu 14: Trong lưu trữ dữ liệu kiểu Queue (Q), giả sử F là con trở trò tới lối trước đầu hàng của Q, R là con trỏ trò tới lối sau cuối hàng của Q. Khi loại bỏ/xóa một phần tử vào Queue, thì R và F thay đổi thế nào trong các phương án sau?
A. F=F+1, R không thay đổi
B. F không thay đổi, R=R+1
C. F không thay đổi, R=R-1
D. F=F-1, R không thay đổi
Câu 19: Hãy cho biết quy tắc đúng của phép duyệt cây theo thứ tự trước/tiền tự trong các phương án sau?
A. Duyệt cây con trái theo thứ tự trước; Duyệt cây con phải theo thứ tự trước; Duyệt gốc T
B. Duyệ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
C. Duyệt gốc, cây trái, cây phải đồng thời theo thứ tự trước
D. Duyệt cây con trái theo thứ tự trước; Duyệt gốc, Duyệt cây con phảitheo thứ tự trước
Câu 19: 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?
A. POP(72), POP(23), POP(72)
B. POP(72), POP(23), PUSH(72)
C. POP(23), PUSH(23), POP(72)
D. POP(23), PUSH(72), POP(72)
Câu 20: Hãy cho biết quy tắc đúng của phép duyệt cây theo thứ tự giữa/trung tự trong các phương án sau?
A. Duyệt gốc, cây trái, cây phải đồng thời theo thứ tự giữa
B. Duyệt 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
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; Duyệt gốc
D. Duyệt cây con trái theo thứ tự giữa; Duyệt gốc: Duyệt cây con phải theo thứ tự giữa
