HCU PHD CS MAY 2012

Question 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
       Database-Management-System       Relational-Algebra
Question 1 Explanation: 
In DBMS the projection operation creates a new table that has less than or equal no. of tuples and less no. of attributes than the original table.
Question 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
Question 2 Explanation: 
File locking is a mechanism that restricts access to a computer file, or to a region of a file, by allowing only one user or process to modify or delete it in a specific time and to prevent reading of the file while it's being modified or deleted.
Question 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
       Engineering-Mathematics       Graph-Theory
Question 3 Explanation: 
Hamiltonian path is a path in a graph that visits each vertex exactly once.
So if each vertex is visited exactly once then to cover those vertices exactly n-1 edges are required,because if vertices are not repeated then edge will also be not repeated.
Question 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
       Database-Management-System       Schemas
Question 4 Explanation: 
While the hierarchical database model structures data as a tree of records, with each record having one parent record and many children, the network model allows each record to have multiple parent and child records, forming a generalized graph structure.
Question 5
A binary search tree (BST) 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
4, 25,70, 40, 15, 12,20
D
4, 12, 15, 20, 25, 40,70
       Data-Structures       Binary-Trees
Question 5 Explanation: 
The given sequence is,
4, 25, 15, 12, 20, 70, 40
Now let’s draw binary search tree for above sequence,

The post order traversal for above BST is,
12, 20, 15, 40, 70, 25, 4.
Question 6
If N is an n-bit number, how many bits long is N!, approximately?
A
nlogn
B
n!
C
2n
D
n2
E
None of the given option is correct.The correct answer is n*2^n.
       Digital-Logic-Design       Number-Systems
Question 6 Explanation: 
Question 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
       Algorithms       Sorting
Question 7 Explanation: 
Selection sort algorithm involves minimum no. of records swap on an average and also in worst case. In selection sort the average or worst case no. of swaps is O(n).
Whereas in Bubble sort tha average no. of swaps is O(n^2) , in insertion sort it is O(n^2), and in quick sort it is O(nlogn).
Question 8
The solution of the recurrence relation T(n)=3T(n/2)+Θ(n), for n ≥ 2, T(1)=0, is
A
Θ(nlog_2^3)
B
Θ(n log n)
C
Θ(n)
D
Θ(n2)
       Algorithms       Recurrences
Question 8 Explanation: 
Question 9
All IP addresses in the range 186.220 .64.0 to 186.220.71.254 arc kept in a VLAN. The correct netmask so that messages are broadcast 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
       Computer-Networks       IP-Address
Question 9 Explanation: 
Let check option wise,




Question 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
rwrxr-xr-x
D
None of the Above
Question 11
The first four bytes of a binary file are CA , FE, BA, BE (in Hexadecimal, of course!). What type of a file is it?
A
MSWindows .exe file
B
IUSWindows .com file
C
Java Class file
D
BNIP Image file
Question 12
For which of the following problems can a Turing Machine not be designed?
A
Find if there exists a sequence of 7 consecutive 7's in the decimal expansion of 22/7
B
Find if there exists a sequence of 7 consecutive 7’s in the decimal expansion of π
C
Find if there exists a sequence of 7 consecutive 7’s in the quotient obtained by dividing all positive integers less than 1064 by the number 125
D
None of the Above
Question 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
Question 14

In the C Programming Language, arrays can be defined in two ways.

The first is static: int a[4000] [3000] ; the second is dynamic: declare as int **a; and then allocate memory using malIoc(). 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[i] [j], 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
       Programming       Arrays-and-pointers
Question 14 Explanation: 
In the static array a[4000] [3000] the memory is contiguous, but in the dynamic declaration **a the memory is not contiguous because **a is the pointer to the array of pointers which in turn is a pointers to the array.
Question 15
If flexibiLity is defined as having maximum choice in cache placement, 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
       Computer-Organization       Cache
Question 15 Explanation: 
In direct mapping each element has to be put in fix block .
In set associative mapping each element has to be put in fix set which in turn have some no. of blocks.So we can also say that in this type of mapping the element can be placed any of the blocks inside the specific set.
In associating mapping the elements can be placed in the any blocks available.
So the correct order in ascending order of flexibility is
Direct Mapping, set-Associative Mapping, Associative Mapping
Question 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 (n) denote the number of comparisons in the linear search. What is the expected (average) value of f(n)?
A
n(n+1)/1
B
n
C
n+1 / 2
D
None of the above
       Algorithms       Searching
Question 16 Explanation: 

Question 17

Let n denote a positive integer. suppose a function L is defined recursively as follows (here ⌊k⌋ denotes the “floor” of k).



What does L find?
A
L= ⌊log 2 n⌋
B
L=(n2/4)+1
C
L=2n
D
None of the above
       Engineering-Mathematics       Combinatorics
Question 17 Explanation: 


Question 18
Which sort will operate in quadratic time relative to the number of elements in the array (on the average)?
A
Quick Sort
B
Merge Sort
C
Radix Sort
D
Bubble Sort
       Algorithms       Sorting
Question 18 Explanation: 
The average time complexity of quick sort is O(nlogn) which is not quadratic.
The average time complexity of merge sort is O(nlogn) which is not quadratic.
The average time complexity of radix sort is O(nlogn) which is not quadratic.
The average time complexity of quick sort is O(n^2) which is quadratic.
Question 19
Which of the following statements best describes quicksort, Mergesort and Heapsort algorithms, respectively?
A
the first two use recursive partitioning, while the third uses static tree-Iike 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
       Algorithms       Sorting
Question 19 Explanation: 
All the sorting methods above discussed uses recursive partitioning.
Question 20
Suppose s consists of the following n=5 letters in the order: A B C D E. What is the number of comparisons to alphabetically sort S using Quicksort algorithm?
A
15
B
12 to 13
C
10
D
25
       Algorithms       Sorting
Question 20 Explanation: 
Beginning with E it takes n-1=4 comparisons to recognize that A is already in its correct position. Sorting S is now reduced to sorting the following sublist with n-1=4 letters.
A B C D E
Beginning with E it takes n-2 = 3 comparisons to recognize that B in sublist is already in its correct position. Sorting is now reduced to sorting the following sublist with n-2=3 letters:
A B C D E
Consequently we have 4 + 3 + 2 + 1 =10
So using Quick sort it takes
C=(n-1) + (n-2) + (n-3) + …. + 2 + 1 = n(n-1)/2 = O(n2)
=52
=25
Whenever the sequence is sorted either in descending order or ascending order the time complexity of quick sort becomes O(n^2). Since the given sequence of elements is in sorted order ,hence the answer will be approximately n^2 = 5^2 = 25.
Question 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)
Question 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
       Algorithms       Searching
Question 22 Explanation: 
Branch and Bound is an algorithmic technique which finds the optimal solution by keeping the best solution found so far. If partial solution can't improve on the best it is abandoned, by this method the number of nodes which are explored can also be reduced
Question 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
       Algorithms       Sorting
Question 23 Explanation: 
In every cases the no. of comparisions required for selection sort of n elements is
(n-1) + (n-2) + (n-3) + . . . . . . . . + 1 = n(n-1)/2 = 5*4/2 = 10
Question 24
The grammar G = < {S}, {0, 1}, P,S >, where p={S → 0S1, S → 0S, S→ S1, S→ 0 } will generate a:
A
Context-free language
B
Context-sensitive language
C
Regular language
D
Recursively enumerable language
Question 25

Consider the following grammar.

S → AB

A→ a

A → BaB

B → bbA

Which of the following statement is FALSE?
A
The length of every string produced by grammar is even
B
No string produced by grammar has an odd number of consecutive b's
C
No string produced by the grammar has 3 consecutive a’s
D
No string produced by grammar has 4 consecutive b’s
       Theory-of-Computation       Languages-and-Grammars
Question 25 Explanation: 
S ⟶ AB
BaBB (∵ A ⟶ BaB)
bbAaBB (∵ B ⟶ bbA)
bbBaBaBB (∵ A ⟶ BaB)
bbbbAaBaBB (∵ B ⟶ bbA)
bbbbaaBaBB (∵ A ⟶ a)
bbbbaabbAaBB (∵ B ⟶ bbA)
bbbbaabbaaBB (∵ A ⟶ a)
bbbbaabbaabbAB (∵ B ⟶ bbA)
bbbbaabbaabbaB (∵ A ⟶ a)
bbbbaabbaabbabbA (∵ B ⟶ bbA)
bbbbaabbaabbabba (∵ A ⟶ a)
Hence we got the string which contains four consecutive b’s.
Hence option (D) is False.
Question 26

What is the order of complexity of the following program?

sum=0 ;

for(i=1; i<=n; i=i*2)

for(j=1; j<=i; j++)

sum++ ;
A
O(log n)
B
O(n log n)
C
O(n)
D
O(2n)
       Algorithms       Asymptotic-Complexity
Question 26 Explanation: 
For i=1, j runs 1 times
For i=21, j runs 2 times
For i=22, j runs 22 times

For i=2k, j runs 2k times
And we know that,
2k = n
So, k = log n
Now order of complexity is,

Question 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 ord.er of complexity of search?
A
O(1)
B
O(n)
C
O(log n)
D
O(n log n)
       Data-Structures       Data-Structures Linked-List
Question 27 Explanation: 
To search for any element in linked list it will take O(n) time because we might have to traverse complete list in the worst case to get the required element.
Question 28

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

Postorder : 99, 6, 14, 38,-5,-12,44,9,100, 88, 12, 85

In order : 99, 14, 6, 38,44,-5,-12,85,12,9, 88, 100

determine the value of right child of 12
A
14
B
88
C
-12
D
6
E
None of the given options is correct.
       Data-Structures       Binary-Trees
Question 28 Explanation: 
Preorder: 99, 6, 14, 38, -5, -12, 44, 9, 100, 88, 12, 85
Inorder: 99, 14, 6, 38, 44, -5, -12, 85, 12, 9, 88, 100
Now the final tree that can be drawn from given preorder and inorder is,

So clearly from the tree it can be seen that there is no right child for the node 12.
Question 29
what is the maximum possible number of directed edges in an n-node, simple, acyclic, directed graph?
A
n-1
B
3n
C
nC2
D
n(n - 1)
       Engineering-Mathematics       Graph-Theory
Question 29 Explanation: 
The maximum possible number of directed edges in an n-node, simple, acyclic, directed graph is n(n-1)/2 which is also can be written as nC2.
Question 30
What is the maximum possible number of edges in an n-node, simple, acyclic, undirected graph?
A
n-1
B
⌊n/2⌋ * ⌈n/2⌉
C
nC2
D
n(n - 1)
       Engineering-Mathematics       Graph-Theory
Question 30 Explanation: 
The maximum possible number of edges that can be possible in an n-node, simple ,acyclic ,undirected graph is n-1.If we try to any more edges in it then it will form a cycle.
Question 31
Which of the following regular expression is equivalent to (a* + b)*(c + d)?
A
a*(c * d) + b(c + d)
B
a*(c * d) + b*(c + d)
C
(a + b)*c + (a + b)*d
D
(a* + b)c + (a* + b)d
       Theory-of-Computation       Regular-Expression
Question 31 Explanation: 
Option A cant generate string ‘c’ which can be generated by the regular expression in the question.
Option B cant generate string ‘abc’ which can be generated by the regular expression given in question.
Option D cant generate string ‘abbc’ which can be generated by the regular expression given in the question.
Option C is correct answer because
(a + b)*c + (a + b)*d = (a+b)* (c+d) = (a*+b)*(c+d)
Question 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 number 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 the frequency of interrupts
A
1 only
B
2 nd 3 only
C
1,2 and 3
D
None of the Above
Question 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
       Operating-Systems       System-Calls
Question 33 Explanation: 
A blocking system call is a one that suspends or puts the calling process on wait until the event (on which the call was blocked) occurs after which the blocked process is woken up and is ready for execution.
Question 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 hit-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
Question 34 Explanation: 
Priority inversion is a operating system scenario in which a higher priority process is preempted by a lower priority process.
So the priority inversion problem can be resolved by priority inheritance method in which it is allowed for a lower priority process to inherit temporarily the priorities of a higher priority process waiting to access the same resource.
Question 35

Deadlocks can be eliminated using resource preemption, and distributing resources to other processes until the 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
       Operating-Systems       Deadlock
Question 35 Explanation: 
Rollbacks and starvation can be the issues during deadlock elimination using resource preemption,and distributing resources to other processes until the deadlock cycle is broken.
Question 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
Question 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
3, non-planar
B
3, planar
C
2, non-planar
D
2, planar
Question 38

Answer question 38 using the following reading passage:

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 thc following, if true, best reconciles the apparent discrepancy 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.
       Reading-Comprehension       Reading-Comprehension
Question 38 Explanation: 
From the given passage we can conclude that Option A best reconciles the apparent discrepancy presented in the passage.
Question 39

Answer questions 39 and 40 using the following reading passage:

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 farm workers combined to cause the industry to hire more 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 domestic life.

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.
       Reading-Comprehension       Reading-Comprehension
Question 39 Explanation: 
The difference in manufacturing and agricultural sectors in the United States following the Second World War was that the no. of women workers got increased and no. of male workers got decreased.
Question 40

Answer questions 39 and 40 using the following reading passage:

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 farm workers combined to cause the industry to hire more 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 domestic life.

Which of the following statements about women’s employment in the United States during and after the second world war is most 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
Question 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.
A
Descriptive Solution
       Algorithms       Time-Complexity
Question 42
Given the decimal value -16.75, use IEEE 32-bit single-precision standard system to represent this value.
A
Descriptive Solution
       Digital-Logic-Design       Number-Systems
Question 43

We have 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 anv two general purpose registers, put the product in register RESULT.

4. copy the value in register RESULT to any one 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)
A
Descriptive Solution
       Computer-Organization       Machine-Instructions
Question 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.
A
Descriptive Solution
       Computer-Organization       RAM
Question 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 (L) - {W such that W is the reverse of V where V Ɛ L}
A
Descriptive Solution
       Theory-of-Computation       Finite-Automata
Question 46
What exactly do you mean by a recursive language and a recursively enumerable language? Prove that there are languages that are not even recursively enumerable.
A
Descriptive Solution
       Theory-of-Computation       Languages-and-Grammars
Question 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.
A
Descriptive Solution
       Operating-Systems       Deadlock
Question 48
Give the logic circuit using NAND gates for the expression a+b+ c
A
Descriptive Solution
       Digital-Logic-Design       Logic-Gates-and-operators
Question 49
Give the structure function of 3 out of 4 system, with subsystem structure functions as f1 , f2, f3 and f4.
A
Descriptive Solution
Question 50

Suppose relation R(A,B,C,D,E) has the functional dependencies

A→ B

BC → D

BE → C

AD → E

CE → A

What are all the keys of R? Of the five given FDs, which ones violate the BCNF condition?
A
Descriptive solution
       Database-Management-System       Normalization
Question 51
Data Structures is the study of Abstract Data Types (ADT), 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.
A
Descriptive solution
       Data-Structures       Arrays
There are 51 questions to complete.