I2206 E – INFO205 Final 2022 - 2023

Friday 6 July 2023

Data Structures Duration 90 minutes
Dr. Zein Al Abidin IBRAHIM

Question I: Multiple Choices

1. In a max-heap, which of the following is correct?
a. The value of a node is less than all its children b. The value of a node is greater than all its children
c. The Value of a node is greater than the ones in the d. None of the choices
left subtree and less than the ones in the right subtree

2. In a heap, the index of the left child of an element located at index 55 is:
a. 27 b. 110
c. 111 d. 112

3. The most efficient implementation of a heap is:

a. Static b. Dynamic
c. Both of them d. None of them

4. Among the following sorting algorithms which one is the best (time and space) in sorting an array of
100 million elements?
a. Quick Sort b. Insertion Sort
c. Bubble Sort d. Selection Sort

5. The complexity of finding an element in a binary search tree is ?

a. O(n2) b. O(n)
c. O(log(n)) d. O(1)

6. _____ is a collision-resolution scheme that searches the hash table sequentially, starting from the original
location specified by the hash function, for an unoccupied location.
a. Linear probing b. Open addressing
c. Quadratic probing d. Double hashing

7. The load factor of a table is calculated as follows:

a. table size + current number of table items b. table size – current number of table items
c. current number of table items / table size d. current number of table items * table size

8. Which of the following statement(s) is TRUE?

a- A hash function takes a message of arbitrary length and generates a fixed length code.
b-A hash function takes a message of fixed length and generates a code of variable length.
c-A hash function may give the same hash value for distinct messages.
a. b and c b. a and b
c. a and c d. All of them

9. What is the complexity of adding an element in a heap tree.

a. O(1) b. O(log(n))
c. O(n) d. O(n2)

10. Which of the following represents a valid binary min heap:

a. 8 10 12 25 14 17 b. 12 10 8 25 14 17
c. 25 17 14 12 10 8 d. 14 17 25 10 12 8

11. Merge sort algorithm uses which of the following method to implement sorting?
a. Selection b. Merging
c. Partitioning d. Splitting

Page 1/10
12. One difference between a queue and a stack is:
a. Queues require linked lists, but stacks do not. b. Stacks require linked lists, but queues do not.
c. Stacks use two ends of the structure, queues use d. Queues use two ends of the structure; stacks use
only one. only one.

13. Which of the following traversals prints the data in ascending order in a binary tree?
a. In-order traversal b. Post-order traversal
c. Pre-order traversal d. Level-order traversal
e. All of them f. None of them

14. Out of the following, what is the most desirable we are waiting from a hash function?
a. it must occupy less space b. it must cause less collisions
c. it must cause more collisions d. it must be easy to implement

15. Which of the following is a linear data structure?

a. Binary Tree b. Array
c. Heap Tree d. Graph

16. What is the average time complexity of searching an element in a binary search tree?
a. O(1) b. O(log(n))
c. O(n) d. O(sqrt(n))

17. Which of the following represents the post-order traversal of a Binary Tree?
a. Right -> Root -> Left b. Left -> Root -> Right
c. Left -> Right -> Root d. Right -> Left -> Root

18. What is a hash function?

a. A function to create the array b. A function to allocate memory for keys
c. A function to compute the location of the key in the d. A function to compute the location of the values
array in the array

19. Which data structure is the best for implementing a priority queue?
a. Array b. Graph
c. Linked List d. Heap

20. Given the following two trees. Fill in the pre-order traversal of the left tree and the post-order traversal
of the right one.

Pre-order (left tree):

Post-order (right tree):

21. Which data structure is used during recursion?

a. Stack b. Queue
c. Tree d. None of them

22. Which of the following is not true about stacks?

a. Top of the stack contains the last inserted element b. Arrays can be used to implement the stack
c. Elements are stored in a sequential manner d. Stack follows FIFO

Page 2/10
23. What is the worst case complexity of searching an element in a hash table if we use one of the open
addressing method for collision resolution?
a. O(n) b. O(log(n))
c. O(1) d. O(sqrt(n))

24. Which of these is not a good application of linked list?

a. Random Access of elements b. To implement non-binary trees
c. To implement file systems d. For separate chaining in hash-tables

25. A hash table of length 14 is shown below. The following keys were inserted in the order from left to
right [3, 6, 7, 8, 42, 12, 28, 14, 20] into the table. Fill in the keys in the appropriate index if Linear
Probing method is used.
0 1 2 3 4 5 6 7 8 9 10 11 12 13

26. A hash table of length 14 is shown below. The following keys were inserted in the order from left to
right [31, 34, 20, 36, 22, 48, 17, 23, 9] into the table. Select the keys in the appropriate index if Quadratic
Probing method is used.
0 1 2 3 4 5 6 7 8 9 10 11 12 13

27. Fill in the table below a min-based heap tree (implemented as an array) after the following data is
inserted into it (from left to right): [48, 84, 69, 5, 39, 56, 57, 90, 11, 29, 62, 95]
0 1 2 3 4 5 6 7 8 9 10 11

28. If we use the open addressing resolution of collision method in hashing, fill in the appropriate
complexity for each of the operations in the table below:
ACTIVITY BEST CASE AVERAGE CASE WORST CASE
Searching
Insertion
Deletion
Space Complexity

29. From which sequence of numbers among the below is made the
following binary search tree:

a. 8, 3, 10, 6, 4, 14, 7, 13, 1

b. 8, 3, 6, 10, 14, 4, 7, 1, 13
c. 8, 10, 3, 1, 6, 14, 13, 7, 4
d. None of them
e. All of them
30. Given a binary heap of n elements where you are asked to insert n more elements. The total time
required for this operation is:
a. O(n) b. O(log(n))
c. O(nlog(n)) d. O(n2)

31. Given a full binary tree of height H, what is the number of nodes in such tree? Recall that a full binary
tree is a type of binary tree in which every node has either 0 or 2 child nodes.
a. 2H + 1 b. 2H+1 – 1
c. 2H+1 d. 2H-1 + 1

32. Given a sorted array in ascending order of n elements that we have filled from left to right into a binary
search tree, what is the worst-case complexity of searching an element in the array and the tree
respectively.
a. Array: O(log(n)), Tree: O(log(n)) b. Array: O(log(n)), Tree: O(n)
c. Array: O(n), Tree: O(log(n)) d. Array: O(n), Tree: O(n)

Page 3/10
33. What is the complexity of the following piece of code? Prove your answer in the box below.
for (int x = 1; x < n*n; x = x * 2)
value += (int) [Link](x,2);
a. Quadratic b. Exponential
c. Logarithmic d. Linear

34. What is the complexity of the following piece of code? Prove that in the box below.
int mysterious (int n) {
if (n == 0) return 0;
else return mysterious (n – 1) + mysterious (n – 1) + mysterious (n – 1);
}
a. Constant b. Logarithmic
c. Linear d. Exponential

35. What is the complexity of the following piece of code? Prove that in the box below.
int f(int n) {
int s = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j = j * 2)
sum += i + j;
return s;
}
a. O(n) b. O(log(n))
c. O(nlog(n)) d. O(n2)

Page 4/10
36. What is the complexity of the following piece of code? Prove that in the box below.
int fabilous(int n) {
if (n <= 0)
return 0;
return fabilous (n / 2) + fabilous (n / 2) + n;
}
a. O(n) b. O(log(n))
c. O(nlog(n)) d. O(n2)

37. Consider the following recurrence function. What is the time complexity of calculating T(n)? Prove.

a. O(n) b. O(log(n))
c. O(log(log(n))) d. O(sqrt(n))

Page 5/10
38. How can an algorithm be described in which the work it does grows as a function of the square of the
problem size?
a. Logarithmic b. Linear
c. Quadratic d. Exponential

39. Given the content of the array [34, 36, 23, 22, -5, 31, -1, -12, 48, 20, 17, -8]. Suppose we applied two
iterations of the quicksort algorithm in which the pivot (key) is always chosen as the first one, fill in the
resulted array. In the second iteration, apply on the two sub-arrays
Iteration 0 1 2 3 4 5 6 7 8 9 10 11
1
2

40. Given the content of the array [34, 36, 23, 22, -5, 31, -1, -12, 48, 20, 17, -8]. Suppose we applied three
iterations of the bubble sort algorithm, fill in the resulted array.
Iteration 0 1 2 3 4 5 6 7 8 9 10 11
1
2
3

Question II: Binary Tree

Given the following structure representing a binary tree node:

typedef struct BTNode{
element data;
struct BTNode *left, *right;
} BTNode;

1. Complete the following recursive function aiming to print the values in a BST that are in the range [a,
b].

typedef struct BTNode{

element data;
struct BTNode *left, *right;
} BTNode;
void printRange(BTNode *root, int a, int b) {
if (root == NULL)
return;
//Complete code here

Page 6/10
2. Complete the following recursive function aiming to check if a binary tree is sum balanced tree or no.
A sum balanced binary tree is a binary tree where the sum of the left subtree of each node is equal
to the sum of the nodes in its right subtree. You should provide a solution with complexity O(n).

int isSumBalanced(BTNode *root) {

int isBalanced = 1;
isSumBalancedUtil(root, &isBalanced);
return isBalanced;
}

int isSumBalancedUtil(BTNode *root, int *isBalanced) {

if (root == NULL)
return 0;
//Complete code here

}
3. Complete the recursive method that takes two values v and x (x is negative) and returns v power x
(vx). The complexity of the function should be no more than O(log(n)).
double powerNegative(double v, int x) {
//Complete code here (x is negative only)

Page 7/10
 Scratch
Pay attention, you should keep all the scratch papers stapled in the booklet exam.

Page 8/10
Scratch

Page 9/10
Scratch

Page 10/10