Câu hỏi trắc nghiệm kiểm tra môn Cấu trúc dữ liệu và giải thuật | Trường đại học kinh doanh và công nghệ Hà Nội

lOMoAR cPSD| 45469857 KIỂM TRA
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Câu 1: Giải thuật đệ quy là:
a. “Trong giải thuật đệ quy có lời gọi tới chính nó nhưng với phạm vi lớn hơn”
b. “Trong giải thuật đệ quy có lời gọi tới một giải thuật khác đã biết kết quả”
c. “Trong giải thuật đệ quy có lời gọi tới chính nó nhưng với phạm vi nhỏ hơn”
d. “Trong giải thuật đệ quy có lời gọi tới chính nó”
Câu 2: Đặc điểm của thủ tục đệ quy:
a. “Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó”
b. “Sau mỗi lần 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ả đều đúng”
Câu 3: Cho hàm đệ qui sau: Function Factorial(n) Begin if n=0 then Factorial:=1
else Factorial := n*Factorial(n-1); End;
Dòng lệnh if n=0 then Factorial:=1 là:
a. “Điều kiện không thực hiện đệ quy” b. “Lặp vô hạn”
c. “Điều kiện dừng đệ quy” d. “Lặp 1 lần”
Câu 4: Cho hàm đệ qui sau: Function Factorial(n)
Begin if n=0 then Factorial:=1
else Factorial := n*Factorial(n-1); _ End;
Kết quả bằng bao nhiêu khi n=6 a. “608” b. “5040” c. “ 120” d. “ 720”
Câu 5: Hàm đệ qui cho kết quả thế nào? Function Factorial(n) Begin
Factorial:= n*Factorial(n-1); End; a. “Tính giai thừa n”
b. “Chương trình báo lỗi” lOMoAR cPSD| 45469857
c. “Lặp vô hạn vì không có điều kiện dừng”
d. “ Tính số cặp thỏ sau n tháng.”
Câu 6: Dãy số Fibonacci bắt nguồn từ bài toán cổ về việc sinh sản của các cặp thỏ.
Bài toán được đặt ra như sau:
Các con thỏ không bao giờ chết. Hai tháng sau khi ra đời một cặp thỏ mới sẽ sinh ra
một cặp thỏ con. Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được
một cặp con mới. Giả sử bắt đầu từ một cặp thỏ mới ra đời thì đến tháng thứ 12 sẽ có bao nhiêu cặp? a. “34” b. “55” c. “89” d. “144”
Câu 7: Giải thuật đệ quy của bài toán Tháp Hà Nội như sau: Procedure Chuyen(n, A, B, C)
Begin if n=1 then chuyển đĩa từ A sang C
else begin call Chuyen(n-1, A, C, B); call Chuyen(1, A, B, C); call Chuyen(n-1, B, A, C) ; end; End;
Khi n=5 có bao nhiêu bước chuyển? a. “7 bước ” b. “31 bước ” c. “9 bước ” d. “15 bước ”
Câu 8: 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à phương án nào sau đây a. i+1 b. i-1 c. 2*i d. 2*i + 1
Câu 9: 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à phương án nào sau đây a. i+1 b. i-1 c. 2*i d. 2*i + 1
Câu 10: Trong biểu diễn dữ liệu dưới dạng cây, cấp của cây là phương án nào sau đây
a. Là cấp cao nhất của nút lá
b. Là cấp cao nhất của nút gốc
c. Là cấp cao nhất của một nút trên cây
d. Là tổng số nút trên cây 2 lOMoAR cPSD| 45469857
Câu 11: Trong biểu diễn dữ liệu dưới dạng cây, nút có cấp bằng 0 là phương án nào sau đây a. Là nút lá b. Là nút gốc c. Là nút trung gian
d. Không có đáp án đúng
Câu 12: 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à
7 thì vị trí tương ứng của nút con trái và nút con phải là phương án nào sau đây a. 14 và 15 b. 13 và 14 c. 12 và 13 d. 16 và 17
Câu 13: Khi lưu trữ cây nhị phân dưới dạng mảng, phần tử ở vị trí số 17 trong mảng
đóng vai trò gì trong các phương án sau đây a. Là nút con trái của nút có vị trí thứ 8
b. Là nút con phải của nút có vị trí thứ 8
c. Là nút con phải của nút có vị trí thứ 7
d. Là nút con trái của nút có vị trí thứ 6
Câu 14: Khi lưu trữ cây nhị phân dưới dạng mảng, phần tử ở vị trí số 18 và 19 trong
mảng đóng vai trò gì trong các phương án sau đây
a. Là nút con trái và con phải của nút có vị trí thứ 9
b. Là nút con phải và con trái của nút có vị trí thứ 9
c. Là nút con phải và con trái của nút có vị trí thứ 8
d. Là nút con trái và con phải của nút có vị trí thứ 8
Câu 15: Cho cây nhị phân T có chiều cao là 5. Số nút tối đa của cây là phương án nào sau đây a. 25 b. 30 c. 32 d. 31
Câu 16: Nếu biểu diễn cây nhị phân có chiều cao 5 bằng phương pháp lưu trữ kế tiếp
thì phải dự trự bao nhiêu ô nhớ (mỗi nút trên cây cần 1 ô nhớ) a. 25 b. 30 c. 31 d. 35
Câu 17: Cho cây nhị phân T có chiều cao là 5, trên cây có 20 nút. Nếu biểu diễn cây
nhị phân bằng phương pháp lưu trữ kế tiếp thì lãng phí bao nhiêu ô nhớ lưu trữ giá trị
rỗng (mỗi nút trên cây chiếm 1 ô nhớ) a. 8 b. 9 c. 10 d. 11 lOMoAR cPSD| 45469857
Câu 18: Trong biểu diễn dữ liệu dưới dạng cây, khái niệm nào sau đây là chiều cao của cây a. Mức của nút gốc
b. Mức nhỏ nhất của một nút trên cây
c. Mức của một nút bất kỳ trên cây
d. Mức lớn nhất của một nút trên cây
Câu 19: Trong biểu diễn dữ liệu dưới dạng cây, nút lá có đặc điểm là phương án nào sau đây: a. Bậc bằng 1 b. Bậc khác 0 c. Bậc bằng 0 d. Bậc bằng 2
Câu 20: Trong biểu diễn dữ liệu dưới dạng cây, khái niệm nào sau đây là của nhị phân tìm kiếm
a. Cây nhị mà mỗi nút trên cây đều thỏa mãn tính chất: Giá trị của nút cha lớn hơn giá
trị của các nút trên cây con trái và nhỏ hơn giá trị của các nút trên cây con phải b. Cây
nhị phân thỏa mãn tính chất của đống c.
Cây nhị mà mỗi nút trên cây đều thỏa mãn tinh chất: Giá trị của nút cha lớn hơn giá trị hai nút con d.
Cây nhị mà mỗi nút trên cây đều thỏa món tính chất: Giá trị của nút cha nhỏ hơn
giá trị của các nút trên cây con trái và lớn hơn giá trị của các nút trên cây con phải Câu 21: Cho dãy số: 11 57 46 65 40 49 8 63 16 14
Chiều cao của cây nhị phân tương ứng với dãy số trên là phương án nào sau đây a. 3 b. 4 c. 5 d. 6 Câu 22: Cho dãy số: 11 57 46 65 40 49 8 63 16 14
Chiều cao của cây nhị phân tìm kiếm tương ứng với dãy số trên là phương án nào sau đây a. 3 b. 4 c. 5 d. 6 Câu 23: Cho dãy số: 11 57 46 65 40 49 8 63 16 14
Trên cây nhị phân tìm kiếm tương ứng dãy số trên để tìm phần tử 49 trên cây cần thực
hiện bao nhiêu phép so sánh. a. 4 b. 6 c. 5 d. 7 4 lOMoAR cPSD| 45469857 Câu 24: Cho dãy số: 11 57 46 65 40 49 8 63 16 14
Trên cây nhị phân tìm kiếm tương ứng dãy số trên để chèn thêm phần tử 20 trên cây
cần thực hiện bao nhiêu phép so sánh. a. 6 b. 4 c. 3 d. 5 Câu 25: Cho dãy số: 11 57 46 65 40 49 8 63 16 14
Áp dụng giải thuật sắp xếp vun đống sắp xếp dãy số trên theo thứ tự tăng dần. Kết quả
thu được dãy số sau lần sắp xếp thứ nhất là phương án nào sau đây a. 65-63-49-57-40- 46-9-11-16-14
b. 14-63-49-57-40-46-9-11-16-65
c. 14-57-49-16-40-46-9-11-63-65
d. 63-57-49-16-40-46-9-11-14-65 Câu 26: Cho dãy số: 11 57 46 65 40 49 8 63 16 14
Áp dụng giải thuật sắp xếp vun đống sắp xếp dãy số trên theo thứ tự tăng dần. Kết quả
thu được dãy số sau lần sắp xếp thứ hai là phương án nào sau đây a. 49-40-46-16-14- 11-8-57-63-65
b. 14-63-49-57-40-46-9-11-16-65
c. 14-57-49-16-40-46-9-11-63-65
d. 63-57-49-16-40-46-9-11-14-65 Câu 27: Cho dãy số: 11 57 46 65 40 49 8 63 16 14
Áp dụng giải thuật sắp xếp vun đống sắp xếp dãy số trên theo thứ tự tăng dần. Kết quả
thu được dãy số sau lần sắp xếp thứ ba là phương án nào sau đây a. 57-40-49-16-14- 46-9-11-63-65
b. 11-40-49-16-14-46-9-57-63-65
c. 14-57-49-16-40-46-9-11-63-65
d. 8-40-46-16-14-11-49-57-63-65 Câu 28: Cho dãy số: 11 57 46 65 40 49 8 63 16 14
Áp dụng giải thuật sắp xếp vun đống sắp xếp dãy số trên theo thứ tự tăng dần. Kết quả
thu được dãy số sau lần sắp xếp thứ tư là phương án nào sau đây
a. 57-40-49-16-14-46-9-11-63-65
b. 11-40-49-16-14-46-9-57-63-65
c. 49-40-46-16-14-11-8-57-63-65
d. 8-40-46-16-14-11-49-57-63-65 Câu 29: Cho dãy số: 11 57 46 65 40 49 8 63 16 14
Áp dụng giải thuật sắp xếp vun đống sắp xếp dãy số trên theo thứ tự tăng dần. Kết quả
thu được dãy số sau lần sắp xếp thứ năm là phương án nào sau đây a. 8-40-11-16-14- 46-49-57-63-65
b. 11-40-49-16-14-46-9-57-63-65
c. 46-40-11-16-14-8-49-57-63-65 lOMoAR cPSD| 45469857
d. 8-40-46-16-14-11-49-57-63-65 Câu 30: Cho dãy số: 11 57 46 65 40 49 8 63 16 14
Áp dụng giải thuật sắp xếp vun đống sắp xếp dãy số trên theo thứ tự tăng dần. Kết quả
thu được dãy số sau lần sắp xếp thứ sáu là phương án nào sau đây a. 8-40-11-16-14- 46-49-57-63-65
b. 40-16-11-8-14-46-49-57-63-65
c. 14-16-11-8-40-46-49-57-63-65
d. 8-14-11-16-40-46-49-57-63-65 1 C 2 D 3 C 4 D 5 C 6 A 7 D 8 C 9 D 10 C 11 A 12 A 13 B 14 A 15 C 16 B 17 B 18 D 19 C 20 A 21 C 22 B 23 C 24 C 25 C 26 B 27 A 28 C 29 A 30 D 6