The primary address of the first element of an array is called
1.floor address
2.foundation address
3.first address
4.base address
The main measures for the efficiency of an algorithm are
1.processor and memory
2.complexity and capacity
3.time and space
4.data and space
time factor when determining the efficiency of algorithm is measured by
1.counting micro seconds
2.counting the number of key operations
3.counting the number of statements
4.counting the kilo bytes of algorithm
The space factors when determining the efficiency of algorithm is measured by
1.counting the maximum memorey needed by the algorithm
2.counting the minimum memorey needed by the algorithm
3.counting the average memeory needed by the algorithm
4.counting the maximum disk space needed by the algorithm
Which of the following cases does not exist in complexity theory
1.Best case
2.worst case
3.average case
4.Null case
The worst case occur in linear search algorithm when
1.Itme is some where in the middle of the array
2.item is not in the array at all
3.item is in the list element in the array
4.item is the last element in the array or is not there at all
The complexity of linear search algorithm is
1.O(n)
2.O(log n)
3.O(n2)
4.O(n log n)
The complexity of binary search algorithm is
which of the following data structures is not linear data structure
1.Arrays
2.linked lists
3.both (a) and (b)
4.none of these
The operations of processing each element in the list is known as
1.sorting
2.merging
3.inserting
4.traversal
Linked list are best suited
1.for relatively permanent collection of data
2.for the size of the structure and the data to the strcuture are constantly changing
4.none of the above
the memory address of fifth element of an array can be calculated by the formula
1.LOC ( array[5] = Base (array) + w( 5-lower bound)
2.LOC ( array[5] = Base (array[5] + ( 5 - lowerbound)
3.LOC (array[5] = base [array[4]) + (5 - lower bound)
If h is any hashing function and is used to hash n keya into a table of size m, where n <= m , the
expected number of collections involving a particular key x is
1.less than 1
2.less than n
3.less than m
4.less than m/2
Let A be an adjacency matrix of a graph G, the ijth entry in the matriz A power k gives
1.the number of paths of length is k from vertex vi to vertex vj
2.shortest path of k edges from vertex vi to vertex vj
3.length of a Eulerian path from vertex vi to vj
4.length of a hamiltonian cycle from vertex vi to vj
The OS of a computer may periodically collect all the free memory space to form contiguous block of free space
This is called
1.concatenation
2.garbage collection
3.collision
4.dynamic memory allocation
you have to sort a list L consisting of a sorted list followed by a new randon elements which of the
following sorting methods would be especially suitable for such a task
1.Bubble sort
2.selection sort
3.quick sort
4.Insertion sort
B-trees are generally
1.very deep and marrow
2.very wide and shallow
3.very deep and very wide
4.can not say
A technique for direct search is
1.binary search
2.linear search
3.tree search
4.hashing
If a node having two children is deleted from a binary tree, it is replaced by its
1.inorder performance
2.inorder successor
3.preorder predecessor
The searching technique tht takes O(1) time to find a data
1.linear search
2.binary search
3.hashing
4.tree search
The number of interchanges required to sort 5,1,6,2, and 4 in ascending order using bubble sort is
1.6
2.5
3.7
4.8
the prefix for a string is ABC+-D*, the actual string will be
1.( A - ( B + C)) * D
2.((A - B) + C) * D)
3.(( A + B ) - C ) * D
4.( A + ( B - C )) * D
The post fix from of the expression ( A + B) * ( C * D - E) * F / G is
1.AB + CD * E - FG / * *
2.AB+CD*E - F ** F/
3.AB+CD*E - *F*G/
4.AB+CDE* - *F*G/
The algorithm that will efficiently sort an array that is neatly sorted except for the interchange
of some adjacent pairs of numbers like { 1,3,2,5,4,6} is
1.quick sort
2.bubble sort
3.merge sort
4.selection sort
What is the time required to insert an element in a stack with linked implementation
1.O(log 2 n)
2.O(n)
3.O(n log 2 n )
4.O(1)
Which of the following is false
1.Every time is a bipetite graph
2.A tree consists a cycle
3.A tree with a nodes contain's n-1 edges
4.A tree is a connected graph
For an indirected graph with n vertices and e edges , the sum of the degree of each vertex is
1.2n
2.(2n-1)/2
3.2e
4.e2/2
In worst case , quick sort has order of complexity
1.o(n log n)
2.O( n 2 / 2)
3.O(log n)
4.(n 2 / 4)
A full binary tree with ( 2 n + 1 ) nodes contain
1.n leaf nodes
2.n non leaf nodes
3.(n-1) leaf nodes
4.non-leaf nodes
which two of the following are equivalent for an undirected graph
(i) G is a tree (ii) There is atleast one path between any two distinct vertices of a
(iii) F contains no cycles and has (n - 1 ) edges
1. i and ii
2. ii and iii
3. ii and iv
4.ii and iii
If a node in a BST has two children , then its inorder predecessor has
1.no left child
2.no right child
3.two children
4.no child
A linear list of elements in which deletion can be done from one end ( from) and insertion
can take place only at another end (rear) is known as a
1.queue
2.stack
3.tree
4.linked list
What is the post fix form of the following prefix expression
A/B * C $ D E
1.ABCDE$*/-
2.A-BCDE$*/-
3.ABC$ED*/-
4.A-BCDE$*/
A full binary tree with n leaves contains
1.n nodes
2.log 2 n nodes
3.2 n - 1 nodes
4.2 n nodes
Which of the following sorting algorithms does not have a worst case running time of D(n2)
1.insertion sort
2.merge sort
4.bubble sort
An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time
required to generate all the connected components
2.O(e)
3.O( e + n)
4.O(e 2)
Queue is a __________ list
1.LIFO
2.LILO
3.FILO
4.FIFO
Consider the linked list of n elements. what is the time take to insert an element after the element
printed by some pointer
1.O(1)
2.O(log 2 n)
3.O(n)
4.O(n log 2 n)
In a circular linked list
1.components are all linked together in some sequential manners
2.there is no begining and no end
3.components are arranged hierarchically
4.forward and backward traversal within the list is permitted
In a heap every element is _______ of all the elements in the sub tree
1.maximum
2.minimum
3.sum
4.product
if ( rear == maxmize - 1) rear = 0 , else rear = rear + 1 is required in
1.circular queue
2.linear queue
3.stack
4.dqueue
How much extra space is used by heap sort
1. O(1)
2.O(log n )
4.O(n 2)
The maximum degree of any vertex in a simple graph, with n vertices is
1. n-1
2.n+1
3.2n-1
4.n
The data structure required for breadth first traversal on a graph is
1. queue
3.array
4.tree
The queue sort algoithm explicit ________ design technique
1. greedy
2.dynamic programming
3.divide and conquer
4.back tracking
The number of different directed trees with 3 nodes are
1. 2
2.3
3.4
4.5
One can convert a binary tree into its mirror image by traversing it in
1.inorder
2.preorder
3.postorder
4.anyorder
The data structure required to evaluate a postfix expression is
Which of the following statement is true
1.Every tree is not a bipartite graph
2.A tree does not contain a cycle
3.A tree with nodes contains (n-1) edges
4.A tree is not a connected graph
A tree is not a connected graph
1.depth first order
2.breadth first order
3.topological order
4.linear order
The number of edges in a complete graph of n vertices is
1.n
2.n(n-1) / 2
3.n(n+!) / 2
4.n 2 / 2
The data structure required to check wheather an expression contains balanced paranthesis is
1.stack
2.queue
4.array
A linear collection of data, where element the linear node is given by means of pointer,
is called
1.linked list
2.node list
3.premitive list
Which of the following is true for binary search tree
1.It gives the ascending order for preorder traversal
2.It gives the ascending order for inorder traversal
3.It gives the descending order for postorder traversal
4.It gives the descending order for preorder traversal
Which of the following is true for walk in a graph
1.edges are not repeated
2.edges may be repeated
3.all nodes many be covered
Which one of the following is a physical data structure
1.array
3.stacks
4.tables
What is the time require to insert an element in a stack with linked implementation
3.O(n log 2 n)
binary search tree is an example of
1.divide an conquer technique
2.greedy algorithm
3.back tracking
4.dynamic programming
Which algorithm has same average worst case and best case time
2.maximum of a number
4.fionacci search
Which of the following data structure its used to implement recursion
1.arrays
2.stacks
3.queues
The height of a binary tree with a nodes , in the worst case is
1.O(log n)
3.omega (n log n)
4.omega (n2)
what is the maximum number of nodes in a B-tree of order 10 of depth B
1.111
2.999
3.9999 (n log n)
4.None of these (n2)
A binary tree with 27 nodes has __________ null branches
1.54
2.27
3.26
The time complexity to build a heap of a elements is
Linear probing suffers from a problem known as
1.secondary clustering
2.primary clustering
4.None of these
which of the following can be time sequence of nodes examined in binary search tree
while searching for key 88
1.90,40,65,50,88
2.90,110,80,85,88
3.190,60,90,85,88,
4.65,140,80,70,88
In what tree , for every node the height of its left sub tree and right subtree
differ atleast by one
1.binary search tree
2.AVL tree
3.threaded binary tree
4.complete tree
The initial configuration of queue in a,b,c,d,e is at the front. To get the configuaration
d,c,b,a how many deletions and additions required
1.2 deletions, 3 additions
2.3 deletions, 2 additions
3.3 deletions , 4 additions
4.3 deletions, 3 additions
which traversal technique lists the nodes of a binary search tree in ascending order
1.post order
2.inorder
3.preorder
The smallest number of keys that will force a B-tree of order 9 to have a height 3 is
1.12
2.10
A linked binary tree with a nodes n >= 0 has exactly
1.(2n+1) NULL links
2.(2n-1) NULL links
3.(n+1) NULL links
4.(n-1) NULL links
The bese sorting method, if numbers of swappings done, is the only measure of efficiency is
2.insertion sort
3.selection sort
which one of the following is false about a strictly binary tree
1.A binary tree is called strictly binary tree , if every non leaf node of it has non-empty left and right sub tree
2.A complete binary tree of depth of d is the strictly binary tree all of where leaves are at level d
3.A strictly binary tree with a leaves always contains 2(n-1) nodes
4.All the nodes of strictly binary tree of depth d must be at level d
How many swaps are required to extract the maximum element form the below max-heap
< 16,15,14,6,8,12,13,7>
1.zero
2.1
3.2
4.3
The keys 1,5,28,19,15,20,33,12,17,10 are inserted into a hash table in which collision
resolution is done by chaining. If the hash function , h(k) = k mod 4 and what is the
length of the longest chain
1.1
2.2
3.3
4.4
Given , the hash function h(k) = l mod 3 , what is the numver of collisions to store the following
sequence of keys 15,11,34,10,98,51,37,14,16,47
1.2
3.9
4.7
Let the following circular queue can accomodate maximum six elements with the following data
front = 2 rear =4 queue = L.M.N...
what will happen when odd operation takes place
1.Front =2 queue=... mar =5 L,M,N,O... rear = 3
2.Front =3 rear=4 queue=..... L,M,N,Q....
3.Front =3 rear=4 queue = L,M,N,Q....
4.Front=2 rear =4 queue = L,M,N,O....
what is the postfix form of the following prefix *+ab-ad
1.ab+ad-*
2.ab+d*-
3.ab+ad-
4.ab+*ad-
which of the following data structure is most efficient in terms of both space and time to reverse a string of characters
1.Linked list
which of the following can be the sequence of nodes examined in a binary search tree while searching for key 98
1.100,50,75,60,98
2.100,120,90,95,98
3.200,70,100,96,98
4.75,150,90,80,98
Which of the following is true for a sorting list with a elements
1.insertion in a sorted array takes constant time
2.insertion in a sorted linked list takes constant time
3.searching for a key in a sorted array can be done in O(log n) time
4.searching for a key in a sorted linear linked list can be done in a (log n) time
If a sequence of operations push(1), push(2), pop,push(1), push(2),pop,pop,pop,push(2), pop are performed on a stack
the sequence of popped values are
1.2,2,1,1,2
2.2,2,1,2,2
3.2,1,2,2,1
4.2,1,2,2,2
the way a card game player arranges hits cards as he picks them up one by one , is an
example of
1.bubble sort
3.insertion sort
4.merge sort
which of the following is useful in implementing heap sort
2.set
3.list
4.queue
stack is useful for implementing
1.recursion
2.breadth first search
3.depth first search
4.both (a) and (b)
In a full binary tree, if the transfer of nodes is 15, then the height of the tree is
what is the most appropriate data structure to implement a priority queue
1.heap
2.circular array
3.linked list
4.binary
A chained hash table has an array size of 100. what is the maximum number of entries that
can be placed in the table
1.100
2.200
3.10000
4.There is no upper limit
If a B-tree of order 5 , the following key are inserted as follows
7,8,1,4,13,20,2,6 and 5
how many elements are present in the root of the tree
consider a rooted tree in which every node has atleast three children what is the
minimum number of nodes at level i ( i > 0) o the tree Assume that the root is at level 0
1.3
2.3i
4.3i+1
what is the minimum time complexity of covering a given array of integer into a heap
2.O(n log n)
4.O(n2)
1.Consider the following translation involving two bank accounts x and y
read(x); x := -50 ; write(x); read(y); y := y - 50; write(y)
The constraint that the sum of the accounts x and y should remain constant is that of
1.Atomicity
2.Consistency
3.Isolation
4.Durability
Consider the following two statements
S1: If a candidate is known to be corrupt, then he will not be elected.
S2: If a candidate is kind , he will be elected
Which one of the following statments follows from S1 and S2 as per sound inference rules of logic?
1.If a person is known to be corrupt, he is not kind
2.If a person is not known to be corrupt, he is not kind
3.If a person is kind , he is not known to be corrupt
4.If a person is not kind, he is not known to be corrupt
a software requirements specification (SRS) document should avoid discussing which
one of the following
1.User interface issues
2.Non-functional requirements
3.design specification
4.interfaces with third party software
which one of the following statements is NOT correct about HTTP cookies?
1.A cookie is a piece of code that has the potential to compromise the security of an internet user
2.A cookie gains entry to the user's work area through an HTTP header
3.A cookie has an expiry data and time
4.cookies can be used to track the browsing pattern of a particular site
In the context of abstract-syntax-tree (AST) and control flow graph (CFG) , which one of
the following is TRUE?
1.In both AST and CFG, let mode N2 be the successor of node N!. In the input program,
2.For any input program, neither AST nor CFG will contain a cycle
3.The maximum number of successors of a node in an AST and a CFG depends on the input program
4.Each node in AST and CFG corresponds to at most one statement in the input program
Let R be the relation on the set of positive integers such that aRb if and only if a and b
are distinct and have a common divisor other than 1. which one of the following statement about R is true
1.R is symmetric and reflexive but not transitive
2.R is reflexive but not symmetric and not transitive
3.R is transitive but not reflexive and not symmetric
4.R is symmetric but not reflexive and not transitive
Consider a complete binary tree where the left and the right subtrees of the root are maxheaps.
Click to buy Cosmo's UGC NET Computer Sceince Book
The lower bound for the number of operators to convert the tree to a heap is
1.Ω(log n)
2.Ω(n)
3.Ω(n log n)
4.Ω(n2)
1.P-2, Q-3, R-1, S-4.
2.P-2, Q-1, R-4, S-3.
3.P-2, Q-4, R-1, S-3
4.P-2, Q-3, R-4, S-1.
Identify the correct order in which a server process must invoke the function calls accept,
blind, listen, and recv according to UNIX socket API.
1.Listen, accept, blind , recv
2.blind, listen, accept, recv
3.blind, accept, listen, recv
4.accept, listen, blind recv
Consider the following statements.
I. The complement of every turning decidable language is turning decidable.
II. There exists some language which is in NP but is not turning decidable
III.If L is a language in NP, L is Turning Decidable
Which of the above statements is/are true?
1.only II
2.only III
3.only I and II
4.only I and III
A graph is self-complementary if it is isomorphic to its complement, for all selfcomplementary
graphs on n vertices, n is
1.A multiple of A
2.Even
3.Odd
4.congruent 0 mod 4, or, 1 mod 4
Given below are some algorithms, and some algorithm design paradigms
1.Dijkstra’s shortest path i.Divide and conquer
2.Floyd-warshall algorithm to compute all ii.Dynamic programming
Pairs shortest path
3.Binary search on a sorted array iii.Greedy design
4.Backtracking search on a graph iv.Depth-first search
v. Breadth-first search
1.1-i,2-iii,3-i,4-v.
2.1-iii,2-iii,3-i,4-v.
3.1-iii,2-ii,3-i,4-iv.
4.1-iii,2-ii,3-i,4-v.
Which one of the following assertions concerning code inspection and code walkthrough
is true
1.code inspection is carried out once the code has been unit tested
2.code inspection and code walkthrough are synonyms
3.Adherence to coding standards is checked during code inspection
4.code walkthrough is usually carried out by an independent test team
In a connected graph, a bridge is an edge whose removal discounts a graph, which one of
the following statments is true
1.A tree has no bridges
2.A bridge can not be part of a simple cycle
3.Every edge of a clique with size
4.A graph with bridges cannot have a cycle
The cardinality of the power set of {0,1,2,……,10} is ____________
Ans : 2048
1.Relational calculus is a
1.Procedural language
2.Non-procedural language
3.data definition language
4.high level language
2.In an E-R diagram attributes are represtented by
1.rectangle
2.square
3.ellipse
4.triangle
3.In case of entity integrity , the primary key may be
1.not null
2.null
3.both null & not null
4.any value
4.a collection of data designed to be used by different people is called a/an
1.organization
2.database
3.relationship
4.schema
5.Which of the following is the oldest database model
1.relational
2.hierarchical
3.physical
4.network
6.which of the following schemas does define a view or views of the database for particular users
1.Internal schema
2.conceptual schema
3.physical schema
4.External schema
7.the relationship between DEPARTMENT and EMPLOYEE is a
1.one-to-one relationship
2.one-to-many relationship
3.many-to-many relationship
4.many-to-one relationship
8.An entity is
1.a collection of items in an application
2.a distinct real world item in an application
3.an inanimate object in an application
4.a data structure
9.Pick entities from the following:
(i) vendor
(ii) student
(iii) attends
(iv) km/hour
1.i,ii,iii
2.i,ii,iv
3.i and ii
4.iii and iv
10. A relationship is
1.an item in an application
2.a meaningful dependency between entities
3.a collection of related entities
4.related data
11. pick the relationship from the following
1.a classroom
2.teacher
3.attends
4.cost per dozen
12. pick the meaningful relationship between entities
1.vendor supplies goods
2.vendor talks with customers
3.vendor complains to vendor
4.vendor asks prices
13. The entity set is a
1.collection of different entities
2.collection of related entities
3.set of entities
4.collection of similar entities
14. pick entity set from the following
1.all vendors supplying to an organization
2.vendors and organizations they supply
3.vendors and transporters
4.a vendor supplying to many organizations
15.Attributes are
(i) properties of relationship
(ii) attributed to entities
(iii) properties of members of an entity set
1.i
2.i and ii
3.i and iii
4.iii
16.The attributes of relationship teaches in teacher teaches course should be
1.teacher code, teacher name, dept, phone no
2.course no, course name, semester offered, credits
3.teacher code, course no, semester no
4.teacher code, course no, teacher name, dept, phone no
17.The expansion of E-R diagram is
1.Entity-Relationship diagram
2.Entity-Relative diagram
3.Entity-Relation diagram
4.Entity-Rationalized diagram
18.In an E-R diagram entities are represented by
1.circles
2.rectangles
3.diamond shaped box
4.ellipse
19.In an E-R diagram relationship is represented by
20. Entities are identified from the word statement of a problem by
1.picking words which are adjectives
2.picking words which are nouns
3.picking words which are verbs
4.picking words which are pronouns
21.Relationships are identified from the word statement of a problem by
22.One entity may be
1.related to only one other entity
2.related to itself
3.related to only two other entities
4.related to many other entities
23.By relation cardinality we mean
1.number of items in a relationship
2.number of relationship in which an entity can appear
3.number of items in an entity
4.number of entity sets which may be related to a given entity
24. If an entity appears in only one relationship then it is
1.a 1:1 relationship
2.a 1:N relationship
3.a N:1 relationship
4.a N:M relationship
25. If an entity appears in N relationship then it is
26.If an entity appears in not more thatn 5 relationships then it is a
2.a 1:5 relationship
3.a 5:1 relationship
4.a 5:5 relationship
27. A pilot can fly three types of planes and a plane can be piloted by any qualified
pilot. The pilot-plane type relationship is
1.a N:3 relationship
2.a 3:N relationship
3.a 1:3 relationship
4.a 3:1 relationship
28. A student can take not more than 5 subjects in a semester. The number of
students allowed in a subject in a semester is not more than 40. The student
- subject relationship is
1.5:40
2.40:5
3.N:5
4.40:M
29. A relation is
1.an entity
2.a relationship
3.members of a relationship set
4.members of an entity set or a relationship set
30. Rows of a relation are called
1.tuples
2.a relation row
3.a data structure
4.an entity
31.Normalization is a process of restructuring a relation to
1.minimize duplication of data in a database
2.maximize duplication of data to ensure reliability
3.make it of uniform size
4.allow addition of data
32.Normalization of database is essential to
(i) avoid accidental deletion of required data when some data is deleted
(ii) eliminate inconsistencies when a data item is modified in the database
(iii) allows storage of data in a computer’s disk
(iv) use a database management system
1.i and iii
3.ii and iii
4.ii and iv
33.A relation is said to be in 1NF if
1.there is no duplication of data
2.there are no composite attributes
3.there are only a few composite attributes
4.all attributes are of uniform type
34. A relation is said to be in BCNF when
1.it has overlapping composite keys
2.it has no composite keys
3.it has no multivalued dependencies
4.it has no overlapping composite keys which have related attributes
