TGPSC HMWSSB Manager Algorithms previous year questions with answers
Every Algorithms question asked in the TGPSC HMWSSB Manager (Engineering) papers on this site, grouped by topic. Answers come from TSPSC's final key; each has a short explanation (free here for a sample, all of them in the practice app).
Practise Algorithms onlineComplexity & Recurrences
Consider the following functions f(n) = 3n^√n g(n) = 2^(√n log₂n) h(n) = n!
- h(n)=O(f(n))
- h(n) is O(g(n))
- g(n) is not O(f(n))
- f(n) is O(g(n))
Show answer
Answer: (4) f(n) is O(g(n))
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which one of the following recurrence relation denotes the running time of selection sort algorithm.
- T(n) = 2T(n/2) + cn
- T(n) = T(n−1) + cn
- T(n) = T(n−1) + c
- T(n) = 2T(n/2) + c
Show answer
Answer: (2) T(n) = T(n−1) + cn
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which one of the following statements is correct? i) The Euler tour of a graph can be determined in polynomial time ii) The Hamiltonian cycle can be determined in polynomial time. iii) Determining whether a directed graph has a Euler tour is NP-complete iv) Determining whether a directed graph has a Hamiltonian cycle is NP-complete
- (i) and (ii)
- (i) and (iv)
- (ii) and (iii)
- (iii) and (iv)
Show answer
Answer: (2) (i) and (iv)
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which of the following statements is incorrect?
- If the output of one polynomial-time algorithm is fed into the input of another, the composite algorithm is polynomial
- Halting problem is NP-hard problem
- Travelling salesperson problem has a polynomial time algorithm
- Satisfiability problem is np-complete
Show answer
Answer: (3) Travelling salesperson problem has a polynomial time algorithm
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
A machine needs a minimum of 100 sec to sort 1000 names by quick sort. The minimum time needed to sort 100 names will be approximately
- 50.2
- 6.7
- 72.7
- 11.2
Show answer
Answer: (2) 6.7
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Sorting & Searching
Which data structure is used to implement radix sort
- Stacks
- Queue
- Linked list
- Tree
Show answer
Answer: (2) Queue
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which of the following sorting algorithm does not have worst case time complexity of O(n²)
- Bubble Sort
- Quick Sort
- Insertion Sort
- Heap Sort
Show answer
Answer: (4) Heap Sort
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
The average time required to perform a successful sequential search for an element in an array A(1:n) is given by
- (n+1)/2
- log₂n
- n(n+1)/2
- n²
Show answer
Answer: (1) (n+1)/2
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Average successful search time taken by binary search on a sorted array of 10 items is
- 2.6
- 2.7
- 2.8
- 2.9
Show answer
Answer: (4) 2.9
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
What is the number of comparisons required for merging two sorted lists of sizes m and n into a sorted list of size m + n.
- O(m)
- O(n)
- O(m+n)
- O(log n + log m)
Show answer
Answer: (3) O(m+n)
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Algorithm Design Techniques
Match the following:
a. Divide and Conquer i. Graph Coloring b. Dynamic Programming ii. Travelling Salesperson Problem c. Backtracking iii. Quicksort - a:iii; b:i; c:ii
- a:iii; b:ii; c:i
- a:ii; b:iii; c:i
- a:ii; b:i; c:iii
Show answer
Answer: (2) a:iii; b:ii; c:i
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which one of the algorithms obtains global optimal solutions?
- Greedy algorithm
- Dynamic Programming
- Greedy algorithm and Dynamic Programming
- Divide and Conquer
Show answer
Answer: (2) Dynamic Programming
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Graph Algorithms
What is the time complexity of depth first search traversal of a graph consisting of n vertices and m edges represented using adjacency list?
- O(n)
- O(m + n)
- O(n²)
- O(mm)
Show answer
Answer: (2) O(m + n)
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
What is the time complexity of Kruskal's algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges?
- O(n)
- O(m + n)
- O(n²)
- O(m log n)
Show answer
Answer: (4) O(m log n)
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which of the following minimal spanning tree algorithm assures connectivity of tree at all steps?
- Kruskal
- Prims
- Both Kruskal and Prims
- Dijkstra
Show answer
Answer: (2) Prims
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.