Kiểm tra kiến thức về giải thuật đệ quy và danh sách tuyến tính

Giải thuật đệ quy là gì?

• Nếu lời giải của 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 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

• Nếu lời giải của 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 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

Trường hợp suy biến xảy ra khi nào trong giải thuật tìm từ trong từ điển?

• Khi xác định từ cần tìm nằm ở nửa trước của từ đIển

• Sau một vàI lần tách đôI từ điển

• Khi xác định từ cần tìm nằm ở nửa sau của từ đIún

• Sau nhiều lần tách đôi từ điển chỉ còn một trang

Một giải thuật đệ quy xảy ra trường hợp suy biến khi nào?

• Sau một số lần có lời gọi đệ quy bài toán còn lại sẽ được giải quyết theo một cách khác

• Sau một số lần có lời gọi đệ quy.

• Khi kết quả của giải thuật bằng giá trị 0

• Khi không thể giảI quyết được giải thuật.

Đặc điểm nào của giải thuật viết bằng đệ quy là sai trong các đặc điểm sau?

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

• Tất cả đều sai

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

• Sau một số lần gọi đệ quy bài toán có giá trị bằng 0

Có Hàm đệ qui sau: Function Factorial(n) Begin if n=0 then Factorial:=1 else Factorial := n*Factorial(n-1); End; Sau mỗi lần gọi đệ quy thì giá trị của n là:

• N=1

• N=0

• Tăng lên 1

• Giảm đi 1

Có Hàm đệ qui sau: Function Factorial(n) Begin if n=0 then Factorial:=1 else Factorial := n*Factorial(n-1); End; Trường hợp suy biến xảy ra khi nào?

• Factorial(n-1)=1

• Factorial(n-1)

• Factorial(n) = 0

• Factorial(0) = 1

Có 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=3

• 2

• 9

• 8

• 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ứ 5 sẽ có bao nhiêu cặp?

• 5 cặp

• 10 cặp

• 9 cặp

• 12 cặp

Cho giải thuật đệ quy sau: Function F(n) Begin if n<=2 then F:=1 else F(n) := F(n-2) + F(n-1); End; Trường hợp suy biến xảy ra khi nào?

• F(1) = 0 và F(2) = 1

• F(1) = 1

• F(2) = 1

• F(1) = 1 và F(2) = 1

Cho giải thuật đệ quy sau: Function F(n:integer):integer; Begin if n<=2 then F:=1 else F(n) := F(n-2) + F(n-1); End; Khi n=4 kết quả của bài toán trên là:

• = 10

• = 8

• = 3

• = 11