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 )
xplain
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