MIDTERM EXAMINATION
Spring 2010
CS301- Data
Structures
Time: 60 min
Marks: 38
Question No: 1
( Marks: 1 ) - Please choose one
A
queue where the de-queue operation depends not on FIFO, is called a priority
queue
► False
► True
Question No: 2
( Marks: 1 ) - Please choose one
The
data of the problem is of 2GB and the hard disk is of 1GB capacity, to solve
this problem we should
► Use better data structures
► Increase
the hard disk space
► Use the better algorithm
► Use as much data as we can store on the hard
disk
Question No: 3
( Marks: 1 ) - Please choose one
Consider the function X as under
int X (int&
Value)
{
return Value;
}
Now a and b are integers in a calling function. Which one of
the following is a valid call to the above function X.
► a = X
(b) ;
► a = X
(&b) ;
► a = X
(*b) ;
► None
of the given options
Question No: 4
( Marks: 1 ) - Please choose one
In the call by value methodology, a copy of the object is
passed to the called function.
► False
► True
Question No: 5
( Marks: 1 ) - Please choose one
The tree data structure is a
► Linear
data structure
► Non-linear data structure
► Graphical
data structure
► Data
structure like queue
Question No: 6
( Marks: 1 ) - Please choose one
When should you use a const reference parameter?
► Whenever
the parameter has huge size.
► Whenever
the parameter has huge size, the function changes the parameter within its
body, and you do NOT want these changes to alter the actual argument.
► Whenever
the parameter has huge size, the function changes the parameter within its
body, and you DO want these changes to alter the actual argument.
► Whenever
the parameter has huge size, and the function does not change the parameter
within its body.
Question No: 7
( Marks: 1 ) - Please choose one
Here is the start of a C++ class declaration:
class foo
{
public:
void x(foo f);
void y(const foo f);
void z(foo f) const;
...
Which of the three member functions can alter the PRIVATE
member variables of the foo object that activates the function?
► Only x
can alter the private member variables of the object that activates the
function.
► Only y
can alter the private member variables of the object that activates the
function.
► Only z
can alter the private member variables of the object that activates the
function.
► Two of
the functions can alter the private member variables of the object that
activates the function.
Question No: 8
( Marks: 1 ) - Please choose one
What
is the maximum depth of recursive calls a function may make?
► 1
► 2
► n
(where n is the argument)
► There
is no fixed maximum
Question No: 9
( Marks: 1 ) - Please choose one
Suppose
n is the number of nodes in a complete Binary Tree then maximum steps required
for a search operation are,
► Log2
(n+1) -1
► Log2
(n+1)
► Log2
(n) – 1
► Log2
(n)
Question No: 10
( Marks: 1 ) - Please choose one
In the linked list implementation of the stack class, where
does the push member function places the new entry on the linked list?
► At the
head
► At the
tail
► After
all other entries that are greater than the new entry.
► After
all other entries that are smaller than the new entry.
Question No: 11
( Marks: 1 ) - Please choose one
Suppose we have a circular array
implementation of the queue class, with ten items in the queue stored at data[2] through data[11]. The CAPACITY is 42, i.e., the array has
been declared to be of size 42. Where does the push member function place the
new entry in the array?
► data[1]
► data[2]
► data[11]
► data[12]
Question No: 12
( Marks: 1 ) - Please choose one
The expression AB+C*
is called ?
► Prefix
expression
► Postfix
expression
► Infix
expression
► None
of these
Question No: 13
( Marks: 1 ) - Please choose one
_________ is a binary tree where every node has a value,
every node's left subtree contains only values less than or equal to the node's
value, and every node's right subtree contains only values that are greater
then or equal ?
► Strictly
Binary Tree
► Binary Search tree
► AVL
tree
► All of
these
Question No: 14
( Marks: 1 ) - Please choose one
Consider the following binary search tree (BST):
If node A in the BST is deleted, which two nodes are the
candidates to take its place?
► J and I
► H and E
► D and E
► L and M
Question No: 15
( Marks: 1 ) - Please choose one
Let’s call the node as a that requires re-balancing.
Consider the two cases given below:
1) An insertion into
left subtree of the left child of a
2) An insertion into
right subtree of the right child of a.
Which of the following statement is correct about these two
cases.
1) The insertion occurs outside (i.e., left-left or
right-right) in cases 1 and 2. single rotation can fix the balance in these two
cases.
2) The insertion occurs inside ((i.e., left-left or
right-right) in cases 1 and 2. single rotation cannot fix the balance in these
two cases
Question No: 16
( Marks: 1 ) - Please choose one
We access elements in AVL Tree in,
► Linear
way only
► Non
Linear way only
► Both
linear and non linear ways
► None
of the given options.
Question No: 17
( Marks: 2 )
AVL Tree is,
► Non
Linear data structure
► Linear
data structure
► Hybrid
data structure (Mixture of Linear and Non Linear)
► None
of the given options.
Question No: 18
( Marks: 2 )
How we can delete a node with two Childs in a binary search
tree using its right sub tree.
Question No: 19
( Marks: 2 )
What
is Function Call Stack Give short answer.
Question No: 20
( Marks: 3 )
Explain the two cases in which we apply double rotation in
an AVL tree.
Question No: 21 ( Marks: 3 )
Here is a small binary tree.
Write the order of the nodes visited in
a)
A Post-order traversal
b)
A level-order traversal
Question No: 22
( Marks: 5 )
Please consider the following AVL tree.
1.
Insert new node 87 in this tree and make tree balance.
2.
Write balance factor of each node after and before
inserting node 87.
Question No: 23
( Marks: 5 )
Consider the
following binary tree
Show the
state of the tree after deleting 24.
No comments:
Post a Comment