Đề thi cuối kỳ Cấu trúc dữ liệu và giải thuật (có đáp án)

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

}

Câu 6: (2.5 điểm)

Cho một danh sách liên kết đơn, tạm gọi tên là InList. Tạo một danh sách lien kết đơn, tạm gọi là OutList cùng kích thước với InList với giá trị của các Node trong OutList tại vị trí i sẽ là tổng của các node từ vị trí 0 đến i – 1 trong InList. (2.5đ)

Ví dụ: InList: 1, 34, 2, 6, 8, 5

🡪 OutList: 1, 35, 37, 43, 51, 56.

Trả lời

void buildOutList (LinkedList inList, LinkedList &outList){

if(inList == null)

return;

Node* p = inList.pHead;

initList(outList);

int data = 0;

while (p!=null){

data = data + p->info;

Node*q = createNode(data);

addLast(outList,q);

}

Node* createNode (int data){

Node* node = new Node();

node->info = data;

node->pNext = null;

return node;

}

void initList (LinkedList &list){

if(list==null)

list.pHead = list.pTail = NULL;

}

void addLast (LinkedList &list, Node* p ){

if(IsEmptyList(list))

list.pHead = list.pTail = p;

else{

list.pTail->pNext = p;

list.pTail = p;

}

}