ĐỀ THI VÀ ĐÁP ÁN MÔN CẤU TRÚC DỮ LIỆU & GIẢI THUẬT #1

ĐỀ THI VÀ ĐÁP ÁN MÔN CẤU TRÚC DỮ LIỆU & GIẢI THUẬT #1

Câu 1: (1 điểm)
     Cho biết kết quả sau khi thực hiện những thao tác sau trên stack x chứa các kí tự. (1đ)x.push('h');
x.push('e');
x.push('l');
cout << x.top();
x.pop();
cout << x.top();
x.pop(); x.push('l');
x.push('o');
cout << x.top();
x.pop();
cout << x.top();
x.pop();
cout << x.top();
x.pop();

     Trả lời: leolh

Câu 2: (1 điểm)
Giả sử bạn có 1 cây lưu các giá trị trong khoảng từ 1 đến 100 và bạn đang muốn tìm giá trị 45. Thứ tự nào sau đây có thể là thứ tự các node được kiểm tra.
a/ 5, 2, 1, 10, 39, 34, 77, 63
b/ 1, 2, 3, 4, 5, 6, 7, 8
c/ 9, 8, 63, 0, 4, 3, 2, 1
d/ 8, 7, 6, 5, 4, 3, 2, 1
e/ 50, 25, 26, 27, 40, 44, 42

Trả lời: B

Câu 3: ( 1.5 điểm)
Sử dụng giải thuật QuickSort để sắp xếp danh sách đặc như sau:
38, 81, 22, 48, 13, 69, 93, 14, 45

Trả lời:
Pivot = 13
Hoán vị A(0) và A(4)
13, 81, 22, 48, 38, 69, 93, 14, 45
Pivot = 38
1/ Hoán vị A(1) và A(7)
13, 14, 22, 48, 38, 69, 93, 81, 45
2/ Hoán vị A(3) và A(4)
13, 14, 22, 38, 48, 69, 93, 81, 45

Pivot = 93
1/ Hoán vị A(6) và A(8)
13, 14, 22, 38, 48, 69, 45, 81, 93

Pivot = 69
1/ Hoán vị A(5) và A(6)
13, 14, 22, 38, 48, 45, 69, 81, 93

Pivot = 48
1/ Hoán vị A(4) và A(5)
13, 14, 22, 38, 45, 48, 69, 81, 93

Câu 4: (1.5 điểm)

Số nguyên tố Palindrome hay còn gọi là số xuôi ngược nguyên tố. Nghĩa là, số này là số nguyên tố, và nếu viết xuôi hay ngược thì nó vẫn là chính nó. Ví dụ: 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, v.v… Viết chương trình kiểm tra số nguyên N nhập vào có phải là số nguyên tố Palindrome hay không?

Trả lời:

bool isSymetric(int n){

string s = std::to_string(n);

int len = s.length();

for (int i = 0; i<= len/2;i++){

       if(s[i] != s[len-1-i])

            return false;

}

return true;

}

bool isPrime(int n){

int i ;

if(n<=1)

       return false;

i = 2;

while (i<n/2 && n % i !=0)

       i++;

if(i<n/2)

       return false;

return true;

}

bool isPalindrome(int n){

if(isSymetric(n) && isPrime(n))

       return true;

return false;

}
Câu 5: (2.5 điểm)

Giả sử chúng ta đã có sẵn các hàm để xây dựng cây nhị phân tìm kiếm. Sử dụng lại chương trình con kiểm tra số n có phải là số Palindrome hay không ở câu 4, viết chương trình đếm số lượng số nguyên tố Palindrome trên cây nhị phân tìm kiếm, với tham số đầu vào là một cây nhị phân tìm kiếm khác rỗng.

Trả lời:

int calculatePalindromeNumbers(Node* root){

if(root == null)

       return 0;

if(isPalindrome(root->info)==true)

       return 1 + calculatePalindromeNumbers(root à pLeft)

+ calculatePalindromeNumbers(rootà pRight);

return calculatePalindromeNumbers(root à pLeft)

+ calculatePalindromeNumbers(rootà pRight);

===============================================

Tải full file docx tại đây:

===============================

Baca juga