Programming Practice Exam: Quiz!

1. What will be the output of the following pseudo code?

6

5

10

15

The output of the pseudo code will be 15 because it is the last number in the given sequence.

Explanation

The output of the pseudo code will be 15 because it is the last number in the given sequence.

2. What is the time complexity of searching for an element in a circular linked list?

O(n)

O(nlogn)

O(1)

None of these

The time complexity of searching for an element in a circular linked list is O(n). This is because in the worst case scenario, the element being searched for could be the last element in the list, and thus the search would have to iterate through all the elements in the list before finding it. Therefore, the time taken to search for an element in a circular linked list is directly proportional to the number of elements in the list, resulting in a time complexity of O(n).

Explanation

The time complexity of searching for an element in a circular linked list is O(n). This is because in the worst case scenario, the element being searched for could be the last element in the list, and thus the search would have to iterate through all the elements in the list before finding it. Therefore, the time taken to search for an element in a circular linked list is directly proportional to the number of elements in the list, resulting in a time complexity of O(n).

3. What will be the output of the following pseudo code?

56

88

72

65

not-available-via-ai

Explanation

not-available-via-ai

4. What will be the value of t if a = 56 , b = 876?

490563

49056

490561

None of these

The value of t can be determined by multiplying the values of a and b. Therefore, t = a * b = 56 * 876 = 49056.

Explanation

The value of t can be determined by multiplying the values of a and b. Therefore, t = a * b = 56 * 876 = 49056.

5. What will be the output of the following pseudocode?

56

78

72

68

The output of the pseudocode will be 72.

Explanation

The output of the pseudocode will be 72.

6. You have an array of n elements. Suppose you implement a quick sort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is:

O(n2)

O(nLogn)

Θ(nLogn)

O(n3)

When implementing quicksort by always choosing the central element as the pivot, the worst case scenario occurs when the array is already sorted or nearly sorted. In this case, the pivot will always be the smallest or largest element, resulting in one partition with n-1 elements and another with no elements. This leads to a time complexity of O(n^2), as each partition takes O(n) time and there are n partitions.

Explanation

When implementing quicksort by always choosing the central element as the pivot, the worst case scenario occurs when the array is already sorted or nearly sorted. In this case, the pivot will always be the smallest or largest element, resulting in one partition with n-1 elements and another with no elements. This leads to a time complexity of O(n^2), as each partition takes O(n) time and there are n partitions.

7. Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

3,0 and 1

3,3 and 3

4,0 and 1

3,0 and 2

The maximum chain length in the hash table is 3, which means that there is a chain of length 3 in the hash table. The minimum chain length is 0, indicating that there are no empty slots in the hash table. The average chain length is 1, which is calculated by dividing the total number of keys (9) by the number of slots in the hash table (9). This means that, on average, each slot in the hash table contains 1 key.

Explanation

The maximum chain length in the hash table is 3, which means that there is a chain of length 3 in the hash table. The minimum chain length is 0, indicating that there are no empty slots in the hash table. The average chain length is 1, which is calculated by dividing the total number of keys (9) by the number of slots in the hash table (9). This means that, on average, each slot in the hash table contains 1 key.

8. Which of the following will give the best performance?

O(n)

O(n!)

O(nlogn)

O(nC)

The correct answer is O(n) because it represents linear time complexity, meaning that the time taken to execute the algorithm increases linearly with the size of the input. In comparison, O(n!) represents factorial time complexity, which grows exponentially with the input size and is extremely inefficient. O(nlogn) represents logarithmic time complexity, which is more efficient than O(n!) but still slower than linear time complexity. O(nC) is not a valid notation for time complexity and does not provide any information about the performance.

Explanation

The correct answer is O(n) because it represents linear time complexity, meaning that the time taken to execute the algorithm increases linearly with the size of the input. In comparison, O(n!) represents factorial time complexity, which grows exponentially with the input size and is extremely inefficient. O(nlogn) represents logarithmic time complexity, which is more efficient than O(n!) but still slower than linear time complexity. O(nC) is not a valid notation for time complexity and does not provide any information about the performance.

9. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

Log 2 n

N/2

Log2n - 1

N

In the worst case scenario, the number of comparisons needed to search a singly linked list of length n for a given element is equal to the length of the list, which is n. This is because in the worst case, the element being searched for could be at the very end of the list, requiring each element to be compared until the desired element is found.

Explanation

In the worst case scenario, the number of comparisons needed to search a singly linked list of length n for a given element is equal to the length of the list, which is n. This is because in the worst case, the element being searched for could be at the very end of the list, requiring each element to be compared until the desired element is found.

10. How many times the following loop be executed?

0

25

26

1

The loop will be executed 25 times because the loop starts at 0 and ends at 24 (25 iterations).

Explanation

The loop will be executed 25 times because the loop starts at 0 and ends at 24 (25 iterations).

11. Let P be a Quick Sort Program to sort numbers in ascending order using the first element as a pivot. Let t1 and t2 be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Which one of the following holds?

T1 = 5

T1 < t2

T1 > t2

T1 = t2

not-available-via-ai

Explanation

not-available-via-ai

12. What will be the value of even_counter if number = 2630?

3

4

2

1

The value of even_counter will be 1 because the number 2630 has only one even digit, which is 2.

Explanation

The value of even_counter will be 1 because the number 2630 has only one even digit, which is 2.

13. What does the following piece of code do?

Preorder traversal

Inorder traversal

Postorder traversal

Level order traversal

The given piece of code performs a postorder traversal. In postorder traversal, the left subtree is visited first, followed by the right subtree, and finally the root node is visited. This traversal method is commonly used to delete nodes from a binary search tree, as it ensures that child nodes are deleted before their parent node.

Explanation

The given piece of code performs a postorder traversal. In postorder traversal, the left subtree is visited first, followed by the right subtree, and finally the root node is visited. This traversal method is commonly used to delete nodes from a binary search tree, as it ensures that child nodes are deleted before their parent node.

14. What will be the value of s if n=127? Read n i=0,s=0 Function Sample(int n) while(n>0) r=n%l0 p=8^i s=s+p*r i++ n=n/10 End While Return s; End Function

27

187

87

120

The given code is a function named "Sample" that takes an integer input "n". It initializes two variables "i" and "s" to 0. Then, it enters a while loop where it performs the following steps:
1. Calculate the remainder of "n" divided by 10 and store it in variable "r".
2. Calculate the power of 8 raised to the power of "i" and store it in variable "p".
3. Multiply "p" and "r" and add the result to "s".
4. Increment "i" by 1.
5. Divide "n" by 10.
This process continues until "n" becomes 0. Finally, the function returns the value of "s".
In this case, if "n" is 127, the function will calculate (7 * 8^0) + (2 * 8^1) + (1 * 8^2) = 7 + 16 + 64 = 87. Therefore, the value of "s" will be 87.

Explanation

The given code is a function named "Sample" that takes an integer input "n". It initializes two variables "i" and "s" to 0. Then, it enters a while loop where it performs the following steps:
1. Calculate the remainder of "n" divided by 10 and store it in variable "r".
2. Calculate the power of 8 raised to the power of "i" and store it in variable "p".
3. Multiply "p" and "r" and add the result to "s".
4. Increment "i" by 1.
5. Divide "n" by 10.
This process continues until "n" becomes 0. Finally, the function returns the value of "s".
In this case, if "n" is 127, the function will calculate (7 * 8^0) + (2 * 8^1) + (1 * 8^2) = 7 + 16 + 64 = 87. Therefore, the value of "s" will be 87.

15. What will be the output of the following pseudo code?

21

15

9

6

not-available-via-ai

Explanation

not-available-via-ai

16. Code to sort given array in ascending order is given below,which of the following statements is incorrect?

Line 4

Line 6

Line 7

No Error

not-available-via-ai

Explanation

not-available-via-ai

17. What will be the output of the following pseudocode? Integer n for (n = 3; n != 0; n–) Print n n = n-1 end for

3 1

3 2 1

3

Infinite Loop

The given pseudocode initializes the variable n to 3 and then enters a for loop. In each iteration of the loop, the value of n is printed and then decremented by 1. However, since the condition for the loop to continue is "n != 0", and n is never updated inside the loop, the value of n will always be 3 and the loop will continue indefinitely. Therefore, the output will be an infinite loop.

Explanation

The given pseudocode initializes the variable n to 3 and then enters a for loop. In each iteration of the loop, the value of n is printed and then decremented by 1. However, since the condition for the loop to continue is "n != 0", and n is never updated inside the loop, the value of n will always be 3 and the loop will continue indefinitely. Therefore, the output will be an infinite loop.

18. Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represented using adjacency matrix.

O(n)

O(m+n)

O(n2)

O(mn)

The tightest upper bound on the running time of Depth First Search (DFS) on graph G with n vertices and m edges, represented using an adjacency matrix, is O(n^2). In DFS, each vertex is visited once, and for each vertex, all its adjacent vertices are explored. In an adjacency matrix representation, checking for adjacent vertices takes O(n) time. Therefore, for each vertex, the total time taken is O(n). Since there are n vertices, the overall time complexity is O(n^2).

Explanation

The tightest upper bound on the running time of Depth First Search (DFS) on graph G with n vertices and m edges, represented using an adjacency matrix, is O(n^2). In DFS, each vertex is visited once, and for each vertex, all its adjacent vertices are explored. In an adjacency matrix representation, checking for adjacent vertices takes O(n) time. Therefore, for each vertex, the total time taken is O(n). Since there are n vertices, the overall time complexity is O(n^2).

19. Consider the following piece of code. What will be the space required for this code?

2n + 8

2n + 4

2n + 2

2n

The space required for this code can be determined by analyzing the expression 2n + 8. The term 2n represents the space required for the variable n, while the term 8 represents the space required for the constant value 8. Therefore, the total space required for this code is the sum of these two terms, resulting in 2n + 8.

Explanation

The space required for this code can be determined by analyzing the expression 2n + 8. The term 2n represents the space required for the variable n, while the term 8 represents the space required for the constant value 8. Therefore, the total space required for this code is the sum of these two terms, resulting in 2n + 8.