HCU PHD CS MAY 2012
Question 1 
In DBMS the projection operation creates a new table that has
more tuples than the original table
 
more attributes than the original table  
both of A and B above  
none of the above 
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
accessed by a user having correct password  
accessed by one user  
used to hide data
 
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
n+1  
n1  
n  
None of the above 
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 n1 edges are required,because if vertices are not repeated then edge will also be not repeated.
So if each vertex is visited exactly once then to cover those vertices exactly n1 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
one parent  one child  
one parent  many children  
many parents  many children  
both of A and B above only 
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
12, 15, 20, 40,70,25, 4  
12, 20,15, 40, 70, 25, 4  
4, 25,70, 40, 15, 12,20  
4, 12, 15, 20, 25, 40,70 
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.
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 nbit number, how many bits long is N!, approximately?
nlogn  
n!  
2^{n}  
n^{2}  
None of the given option is correct.The correct answer is n*2^n. 
Question 6 Explanation:
Question 7 
Which one of these sorting algorithms involves minimum record swaps during execution on an average?
bubble sort  
insertion sort  
selection sort  
quicksort 
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).
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
Θ(n^{log_2^3})  
Θ(n log n)  
Θ(n)  
Θ(n^{2}) 
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
186.220.255.255  
186.220.248.0  
186.220.248.255  
186.220.8.0 
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
rwxrxx  
rwxrxr  
rwrxrxrx  
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?
MSWindows .exe file  
IUSWindows .com file  
Java Class file  
BNIP Image file 
Question 12 
For which of the following problems can a Turing Machine not be designed?
Find if there exists a sequence of 7 consecutive 7's in the decimal expansion of 22/7  
Find if there exists a sequence of 7 consecutive 7’s in the decimal expansion of π  
Find if there exists a sequence of 7 consecutive 7’s in the quotient obtained by dividing all positive integers less than 10^{64 }by the number 125  
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?
The method fails because we can only show that the two strings are not equal.  
The method fails because we can only show that the two strings are equal.  
The method is OK and works even if the strings are of infinite length.  
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?
In the first case, memory is contiguous while in the second case, memory is not contiguous.  
In the first case, elements may be accessed as a[i] [j], while in the second, they cannot be accessed so.  
In the first case, the array elements are stored in rowmajor order, while in the second they are stored in columnmajor order.  
None of the Above 
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?
Direct Mapping, setAssociative Mapping, Associative Mapping  
setAssociative Mapping, Direct Mapping, Associative Mapping  
Associative Mapping, setAssociative Mapping, Direct Mapping  
None of the Above 
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, setAssociative Mapping, Associative Mapping
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, setAssociative 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)?
n(n+1)/1  
n  
n+1 / 2  
None of the above 
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?
L= ⌊log _{2} n⌋  
L=(n^{2}/4)+1  
L=2^{n}  
None of the above 
Question 17 Explanation:
Question 18 
Which sort will operate in quadratic time relative to the number of elements in the array (on the average)?
Quick Sort  
Merge Sort  
Radix Sort  
Bubble Sort 
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.
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?
the first two use recursive partitioning, while the third uses static treeIike structure  
All of them use recursive partitioning  
the first two use static treelike structure, while the third uses recursive partitioning  
the first two use nested do loop where both loops are bounded by the array size, while the third uses static treelike structure 
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?
15  
12 to 13  
10  
25 
Question 20 Explanation:
Beginning with E it takes n1=4 comparisons to recognize that A is already in its correct position. Sorting S is now reduced to sorting the following sublist with n1=4 letters.
A B C D E
Beginning with E it takes n2 = 3 comparisons to recognize that B in sublist is already in its correct position. Sorting is now reduced to sorting the following sublist with n2=3 letters:
A B C D E
Consequently we have 4 + 3 + 2 + 1 =10
So using Quick sort it takes
C=(n1) + (n2) + (n3) + …. + 2 + 1 = n(n1)/2 = O(n^{2})
=5^{2}
=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.
A B C D E
Beginning with E it takes n2 = 3 comparisons to recognize that B in sublist is already in its correct position. Sorting is now reduced to sorting the following sublist with n2=3 letters:
A B C D E
Consequently we have 4 + 3 + 2 + 1 =10
So using Quick sort it takes
C=(n1) + (n2) + (n3) + …. + 2 + 1 = n(n1)/2 = O(n^{2})
=5^{2}
=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?
logarithmic (with respect to the number of edges)  
linear (with respect to the number of edges)  
quadratic (with respect to the number of edges)  
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:
Hillclimbing  
Bestfirst  
Breadthfirst  
Branchandbound 
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?
0  
1  
10  
20 
Question 23 Explanation:
In every cases the no. of comparisions required for selection sort of n elements is
(n1) + (n2) + (n3) + . . . . . . . . + 1 = n(n1)/2 = 5*4/2 = 10
(n1) + (n2) + (n3) + . . . . . . . . + 1 = n(n1)/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:
Contextfree language  
Contextsensitive language  
Regular language  
Recursively enumerable language 
Question 25 
Consider the following grammar.
S → AB
A→ a
A → BaB
B → bbA
Which of the following statement is FALSE?
The length of every string produced by grammar is even  
No string produced by grammar has an odd number of consecutive b's  
No string produced by the grammar has 3 consecutive a’s  
No string produced by grammar has 4 consecutive b’s 
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.
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++ ;
O(log n)  
O(n log n)  
O(n)  
O(2^{n}) 
Question 26 Explanation:
For i=1, j runs 1 times
For i=2^{1}, j runs 2 times
For i=2^{2}, j runs 2^{2} times
⋮
For i=2^{k}, j runs 2^{k} times
And we know that,
2^{k} = n
So, k = log n
Now order of complexity is,
For i=2^{1}, j runs 2 times
For i=2^{2}, j runs 2^{2} times
⋮
For i=2^{k}, j runs 2^{k} times
And we know that,
2^{k} = 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?
O(1)  
O(n)  
O(log n)  
O(n log n) 
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
14  
88  
12  
6  
None of the given options is correct. 
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.
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 nnode, simple, acyclic, directed graph?
n1  
3n  
^{n}C_{2}  
n(n  1) 
Question 29 Explanation:
The maximum possible number of directed edges in an nnode, simple, acyclic, directed graph is n(n1)/2 which is also can be written as ^{n}C_{2}.
Question 30 
What is the maximum possible number of edges in an nnode, simple, acyclic, undirected graph?
n1  
⌊n/2⌋ * ⌈n/2⌉  
^{n}C_{2}  
n(n  1) 
Question 30 Explanation:
The maximum possible number of edges that can be possible in an nnode, simple ,acyclic ,undirected graph is n1.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*(c * d) + b(c + d)  
a*(c * d) + b*(c + d)  
(a + b)*c + (a + b)*d  
(a* + b)c + (a* + b)d 
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)
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
1 only  
2 nd 3 only  
1,2 and 3  
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
Nonblocking system call  
Asynchronous I/O system call  
Abort system call  
Blocking system call 
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
Using Banker's Algorithm  
Doing a hitwise XOR to pID value  
By allowing a lower priority process to inherit temporarily the priorities of a higher priority process waiting to access the same resource  
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.
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
1 only  
2 only  
1 and 2 only  
2 and 3 only 
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
Addition  
Subtraction  
Product  
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
3, nonplanar  
3, planar  
2, nonplanar  
2, planar 
Question 38 
Answer question 38 using the following reading passage:
In the past ten years, there have been several improvements in mountainclimbing equipment. These improvements have made the sport both safer and more enjoyable for experienced climbers. Despite these improvements, however, the rate of mountainclimbing injuries has doubled in the past ten years.
Which of thc following, if true, best reconciles the apparent discrepancy presented in the passage?
Many climbers, lulled into a false sense of security, use the new equipment to attempt climbing feats of which they are not capable.
 
Some mountainclimbing injuries are caused by unforeseeable weather conditions.  
Mountain climbing, although a dangerous sport, does not normally result in injury to the experienced climber.  
Although the rate of mountainclimbing injuries has increased. the rate of mountainclimbing deaths has not changed. 
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 (19391945) 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?
The rate of expansion in each sector.  
The percentage of employees in each sector who were men  
The attitude of the popular media toward the employment of women in each sector.  
The trend in the wages of men employed in each sector. 
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 (19391945) 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?
Most women who joined the workforce during the Second World War wanted to return to domestic life when the war ended.  
The great majority of women who joined the workforce during the second world war were employed in manufacturing jobs.
 
The end of the second world war was followed by a large scale transfer of women workers from manufacturing to agriculture.
 
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.
Descriptive Solution 
Question 42 
Given the decimal value 16.75, use IEEE 32bit singleprecision standard system to represent this value.
Descriptive Solution 
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 6bit binary machine code that encodes these instructions (each instruction must be 6 bits). provide the details of your encoding (describe your machine code here)
Descriptive Solution 
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 highestorder 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.
Descriptive Solution 
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}
Descriptive Solution 
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.
Descriptive Solution 
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.
Descriptive Solution 
Question 48 
Give the logic circuit using NAND gates for the expression a+b+ c
Descriptive Solution 
Question 49 
Give the structure function of 3 out of 4 system, with subsystem structure functions as f1 , f2, f3 and f4.
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?
Descriptive solution 
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.
Descriptive solution 
There are 51 questions to complete.