University of Hyderabad (UoH) 2010 Ph.D Computer Science Engineering Entrance (e ) in Computer Science - Question Paper
Entrance Examination (June 2010)
Time: 2 Hours Max. Marks: 75
Hall Ticket Number:
1. Write your Hall Ticket Number in the box above AND on the answer script.
2. This test is for 2 hours duration carrying 75 marks. There is a negative marking of 0.33 mark for every wrong answer in PART A.
3. ALL PARTS ARE COMPULSORY. Please write answers for multiple-choice questions of PART A in the table provided on Page 2 of the Question paper and the remaining parts must be answered on the answer script.
4. Clearly write Part and Question Numbers. Each part should start on a new page. Answer questions in order.
5. Give precise answers and write clearly.
6. Do all the rough work only on the last page of the answer script, nowhere else. Label the page Rough Work.
7. Use of non-programmable calculator and log-tables is allowed.
8. Submit both the question paper and the answer script to the invigilator before leaving the examination hall.
PART A: OBJECTIVE TYPE QUESTIONS (40 Marks)
|
Question JNo. |
Answer || Question No. |
Answer |
|
1 |
..... II 21 | |
|
2 |
_ II 2* | |
|
6 |
_ II | |
|
4 |
_ II | |
|
5 |
II 2b | |
|
(j |
__ II *> | |
|
7 |
.... II | |
|
8 |
II 28 | |
|
y |
........ II M | |
|
1U |
II 3U | |
|
ii |
551 | |
|
12 |
. II '62 | |
|
13. |
II 33 | |
|
14 |
II 34 | |
|
lb |
II | |
|
It) |
. II 36 | |
|
17 |
......... II 37 | |
|
18 |
II | |
|
iy |
II 3y | |
|
20 |
_ II 4U |
1. The average case time complexity of finding minimum element in a Max-heap having N elements is
B. Q(logN)
C. 0(1) .
2. The integers {1-1000} are stored in a Binary Search Tree (BST). Suppose the search algorithm is implemented on the key 363, one of the following sequences is NOT a possible sequence of nodes that is examined. It is
A. 2, 252, 401, 398, 330, 344, 397, 363
B. 924, 220, 911, 244, 898, 258, 362, 363
C. 925, 202, 911, 240, 912, 345, 245, 363
D. 2, 399, 387, 219, 266, 382, 381, 278, 363
3. It is NOT KNOWN if an NP-complete problem A is such that
B. Ag P
C. A e NP-Hard
D. Circuit-Sat reducible to A.
4. Which of the following statements is TRUE about the worst-case time complexity for operations on heaps?
A. Neither insertion nor removal is better than linear.
B. Insertion is better than linear, but removal is not.
C. Removal is better than linear, but insertion is not.
D. Both insertion and removal are better than linear.
5. A priority queue is implemented by storing the items in a min-heap (using an array for the heap items). In a min-heap, the value at parent is less than the value at the child position. If re-heapification is done upward and the out-of-place node is at data[i] with priority given by data[i], Which of the following boolean expressions is TRUE to indicate that the re-heapification IS NOT YET DONE.
A. (i > 0)
B. (data[{i - l)/2] < data[i])
C. (i > 0) && (data[{i - l)/2] < data[i\) '
D. (i > 0) || (data[(i - l)/2] < data[i})
6. An algorithm has a run time complexity of 0{log N). The algorithm requires 110 operations for an input of size 1000. When the input size is doubled to 2000, the algorithm now requires 120 operations. What is your best guess for the number of operations required when the size is doubled to 4000?
A. 130
B. 140
C. 150
D. 160
7. A stack data structure is used in which of the following implementations
A. Priority queue
B. Depth First Search
C. Breadth First Search
D. Post order traversal
8. Class of languages recognized by finite automata is called as:
A. Context Sensitive languages
B. Recursive Languages
C. Regular languages
D. Context free Languages
9. Given an arbitrary Non-deterministic Finite Automaton (NFA) with N states, the maximum number of states in an equivalent
|
A. |
N2 |
|
B. |
2n |
|
C. |
2 N |
|
D. |
N\ |
10. Which of the following statements is FALSE?
A. If a language is context free it can always be accepted by a non-deterministic push-down automaton
B. The union of two context free languages is context free
C. The intersection of two context free languages is context free
D. A regular language is context free
11. If the regular set A is represented by A = (01 + 1)* and the regular set B is represented by B = ((01)*1*)*, which of the following statements is TRUE?
A. A is a proper subset of B
B. B is a proper subset of A
C. A and B are incomparable
D. A = B
12. The Language L {a2k : k > 0} is
A. Regular Language
B. Non-regular Language
\
C. Non Context-free language
D. None of the above
13. The number of columns in a table is known as its
A. Range
B. Cardinality
C. Domain
D. Degree
14. To transmit data bits 1011, the correct even parity seven bit Hamming Code is:
15. Which of the following is the name of the data structure in a compiler that is responsible for managing information about variables and their attributes?
A. Parse Table
B. Attribute Grammar
C. Symbol Table
D. Semantic Stack
16. Overloading involves writing two or more functions with
A. the same name and the same argument list
. B. different names but the same argument list
C. the same name but different argument list
D. different names and different argument list
17. Cyclomatic complexity is a metric to count
A. the number of functionalities of a program
B. the number of distinct paths a program has
C. the number of insertion points a program has
D. the average number of functions a class has
18. Chidambaram Metric is used to measure efficiency of
A. function interactions in a class
B. object oriented programs
C. object oriented testings
D. object oriented designs
19. Resolution of externally defined symbols is performed by
A. Linker
B. Compiler
C. Assembler
D. Loader
20. Which of the following is(are) serious problem(s) of file management systems?
A. Data redundancy
B. Program dependence
C. Lack of data independence
D. All of the above
21. A database with network schema allows
A. one-to-many relationships
B. many-to-many relationships
C. data organization in tables
D. hierarchical data organization
22. How many bit strings of length 8 either start with a bit 1 or end with the two bits 00?
|
A. |
160 |
|
B. |
255 |
|
C. |
128 |
|
D. |
64 |
23. Which of the following algorithms can be used to find a spanning tree of a given connected graph G1
A. Breadth First Search v
B. Depth First Search
C. Kruskals Algorithm
D. All of the above
24. In standard computer networking terminology we use the terms
(i) segment and (ii) frame, both to describe packets. Usually these terms refer to which of the following:
A. Segment deals with layer 3 packets (network) while frame is for layer 4 (transport) packets.
B. Segment deals with layer 3 packets (network) while frame is for layer 2 (data link) packets.
C. Both actually deal with layer 2 (data link) packets but just are different names
D. Segment deals with layer 4 (transport) while frame is for layer 2 (data link) packets.
25. The least number of IP addresses a router and a host may have, excluding loopback addresses, is
A. As many for a router and one for a host
B. Two for a router and one for a host
C. Both routers and hosts can have atmost a single unique address
D. Two for a router and none are really needed for a host
26. Consider the situation where a datagram of 4,000 bytes (where 20 oytes are of the IP header) arrives at a router that must forward packets to a link with Maximum Transmission Unit (MTU) of
1,500 bytes. If fragmentation is permitted, which of the following is the most likely behaviour of the router? b
A. Forward the packet by breaking into three fragments with identical identification and offset values in the headers
B. Forward the packet by copying data into three fragments each with identical identification and flag values in the headers
C. Forward the packet by copying data into three fragments
with each fragment having different flag and offset values in the header
D. Forward the packet by breaking into three fragments with different identification values in the headers
27. Imposing a linear order on all resource types, and letting processes
request resources in increasing order of enumeration is an example of:
A. Deadlock avoidance where the system will never enter an unsafe state
B. Deadlock detection where out-of-sequence resource requests can easily be identified
C. Deadlock avoidance where hold and wait conditions cannot, occur
D. Deadlock prevention where circular waits for resources can never take place
28. In TCP congestion control which of the following is MOST CORRECT?
O s-fc
A. The sender responds to a loss event by reducing its congestion window size
B. The receiver does not drop excess packets but due to congestion does not forward them
C. The receiver drops excess packets due to congestion
D. To compensate for the loss event, sender doubles its congestion window size
29. The amount of time required to read a block of data from a disk into memory is composed of seek time, rotational latency, and transfer time. Rotational latency refers to
A. the time it takes for the platter to make a full rotation
B. the time it takes for the read-write head to move into position over the appropriate track
C. the time it takes for the platter to rotate the correct sector under the head
D. None of the above
30. According to the specifications of a particular hard disk a seek takes 3 msecs between adjacent tracks. If the disk has 100 cylinders how long will it take for the head to move from the innermost cylinder to the outermost cylinder?
A. 30 microseconds
B. 3000 msecs
C. 3 microseconds
|
p |
q |
r |
f(p,q,r) |
g(p, q, r) |
|
1 |
l |
1 |
0 |
i |
|
1 |
l |
0 |
0 |
l |
|
1 |
0 |
1 |
1 |
l |
|
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
l |
|
0 |
0 |
1 |
1 |
l |
|
0 |
0 |
0 |
0 |
l |
31. The Principal Disjunctive Normal Form (DNF) for f(p, q. r) given in the table is: (Note: A means not-of-4)
A. pqr+pqf+pqr
B. pqr+pqr+pqr
C. pqr+pqf+pqr
D. p q r+pqr+pqr
32. The simplified equivalent logical expression for g(p, q, r) is:
A. (p q r)
C. (p q r)
D. (p q r)
33. Which of the following is (are) TRUE about virtual memory systems that use pages?
I. The virtual address space can be larger than the amount of physical memory.
II. Programs must be resident in main memory throughout their execution.
III. Pages correspond to semantic characteristics of the program.
A. I only
B. II only
C. I and II
D. I and III
34. A certain pipelined RISC machine has 8 general-purpose registers RO, Rl,..., R7 and supports the following operations.
ADD Rsl,Rs2,Rd :Add Rsl & Rs2 and put the sum in Rd
MUL Rsl,Rs2,Rd :Multiply Rsl & Rs2 and product in Rd
An operation normally takes one cycle; however, an operation takes two cycles if it produces a result required by the immediately following operation in an operation sequence. Consider the expression AB + ABC + BC, where variables A, B, C are located in registers RO, Rl, R2. If the contents of these three registers must not be modified, what is the minimum number of clock cycles required for an operation sequence that computes the value of AB + ABC + 5C?
A. 5
B. 6
C. 7
D. 8
35. Which of the following statement(s) is / are TRUE:
I. Deterministic finite automaton has the same power as the non-deterministic finite automaton.
II. Deterministic push down automaton has the same power as the non-deterministic push down automaton.
III. Deterministic turing machine has the same power as non-deterministic turing machine.
A. I, II and III
B. I only
C. I and III only
D. I and II only
36. The von Neumann bottleneck arises due to
A. mismatch in speed between secondary and primary storage
B. mismatch in speed between CPU and primary storage
C. slow speed of I/O devices
D. low clock speeds
37. Accessing disk storage is slower than accessing RAM by an order of
A. 10
B. 100
C. 1000
D. 100,000
After reading the following passage, choose the best answer to each question. Answer questions 38 - 40 following the passage on the basis of what is stated or implied in the passage.
An essay which appeals chiefly to the intellect is Francis Bacons Of Studies. His careful tripartite division of studies expressed succinctly in aphoristic prose demands the complete attention of the reader. He considers studies as they should be: for pleasure, for self-improvement, for business. He considers the evils of excess study: laziness, affectation, and precocity. Bacon divides books into three categories: those to be read in part, those to be read cursorily, and those to be read with care. Studies should include reading, which gives depth; speaking, which adds readiness of thought; and writing, which trains preciseness. Somewhat mistakenly, the author ascribes certain virtues to individual fields of study: wisdom to history, wit to poetry, subtlety to mathematics, and depth to natural philosophy. Bacons four-hundred-word essay, studded with Latin phrases and highly compressed in thought, has intellectual appeal indeed.
38. Which of the following is the most appropriate title for the passage, based on its content?
A. Francis Bacon and the Appeal of the Essay
B. Of Studies: A Tripartite Division
C. An Intellectual Exercise: Francis Bacons Of Studies
D. The Categorization of Books According to Bacon
39. According to the passage, who has mistakenly ascribed certain virtues to individual fields of study.
A. Scholars of the Society
B. General Reader
C. The author of the passage
D. Francis Bacon
40. The passage suggests that the author would be most, likely to agree with which of the following statements?
A. Of Studies belongs in the category of works that demand to be read with care.
B. Scholars personalities are shaped by the academic discipline in which they are engaged.
C. An author can be more persuasive in a long essay than in a shorter one.
D. It is an affectation to use foreign words in ones writing.
PART B: SHORT ANSWER QUESTIONS (20 Marks)
Answer any FIVE Questions. Each Question carries Four Marks
1. Given a list of numbers, for each of the operations listed below, briefly describe an algorithm to implement it and state the algorithms asymptotic time complexity.
(a) Find the minimum value of the list.
(b) Compute the arithmetic mean
(c) Find the mode (the element that is repeated the most).
2. Let G be an undirected graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if \i~j\ = 6 or \i j\ 10. What is the number of connected components in G? (Hint: Look at the connected edges in the adjacency matrix, ignoring any bridges between the two sets).
3. TCP uses a timeout / retransmit mechanism to recover from lost segments. Explain the essential concepts of how this timeout value may be estimated.
4. Consider the grammar G whose productions are: S > SbS | a
(a) Does the string abababa belong to the language generated by the grammar G1
(b) Is the grammar G ambiguous? Justify your answers.
5. What is the value of k after the following pseudocode has been executed? Please justify your answer clearly.
k = 0;
for i\ 1 to n, for i2 = 1 to ii,
for im = 1 to iml k k lj
6. Obtain a minimum spanning forest for the following weighted undirected graph represented by the 10 x 10 matrix A (0 indicates there is no edge).
|
f 0 |
0 |
4 |
4 |
5 |
0 |
0 |
0 |
0 |
0 N |
|
0 |
0 |
2 |
5 |
3 |
0 |
0 |
0 |
0 |
0 |
|
4 |
2 |
4 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
4 |
5 |
0 |
3 |
5 |
0 |
0 |
0 |
0 |
0 |
|
5 |
3 |
1 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
3 |
4 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
2 |
2 |
|
0 |
0 |
0 |
0 |
0 |
5 |
7 |
0 |
3 |
2 |
|
0 |
0 |
0 |
0 |
0 |
3 |
2 |
3 |
2 |
1 |
|
1 |
0 |
0 |
0 |
0 |
4 |
2 |
2 |
1 |
8) |
7. Write a boolean expression that is equivalent to the circuit diagram given in Figure 1. Please show the intermediate steps clearly.
PART C: LONG ANSWER QUESTION (10 Marks)
Write a program in C for implementing a Binary Search Tree (BST) data structure. Your program should have Insert, Delete and Find functions as well as function(s) to read a file that contains operations on the BST in the following format: Function Value. An example of a file shown below:
Insert 20 Insert 10 Delete 20 Insert 30 Find 10
I. Give the code of functions for operations on BST.
II. Give the code of function(s) for handling the input text file and I/O.
III. Show the output of your program after each line for the example text file given above.
PART Dl (5 Marks)
1. The following questions pertain to your research interest. Answer briefly and to-the-point.
a. State your topic of research interest.
b. Why do you choose to do research on this topic?
c. Mention an important research publication you have studied in this research area. What is the contribution of this paper?
d. Wrhat are the potential applications of this research?
e. How do you think your education, training and experience help you do research in the area you have chosen?
17
|
Attachment: |
| Earning: Approval pending. |
