A-58

Entrance Examination (June 2012)
PhD in Computer Science


1. In DBMS the projection operation creates a new table that has

A. more tuples than the original table

B. more attributes than the original table

C. both of A and B above

D. none of the above

2. A locked file can be

A. accessed by a user having correct password

B. accessed by one user

C. used to hide data

D. none of the above

3. The length of a Hamiltonian path (if exists) in a simple connected graph of n vertices is

A. n+1

B. n-1

C. n

D. none of the above

4. A network schema is different from a hierarchical schema, for, it allows

A. one parent -one child

B. one parent -many children

C. many parents -many children

D. both of A and B above only

5. A binary search tree is built by inserting the following values in the given order: 4,25,15,12,20,70,40. The Post Order Traversal will be

A. 12, 15, 20, 40, 70, 25, 4

B. 12, 20, 15, 40, 70, 25, 4

C. 25, 70, 40, 15, 12, 20

D. 12, 15, 20, 25, 40, 70


6. If N is an n-bit number, how many bits long is approxi111ately?

A. nlogn

B.

C. 2n

D. n2

7. which one of these sorting algorithms involves minimum record swaps during execution on an average?

A. bubble sort

B. insertion sort

C. selection sort

D. quicksort

8. The solution of the recurrence relation for n is

A. theta(nlog23)

B. theta(n log

C. theta(n)

D. theta(n2)

9. All IP addresses in the range 186.220.64.0 to 186.220.71.254 are kept in a VLAN. The correct netmask so that messages are broad­cast only within this VLAN is

A. 186.220.255.255

B. 186.220.248.0

C. 186.220.248.255

D. 186.220.8.0

10. On a Linux system, a person found that it is possible to display the contents of a file named usr/foo/public/award .html but could not list the files in the directory using Is usr/foo/public. The permissions on the directory may have been

A. rwxr-x--x

B. rwxr-xr--

C. rwxr-xr-x

D. None of the Above

11. The first four bytes of a binary file are CA, FE, BA, BE (in Hexadec­imal, of course!). What type of a file is it?

A. MSWindows .exe file

B. MSWindows .com file

C. Java Class file

D. BMP lInage file

12. For which of the following problems can a Turing machine not be designed?

A. Find if there exists a sequence of 7 consecutive in the decimal expansion of 22/7

B. Find if there exists a sequence of 7 consecutive in the decimal expansion of pie

C. Find if there exists a sequence of 7 consecutive in the quotients obtained by dividing all positive integers less than 10 64 by the number 125

D. None of the Above

13. One way of showing that one string is equal to another string is to compare and match them character by character. What happens if we allow both the strings to be of infinite length?

A. The method fails because we can only show that the two strings are not equal.

B. The method fails because we can only show that the two strings are equal.

C. The method is OK and works even if the strings are of infinite length.

D. None of the Above

14. In the C Programming Language, arrays can be defined in two ways. The first is static: int a [4000] the second is dynamic: declare as int and then allocate memory using malloc(). Which of the following is then TRUE?

A. In the first case, memory is contiguous while in the second case, memory is not contiguous.

B. In the first case, elements may be accessed as a while in the second, they cannot be accessed so.

C. In the first case, the array elements are stored in row-major order, while in the second they are stored in column-major order.

D. None of the Above

15. If flexibility is defined as having maximum choice in cache place­ mcnt, which of the following is correctly ordered in ascending order of flexibility?

A. Direct Mapping, Set-Associative Mapping, Associative Mapping

B. Set-Associative Mapping, Direct Mapping, Associative Mapping

C. Associative Mapping, Set-Associative Mapping, Direct Mapping

D. None of the Above

16. A linear array has n elements. Suppose the item we are searching for in the array appears randomly in the array, and we use linear search to find the location of the item. Let f denote the number of comparisons in the linear search. What is the expected (average) value of

A.

B. n

C.

D. None of the above


17. Let n denote a positive integer. Suppose a function L is defined recursively as follows (here denotes the "floor" of k).

<img src='./qimages/1989-17.jpg'>

That does L find?

A. log2

B. L n2/4 1

C. L 2n

D. None of the above

18. Which sort will operate in quadratic time relative to the nun1ber of elements in the array (on the average)?

A. Quick Sort

B. Merge Sort

C. Radix Sort

D. Bubble Sort

19. Which of the following statements best describes Quicksort, Merge­sort and Heap-sort algorithms, respectively?

A. the first two use recursive partitioning, while the third uses static tree-like structure

B. All of them use recursive partitioning

C. the first two use static tree-like structure, while the third uses recursive partitioning

D. the first two use nested do loop where both loops are bounded by the array size, while the third uses static tree-like structure

20. Suppose S consists of the following n 5 letters in the order: A B C D E. What is the nUluber of comparisons to alphabetically sort S using Quicksort algorithm?

A. 15

B. 12 to 13

C. 10

D. 25

21. Assume that a graph is given as an array of pairs (edges) and the colouring of the edges is given as an array of N nodes numbered 1 to N. If a particular colour assignment for the graph is given, what is the (best) time complexity for verifying whether the given colour assignment is valid or not?

A. logarithmic (with respect to the number of edges)

B. linear (with respect to the number of edges)

C. quadratic (with respect to the number of edges)

D. exponential (with respect to the number of edges)

22. A search technique where we keep expanding nodes with least accumulated cost so far is called:

A. Hill-climbing

B. Best-first

C. Breadth-first

D. Branch-and-bound

23. How many comparisons are required to sort an array of length 5 if selection sort is used and the array is already sorted in the opposite order?

A. 0

B. 1

C. 10

D. 20

24. The grammar G S where P 0S1, S S S will generate

A. Context-free language

B. Context-sensitive language

C. Regular language

D. Recursively enumerable language

25. Consider the following grammar.

AB
a
A BaB
B bbA

Which of the following statement is FALSE?

A. The length of every string produced by gran1ll1ar is even

B. No string produced by grammar has an odd number of consecutive

C. No string produced by the grammar has 3 consecutive s

D. No string produced by grammar has 4 consecutive s


26. That is the order of complexity of the following program?

sum=0;




A. O(log

B. O(n log

C.

D.

27. In a linked list, we require that the element that is requested for is always deleted from its current position and moved to the beginning of the list. what is order of complexity of search?

A.

B.

C. O(log

D. O(n log

28. Inorder and postorder traversals of a binary tree are as follows:

Postorder:
Inorder:

Determine the value of right child of 12

A. 14

B. 88

C. -12

D. 6

29. What is the maximum possible nun1ber of directed edges in an n-node, simple, acyclic, directed graph?

A. n-l

B. 3n

C. nC2

D.

30. What is the maximum possible number of edges in an n-node, sin1ple, acyclic, undirected graph?

A. n-1

B.

C. nC2

D.

31. which of the following regular expressions is equivalent to

A. b(c

B.

C.

D. b)c b)d

32. which of the following is expected to improve the efficiency of Input/Output transfer in an Operating System?

1 Reducing the number of Context Switches

2 Reducing the nUlllber of times data must be copied in memory while passing between device and application

3 Doing I/O with larger data transfer for each interrupt and reducing frequency of interrupts

A. 1 only

B. 2 and 3 only

C. 1,2 and 3

D. None of the Above

33. A system call x is issued by an application, due to which the following sequence takes place: the execution of the application is suspended, the application is moved from run queue to wait queue. After the system call completes, the application is moved back to the run queue. This behavior of the system call x can be best described as

A. Non-blocking system call

B. Asynchronous I/O system call

c. Abort system call

D. Blocking system call


34. The problem known as Priority Inversion occurs in systems with more than two priorities and can be solved by

A. Using Banker's Algorithm

B. Doing a bit-wise XOR to PID value

C. By allowing a lower priority process to inherit temporarily the priorities of a higher priority process waiting to access the same resource

D. By using semaphores

35. Deadlocks can be eliminated using resource preemption, and distributing resources to other processes until deadlock cycle is broken. Which of the following may become issues with this approach?

1 Bankers Algorithm·

2 Roll Back

3 Starvation


A. 1 only

B. 2 only

C. 1 and 2 only

D. 2 and 3 only

36. The generating function of the convolution of two signals is of the generating functions of the respective signals

A. Addition

B. Subtraction

C. Product

D. Division

37. The piecewise Bezier curve of second degree will be useful for modeling real world curves of dimension less than or equal to although each Bezier curve is a curve

A. non-planar

B. planar

C. non-planar

D. planar


38. In the past ten years, there have been several 'improvements in, mountain-climbing equipment. These improvements have made the sport both safer and more enjoyable for experienced climbers. Despite these improvements, however, the rate of mountain-climbing injuries has doubled in the past ten years.

Which of the following, if true, best reconciles the apparent dis­crepancy presented in the passage?

A. Many climbers, lulled into a false sense of security, use the new equipment to attempt climbing feats of which they are not capable.

B. Some mountain-climbing injuries are caused by unforeseeable weather conditions.

C. mountain climbing, although a dangerous sport, does not normally result in injury to the experienced climber.

D. Although the rate of mountain-climbing injuries has increased, the rate of mountain-climbing deaths has not changed.

39. while most scholarship in women's employment in the United States recognizes that the Second World War (1939-1945) dramatically changed the role of women in the workforce, these studies also acknowledge that few women remained in manufacturing jobs once men returned from the war. But in agriculture, unlike other industries where women were viewed as temporary workers, women's employment did not end with the war. Instead, the expansion of agriculture and a steady decrease in the number of male farmworkers combined to cause the industry to hire Ignore women in the postwar years. Consequently, the 1950s saw a growing number of women engaged in farm labour, even though rhetoric in the popular media called for the return of women to clOluestic life.

39. The manufacturing and agricultural sectors in the United States following the Second World War differed in which of the following respects?

A. The rate of expansion in each sector.

B. The percentage of employees in each sector who were men.

C. The attitude of the popular media toward the employment of women in each sector.

D. The trend in the wages of men employed in each sector.

40. which of the following statements about women's employment in the United States during and after the Second World War is nlOst clearly supported by the passage?

A. most women who joined the workforce during the Second World War wanted to return to domestic life when the war ended.

B. The great majority of women who joined the workforce during the Second World War were employed in manufacturing jobs.

C. The end of the Second World War was followed by a large scale transfer of women workers from manufacturing to agriculture.

D. The increase in women's employment that accompanied the Second World War was longer lasting in agriculture than it was in manufacturing. The end in the wages of men employed in each sector.


41. Give an example of an algorithm whose average case running time is different from its worst case running time. Explain your answer in clear terms.

42. Given the decimal value -16.75, use IEEE 32-bit single-precision standard system to represent this value.

43. We want to create a (small) instruction set for a computer that has 4 general purpose registers named R1, R2, R3 and R4, and one dedicated register named RESULT. The individual instructions that the computer needs are as follows:

1 increment a register (add 1 to the contents of the register, stores the new value in register RESULT).

2 add any two general purpose registers, put the sum in register RESULT.

3 multiply any two general purpose registers, put the product in register RESULT.

4 copy the value in register RESULT to anyone of the 4 general purpose registers.

Develop a 6-bit binary machine code that encodes these instructions (each instruction must be 6 bits). Provide the details of your encoding (describe your machine code here)

44. A computer employs RAM chips of size 256 x 8 and ROM chips of size 1024 x 8. The computer system needs 2K words (word size 16 bits) of RAM, 4K bytes of ROM, and four interface units each with four registers. The two highest-order bits of the address bus are assigned 00 for RAM, 01 for ROM and 10 for interface units. Prepare a memory/ component address map for addressing these components.

45. Let L be a language recognizable by a finite automaton. Determine the type of language realized by REVERSE(L)? Please justify your answer.

REVERSE such that W is the reverse of V
where V E

46. what exactly do you mean by a recursive language and a recursively enumerable language? Prove that there are languages that, arc not even recursively enumerable.

47. If deadlock is to be eliminated by aborting a process and reclaiming system resources, list a number of factors that may affect the choice of the process to abort.

48. Give the logic circuit using NAND gates for the expression a b c·

49. Give the structure function of 3 out of 4 system, with subsystem structure functions as £1, f2, f3 and f4.

50. Suppose relation has the functional dependencies

A B
BC D
BE C
AD E
CE A

what are all the keys of Of the five given FDs, which ones violate the BCNF condition?

51. Data Structures is the study of Abstract Data Types wherein we are interested only in the logical organization of data and operations that are performed on that data, without regard to how data is physically stored in memory. Define an ADT for the Array Data Structure.