HCU PHD CS MAY 2010

Question 1
The average case time complexity of finding minimum element in a Max-heap having N elements is
A
Θ(N)
B
Θ(logN)
C
O(1)
D
Θ(NlogN)
Question 1 Explanation: 
In max-heap to find the minimum element we have to search the all leaf nodes,because the smallest element in max heap will be present at the leaves.And the no. of leaf nodes in heap tree is approx n/2.Hence average time complexity required to find the minimum element in max-heap is Θ(N).
Question 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, 397, 219, 266, 382, 381, 278, 363
Question 2 Explanation: 




Question 3
It is NOT KNOWN if an NP-complete problem A is such that
A
A Ɛ NP
B
A Ɛ P
C
A Ɛ NP-Hard
D
Circuit-Sat reducible to A.
Question 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
Question 4 Explanation: 
Both insertion and removal of elements in heap take O(logn) time which is better than linear which is O(n) time.
Question 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, - 1)/ 2] < data[i])
C
(i > 0) && (datal(i-1)/2] < data[i])
D
(i > 0) ll (data[(i -1)/2) < data[i])
Question 6
An algorithm has a run time complexity of o(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
Question 6 Explanation: 
We can use the theoretical concept here. Initially when the input size was 1000 the no. of operations required was 110.Now when input size is doubled to 2000, the no. of operations got increased by 10 and became 120. Now again the input size is further doubled to 4000 ,so again the no. of operations will get increased by 10 and the no. of operations will become 130.
Question 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
Question 7 Explanation: 
Priority queue uses heap data structure.
Depth first search uses stack data structure.
Breadth first search uses Queue data structure.
Post order traversal uses tree data structure.
Question 8
Class of languages recognized by finite automata is called as:
A
Context Sensitive languages
B
Recursive Language
C
Regular Language
D
Context free languages
Question 8 Explanation: 
Class of languages recognized by finite automata is called regular language.
Question 9
Given an arbitrary Non-deterministic Finite Automaton (NFA) with N states, the maximum number of states in an equivalent minimized deterministic Finite Automaton (DFA) is at least.
A
N2
B
2N
C
2N
D
N!
Question 9 Explanation: 
The question is wrong .The question should have asked ”the maximum number of states in an equivalent minimized deterministic Finite Automaton (DFA) is at most”.
In DFA any subset of N states can become a new state in DFA and can remain even if the DFA is minimized. No. of subsets possible with N is 2^N.So at max we can have 2^N state in the minimized DFA.
Question 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
Question 10 Explanation: 
Option C is false because context free language is not closed under intersection.
Question 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.
Question 11 Explanation: 
Note that,
(a+b)* = (a*+b*)*= (a+b*)* = (a*+b)* = (a*b*)*
So from above Note it is clear that ,
(01+1)* = ((01)*1*)*
Question 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
Question 12 Explanation: 

Question 13
The number of columns in a table is known as its
A
Range
B
Cardinality
C
Domain
D
Degree
Question 13 Explanation: 
The no. of columns or attributes in a table is known as its degree.
Question 14
To transmit data bits 1011, the correct even parity seven bit Hamming Code is:
A
0101101
B
1010101
C
1100111
D
0110111
Question 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
Question 15 Explanation: 
Symbol table is an important data structure created and maintained by compilers in order to store information about the occurrence of various entities such as variable names, function names, objects, classes, interfaces, etc. Symbol table is used by both the analysis and the synthesis parts of a compiler.
Question 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
Question 16 Explanation: 
Function overloading or method overloading is the ability to create multiple functions of the same name but different argument list.
Question 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
Question 17 Explanation: 
Cyclomatic complexity is a software metric used to indicate the complexity of a program. It is a quantitative measure of the number of linearly independent paths through a program's source code.
Question 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
Question 19
Resolution of externally defined symbols is performed by
A
Linker
B
Compiler
C
Assembler
D
Loader
Question 19 Explanation: 
Symbol resolution is performed by linker.
Question 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
Question 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
Question 21 Explanation: 
In network database model data is organised more like a graph, and are allowed to have more than one parent node.
In this database model data is more related as more relationships are established in this database model. Also, as the data is more related, hence accessing the data is also easier and fast. This database model was used to map many-to-many data relationships.
Question 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
Question 22 Explanation: 


Question 23
Which of the following algorithms can be used to find a spanning tree of a given connected graph G?
A
Breadth First Search
B
Depth First Search
C
Kruskal's Algorithm
D
All of the above
Question 23 Explanation: 
Since nothing is given so we assume the graph with all edges have the same weight. So for this type of graph BFS or DFS or Kruskals algorithm can be used to find the spanning tree and in this type of graph any spanning tree is minimum spanning tree.
Question 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 flame 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.
Question 24 Explanation: 
Segment deals with transport layer.
Frame deals with data link layer.
Datagram deals with network layer
Question 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 at most a single unique address
D
Two for a router and none are really needed for a host
Question 25 Explanation: 
Router is a device which has atleast two interfaces or it connects atleast two different networks.The main work of the router is to send the data packets from one interface to other. Now for each interface it should have an IP address so the router must have atleast two IP address.
A network host is a computer or other device connected to a computer network. A host may work as a server offering information resources, services, and applications to users or other hosts on the network. Hosts are assigned at least one network address.A computer participating in networks that use the Internet protocol suite may also be called an IP host. Specifically, computers participating in the Internet are called Internet hosts. Internet hosts and other IP hosts have one or more IP addresses assigned to their network interfaces
Question 26
Consider the situation where a datagram of 4,000 bytes (where 20 bytes 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?
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
Question 26 Explanation: 
MTU is 1500 bytes out of which 1480 are data bytes and 20 bytes for IP header.
But we have a datagram of size 4000 bytes out of which 3980 are data bytes and 20 bytes for IP header. But MTU is 1480 bytes of data. So we have to fragment the 3980 bytes of data.
Now 3980 bytes of data will be divided into three parts,
1480, 1480, 1020.
So the 1st packet will contain 1480 B of data which will have 0 offset value.
2nd packet will contain 1480 B of data which will have offset value as,
1480/8 = 185
3rd packet will contain 1020B of data which will have offset value as,
185 + 1480/8 = 370
So the router will forward the packet by copying the data into three fragments with each fragment having different offset values and different flag values and same identification number.
Question 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 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
Question 27 Explanation: 
For deadlock to take place there are four condition to be hold:
->Mutual Exclusion
->Hold and wait
->No preemption
->Circular wait
If any of the above four condition gets violated then deadlock cannot occur or deadlock can be prevented.
So letting processes request resources in increasing order of enumeration is an example of deadlock prevention where circular waits for resources can never take place.
Question 28
In TCP congestion control which of the following is MOST CORRECT?
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
Question 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
Question 29 Explanation: 
Rotational latency also called rotational delay, the amount of time it takes for the desired sector of a disk (i.e., the sector from which data is to be read or written) to rotate under the read-write heads of the disk drive.
Question 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
D
300 msecs
Question 30 Explanation: 
None of the the given option is correct.The correct answer is 297 msec
Suppose the index of first cylinder is 1 and the index of last cylinder is 100. Now a seek between adjacent tracks or movement between adjacent tracks takes 3 msecc. And total no. of movements from inner track to outer track is (100 - 1) = 99 movements and each movement timing is 3 msec.Hence total seek time will be 99*3=297 msec.
Question 31

For Questions 31 and 32, use the following table.



The Principal Disjunctive Normal Form (DNF) for f (p,q, r) given in the table is: (Note: A’ means not-of-A)
A
p’q’r + p’qr’ + p’q’r
B
pq’r + p’q’r’ + p’q’r
C
pq’r + p’qr’ + p’q’r’
D
pq’r + p’qr’ + p’q’r
Question 31 Explanation: 
From the table it is clear that the principle DNF for f is
pq’r + p’qr’ + p’q’r
Question 32

For Questions 31 and 32, use the following table.



The simplified equivalent logical expression for g(p,q, r) is:
A
(p ↔qr)’
B
(p → qr)’
C
(p ← qr)’
D
(p ↔ qr)
E
None of the given options is correct.
Question 32 Explanation: 




Question 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.

Il. 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
Question 34

A certain pipelined RISC machine has 8 general-purpose registers R0, R1,. . . , R7 and supports the following operations.

ADD Rs1, Rs2, Rd : Add Rs1 & Rs2 and put the sum in Rd

MUL Rs1, Rs2, Rd : Multiply Rs1 & 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 R0, R1, 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 + BC?
A
5
B
6
C
7
D
8
Question 35

Wrich 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
Question 35 Explanation: 
(I) is true
(II) is false because Non deterministic push down automata is more powerful than deterministic push down automata.
(III) is true
Question 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
Question 36 Explanation: 
The von Neumann bottleneck arises from the fact that CPU speed and memory size have grown at a much more rapid rate than the throughput between them; thus, although memory may hold a lot of data that needs to be processed, and the CPU may be using only a fraction of its computational power, the limited data access speed prevents the computer from doing its work any faster .
Question 37
Accessing disk storage is slower than accessing RAM by an order of
A
10
B
100
C
1000
D
100,000
Question 37 Explanation: 
Accessing disk storage is slower than accessing RAM by an order of 100,000.
Question 38

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 Bacon's "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. Some what 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. Bacon’s four-hundred-word essay, studded with Latin phrases and highly compressed in thought, has intellectual appeal indeed.

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 Bacon’s “Of Studies”
D
The Categorization of Books According to Bacon
Question 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
Question 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 one's writing.
Question 41

Given a list of numbers, for each of the operations listed below, briefly describe an algorithm to implement it and state the algorithm's 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).
A
Descriptive Solution
Question 42
Let G be an undirected graph with 100 vertices numbered 1 to 100. Two vertices e 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).
A
Descriptive Solution
Question 43
TCP uses a timeout / retransmit mechanism to recover from lost segments. Explain the essential concepts of how this timeout value may be estimated.
A
Descriptive Solution
Question 44

Consider the grammar G whose productions are: S → SbS | a

(a) Does the string abababa belong to the language generated by the grammar G?

(b) Is the grammar G ambiguous? Justify your answers.
A
Descriptive Solution
Question 45

What is the value of ft after the following pseudocode has been executed? Please justify your answer clearly.

k =0;

for i1 = 1 to n,

for i2 = 1 to i1,

;

for im = 1 to im-1

k=k+1;
A
Descriptive Solution
Question 46

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).


A
Descriptive solution
Question 47

Write a boolean expression that is equivalent to the circuit diagram given in Figure 1. Please show the intermediate steps clearly.


A
Descriptive solution
Question 48

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.
A
Descriptive Solution
Question 49

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. What 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?
A
Descriptive Solution
There are 49 questions to complete.