University of Hyderabad (UoH) 2011 Ph.D Computer Science Engineering Entrance for (Computer Science) - Question Paper
Entrance Examination (June 2011)
Time: 2 Hours Max. Marks: 75
Hall Ticket Number:
1. Write your Hnll "Picket Number in the box above AND on the answer script.
2. This question paper consists of two parts: PART A and PART H. BOTII PARTS ARE COMPULSORY. Please write answers for multiple-choice question.0 of PART A in the table provided on Pago 2 of the Question paper and the Questions in PART B must be answered on the answer script.
3. This test, is for 2 hours duration carrying 75 marks. There is a negative marking of 0.33 mark for cverj wrong answer in PART A.
4. 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.
y>-
40 OBJECTIVE TYPE QUESTIONS OF ONE MARK EACH
|
Question No. |
Answer |
Question No. |
Answer |
|
I |
21 ' | ||
|
2 |
22 ' | ||
|
3 |
........ 23" ' | ||
|
4 |
.....24' | ||
|
& |
25 | ||
|
6 |
26 | ||
|
( |
27 ........ | ||
|
.........28 | |||
|
a |
29 | ||
|
kj |
......30....... | ||
|
_n------- |
31 | ||
|
12 |
- |
.....32 | |
|
13 |
J |
CO :o | |
|
14 |
...... 34...... | ||
|
15 ' ' |
" 35 | ||
|
16 |
36 | ||
|
JY |
3? | ||
|
18 |
38 | ||
|
iy |
1 to 1 | ||
|
2U |
40 |
O
1. Heap sort algorithm is the same as which of the following algorithms, except for the fact that it uses the heap data structure
A. Bubble Sort
B. Shell Sort
C. Merge Sort
D. Selection Sort
2. Consider the graph G given below:
The graph G is
A. Hamiltonian and Euclidcan
B. Euclidcan but not Hamiltonian
C. Hamiltonian but not Euclidean
D. Neither Hamiltonian nor Euclidean
3. Which of the following is in correct LEXICOGRAPHIC order when using ASCII code?
A. a, an, OR, AND
B. 1, 5, 15, 125
C. AND, OR, a, an
D. 1, 15, 125, 5
4. The number of times the statement x=x-f 1 is executed in the following program fragment using notation in terms of n is
j=n:
whileCj>=l) i
for(i=l;i<=j;++i) x=x+l; j=j/2i
>
A. 0(n)
B. (logn)
C. B(rr)
5. A list of integers is almost sorted with only the largest number being out of place. If this information is not known to the algorithm, then which of the following algorithms can sort the list the fastest?
A. Bubble Sort
B. Selection sort
C. Insertion Sort
D. Shell Sort
G. The Depth First and Breadth First Traversal Algorithms visit the nodes in exactly the same order in which of the following type of graphs:
A. Binary Tree
B. Linear Chain
C. Complete Graph
D. None of the above
7. The postfix expression ABC-f*DE*/ is equivalent to which of the following prefix expression?
A. */*A+BCDE
B. /*A+BC*DE
C. /+*ABC*DE
x-l*?
8. Algorithm for finding strongly connected components in linear time makes use of
A. BFS
B. DFS
C. Shortest Path
D. None of the above
9. What is the value of the C language expression n*n + 2*n++ + 1?
A. n2 + n - 1
B. n2 + 2n - 1
C. n2 + 2
D. n2
10. Which of the following results in the maximum value if their declarations are
int x = 5, y = 4; double z = 10.0; char c = * a *;
(Assume the ASCII value of *a is 97)
A. z*y/x+c
B. z/y*x+c
C. z+c/y*x
D. z/c+y*x
11. Consider the following function:
double power(double base, unsigned int exponent)
C
if (exponent == 0) return 1.0; else if (even(exponent))
return power(base*base, exponent/2);
else
return power(base*base, exponent/2)*base;
>
How many multiplications arc executed as a result of the call power(5.0, 12)? (Do not include divisions in this total)
A. 5
B. 8
C. 9
D. 12
12. Consider the following program segment.:
:: = b; k = n; z = 1; while (k >=0)
<
if (odd(k)) z = z*x; x = x*x; k = k/2;
>
When the loop terminates, which of the following must be true?
A. x - b
B. z = b"
C. b = z"
D. b = x"
13. Consider the following code:
#include <stdio.h> main()
C
float sum =0.0, j=1.0, i=2.0; while (i/j > 0.001)
c
sum=sum+i/j; printf ('"/,f \n", sum) ;
>
>
When this code is executed, which of the following integers best approximates the last number that is printed?
A. 0
B. 1
C. 2
D. 3
14. Thrashing problem in operating systems can not be solved by
(1) Increasing the degree of multiprogramming
(2) Increasing the clock speed of the processor
(3) Decreasing the degree of multiprogramming
(4) Increasing the memory
A. (2), (3) and (4)
B. (1), (3), and (4)
C. (1) and (2)
D. (1) and (4)
15. In operating systems when does multi-level feedback scheduling become FCFS?
A. When the time for migration is infinite
B. When the priority is same for all processes
C. When time slice is same
D. Quantum of time needed by each process is same
16. Consider a reference sequence n, f2, ra,..., rn with a FIFO page replacement algorithm and that gives Ki page faults with ? page frames allotted. When the number of page frames is j, then for Kj and I<i which of the following is always true TRUE when i < j?
A. Ki < Kj
B. Ki = Kj
D. None; of the above
17. If a system has 1GB RAM with a page size of 8KB and the operating system occupies 16 MB of RAM, how many page frames docs the system have for user processes?
A. 129024
B. 120924
C. 131072
D. 1198G4
18. In databases, spurious tuples may occur due to (J) Bad normalization
(2) Thota joins
(3) Updating tables from joins other than thcta joins
A. (2) only
B. (1) and (2) only
C. (1) and (3) only
D. (2) and (3) only
19. In the context of databases, entity integrity constraint states that
A. Primary key value can not be NULL
%
B. Foreign key value can not be NULL
C. Every relation has at least one superkey
D. Superkey of smallest size should be chosen as primary key
20. Suppose there is an open(extenial) hash table with four buckets, numbered 0, 1, 2, 3. Suppose integers are hashed into these buckets using hash function r mod 4. If the sequence of perfect squares 1, -1, 9,...,r\... is hashed into the table, then as the total number of entries in the table grows, what will happen?
A. All buckets will receive approximately the same number of entries
B. All entries will go into one particular bucket
C. Three of the buckets will each get approximately one-third of the entries, and the fourth bucket will remain empty
D. Two of the buckets will get. approximately half the entries, and the other two will remain almost empty
21. The truth table for (p V q) V (p A r) is same as t ruth table for
A. (p V q) A (p V 7*)
B. (p V 7) A r
C. (p V q) A (p A r)
D. p V q
22. The number of distinct regulai binary trees that can be constructed with 7 nodes named as a, b, c, d, e, f, gis
A. 25200
B. 1120
r H
2!
D. None of the above
23. The boolean function that is equivalent to the boolean function
p a q)A ~ (~ pA ~ q)) V (p A r) is
A. q
B. r
C. p A r
D. p V q
24. In octal, the twelve-bit twos complement of the hexadecimal number 2AF1C> is
A. 6522g
B. 62518
C. 6521b
25. What is the radix of the numbers if the solution to the quadratic equation x2 lOx + 31 = 0 is x 5 and x 8?
A. 10
B. 11
C. 13
D. None of the above
26. A 3G-bit. floating-point binary number has eight bits plus sign bit for t lie exponent and 26 bits plus sign bit for the mantissa. The mantissa is a normalized fraction. Numbers in the mantissa and exponent arc in signed magnitude representation. The largest and smallest positive quantities that can be represented excluding zero are
A. (2 2(1) x 2125r\ 2 *25(i
B. (1-2 2(i) x 2 *2r,r>, 2 '2r,G
C. (1 - 2-20) x 2+25r\ 2 25r>
D. None of the above
27. Using Karnaugh map. four variable boolean function F(A, Z?, C, D) E(3, 7,11,13. I I. 15) can be simplified to
A. CD f- ABC + ADD
B. ACD 4 BCD -I- ABC + ABD
C. ABC'D + ABC + C'D
D. None of the above
28. Let r - 1(1 ())*, .? 11*0 and t = 1*0 be three regular expressions respectively corresponding to three regular sets R, S and T, then which one of the following is TRUE?
A. 5c/?
B. RcS
C. TcS
D. None of the above
29. Which of the following is (are) FALSE about Context Free Languages?
(1) Context Free Languages are closed under intersection.
(2) Context Free Languages are closed under concatenation.
(3) Context Free Languages are closed under Kleene's closure.
A. (1) only
B. (3) only
C. (1) and (3) only
D. (2) and (3) only
30. Which of the following is (*up) undecidablc problcm(s)?
(1) Determination of ambiguitx of context free grammars.
(2) Given two context free grammars Gi and Q>, determining whether they generate exactly the same language.
(3) Determining whether the language accepted by a Turing machine is finite or infinite.
A. (2) only
B. (1) and (2) only
C. (2) and (3) only
D. (1). (2) and (3)
31. Consider the following jrrammar where A denotes the null string S > aSb
S > bSa SSS S-* A
Which of the following best characterizes the language generated by the above grammar?
A. All strings of the form alb>ak where i + j = k
B. All palindromes over a and b
C. All strings with equal number of as and bs
D. All evcn-lcngth strings of as and Vs
32. In computer networking, an Internet socket or network socket is an endpoint. of a bidirectional inter-process communication flow across an Internet Protocol-based computer network. A socket address combines which of the following?
A. A http URL and an IP address
B. An IP address and a port number
C. An IP address and a proxy address
D. An IP address and a PID (process identifier)
Questions 33 - 34 are based on the following:
In a Distance Vector (DV) routing algorithm each node x maintains a distance vector Dj; where costs of paths from node x to any other node y in the network with N nodes are estimated. Each node then updates its DV based on the DV update from its neighbor v as: Dx(y) = min{c(j:, u) -r l)r(y)}for each node y in N
33. Consider the case when after an update Dx(y) does not change, then it implies that.
A. the algorithm is unstable
B. a path better than a previous estimate is found
C. the algorithm has converged
D. there is neeessarity a count to infinity problem
3-1. Consider the case when after an update Dx(y) has changed, then which of the following art' correct:
(1) The update helps to find a least-cost path from node x to y.
(2) The update needs to be communicated to x's neighbours in an asynchronous fashion.
(3) There is necessarily a count to infinity problem
A. (1) only
B. (2) and (3) only
C. (3) only
D. (1) and (2) only
35. A router software had a bug that set TTL field values to NULL when forwarding IP packets, irrespective of the actual TTL value. How many hops further will these IP packets be forwarded
C. infinity times since TTL is NULL
D. TTL field does not really matter for this
36. Consider the queuing delay in a router buffcr(preceding an outbound link). Suppose all packets arc L bits, the transmission rate is R bps and that N packets arrive I ' the buffer every seconds. The average queuing delay of a packet is
r. IAK 1)
m 11 2
N 2
37. UDP checksum for two 1Gbit numbers: 1110011001100110,1101010101010101 is
A. 0100010001000011
B. 1011101110111100
C. 0011010111110100
D. 1011101110111111
After reading the following passage carefully, answer questions 38 - 40 on the basis of what is stated or implied in the passage.
There was a table set out under a tree in front of the house, and the March Hare and the Hatter were having tea at it: a Dormouse was sitting between them, fast asleep, and the other two were using it as a cushion, resting their elbows on it, and talking over its head. Very uncomfortable for the Dormouse, thought Alice; only as its asleep, I
suppose it doesnt mind."
The table was a large one, but the three were all crowded together at one comer of it. No room! No room! they cried out when they saw Alice coming. Theres plenty of room! said Alice indignantly, and she sat down in a large arm-chair at one end of the table.
38. Who were the three* sitting at one corner of the table?
A. Alice, March Hare and the Hatter
B. March Hare, the Ilatter and the Dormouse
C. March Hare, Dormouse and Alice
D. Dormouse, the Hatter and Alice
39. According to Alice, which of the following is TRUE?
A. Tlieies 110 room at the table
B. Dormouse is talking in its sleep
C. You dont feci uncomfortable sleeping at a table
D. You feel uncomfortable only if you arc awake
*10. Which of the following is TRUE from the above passage?
A. March Hare, t.lie Hat-tor and the Dormouse wanted Alice to join them at the table
B. March Hare and the Hatter are sitting next to one another
C. There arc only three chairs at the table
D. There are only three chairs at one end of the table.
PART B: SHORT ANSWER QUESTIONS (35 Marks) Answer any SEVEN Questions. Each Question carries FIVE Marks.
1. A digital computer has a common bus system for 16 registers of 32 bits each. The bus is constructed with multiplexers.
(a) How many selection inputs are there in each multiplexer?
(b) What size of multiplexers are needed?
(c) How many multiplexers arc there in the bus?
2. The access time of a cache memory is 100ns and that of main memory is 1000ns. It is estimated that 80% of the memory requests are for read and the remaining 20% for write. The hit ratio for read accesscs only is
0.9. A write-through procedure is used.
(a) What is the average access time of the system considering only memory read cycles?
(b) What is the average access lime of the system considering both the read and write requests?
(c) What is the hit ratio taking into consideration the write cycles?
3. The size of a file is 16MB in a file system that uses 2KB as the block size. How many index blocks are needed to store this file in indexed allocation? Assuming the inode structure, how nuiny levels of indexing is needed? How many disk blocks, other than the inode, need to be read to access the 300/* block?
4. Design Push Down Automaton for the language consisting of all words of the form anbrnabn, where m, n > 0 over the alphabet E = {a, 6}. Also provide a context free grammar that generates this language.
5. Show that the following grammar is ambiguous, where A is the start symbol and A is null string:
A > bBaAC
A-> C C->
d
cA
X
6. Prove n*-0 2i+l 2*+2 = (2n+2)l or n
7. Suppose the delete-min algorithm for a min-hcap is carricd out as follows: Delete the root and adjust the heap by moving up the minimum of its child nodes. Continue this operation recursively. Does this algorithm work? Explain.
8. Write an algorithm to find a maximum cost spanning tree, i.e., the spanning tree with highest possible cost. Suppose the edges are sorted according to non-increasing order of their costs and stored in a list. If there are n nodes in the input graph then will the first n 1 edges of this list always be part of the maximum spanning tree? Justify your answer.
9. Suppose that G is a connected planar graph with less than 12 regions and such that each vertex of G has degree > 3. Then prove that G has a region of degree < 4.
10. Consider the following relation STUDY and functional dependencies Fl, F2, F3, F4 and F5.
Relation
STUDY [Stid, Name, Birtlidate, Coursecode, Title, Credits, Dept, Dname, Location, Semester, Marks, Grade]
Functional Dcpcndcncies Fl: {Stid} > {Name, Birth date}
F2: {Coursecode} * {Title, Credits, Dept}
F3: {Dept} > {Dname, Location}
F4: {St.id, Coursecode} > {Semester, Marks, Grade}
F5: {Marks} {Grade}
(a) Find all candidate keys for relation STUDY.
(b) What is the highest normal form of relation STUDY?
(c) Decompose STUDY (if required) into BCNF. For each decomposition you make, identify the normal form of the original and the resulting relations? Give brief justification for each normalization step.
11. In C language, how do you declare and define a two dimensional array D of integers with r rows and c columns dynamically In C language, a two dimensional array M with 4 rows and 6 columns may be declared as a formal parameter to a function as M[ ][G], but not as i\7[4][ ]. Why?
12. A machine uses a 10-bit twos complement representation for integers, and little-endian byte-ordering, this means that the least significant byte* of an integer is stored at the lower address. Determine what, the following program fragment will print:
int x; /* 16 bit signed integer */ char *p = (char *) x = 0x0013;
printf("x is 7,d\n", x); printf ("7.d 7,d\n", p [0] , p [1] ) ;
17
|
Attachment: |
| Earning: Approval pending. |
