Kerala PSC Range Forest Officer Previous Question Paper – 049/2021

The Commission publishes this paper without an answer key, so no answers are shown.

1. Write a pseudocode for interchanging the values of two numeric variables a and b without using any auxiliary (temporary) variables. (2)

2. Show the result obtained in doing preorder traversal of the following binary tree:
J has left child H and right child I; H has right child F; F has left child D; D has left child A and right child B; I has left child G; G has right child E; E has left child C. (2)

3. What is meant by primary key of a database table ? Is name of person, a good attribute to be a primary key? (2)

4. What is the octal representation of the hexadecimal number (3F.42)₁₆? (2)

5. Is the class of regular languages closed under complementation ? Justify your answer. (2)

6. Briefly describe any two advantages of a linear linked list over a single dimensional array. (2)

7. Briefly explain what is context switching in an Operating System. (4)

8. Explain the difference between response time and turn around time in an Operating System. (4)

9. Briefly explain how programmers benefit from functional abstraction provided by high level programming languages like C. (4)

10. List any four features of an algorithm. (4)

11. Let S be the source code of a correct program for solving a computational problem P and I₁ and I₂ be two instances (input values) of P. Compare the process of obtaining the output values O₁ and O₂, respectively, for the input values I₁ and I₂, when we use the following language translators for S:
1. Compiler
2. Interpreter (5)

12. Show the postfix expression equivalent to the infix expression A + (B − C^D)/(E * F) − G. Use ^ to represent the power operator. (5)

13. Show the worst-case asymptotic time complexities of the following sorting algorithms.
Bubble sort, Selection sort, Merge sort, Quick sort and Heap sort. (5)

14. Suppose a processor has 32-bit virtual address, 26-bit physical address and 1 Kb pages. Show how many bits are required for the virtual and physical page numbers? (5)

15. Consider m input lines and n output lines for a decoder that is used to uniquely address a byte addressable 2 KB RAM. Calculate the minimum value of m + n. (5)

16. What is peephole optimisation ? (5)

17. Consider three CPU-intensive processes, which require 5, 10 and 15 time units to complete their
operations and they arrive at times 0, 1 and 3 respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm on a uniprocessor ? Do not count the context switches at time zero and at the end. (5)

18. Write a pseudocode to find the single-digit-sum of a natural number n. The process needs to first
compute the digit-sum of n and then check whether the obtained digit-sum is single-digit, if not, it should repeat the process on the obtained digit-sum until a single-digit-sum is obtained. For example, when n = 73, the single-digit-sum required is 1. In this case, the process should first find the digit-sum of 73 as 10 in the first step and since 10 is not a single-digit number, it should again compute the sum of digits of 10, which will give the required result 1. (5)

19. Write a pseudocode with linear time complexity to find the 3rd largest element from a sequence S of n numbers. (7)

20. Consider the following database tables:
EMP_ID | NAME | SALARY | DEPARTMENT_ID
101 | Anil | 13,000 | 1
102 | Binu | 8,000 | 1
103 | Cyril | 11,000 | 1
104 | Deepa | 12,000 | 2
105 | Emil | 15,000 | 2
DEPARTMENT_ID | DEPARTMENT_NAME | HOD_EMP_ID
1 | Marketing | 101
2 | Sales | 105
Write SQL queries for the following:
1. To print the second highest salary.
2. To print the total amount of salary paid by each department. (7)

21. Is the class of Context-Free languages closed under the operation set union ? Argue that your answer is correct. (7)

22. Determine the minimum number of arithmetic (addition and multiplication) operations required to evaluate the polynomial Q(x) = x⁴ + 8x² + 3x + 4 for a given value of x, when you are allowed to use only one temporary variable. Also show how you will implement this expression using the proposed number of registers. (7)

23. Let arr be a two-dimensional array of numbers with 2 rows (row 1 and row 2) and n columns (1 … n). In the input instance, the first row contains a sequence of n input numbers and the second row contains n unknown values. Write a pseudocode to compute the output instance such that the numbers in the first row is not altered and the second row is filled with the repetition counts of the input numbers in the first row. The following figure shows a sample output instance:
Row 1: 12 | 36 | 11 | 12 | 12 | 8 | 36 | 9 | 8
Row 2: 3 | 2 | 1 | 3 | 3 | 2 | 2 | 1 | 2
Also, show the asymptotic complexity of your pseudocode. (10)

24. Write a pseudocode to reverse a natural number n. For example, if n = 12345, then the output required is 54321. Use only numeric variables in the pseudocode (use of arrays or any other data structure is not allowed). Also, show the asymptotic complexity of your pseudocode. (10)

25. Let h be a pointer to the first node of a linear linked list with nodes having the following structure: node x contains data and next fields; x → data is the data stored at node x, and x → next is the address of the next node. Write a pseudocode to reverse the linked list. (10)

26. Argue that the problem of checking whether a given undirected graph G = (V, E) is Hamiltonian, is in the complexity class NP. (10)

27. Consider the computational problem to search for an element e in an ordered sequence of n elements. Argue that the minimum asymptotic time complexity is O(log n) for any comparison-based algorithm to solve this problem. (10)

28. What is meant by normalisation in database systems? What are the conditions to be satisfied for the second normal form (2NF)? Normalise the following database table to make it satisfy the conditions for 2NF:
Faculty_ID | Faculty_Room | Faculty_Subject
101 | 210 | Maths
102 | 202 | English
103 | 210 | Physics (10)

29. Consider a set-associative cache of size 4 KB (1 KB = 2¹⁰ bytes) with a cache block size of 64 bytes. Assume that the cache is byte-addressable and a 32-bit address is used for accessing the cache. Calculate the associativity of the cache if the width of the tag field is 21 bits. (10)

30. Consider four processes (say P₁, P₂, P₃, P₄) assumed to have arrived at time 0. Their burst times are 7, 6, 1 and 3 respectively. These processes are scheduled on a uniprocessor using Round Robin (RR) algorithm, in the order P₁, P₂, P₃, P₄. The time quantum for RR is 4 ms. Calculate the average turn-around time (in ms) of RR. (10)

31. Consider four processes (say P₁, P₂, P₃, P₄) assumed to have arrived at time 0. Their burst times are 9, 8, 3 and 5 respectively. These processes are scheduled on a uniprocessor using Non-preemptive Shortest Job First (SJF) algorithm. Calculate the average turn-around time (in ms) of SJF. (10)

32. What is the maximum number of nodes possible at level d in a rooted binary tree ? Here, level of a node x is the number of edges to be traversed to reach the node x from the root node. Prove that your answer is correct. (10)