Sunday, May 20, 2012

UGC NET Computer Science and Application December 2009 Solution

1. If she is my friend and you are her friend, 
then we are friends. Given this, the friend relationship 
in this context is ________________.
(i) Commutative (ii) transitive (iii) implicative (iv) equivalence
(A) (i) and (ii)                                                  (B) (iii) 
(C) (i),(ii),(iii) and (iv)                                   (D) None of these

2. Circle has ________ 
(A) No vertices                                         (B) only 1 vertex 
(C) vertices                                                (D) None of these

8. The highest noise margin is offered by
(A) BICMOS                                              (B) TTL 
(C) ECL                                                       (D) CMOS

9. The answer of the operation (10111)2 * (1110)
in hex equivalence is
(A) 150                                                    (B) 241 
(C) 142                                                     (D) 101011110

10. How many ‘1’ are present in the binary representation of 
3 X 512 + 7 X 64 + 5 X 8 + 3
(A) 8                                                     (B) 9 
(C) 10                                                    (D) 11

11. Recursive functions are executed in a 
(A) First in first out order                         (B) Last in first out order
(C ) Parallel fashion                                    (D) Load Balancing

12. What would be the output of the following program, 
if run from the commandline as “myprog 1 2 3”?
main(int argc,char *argv[])
int i;
(A) 123                                                (B) 6 
(C) Error                                             (D) “123”

13. A ________________ is a special method used to initialize 
the instance variable of a class.
(A) Member function                                 (B) Destructor
 (C) Constructor                                         (D) structure

14. Encapsulation is
(A) Dynamic binding   (B) A mechanism to associate the code and data
(C ) Data abstraction   (D ) Creating new class

15. Which of the statements are true?
I. Function overloading is done at compile time.
II. Protected members are accessible to the member of a derived class.
III. A derived class inherits constructors and destructors
IV. A friend function can be called like a normal function.
V. Nested class is a derived class.
(A) I,II,III                                              (B) II,III,V 
(C) III,IV,V                                            (D) I,II,IV

16. The E-R model is expressed in terms of 
I. Entities
II. The relationship among entitites
III. The attributes of the entities.
IV. Functional relationship.
(A) I,II                                                (B) I,II, IV 
(C) II,II,IV                                         (D) I,II,IV

17. Specialization is ________________process.
(A) top-down                                           (B) bottom up
(C ) both (A) and (B)                               (D) none of these

18. Match the following:
(1) Determinants                  (a) No attributes
(2) Candidate key                 (b) Uniquely identified a row
(3) Non-redundancy            (c ) A constraint between two attributes
(4) Functional dependency (d) Group of attributes on the left hand side of arrow 
of function dependency
(A) 1 – d, 2 – b, 3 – a, 4 – c                      (B) 2 – d, 3 – a, 1- b, 4 – c
(C) 4 – a, 3 – b, 2 – c, 1 – d                      (D) 3 – a, 4 – b, 1 – c, 2 – d

19. A function that has no partial functional 
dependencies is in _____________ form.
(A) 3 NF                                                        (B) 2 NF 
(C) 4 NF                                                        (D) BCNF

20. Which of the following statement is wrong?
I. 2-phase locking protocol suffer from dead lock.
II. Time stamp protocol suffer from more aborts.
III. A block hole in a DFD is a data store with only inbound flows.
IV. Multivalued dependency among attribute is checked at 3 NF level.
V. An entity-relationship diagram is a tool to represent event model.
(A) I ,II,III                                             (B) II,III,IV 
(C) III,IV,V                                           (D) II,IV,V

21. If the number of leaves in a strictly binary tree 
is an odd number, then what can you say with full conviction 
about total number of nodes in a tree? 
(A) It is an odd number.                                          (B) It is an even number.
(C ) It cannot be equal to the number of leaves. (D ) It is always greater than twice the number of leaves.

22. The number of edges in a complete graph of n vertices is
(A) n                                                        (B) n(n-1)/2 
(C ) n(n+1)/2                                           (D) n2/2

23. At a hill station, the parking lot is one long drive way snaking up a hill side. 
ars drive in and park right behind the car in front of them, one behind another.
A car can’t leave until all the cars in front of it have left. Is the parking lot more like 
(A) An array                                                  (B) A stack
(C) A queue                                                  (D) A linked list

24. With regard to linked list, which of the following statement is false ?
(A) An algorithm to search for an element in a singly linked list requires O(n) operations in the worst case. 
(B) An algorithm for deleting the first element in a singly linked list requires o(n) operations in the worst case.
(C ). An algorithm for finding the maximum value in a circular linked list requires o(n) operations.
(D ). An algorithm for deleting the middle node of a circular linked list requires o(n) operations. 

25. A hash function f defined as f(key)=key mod 7, with linear probing used to resolve collisions.
Insert the keys 37,38,72,48,98 and 11 into the table indexed from 0 to 6. What will be the location of 11?
(A) 3                                                    (B) 4
(C ) 5                                                    (D) 6

26. Device on one network can communicate with devices on another network via a 
(A) Hub/switch                                                (B) Utility server
( C) File server                                                 (D) Gateway

27. What is the maximum window size in 
sliding window protocol used in a computer network?
(A) 4                                                                   (B) 8 
(C ) 15                                                                (D) 16

28. Which of the following are Data Link Layer standard?
1. Ethernet 2. HSSI 3. Frame Relay
4. 10-Base T 5. Token Ring
(A) 1,2,3                                               (B) 1,3,5
(C) 1,3,4,5                                            (D) 1,2,3,4,5

29. In case of Bus/Tree topology signal balancing issue is overcome by
(A) Modulation                                                (B) Polling
(C ) Segmentation                                            (D) Strong transmitter

30. Match the following:
(i) Ethernet (a) Deterministic
(ii) Token Ring (b) Utilize the full wire speed
(iii) Cut-through switch (c ) Prevent Looping
(iv) Spanning tree (d) Checking valid address
(A) i-d,ii-a,iii-b,iv-c                                    (B) i-a,ii-d,iii-b,iv-c
(C ) i-d,ii-d,iii-c,iv-b                                   (D) i-d,ii-c,iii-b,iv-a

31. In an absolute loading scheme which loader function is accomplished by assembler?
(A) re-allocation                                  (B) allocation 
(C ) linking                                            (D) loading

32. Which of the following grammar is LR(1)?

33. A shift-reduce parser carries out the actions specified within braces immediately 
after reducing with the corresponding rule of the grammar.
S->xxW[ print “1” ]
S->y [ print “2” ]
W->S2 [ print “3” }, what is the translation of “x x x x y z z”?
(A) 1 1 2 3 1                                            (B) 1 1 2 3 3
(C) 2 3 1 3 1                                            (D) 2 3 3 2 1

34. Context-free Grammar(CFG) can be recognized by
(A) Finite state automata               (B) 2-way linear bounded automata
(C ) push down automata               (D ) Both (B) and (C)

35. Synthesized attribute can be easily simulated by a 
(A) LL grammar                                    (B) Ambiguous grammar
(C ) LR grammar                                   (D) None of the above

36. In the process management Round-robin method is essentially
the pre-emptive version of _______________.
(A) FILO                                          (B) FIFO
(C ) SSF                                            (D) Longest time first

37. A page fault
(A) is an error specific page
(B) is an access to the page not currently in memory
(C ) occur when a page program occur in a page memory.
(D ) page used in the previous page reference.

38. A semaphore count of negative n means (s=-n) 
that the queue contains ___n__________ waiting processes.
(A) n + 1                                         (B) n 
(C) n – 1                                         (D) 0

39. A program is located in the smallest available 
hole in the memory is ______________
(A) best-fit                                             (B) first-bit 
(C ) worst-fit                                         (D ) buddy

40. The unix command used to find out the number of characters in a file is
(A) nc                                                       (B) wc 
(C ) chcnt                                                 (D) lc

41. Software Engineering is a discipline that integrates __________ 
for the development of computer software.
(A) Process                                           (B) Methods
(C ) Tools                                               (D) All

42. Any error whose cause cannot be identified anywhere within the 
software system is called _________________.
(A) Internal error                                        (B) External error
(C ) Inherent error                                      (D) Logic error

43. Recorded software attributes can be used in the following endeavours:
(i) Cost and schedule estimates.
(ii) Software product reliability predictions
(iii )Managing development process
(iv). No where
(A) (i) (ii) (iv)                                                  (B) (ii) (iii) (iv)
(C) (i) (ii) (iii)                                                  (D) (i) (ii) (iii) (iv)

44. Black box testing is done
(A) To show that s/w is operational at its interfaces i.e. input and output.
(B) To examine internal details of code
(C) At client side
(D) None of the above

45. The name of the transaction file shall be provided by the operator 
and the file that contains the edited transactions ready for execution shall be called
(A) Batch.exe                                             (B) Trans.exe
(C ) Opt.exe                                                (D) Edit.exe

46. The single stage network is also called
(A) One sided network                               (B) two sided network
(C ) recirculating network                         (E) pipeline network

47. Analysis of large database to retrieve information is called
(A) OLTP                                                      (B) OLAP 
(C ) OLDP                                                     (D) OLPP

48. Which technology is sometime referred to as wireless cable?
(A) MMDS                                                   (B) ATM 
(C ) LMDS                                                    (D) CDMA

49. Another name of IEEE 802.11 a is ______________
(A) Wi-Max                                                  (B) Fast Ethernet
(C) Wi-fi                                                        (D) 802.11 g

50. The unlicensed National Information Infrastructure 
band operates at the ____________frequency
(A) 2.4 GHz                                                     (B) 5 GHz 
(C ) 33 MHz                                                    (D) 5 MHz

Thursday, May 10, 2012

UGC NET Computer Science and Application December 2006 Solution

Computer Science and Applications
Note :   This paper contains fifty (50) objective-type questions, 
each question carrying two (2) marks. Attempt all of them.

1.   Which of the regular expressions corresponds to this grammar ?
      S → AB/AS, A → a/aA, B → b
     (A)   aa*b +            (B)    aa*b           (C)  (ab)*        (D)   a(ab)*

2.   The proposition ~ q ∨ p is equivalent to :
     (A)                     (B)                      (C)                    (D)

3.   The number of edges in a complete graph with N vertices is equal to :
     (A) N (N−1)       (B) 2N−1           (C) N−1     (D)   N(N−1)/2

4.   Which of the following is not true ?
     (B)    A − B =A ∩ ~ B

5.   If (a2−b2) is a prime number where a and b  belongs to N, then :
     (A) a2−b2=3                                (B) a2−b2=a−b
     (C) a2−b2=a+b                              (D) a2−b2=5
Here, a2-b2=prime
==> (a+b)*(a-b)=some_prime*1
==> a+b=some_prime; a-b must be =1 

6.   The hexadecimal equivalent of (10111)2×(1110)2 is :
     (A) 150                 (B) 241                  (C) 142     (D)   101011110 
7.   An example of a self complementing code is :
     (A) 8421 code                              (B) Gray code
     (C) Excess-3 code                        (D) 7421 code

8.   A sum of products expression can be implemented with __________ logic gates.
     (A) AND − OR                               (B) NAND − OR
     (C) AND − NOT                              (D) OR − AND

9.   The characteristic equation of the D flip-flop is :
     (A)                     (B)    Q=D               (C)  Q=1        (D)   Q=0

10. Which of the following logic is the fastest ?
    (A)    RTL                (B)   ECL             (C)    HTL        (D)    HCL

11. When a function is recursively called, all automatic variables :
    (A)    are initialized during each execution of the function
    (B)    are retained from the last execution
    (C)    are maintained in a stack
    (D)    are ignored

12. Enumeration variables can be used in :
    (A)    search statement like an integer variable
    (B)    break statement
    (C)    preprocessor commands
    (D)    function statement

13. int arr[ ]={1, 2, 3, 4}
    int count;
    incr( ) {return ++count;}
    main( )
        arr[count ++]=incr( );
       printf(“arr[count]=%d\n”, arr[count]);
    The value printed by the above program is :
    (A)    1                  (B)   2               (C)    3              (D)    4

14. When one-dimensional character array of unspecified length is assigned an initial
    value :
    (A)    an arbitrary character is automatically added to the end of the string
    (B)    ‘o’ is added to the end of the string
    (C)    length of the string is added to the end of the string
    (D)    ‘end’ is added to the end of the string
15. The declaration “unsigned u” indicates :
    (A)    u is an unsigned character
    (B)    u is an unsigned integer
    (C)    u is a character
    (D)    u is a string

16. Which possibility among the following is invalid in case of a Data Flow Diagram ?
    (A) A process having in-bound data flows more than out-bound data flows
    (B) A data flow between two processes
    (C) A data flow between two data stores
    (D) A data store having more than one in-bound data flows

17. In DBMS, deferred update means :
    (A) All the updates are done first but the entries are made in the log file later
    (B) All the log files entries are made first but the actual updates are done later
    (C) Every update is done first followed by a writing on the log file
    (D) Changes in the views are deferred till a query asks for a view

18. Which statement is false regarding data independence ?
    (A) Hierarchical data model suffers from data independence
    (B) Network model suffers from data independence
    (C) Relational model suffers only from logical data independence
    (D) Relational model suffers only from physical data independence

19. Which of the following tools is not required during system analysis phase of system
    development life cycle ?
    (A) Case tool                             (B) RAD tool
    (C) Reverse engineering                   (D) None of these

20. Two  phase protocol in a database management system is :
    (A)  a concurrency mechanism that is not deadlock free
    (B)  a recovery protocol used for restoring a database after a crash
    (C)  Any update to the system log done in 2-phases
    (D)  not effective in Database

21. Which algorithm has same average, worst case and best case time ?
    (A) Binary search                         (B) Maximum of n number
    (C) Quick sort                            (D) Fibonacci search

22. Binary search tree is an example of :
    (A) Divide and conquer technique
    (B) Greedy algorithm
    (C) Back tracking
    (D) Dynamic Programming

23. What is the time required to insert an element in a stack 
with linked implementation ?
    (A) O (log2n)           (B) O (n)              (C) O (n log2n)     (D) O (1)

24. The equivalent postfix expression for d (e+ f) +b*c :
    (A)  defbc/++*                     (B)    def+/bc+*
    (C)  def+/bc *+                    (D)    None of these

25. Which one of the following is a physical data structure ?
    (A) Array                          (B) Linked lists
    (C) Stacks                         (D) Tables

26. How many DS1 signals are transported on a DS3 signal ?
    (A) 24                 (B) 672                 (C) 14                (D) 28

27. A 10 BASE-2 network is limited to :
    (A) 20 bytes per data field               (B)  30 stations per segment
    (C) 40 segments                                (D)  50 feet of cable

28. The network is a :
    (A) Class A Network                       (B)  Class B Network
    (C) Class C Network                       (D)  Class D Network

29. The subnet mask
    (A)  Extends the network portion to 16 bits
    (B)  Extends the network portion to 26 bits
    (C)  Extends the network portion to 36 bits
    (D)  Has no effect on the network portion of an IP address

30. The LAPB frame structure and the frame structure of SDLC are :
    (A) Opposite                              (B) Identical
    (C) Reversed                              (D) Non-identical

31. Linking :
    (A) cannot be performed before relocation
    (B) cannot be performed after relocation
    (C) can be performed both before and after relocation
    (D) is not required if relocation is performed

32. Which of the following is the most general phase-structured grammar ?
    (A) Regular                               (B) Context-sensitive
    (C) Context free                       (D) Syntax tree

33. A compiler for a high level language that runs on one machine and produces code for
    a different machine is called :
    (A) Optimizing                          (B) One pass compiler
    (C) Cross compiler                      (D) Multipass compiler

34. The ‘K’ in LR (R) cannot be :
    (A) 0                  (B) 1                 (C)   2     (D)  None of these

35. Peer-hole optimization is a form of :
    (A) loop optimization                   (B)  local optimization  (C) constant folding                    (D)  data flow analysis

36. An operating system is :
    (A) Collection of hardware components (B)   Collection of input-output devices
    (C) Collection of software routines          (D)   All the above

37. ____________ is one of pre-emptive scheduling algorithm.
    (A) Shortest-Job-first                  (B) Round-robin
    (C) Priority based                      (D) Shortest-Job-next

38. A software to create a Job Queue is called ____________ .
    (A) Linkage editor                      (B) Interpreter
    (C) Driver                                    (D) Spooler

39. A permanent database of a general model of compiler is ____________ .
    (A) Identifier table                    (B) Page map table
    (C) Literal table                        (D) Terminal table

40. Loading operating system from secondary memory to primary memory is called
    ____________ .
    (A) Compiling                           (B) Booting   
    (C) Refreshing                          (D) Reassembling

41. Software Cost Performance index (CPI) is given by : 
(A) BCWP /ACWP                               (B)ACWP
 (C) BCWP−ACWP                           (D) BCWP−BCWS
    Where :     BCWP stands for Budgeted Cost of Work Performed
                BCWS stands for Budget Cost of Work Scheduled
                ACWP stands for Actual Cost of Work Performed

42. Software Risk estimation involves following two tasks :
    (A) risk magnitude and risk impact
    (B) risk probability and risk impact
    (C) risk maintenance and risk impact
    (D) risk development and risk impact

43. In a object oriented software design, ‘Inheritance’ is a kind of __________ .
    (A) relationship                     (B) module
    (C) testing                             (D) optimization

44. Reliability of software is directly dependent on :
    (A) quality of the design
    (B) number of errors present
    (C) software engineer’s experience
    (D) user requirement

45. ‘Abstraction’ is ____________ step of Attribute in a software design.
    (A) First                (B) Final           (C) Last             (D)  Middle

46. The frequency band allocated for the downlink in GSM is :
    (A) 960 - 985 MHz                    (B) 935 - 960 MHz
    (C) 920 - 945 MHz                    (D) 930 - 955 MHz

47. Which of the following is an EDI standard ?
    (A) ANSI X.15                        (B) ANSI X.14
    (C) ANSI X.13                         (D) ANSI X.12

48. An INT file in Windows 95 is :
    (A) a program file                   (B)  a message file
    (C) a text file                           (D)  link file

49. Link analysis operation in data mining uses ___________ technique.
    (A) Classification                   (B) Association discovery
    (C) Visualisation                     (D) Neural clustering

50. The maximum size of SMS in IS-95 is ______ octets.
    (A) 120                  (B) 95                  (C) 128              (D)  64

Saturday, May 5, 2012

UGC NET Computer Science and Applications December-2005 Paper- II Solution

Computer Science and Applications December-2005

Note :    This paper contains fifty (50) objective-type questions, each question carrying two (2) marks. Attempt all of them.
1.   T is a graph with n vertices. T is connected and has exactly n-1 edges, then :
     (A)    T is a tree
     (B)    T contains no cycles
     (C)    Every pairs of vertices in T is connected by exactly one path
     (D)    All of these

2.   If the proposition 7P ⇒ Q is true, then the truth value of the proportion 7 PV (P ⇒ Q) is :
     (A)    True                          (B)   Multi - Valued
     (C)    Flase                         (D)   Can not determined

3.   Let A and B be two arbitrary events, then :
     (A)    P(A ∩ B) = P(A) P (B)         (B)   P(P ∪ B) = P(A) + P (B)
     (C)    P(A ∪ B)<=P(A) + P (B)        (D)   P(A/B) = P(A ∩ B) + P (B)

4.   Which sentence can be generated by S → d/bA, A → d/ccA :
     (A)    bccddd       (B) aabccd             (C)   ababccd          (D)  abbbd
* None of these, as there is no symbol 'a' in the production except (A) 
and (A) cant be produced by given productions. May be some printing mistakes 
in the question paper.

5.   Regular expression a+b denotes the set :
     (A)    {a}       (B) {e, a, b}     (C)   {a, b}     (D)  None of these

6.   Which of the following is divisible by 4 ?
     (A)    100101100                     (B)   1110001110001
     (C)    11110011                      (D)   10101010101010
*last 2 digits must be '0'.

7.   A half-adder is also known as :
     (A)    AND Circuit                   (B)   NAND Circuit
     (C)    NOR Circuit                   (D)   EX-OR Circuit

8.  Consider the following sequence of instructions :
    a=a⊕b, b=a ⊕ b, a=b ⊕ a This Sequence
    (A)    retains the value of the a and b
    (B)    complements the value of a and b
    (C)    swap a and b
    (D)    negates values of a and b
I am confused about options. The table before and after operation is like:
Before  After
0   0   0   0
0   1   1   1
1   0   1   1
1   1   0   0
So its neither retains/complements/swap nor negates.
9.  Consider the following circuit :
 to make it a Tautology the "?" should be :
 (A)    NAND gate     (B)   AND gate     (C)    OR gate     (D)  EX-OR gate

10. When an inventor is placed between both inputs of an S-R flip flop, the resulting flip
 flop is :
 (A)    JK flip-flop                  (B)   D-flip-flop
 (C)    T flip-flop                   (D)   None of these

11. What is the output of the following C-program main () :
    {printf(''%d%d%d'', size of (3.14f), size of (3.14), size of (3.141));}
    (A)    444            (B)   4 8 10         (C)    848       (D) 888

None of these are correct. Answer should be 488(tested in visual studio and gcc compiler)

12. The bitwise OR of 35 with 7 in C will be :
    (A)    35           (B)   7       (C)    42        (D) 39

13. Data members and member function of a class by default is respectively :
    (A)    private and public            (B)   public
    (C)    public and private            (D)   private

14. Function over loading done at :
    (A)    Runtime                       (B)   Compile time
    (C)    Linking time                  (D)   Switching from function to function

15. What will be the value of i for the following expression :
    int f=11, i=3 ;
    i+=(f >3) ? i & 2:5 ;
    (A)   2            (B)  5                 (C)    13                (D)   12

16. A schema describes :
    (A)   data elements                 (B)   records and files
    (C)   record relationship           (D)   all of the above

17. One approach to standarolizing storing of data :
    (A)   MIS                           (B)   CODASYL
    (C)   Structured Programing         (D)   None of the above

18. In a relational schema, each tuple is divided in fields called :
    (A)   Relations     (B)   Domains      (C)   Queries   (D)   All the above

19. An embedded printer provides :
    (A)   Physical record key           (B)   An inserted Index
    (C)   A secondary access path       (D)   All the above

20. A locked file can be :
    (A)   accessed by only one user
    (B)   modified by users with the correct password
    (C)   is used to hide sensitive information
    (D)   both (B) and (C)

21. In what tree, for every node the height of its left subtree and right subtree differ at least by one :
    (A)   Binary search tree            (B)   AVL - tree
    (C)   Threaded binary tree          (D)   Complete tree

22. A hash function f defined as f(key)=key mod 7, with linear probing it is used to insert the key 37,38,72,48,98,11,56 into a table index from 0 to 6. What will be the locations of 11 :
    (A)   3            (B)  4                 (C)    5                 (D)   6

23. Consider the graph, which of the following is a valid topological sorting ?
    (A)    ABCD              (B)   BACD                (C)     BADC               (D)   ABDC
I think the given graph has no topological sorting as it contains cycle.
24. The initial configuration of quaue is a, b, c, d. 'a' is at the front. To get the configuration
 d, c, b, a how many deletions and additions required :
 (A)    2 deletions, 3 additions             (B)    3 deletions, 2 additions
    (C)    3 deletions, 4 additions             (D)    3 deletions, 3 additions

25. Which traversal techniques lists the nodes of a binary search tree in ascending order ?
 (A)    post - order                         (B)    in - order
 (C)    pre - order                          (D)    linear – order

26. The data unit in the TCP/IP application Layer is called a __________ .
 (A)    message           (B)   segment             (C)     datagram          (D)    frame

27. Which of following file retrieval methods use hypermedia ?
 (A)    HTML              (B)   Veronica            (C)     WAIS               (D)   HTTP

28. Which of following is an example of a client - server model :
 (A)    DNS         (B)   FTP       (C)    TELNET       (D)   All the above

29. __________ provide a method to recover data that has been delivered but not get
 used :
 (A)    Segmentation                         (B)    Concatenation
 (C)    Transalation                         (D)    Synchronization

30. Encryption and decryption are the functions of the __________ layer of OSI model :
 (A)    transport         (B)   session             (C)     router       (D)   presentation

31. The Register or main memory location which contains the effective address of the
 operand is known as :
 (A)    Pointer                              (B)    Indexed register
 (C)    Special Locations                    (D)    Scratch Pad

32. A Top - down Parse generates :
 (A) Left most derivation                        (B)    Right - most derivation
 (C) Right - most derivation in reverse          (D)    Left - most derivation in reverse

33. A general macroprocessor is an in built function of :
 (A) Loader              (B) Linker              (C) Editor               (D)   Assembler

34. Which of the following is not collision Resolution Technique :
 (A) Hash addressing                       (B) Chainning
 (C) Indexing                              (D) None of these

35. Which activities is not included in the first pass of two pass assembler ?
 (A) build the symbol table
 (B) construct the Intermediate code
 (C) separate memonic opcode and operand field.
 (D) none of these

36. Producer consumer problem can be solved using :
 (A) semaphores                            (B) event counters
 (C) monitors                              (D) all the above

37. If you want to execute more than one program at a time, the systems software that are
 used must be capable of :
 (A) word processing                       (B) virtual memory
 (C) compiling                             (D) multitasking

38. Which of the following checks cannot be carried out on the input data to a system ?
 (A) Consistency check                     (B) Syntax check
 (C) Range check                           (D) All the above

39. Nonmodifiable procedures are called :
 (A) Serially usable procedure             (B)   Concurrent procedure
 (C) Reentrant procedure                   (D)   Topdown procedure

40. Banker's algorithm is used for __________ purpose :
 (A) Deadlock avoidance                    (B) Deadlock removal
 (C) Deadlock prevention                   (D) Deadlock continuations

41. The testing of software against SRS is called :
    (A) Acceptance testing                    (B) Integration testing
    (C) Regression testing                    (D) Series testing

42. The lower degree of cohesion is :
 (A)   logical cohesion              (B)    coincidential cohesion
 (C)   procedural cohesion           (D)    communicational cohesion

43. The Reliability of the software is directly dependent upon :
 (A)   Quality of the design         (B)    Programmer’s experience
 (C)   Number of error               (D)    Set of user requirements

44. Succesive layer of design in software using but ton-up design is called :
 (A)   Layer of Definement           (B)    Layer of Construction
 (C)   Layer of abstraction          (D)    None of the above

45. Sliding window concept of software project management is :
 (A)   Preperation of comprehenciable plan
 (B)   Preperation of the various stages of development
 (C)   Ad-hoc planning
 (D)   Requirement analysis

46. Which of the following transonission media is used in Blue tooth Technology :
 (A)   Radio links                   (B)    Microwave links
 (C)   VSAT Communication            (D)    Fiber – optic

47. Which of the following is a EDI standard ?
 (A)   ANSI X.15   (B)   ANSI X.14      (C)   ANSI X.13    (D) ANSI X.12

48. Analysis of large database to retrive information is called :
 (A)   OLTP              (B)   OLAP               (C)   OLDP           (D) TLPP

49. The cost of the network is usually determined by :
 (A)   Time complexity               (B)    Switching complexity
 (C)   Circuit complexity            (D)    None of these

50. The mechanism with which several uses can share a medium without interference is :
    (A)   Frequency modulation          (B)    Amplitude modulation
    (C)   Multiplexing                         (D)    None of these

Friday, May 4, 2012

MCQ on System Software and Compiler

Q.1   Translator for low level programming language were termed as
         (A) Assembler                   (B) Compiler
         (C) Linker                      (D) Loader
      Ans: (A)

Q.2   Analysis which determines the meaning of a statement once its grammatical structure becomes known is termed as
        (A) Semantic analysis                  (B) Syntax analysis
        (C) Regular analysis                   (D) General analysis
      Ans: (A)

Q.3   Load address for the first word of the program is called
         (A) Linker address origin              (B) load address origin
         (C) Phase library                     (D) absolute library
      Ans: (B)

Q.4   Symbolic names can be associated with
          (A) Information                       (B) data or instruction
          (C) operand                           (D) mnemonic operation
      Ans: (B)

Q.5   The translator which perform macro expansion is called a
          (A) Macro processor                    (B) Macro pre-processor
          (C) Micro pre-processor                 (D) assembler
      Ans: (B)

Q.6   Shell is the exclusive feature of
          (A) UNIX                               (B) DOS
          (C) System software              (D) Application software
      Ans: (A)

Q.7 An assembler is
        (A) programming language dependent.
        (B) syntax dependant.
        (C) machine dependant.
        (D) data dependant.
      Ans: (C)

Q.8  Program generation activity aims at
        (A) Automatic generation of program
        (B) Organize execution of a program written in PL
        (C) Skips generation of program
        (D) Speedens generation of program
     Ans: (A)

Q.9  Which of the following loader is executed when a system is first turned on or restarted
         (A) Boot loader                     (B) Compile and Go loader
         (C) Bootstrap loader                (D) Relating loader
       Ans: (C)

Q.10    A parser which is a variant of top-down parsing without backtracking is
         (A) Recursive Descend.           (B) Operator Precedence.
         (C) LL(1) parser.               (D) LALR Parser.
         Ans: (A)

 Q.11.    In a two-pass assembler, the task of the Pass II is to
          (A) separate the symbol, mnemonic opcode and operand fields.
          (B) build the symbol table.
          (C) construct intermediate code.
          (D) synthesize the target program.
        Ans: (D)

Q.12    A linker program
          (A) places the program in the memory for the purpose of execution.
          (B) relocates the program to execute from the specific memory area
                allocated to it.
          (C) links the program with other programs needed for its execution.
          (D) interfaces the program with the entities generating its input data.
        Ans: (C)

Q.13  Which of these is not a part of Synthesis phase
         (A) Obtain machine code corresponding to the mnemonic from the
        Mnemonics table
         (B) Obtain address of a memory operand from the symbol table
         (C) Perform LC processing
         (D) Synthesize a machine instruction or the machine form of a constant
      Ans: (C)

Q.14 The syntax of the assembler directive EQU is
        (A) EQU
                 (B) EQU

        (C) EQU                         (D) None of the above
      Ans: (B)

Q.15 The following features are needed to implement top down parsing
        (A) Source string marker
        (B) Prediction making mechanism
        (C) Matching and Backtracking mechanism
        (D) All of the above
      Ans: (D)

Q.16  An assembly language is a
         (A) low level programming language
          (B) Middle level programming language
          (C) High level programming language
          (D) Internet based programming language
     Ans: (A)

Q.17    TII stands for
         (A) Table of incomplete instructions
         (B) table of information instructions
         (C) translation of instructions information
         (D) translation of information instruction
     Ans: (A)

Q.18 An analysis, which determines the syntactic structure of the source statement, is
         (A) Sementic analysis            (B) process analysis
         (C) Syntax analysis             (D) function analysis
     Ans: (C)

Q.19   Action implementing instruction’s meaning are a actually carried out by
         (A) Instruction fetch
         (B) Instruction decode
         (C) instruction execution
         (D) Instruction program
     Ans: (C)

Q.20  The field that contains a segment index or an internal index is called
         (A) target datum        (B) target offset
         (C) segment field      (D) fix dat
     Ans: (A)

Q.21   Resolution of externally defined symbols is performed by
         (A) Linker                             (B) Loader
         (C) Compiler                           (D) Editor
       Ans: (A)

Q.22   Relocatable programs
          (A) cannot be used with fixed partitions
          (B) can be loaded almost anywhere in memory
          (C) do not need a linker
          (D) can be loaded only at one specific location
       Ans: (B)

Q.23  Which of the following are language processors?
      (A) Assembler                             (B) Compiler
      (C) Interpreter                           (D) All of the above
        Ans: (D)

Q.24  Recognition of basic syntactic constructs through reductions, this task is performed
     (A) Lexical analysis                       (B) Syntax analysis
     (C) Semantic analysis                     (D) Structure analysis
       Ans: (B)

Q.25   A grammar for a programming language is a formal description of
      (A) Syntax                               (B) Semantics
      (C) Structure                            (D) Code
      Ans: (C)

Q.26  Which of the following is most general phase structured grammar?
       (A) Context – Sensitive                 (B) Regular
       (C) Context – Free                      (D) None of the above
      Ans: (A)
Q.23  Which of the following are language processors?
      (A) Assembler                             (B) Compiler
      (C) Interpreter                           (D) All of the above
        Ans: (D)

Q.24  Recognition of basic syntactic constructs through reductions, this task is performed
     (A) Lexical analysis                       (B) Syntax analysis
     (C) Semantic analysis                     (D) Structure analysis
       Ans: (B)

Q.25   A grammar for a programming language is a formal description of
      (A) Syntax                               (B) Semantics
      (C) Structure                            (D) Code
      Ans: (C)

Q.26  Which of the following is most general phase structured grammar?
       (A) Context – Sensitive                 (B) Regular
       (C) Context – Free                      (D) None of the above
      Ans: (A)

Thursday, May 3, 2012

Graph Theory Notes and Previous years solutions for UGC NET Computer Science & Application

Some Basic Definitions

A simple graph can be thought of as a triple G=(V,E,I), where V and E are disjoint finite sets and I is an incidence relation such that every element of E is incident with exactly two distinct elements of V and no two elements of E are incident to the same pair of elements of V. Obviously, these requirements can be varied (and we get general graphs, hypergraphs, infinite graphs, directed graphs, oriented graphs, etc.). We call V the vertex set and E the edge set of G.
Regular Graph
If all the vertices of G have the same degree k, then G is k-regular , or simply regular . A cubic 3-regular graph is called cubic.
Degree of a vertex
The degree, d(v), of a vertex v is the number of edges with which it is incident. Two vertices are adjacent if they are incident to a common edge. The set of neighbours, N(v), of a vertex v is the set of vertices which are adjacent to v. The degree of a vertex is also the cardinality of its neighbour set.
A digraph (or a directed graph) is a graph in which the edges are directed. (Formally: a digraph is a (usually finite) set of vertices V and set of ordered pairs (a,b) (where a, b are in V) called edges. The vertex a is the initial vertex of the edge and b the terminal vertex.
Informally, a pseudograph is a graph with multiple edges (or loops) between the same vertices (or the same vertex). Formally: a pseudograph is a set V of vertices along, a set E of edges, and a function f from E to {{u,v}|u,v in V}. (The function f shows which vertices are connected by which edge.) An edge is a loop if f(e) = {u} for some vertex u in V.
A loop is an edge that connects a vertex to itself.
A walk is an alternating sequence of vertices and edges, with each edge being incident to the vertices immediately preceding and succeeding it in the sequence.
A trail is a walk with no repeated edges.
A path is a walk with no repeated vertices. A walk is closed if the initial vertex is also the terminal vertex.

The length of a walk is the number of edges in the sequence defining the walk. Thus, the length of a path or cycle is also the number of edges in the path or cycle. If u and v are vertices, the distance from connected graphu to v, written d(u,v), is the minimum length of any path from u to v. In an undirected graph, this is obviously a metric. The eccentricity, e(u), of the vertex u is the maximum value of d(u,v), where v is allowed to range over all of the vertices of the graph. The radius of the graph G, rad(G), is the minimum value of e(u), for any vertex u, and the diameter, diam(G), is the corresponding maximum value. It should be obvious that diam(G) ≤ 2rad(G).

For a set of vertices X, we use G[X] to denote the induced subgraph of G whose vertex set is X and whose edge set is the subset of E(G) consisting of those edges with both ends in X. For a set S of edges, we use G[S] to denote the edge induced subgraph of G whose edge set is S and whose vertex set is the subset of V(G) consisting of those vertices incident with any edge in S. If Y is a subset of V(G), we write G-Y for the subgraph G[V(G)-Y].
Complete Graph
A graph is complete, or a clique, if every pair of distinct vertices is adjacent. (The adjacency matrix of a complete graph has zeroes on the main diagonal, and ones off the diagonal.) We write Km for the complete graph on m vertices. Number of edges = m(m-1)/2
Connected Graph
A non-empty graph G is called connected if any two of its vertices are linked by a path in G. If U ⊆ V (G) and G [ U ] is connected, we also call U itself connected (in G). Instead of ‘not connected’ we usually say ‘disconnected’. A graph G has connectivity k if G is k-connected but not (k+1)-connected. A complete graph on k+1 vertices is defined to have connectivity k.
Bipartite graphs
Let r >2 be an integer. A graph G = (V, E) is called r-partite if V admits a partition into r classes such that every edge has its ends in different classes: vertices in the same partition class must not be adjacent. Instead of ‘2-partite’ one usually says bipartite.
An r-partite graph in which every two vertices from different partition classes are adjacent is called complete; the complete r-partite graphs for all r together are the complete multipartite graphs. Graphs of the form K1,n are called stars; the vertex in the singleton partition class of this K1,n is the star’s centre.

A cycle is a closed trail with at least one edge and with no repeated vertices except that the initial vertex is the terminal vertex.
A circuit is a path which ends at the vertex it begins (so a loop is an circuit of length one).
A graph is acyclic if it has no cycles. An acyclic graph is also called a forest.

Acyclic Graph

An acyclic graph is a graph having no graph cycles.
A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).
The numbers of acyclic graphs (forests) on n =1, 2, ... are 1, 2, 3, 6, 10, 20, 37, 76, 153, ...

A tree is a connected, acyclic graph. Thus every connected component of a forest is a tree.
Spanning tree
A spanning tree of a graph G is a subgraph T of G which is a tree and which satisfies |V(T)|=V|(G)|.
If T is a tree, then |V(T)|=E|(T)|+1. Any tree with at least two vertices must have a vertex of degree one. Alternately, one could define a tree as a connected graph T satisfying |V(T)|=E|(T)|+1 or as an acyclic graph T satisfying |V(T)|=E|(T)|+1. Every connected graph must have a spanning tree.
The number of spanning trees in the complete graph Kn with n vertices is = t(Kn)= nn-2
Minimum Spanning Tree (MST)
A minimum spanning tree (MST) or minimum weight spanning tree is a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of minimum spanning trees for its connected components.
Kruskal's algorithm
Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). Kruskal's algorithm is an example of a greedy algorithm. If E is the number of edges in the graph and V is the number of vertices, Kruskal's algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time
Let G be a graph and v be a vertex of G. The eccentricity of the vertex v is the maximum distance from v to any vertex. That is, e(v)=max{d(v,w):w in V(G)}.
The radius of G is the minimum eccentricity among the vertices of G. Therefore, radius(G)=min{e(v):v in V(G)}.
The diameter of G is the maximum eccentricity among the vertices of G. Thus, diameter(G)=max{e(v):v in V(G)}.
The girth of G is the length of a shortest cycle in G.
The center of G is the set of vertices of eccentricity equal to the radius. Hence, center(G)={v in V(G):e(v)=radius(G)}.
A graph is planar if it can be drawn on a plane so that the edges intersect only at the vertices. (For example, of the five first complete graphs all but the fifth, K5, is planar.)
Hamiltonian path
A Hamiltonian path or traceable path is a path that visits each vertex exactly once. A graph that contains a Hamiltonian path is called a traceable graph. A graph is Hamiltonian-connected if for every pair of vertices there is a Hamiltonian path between the two vertices.
A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that visits each vertex exactly once (except the vertex that is both the start and end, and so is visited twice). A graph that contains a Hamiltonian cycle is called a Hamiltonian graph.
Similar notions may be defined for directed graphs, where each edge (arc) of a path or cycle can only be traced in a single direction (i.e., the vertices are connected with arrows and the edges traced "tail-to-head").
Eulerian Path
An Eulerian trail (or Eulerian path) is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail which starts and ends on the same vertex.
The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs.
For the existence of Eulerian trails it is necessary that no more than two vertices have an odd degree; this means the Königsberg graph is not Eulerian. If there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. A graph that has an Eulerian trail but not an Eulerian circuit is called semi-Eulerian.
Some important things in graph theory
1.The sum of degrees of the vertices of a graph is even
2. Every graph has an even number of odd vertices
    1. If the number of odd vertices is greater than 2 no euler walk exists
    2. If the number of odd vertices is 2, euler walks exist starting at either of the odd vertices
    3. With no odd vertices, euler walks can start at an arbitrary vertex
    4. For a graph, the sum of degrees of all its nodes equals twice the number of edges.
    5. For a graph, the sum of degrees of all its nodes is even

  1. Elements of an edge are said to be incident to that edge.
  2. Likewise, an edge is incident to its elements.
  3. A degree of a vertex is the number of edges incident to it (loops being counted twice).
  4. A vertex of odd (even) degree is said to be odd (even).
  1. A walk v0, e1, v1, e2, ..., vn is said to connect v0 and vn.
  2. A walk is closed if v0n. A closed walk is called a cycle.
  3. A walk which is not closed is open.
  4. A walk is an euler walk if every edge of the graph appears in the walk exactly once.
  5. A graph is connected if every two vertices can be connected by a walk.
1. If a graph has a closed euler walk then every vertex is even.
    2. If every vertex of a connected graph is even, the graph has an euler walk.
    3. If a graph has an open euler walk it has exactly two odd vertices.
    4. If a connected graph has exactly two odd vertices it also has an open euler walk.

Previous year question and answer on graph theory and answer:
1) The graph K3,4 has :
     (A) 3 edges     (B)   4 edges       (C)   7 edges       (D)  12 edges
2) The total number of spanning trees that can be drawn using five labelled vertices is :
     (A) 125                   (B) 64                  (C) 36          (D) 16
3) Which of the following does not define a tree ?
     (A) A tree is a connected acyclic graph.
     (B) A tree is a connected graph with n-1 edges where 'n' is the number of  
         vertices in the graph.
     (C) A tree is an acyclic graph with n-1 edges where 'n' is the number of 
         vertices in the graph.
     (D) A tree is a graph with no cycles.
4) The complexity of Kruskal's minimum spanning tree algorithm on a graph with 'n' nodes and 'e' edges is :
     (A) O (n)         (B) O (n log n)         (C) O (e log n)        (D) O (e)
5) The number of edges in a complete graph with 'n' vertices is equal to :
     (A)    n(n-1)                             (B)n(n-1)/2
     (C)    n2                                 (D)   2n-1
6) Depth travels option of the following directed graph is :

     (A)  ABCDEF                         (B)   ABDEFC
     (C)  ACEBDF                         (D)   None of the above
7) The maximum number of nodes in a binary tree of depth 10 :
     (A) 1024           (B) 210 -1         (C) 1000         (D) None of them
8) The number of edges in a complete graph with N vertices is equal to :
     (A) N (N−1)       (B) 2N−1         (C) N−1      (D)   N(N−1)/2
9) For a complete graph with N vertices, the total number of spanning trees is given by :
     (A) 2N-1       (B) NN-1             (C) NN-2                   (D) 2N+1
10) T is a graph with n vertices. T is connected and has exactly n-1 edges, then :
     (A)    T is a tree
     (B)    T contains no cycles
     (C)    Every pairs of vertices in T is connected by exactly one path
     (D)    All of these
11) Which of the following statement is false ?
    (A)   Every tree is a bipertite graph
    (B)   A tree contains a cycle
    (C)   A tree with n nodes contains n-1 edges
    (D)   A tree is a connected graph
12) The following lists are the degrees of all the vertices of a graph :
     (i)    1, 2, 3, 4, 5                       (ii) 3, 4, 5, 6, 7
     (iii) 1, 4, 5, 8, 6                        (iv) 3, 4, 5, 6
     (A) (i) and (ii)                           (B) (iii) and (iv)
     (C) (iii) and (ii)                         (D) (ii) and (iv)