Data Structures Test
Which of the following applications may use a stack?
a. A
parentheses balancing program
b.
Keeping track of local variables at run time
c.
Syntax analyzer for a compiler
d. All
of the above
You
have implemented a queue with a circular array keeping track of the first item,
the last item, and the count (the number of items in the array). Suppose the
address of the first is zero, and that of the last is CAPACITY-1, what can you
say about the count?
a. The
count must be zero
b. The
count must be CAPACITY
c. The
count can be zero or CAPACITY, but no other value can occur
d. None
of the above
What
do we call a binary tree in which all the levels, except possibly the last
level, have the maximum number of nodes, and in which all the nodes at the last
level appear as far left as possible?
a. Full
binary tree
b.
2-Tree
c.
Threaded tree
d.
Complete binary tree
Which
of the following statements about binary trees is false?
a.
Every Node must have at least two children
b.
Every non-empty tree has exactly one root node
c.
Every node has at the most two children
d. None
of the above
Which
of these is the correct big -Oh expression for 1+2+3+...+n?
a.
O(log n)
b. O(n)
c. O(n
log n)
d. O(n2)
State
whether True or False.
For
all possible inputs, a linear algorithm to solve a problem must perform faster
than a quadratic algorithm to solve the same problem.
a. True
b.
False
What
is the best definition of a collision in a hash table?
a. Two entries are identical except for their
keys
b. Two
entries with different data have exactly the same key
c. Two
entries with different keys have exactly the same hash value
d. Two
entries with exactly the same key have different hash values
Which
of the following formulae in big-Oh notation best represents the expression n2+35n+6?
a. O(n3)
b. O(n2)
c. O(n)
d.
O(42)
The
operation for removing an entry from a stack is traditionally called ___________.
a.
delete
b. peek
c. pop
d.
remove
What
is the maximum number of statements that may be recursive calls in a single
function declaration?
a. 1
b. 2
c. n (n
is the argument)
d. There is no fixed maximum
What
is the minimum number of nodes in a complete binary tree with depth 3?
a. 4
b. 8
c. 11
d. 15
The
number of distinct simple graphs with up to three nodes is ___________.
a. 15
b. 10
c. 7
d. 9
Consider
a linked list implementation of a queue with two pointers: front and rear. The
time needed to insert element in a queue of length n is:
a. O(1)
b.
O(log2n)
c. O(n)
d.
O(n*log2n)
In a
complete binary with k nodes the number of internal nodes are ___________.
a. 2k
b. 2k+1
c. K/2
d. 2K-1
What
is the worst-case scenario for quicksort to sort an array of n elements?
a.
O(log n)
b. O(n)
c. O(n
log n)
d.
O(n2)
Which
of these are standard operations of Stack Data Structure?
a.
Push, delete
b.
Insert, pop
c. Put,
extract
d.
Push, pop
The
number of nodes in the largest maximal independent set of the complete
bipartite graph K(4,2) is___________.
a. 2
b. 3
c. 4
d. 6
A
matrix is called sparse when___________.
a. most
of its elements are non-zero
b. most of its elements are zero
c. all
of its elements are non-zero
d. None
of the above
If
'data' is a circular array of CAPACITY elements and 'last' is an index in that
array, what is the formula for the index after 'last'?
a.
(last % 1) + CAPACITY
b. last
% (1 + CAPACITY)
c. (last + 1) % CAPACITY
d. last
+ (1 % CAPACITY)
For
a complete binary tree with depth d, the total number of nodes is:
a. 2d+1
b. 2d
c.
2d+1-1
d. 2d2
The
linked list implementation of sparse matrices is superior to the generalized
dope vector method because it is ___________.
a. conceptually easier and completely dynamic
b.
efficient if the sparse matrix is a band matrix
c.
efficient in accessing an entry
d. all
of these
How
many real links are required for a sparse matrix having 10 rows, 10 columns and
15 non-zero elements? (Pick the nearest answer)
a. 15
b. 20
c. 50
d. 100
What
is true of the complete bipartite graphs K(3,3) and K(2,4)?
a. Both
are planar
b.
Neither is a planar
c. Both
are isomorphic
d. None
of these
Which
of the following stack operations could result in a stack underflow?
a.
is_empty
b. pop
c. push
d. Two or more of the above answers
A
given connected graph G is a Euler graph if and only if all vertices of G are
of ___________.
a. the same degree
b. even
degrees
c. odd
degrees
d.
different degrees
What
kind of list is the best to answer questions such as "Which is the item at
position n?"
a.
Lists implemented with an array
b. Doubly-linked lists
c. Singly-linked
lists
d.
Doubly-linked or singly-linked lists are equally good
Let
A be a sorted array of n=10 elements. Assume that only one comparison is
required to determine whether the target is equal to, less than, or greater
than A[i]. Which of the following denotes the average successful time of
finding an arbitrary element x in A using the binary search?
a. 1.6
b. 2.9
c. 4.2
d. 5.5
What
will happen if in data structure a pop operation on the stack causes the stack
pointer to move past the origin of the stack?
a.
Overflow
b.
Underflow
c. Null
d.
Garbage collection
You
have implemented a queue with a linked list keeping track of a front pointer
and a rear pointer. Which of these pointers will you change during an insertion
in the middle of a NONEMPTY queue?
a.
Neither of them changes
b. Only
front_ptr changes
c. Only
rear_ptr changes
d. Both
change
Tree
algorithms typically run in time O(d) . What is d?
a. The depth of the tree
b. The
number of divisions at each level
c. The
number of nodes in the tree
d. The
total number of entries in all the nodes of the tree
What
is the worst-case scenario for heapsort to sort an array of n elements?
a.
O(log n)
b. O(n)
c. O(n
log n)
d. O(n2)
A
binary search tree is generated by inserting the following integers in the
order: 50,15,62,5,20,58,91,3,8,37,60,24. How many nodes are in the left and
right subtrees, respectively?
a. (4,7)
b. (7,4)
c. (8,3)
d. (3,8)
Which
of the operations is simpler in the doubly linked list than it is in the simple
linked list?
a. Insertion
b. Deletion
c. Both a and b
d. None
of the above
The
hashing function which dynamically adapts to changes in the table being
accessed is called ___________.
a. Real
b. Linear
c. Partial
d. Virtual
Which
of the following is false?
a. A
binary search begins with the middle element in the array
b. A
binary search continues halving the array either until a match is found or
until there are no more elements to search
c. If
the search argument is greater than the value located in the middle of the array/sub-array,
the binary search continues in that half of the array/sub-array whose all
elements are smaller than the middle element.
A
circuit which is a connected graph and which includes every vertex of the graph
is known as ___________.
a. Euler
b. Unicursal
c. Hamiltonian
d. Clique
If h
is the depth of the tree, which formula will be used to find the maximum number
of nodes n in a perfect binary tree?
a. 2h +
1 - 1
b. 2h +
1
c. 2h
d. 2h +
1 + 1
The
post-order traversal of a binary tree starts with:
a. Post-order traversal of the left sub tree
b. Post-order
traversal of the right sub tree
c. Post-order
traversal of the root
d. Post-order
traversal of the lowest node
Which
of the following techniques is used to resolve collision in hashing?
a. Separate
chaining
b. Open
addressing
c. Linear
probing
d. All of the above
Which
of the following operations is more expensive in the dynamically created linked
list than it is in the conventional array?
a. Finding
Kth element
b. Insertion
c. Deletion
d. Traversing