ÔN TẬP DSA

10.
A hardware vendor, XYZ Corp., claims that their latest computer runs 100 times faster than
their competitor AMC Inc.’s computer. If the AMC computer can execute a program with input
size n in one hour, what input size can XYZ’s computer execute in one hour for each algorithm
with the following growth rate equations of s?
(a) 10n
(b) 100n
(c) n
(d) 10000n
Answer:
12. The Rearrange function takes as its parameter a pointer head that contains the address of the
first element of a singly linked list. This function rearranges the elements in some way.
struct Node{
int data;
Node* next;
};
void Rearrange(Node* head){
Node *p, *q;
int temp;
if (!head || !head->next)
return;
p = head;
q = head->next;
while(q){
temp = p->data;
p->data = q->data;
 q->data = temp;
p = q->next;
if (p)
q = p->next;
else
q = 0;
}
}
We pass to this function the pointer head of the following singly linked list:
1→2→3→4→5→6→7
What will be the contents of the list after the function finishes execution?
(a) 1 → 2 → 3 → 4 → 5 → 6 → 7
(b) 2 → 1 → 4 → 3 → 6 → 5 → 7
(c) 1 → 3 → 2 → 5 → 4 → 7 → 6
(d) 2 → 3 → 4 → 5 → 6 → 7 → 1
13. Suppose that:
(a) An array A[m] is used to implement a circular queue.
(b) The positions of the front and rear are denoted by the indices front and rear, respectively.
How is the number of elements currently in the queue calculated?
(a) (rear - front + m) % m - answer
(b) (rear - front + 1) % m
(c) rear - front
(d) (rear - rear + m) % m + 1
14. Criteria: The time complexity in the best case is O(n). Which of the following options
satisfies this criterion?
(a) Straight-Insertion-Sort, Selection-Sort
(b) Quick-Sort
(c) Quick-Sort, Merge-Sort
(d) Bubble-Sort, Quick-Sort – this is the answer
17. Given the function foo as follows:
void foo(int arr[], int n) {
 for (int i = n - 2; i > 0; i--) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) swap(arr[i], arr[j]);
}
}
}
What is the time complexity of foo among the options below?
(a) O (log n)
(b) O(n²) - is the answer
(c) O(n)
(d) O (n log n)

20. A sorting algorithm is called stable when:

(a) It maintains the order of elements that are equal.
(b) The time complexity of the algorithm is O(n²).
(c) It must be implemented using the divide-and-conquer technique.
(d) The space complexity of the algorithm is O(n).

21. Given the declaration of an element in a singly linked list as follows:

template <typename T>
class Link {
public:
T element;
Link* next;
Link(const T& ele, Link* nextval = nullptr) :
element(ele), next(nextval) {}
};
Assume the variable tail is linked to the last element of a singly linked list containing n elements
of type Link<T>. Choose the appropriate values to fill in the blanks (1) and (2) in the append
function below to append a new element containing the value ele to the end of the list.
void append(const T& ele) {
__(1)__ = new Link<T>(ele);
__(2)__;
}
The blanks (1) and (2) are respectively:
(a) tail = nullptr
(b) tail->next, nullptr
(c) tail->next, tail->next = tail
(d) tail->next, tail = tail->next

22. Given the integer array [9, 8, 4, 4, 8, 1, 2] Use the "Bubble Sort" algorithm (from right to
left) to sort the array in descending order. The cost of swapping two numbers is 3 coins, and
ignoring other costs. How much will it cost (in terms of swaps) to place the number 1 in its
correct position (the position in the sorted array)?
(a) 5
(b) 20
(c) 25
(d) 10

25. Input string: "ESC**#03*#"

In the following process, a Queue is used to store data.
Process: Read each character (from left to right) from the input string, called ch. If ch is '*', you
pop (dequeue) an item from the queue and print it to the screen. If ch is '#', you peek an item
from the queue and print it to the screen. If ch is neither '' nor '#', you push (enqueue) it onto the
queue.
Which of the following strings will be displayed on the screen?
(a) ESC03
(b) ESCC0
 (c) ESC00
(d) All other options are incorrect.
26. The func1 function takes as its parameter a pointer head that contains the address of
the first element of a singly linked list.
Code:
struct Node {
int data;
Node* next;
};
int func1(Node* head){
Node* p1 = head;
Node* p2 = head;
while(p1->next != 0 && p1->next->next != 0){
p1 = p1->next->next;
p2 = p2->next;
}
return p2->data;
}
We pass to the function the pointer head of the following singly linked list:
rust
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
Ans: 4
27. Given a list implemented using an array consisting of integers sorted in ascending order
as follows:
[2, 3, 5, 7, 11, 23, 50]
To insert the value 3 into the array while maintaining the correct order (after insertion), how
many elements need to be shifted?
(a) 2
(b) 3
(c) 4
(d) 1
Q28-29/
In the next two questions, assume that XArrayList and XDLinkedList are classes supporting
the List interface and are implemented using arrays and doubly linked lists, respectively. The get
method returns the element at the index passed as its parameter. The size method returns the
number of elements in the list, and its time complexity is O(1).
Consider the following code snippet:
for(int i=0; i<list.size(); i++)
cout << list.get(i);
28. If list in the code snippet is of type XArrayList, which of the following is the time
complexity of the code? (where n is the size of the list)
(a) O(n) – answer
(b) O(n²)
(c) O(1)
(d) O(log n)

29. If list in the code snippet is of type DLinkedList, which of the following is the time
complexity of the code? (where n is the size of the list)
(a) O(n)
(b) O(n²) - answer
(c) O(1)
(d) O(log n)
30. In the bracket checking problem, bracket sequences including opening and closing
brackets are checked. Given the input string: "(()())" and assuming a stack is used, what is
the maximum number of elements in the stack during processing?
(a) 2 - answer
(b) 3
(c) 1
(d) 4
31. How can you check if a binary tree is a binary search tree?
(a) Perform a preorder traversal and check if the result is sorted
(b) Perform an inorder traversal and check if the result is sorted
(c) Perform a postorder traversal and check if the result is sorted
(d) Perform a breadth-first traversal and check if the result is sorted

38. Select the correct statement when implementing a list using an array:
(a) Implementing a list using an array is suitable for lists that frequently involve adding and
removing elements.
(b) Implementing a list using an array should only be applied to lists with many elements.
(c) There is no need to shift existing elements when adding a new element to the beginning of the
list.
(d) There is no need to shift existing elements when adding a new element to the end of the list.
answer
D
39. Choose the FALSE statement from the following:
(a) The "List ADT" can be defined in multiple ways.
(b) A Sorted-list is categorized as a restricted list.
(c) An element can be added to or removed from a list.
(d) The "List ADT" can be implemented by an abstract class.
Answer: B

40. In a singly linked list, element A is said to be before element B if element B is after
element A. When element A contains a link to element B, the algorithm for deleting an
element x in a singly linked list, with time complexity O(1), requires the input to be a link to
which of the following?
(a) The element to be deleted
(b) The element after the element to be deleted
(c) The first element of the list
(d) The element before the element to be deleted