Dec 2012 Paper III- Part 3

Introduction

UGC NET Exam is one of the popular exams in India for people interested in research. Previous Year Questions are an excellent option to learn about the exam pattern. By solving the PYQs, you will get a basic idea about your preparation. You can evaluate your weak areas and work on them to perform better in the examination. In this article, we have given the questions of UGC NET 2012 December Paper-III. We have also explained every problem adequately to help you learn better.

We have discussed the last 25 questions of the paper and for the other questions you can visit this link December 2012 Paper-III Part-2 and December 2012 Paper-III Part-1.

Questions 51 to 75

51. Suppose there are logn sorted lists of n logn elements each. The time complexity of producing a sorted list of all these elements is (use heap data structure)

 (A) O (n log logn)

 (B) θ (n logn)

 (C) Ω(n logn)

 (D) Ω (n3/2)

Answer: A

Explanation:

Using Heap data structure the idea is to maintain a min-heap of the k lists, each keyed by their smallest current element. A simple algorithm builds an output buffer with nodes from the heap. Start by building a min-heap of nodes, where each node consists of a head element of the list and the rest (or tail) of the list. Because the lists are sorted initially, the head is the smallest element of each list; the heap property guarantees that the root contains the minimum element overall lists. 

Extract the root node from the heap, add the head element to the output buffer, create a new node out of the tail, and insert it into the heap. Repeat until there is only one node left in the heap, at which point just append that remaining list (head and tail) to the output buffer.Hence by finding the time complexity using heap data structure is O (n log logn).

52. Consider the program below in a hypothetical programming language which allows global variables and a choice of static or dynamic scoping

 int i;

 program Main( )

 {

 i = 10;

 call f ( );

 }

 procedure f( )

 {

 int i = 20;

 call g ( );

 }

 procedure g( )

 {

 print i;

 }

 Let x be the value printed under static scoping and y be the value printed under dynamic scoping. Then x and y

are

 (A) x = 10, y = 20

 (B) x = 20, y = 10

 (C) x = 20, y = 20

 (D) x = 10, y = 10

Answer: D

Explanation:

For Static Scoping:

int i;
program main()
{
i = 10;
call f();
}
procedure f()
{
int i = 20;
call g();
}
procedure g()
{
print i;
}

So, 10 is printed

For Dynamic Scoping:

int i;
program main()
{
i = 10;
call f();
}
procedure f()
{
int i = 20;
call g();
}
procedure g()
{
print i;
}

So, 10 is printed for Dynamic Scoping.

53. If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i, then the word w is of length

 (A) no greater than 2i+1

 (B) no greater than 2i

 (C) no greater than 2i–1

 (D) no greater than i 

Answer: C

Explanation:

If a parse tree for a word string w is generated by a CNF and the parse tree has a path length of at most i, then the length of w is at most 2^i-1

          We Know A->BC. , where B,C are variables.

Or   A->a.(terminal)

Whereas Greibach NFA->aV1V2—Vk  where k>=0.

Here A is a terminal and Vi is a variable.

        Consider  the following Chomsky grammar.

A->BC.

B->BC.

C->AC

A->AB.

A->a

B->b

C->c..

While making a parse tree, it is observed that when the path is of length 1. It has the  form like A->a.   its length of word is 1.

When path  is of length 2. It has the form A-> AB->ab. Or Or A->BC->bc. Its length of word is 2.

When path is of length 3. It has the form A->AB->ABBC->abbc its length is of 4.

• So it is generalized as path of length i, word will be of length 2i-1.

54. The Object Modelling Technique (OMT) uses the following three kinds of model to describe a system

 (A) Class Model, Object Model and

Analysis Model.

 (B) Object Model, Dynamic Model,

and Functional Model.

 (C) Class Model, Dynamic Model

and Functional Model.

 (D) Object Model, Analysis Model

and Dynamic Model.

Answer: B

Explanation:

The Object Modelling Technique (OMT) specifies the system's object model or static structure.

Testing physical entities before building them (simulation), communication with consumers, visualisation (alternative display of information), and minimization of complexity are all goals of modelling.

Three sorts of the model is proposed by OMT:

Object model: The static modelled domain is represented by the object model. Classes and associations with properties and operations are the main concepts. Predefined relationships exist between aggregation and generalisation (with multiple inheritances).

Dynamic model: The dynamic model represents the model's point of view. States, transitions between states, and events that generate transitions are the main notions. Modelling actions as occurring within states is possible. Predefined correlations exist between generalisation and aggregation (concurrency).

The functional model: It which is approximately equivalent to data flow diagrams, deals with the model's process perspective. Process, data store, data flow, and actors are the main concepts.

The Unified Modelling Language is a forerunner of OMT (UML).

55. The factors that determine the quality of a software system are

 (A) correctness, reliability

 (B) efficiency, usability, maintainability

 (C) testability, portability, accuracy,

error tolerances, expandability,

access control, audit.

 (D) All of the above

Answer: D

Explanation:

The ISO 9126-1 software quality model identifies 6 main quality characteristics, namely:

Functionality

Reliability

Usability

Efficiency

Maintainability

Portability

56. If a relation with a Schema R is decomposed into two relations R1 and R2 such that (R1  R2) = R1 then which one of the following is to besatisfied for a lossless joint decomposition ( indicates functional dependency)

 (A) (R1 ⋂ R2) ➡ R1 or R1 ⋂ R2 ➡ R2

 (B) R1 ⋂ R2 ➡ R1

 (C) R1 ∩ R2 ➡ R2

 (D) R1 ⋂ R2 ➡ R1and R1⋂  R2 ➡ R2

Answer: A

Explanation:

If we decompose a relation R into relations R1 and R2, All dependencies of R either must be a part of R1 or R2 or must be derivable from a combination of FD's of R1 and R2.

Consider R(A,B,C) and B is the key.

 Let R1==(A,B) AND R2=(B)   So  R1 U  R2 = R1

Definition of Lossless D says that if the intersection of two relation has a common attribute and that is a key in any relation then it is lossless

Now R1 ∩  R2 =B and  B-->R1(because B is the Key) So it is Lossless and it can also be stated as

      R1 ∩ R2 =B..AND  B-->R2  hence it is Lossless

Therefore if we have any one of the above then it is lossless and hence the ans is A option.

57. Given the following statements :

 (i) Recursive enumerable sets are closed under complementation.

 (ii) Recursive sets are closed under complementation.

 Which is/are the correct statements ?

 (A) only (i)

 (B) only (ii)

 (C) both (i) and (ii)

 (D) neither (i) nor (ii)

Answer: B

Explanation:

Recursive languages are closed under the following operations.

The Kleene star L * of L 

The concatenation L * o P of L and P The union L U P The intersection L ∩ P.

58. Skolmization is the process of

 (A) bringing all the quantifiers in the

beginning of a formula in FDL.

 (B) removing all the universal

quantifiers.

 (C) removing all the existential

quantifiers.

 (D) all of the above.

Answer: C

Explanation:

Skolemization is the process of removing all the existential quantifiers . It is one of the steps in conversion  of first order logic sentences into its equivalent  CNF(conjuctive normal form).

59. Which level of Abstraction describes how data are stored in the data base ?

 (A) Physical level

 (B) View level

 (C) Abstraction level

 (D) Logical level

Answer: A

Explanation:

Physical Level

At the physical level, we only know how and where data is stored in memory.Database information on data abstraction using the tree or box line method is provided at the physical level.

Conceptual level 

This level describes the relationships between the stored data.

Logical Level

The logical data abstraction is described at this level.

File option level

This is not a data abstraction of any kind.

60. The transform which possesses the “multi-resolution” property is

 (A) Fourier transform

 (B) Short-time-Fourier transform

 (C) Wavelet transform

 (D) Karhunen-Loere transform

Answer: C

Explanation:

A multi-resolution analysis (MRA) or multi-scale approximation (MSA) is the design method of most of the practically relevant discrete wavelet transforms (DWT) and the justification for the algorithm of the fast wavelet transform (FWT).

61. Which one is a collection of templates and rules ?

 (A) XML

 (B) CSS

 (C) DHTML

 (D) XSL

Answer: D

Explanation:

XSL stands for EXtensible Stylesheet Language, and is a style sheet language for XML documents.Hence XSL is a collection of templates and rules.

62. A program P calls two subprograms P1 and P2. P1 can fail 50% times and P2

40% times. Then P can fail

 (A) 50%

 (B) 60%

 (C) 10%

 (D) 70%

Answer: D

Explanation:

Program P fails when either P1 fails or P2 fails, i.e. failure of P1 + failure of P2.

But this will also contain the case when both P1 and P2 fails at the same time, i.e. failure of P1 ∩ failure of P2, since this case will be already be counted on (P1+P2).

Therefore, our final answer will be failure of P1 + failure of P2 - (failure of P1 ∩ failure of P2)

= (50/100) + (40/100) -(50/100∗40/100)

= (90/100) - (2000/10000)

= (90/100) - (20/100)

= (70/100)

63. Third normal form is based on the concept of ______.

 (A) Closure Dependency

 (B) Transitive Dependency

 (C) Normal Dependency

 (D) Functional Dependency

Answer: D

Explanation:

The third normal form (3NF) is a normal form used in database normalization Codd's definition states that a table is in 3NF if and only if both of the following conditions hold:

• The relation R (table) is in seconfd normal form(2NF)
• Every non-prime attribute of R is non-transitively dependent on every key of R.

A non-prime attribute of R is an attribute that does not belong to any candidate key of R.

A transitive dependency is a functional dependency in which 

X → Z(X determines Z) indirectly, by virtue of X → Y and Y → Z (where it is not the case that Y → X).

64. If the Fourier transform of the function f(x, y) is F(m, n), then the Fourier

transform of the function f(2x, 2y) is :

1. ¼ F(m/2,n/2)
2. 1/4F(2m,2n)
3. 1/4F(m,n)
4. 1/4F(m/4,n/4)

Answer: A

Explanation:

For the function to take a parameter of  2m and returm m, 2m must be multiplied by

 ½ . Therefore the associated frequency function for  f(2x) is  F(1/2m)

To determine the factor by which the frequency changes, recall 

F(ω)=∫+∞−∞f(x)e2πixωdx

Replace  x with  2x. Then, 

F(ω)=∫−∞+∞f(2x)e4πixωdx. Let 

2x=u. Then, 

du/dx=2 or 

dx=du/2.

 Substituting gives 

F(ω)=1/2∫−∞+∞f(u)e2πiuωdu. But this integral is the same as the defining integral for the fourier transform for  f(x) with the x's replaced with u's! Therefore, 

F(ω)=1/2F(ω′). But we know 

ω′=m/2, So F(ω) for f(2x) is  1/2F(m/2). 

By similar argument, for f(2y), 

F(ω)=1/2F(n/2).

Combining the functions gives the fourier transform, for f(2x,2y), as  1/4F(m/2,n/2).

65. ______ establishes information about when, why and by whom changes are

made in a software.

 (A) Software Configuration

   Management.

 (B) Change Control.

 (C) Version Control.

 (D) An Audit Trail.

Answer: D

Explanation:

A record of who has accessed a computer system and what operations he or she has performed over a specified time period. Audit trails can be used to maintain security as well as retrieve lost transactions. An audit trail is included in most accounting and database management systems. There are other distinct audit trail software programs that allow network managers to keep track of how network resources are being used.

66. Match the following with respect to HTML tags and usage.

a. CITE 1. Italic representation

b. EM      2. Represents output from programs

c. VAR   3. Represents to other source

d. SAMP  4. Argument to a programme

 Codes :

       a b c d

 (A) 3 1 4 2

 (B) 2 3 1 4

 (C) 4 2 3 1

 (D) 1 3 4 1 

Answer: A

Explanation:

<cite> tag defines a citation.

<em> tag is a phrase tag. It renders as emphasized text.

<var> defines a variable.

<samp>  defines sample output from a computer program.

Hence Answer is A

67. An expert system shell is an expert system without

 (A) domain knowledge

 (B) explanation facility

 (C) reasoning with knowledge

 (D) all of the above

Answer: A

Explanation:

An expert system is a computer program that simulates the abilities of a human expert to make decisions. The inference engine and the knowledge base are the two subsystems of an expert system. Facts and rules are represented in the knowledge base.

68. An example of a dictionary-based coding technique is

 (A) Run-length coding

 (B) Huffman coding

 (C) Predictive coding

 (D) LZW coding

Answer: D

Explanation:

A dictionary coder, also known as a substitution coder, is a type of lossless data compression method that searches for matches between the text to be compressed and a collection of strings stored in the encoder's data structure (called the 'dictionary'). When the encoder detects a match, it replaces the string's location in the data structure with a reference to the string's position in the data structure.Hence, LZW coding is the correct answer. It uses a dictionary to code the input text.

69. Which is the method used to retrieve the current state of a check box ?

 (A) get State ( )

 (B) put State ( )

 (C) retrieve State

 (D)  write state ()

Answer: A

Explanation:

getState() is the method to get the present state of the checkbox.

70. Referential integrity is directly related to

 (A) Relation key

 (B) Foreign key

 (C) Primary key

 (D) Candidate key

Answer: B

Explanation:

Referential integrity is a database concept that assures the consistency of relationships between tables. When one table has a foreign key to another table, the concept of referential integrity asserts that you can't add a record to the one with the foreign key unless the connected table has a corresponding record. It also provides cascading update and cascading delete procedures, which ensure that changes in the linked table are reflected in the primary table.

71. You are given four images represented

as

I1=   0   0  

        0  0 

I2=   0   1 

        0   0

I3=   0   1 

        1   0

I4=  1   1

       1    0

 The value of entropy is maximum for

image

 (A) I1

 (B) I2

 (C) I3

 (D) I4

Answer: C

Explanation:

Entropy of image represents the randomness in pixels.

In I1 as all pixels are same so the entropy is 0.

In I3 only two pixels are same whereas other two are different.

In I2 and I4  three pixels are same.

Hence value of entropy is maximum for I3

72. A cryptarithmetic problem of the type  

   SEND

+ MORE

_________

 MONEY

 Can be solved efficiently using

 (A) depth first technique

 (B) breadth first technique

 (C) constraint satisfaction technique

 (D) bidirectional technique

Answer: C

Explanation:

In this cryptoarithmetic problem  there are some constraints like 

1) no two alphabets can have same number

2)every number can have values in the range 0-9

by considering these constraints we will solve the above problem which satsify these constraints   like M will be 1 as it is carry and so on

73. Match the following :

a. Supervised learning             1. The decision system receives rewards for its

action at the end of a sequence of steps.

 b. Unsupervised learning        2. Manual labels of inputs are not used.

c. Reinforcement learning        3. Manual labels of inputs are used.

d. Inductive learning                 4. System learns by example

 Codes :

      a b c d

 (A) 1 2 3 4

 (B) 2 3 1 4

 (C) 3 2 4 1

 (D) 3 2 1 4 

Answer: D

Explanation:

Supervised learning and Unsupervised learning both are machine learning task

Basic difference between supervised learning and unsupervised learning is In supervised learning, the output datasets are provided which are used to train the machine and get the desired outputs whereas in unsupervised learning no datasets are provided, instead the data is clustered into different classes .

Reinforcement learning is an area of machine learning inspired by behaviourist psychology, concerned with how software agents ought to take actions in an environment so as to maximise some notion of cumulative reward.

Inductive Learning is a powerful strategy for helping students deepen their understanding of content and develop their inference and evidence-gathering skills. In an Inductive Learning lesson, students examine, group, and label specific "bits" of information to find patterns.

74. A* algorithm is guaranteed to find an optimal solution if

 (A) h' is always 0.

 (B) g is always 1.

 (C) h' never overestimates h.

 (D) h' never underestimates h.

Answer: C

Explanation:

A*  is a computer algorithm that is widely used in path-finding and graph traversal. A* is an informed search algorithm, or a best-first search, meaning that it solves problems by searching among all possible paths to the solution (goal) for the one that incurs the smallest cost (least distance travelled, shortest time, etc.), and among these paths it first considers the ones that appear to lead most quickly to the solution. It is formulated in terms of weighted graphs, starting from a specific node of a graph, it constructs a tree of paths starting from that node, expanding paths one step at a time, until one of its paths ends at the predetermined goal node.

75. Let (x, y, z) be the statement “x + y = z” and let there be two quantifications given as

 (i) ∀x∀y∃zθ(x,y,z)

 (ii) ∃z∀x∀yθ(x,y,z)

 Where x, y, z are real numbers. Then

which one of the following is correct ?

 (A) (i) is true and (ii) is true.

 (B) (i) is true and (ii) is false.

 (C) (i) is false and (ii) is true.

 (D) (i) is false and (ii) is false. 

Answer: B

Explanation:

x+y=z  for all x for all y there exist some Z which will satisfy this equation as e.g x=4351 y=1111 then some Z =5462 is there and so on.

for some z say z=100 there do not exist all x and all y (there exist only some x, y ) which satisfies this equation hence II is false

“Must Recommended Topic, procedure call in compiler design“