MIDTERM EXAMINATION
Fall 2009
CS301- Data Structures (Session -
5)
Ref No: 885482
Time: 60 min
Marks: 38
Question No: 1 ( Marks:
1 ) - Please choose one
Which one of the following is a valid postfix expression?
► ab+c*d-
► abc*+d-
► abc+*d-
► (abc*)+d-
Question No: 2 (
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: 3 (
Marks: 1 ) - Please choose one
A Compound Data Structure is the data structure which can have multiple data items of same type or of different types. Which of the following can be considered compound data structure?
► Arrays
► LinkLists
► Binary Search Trees
► All of the
given options
Question No: 4 (
Marks: 1 ) - Please choose one
Suppose a
pointer has been declared in main but has not assigned any variable address
then
►That pointer points to First byte in main function
►That pointer contains a NULL value
►None of these
►That pointer points to any memory address
Question No: 5 (
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: 6 (
Marks: 1 ) - Please choose one
The operation for removing an entry from a stack is traditionally called:
► delete
► peek
► pop
► remove
Question No: 7 (
Marks: 1 ) - Please choose one
Which statement of the following statements is incorrect?
► Lists can be
implemented by using arrays or linked lists
► A list is a
sequence of one or more data items
► Stack is a special
kind of list in which all insertions and deletions take place at one end
► Stacks are
easier to implement than lists
Question No: 8 (
Marks: 1 ) - Please choose one
Parameters in
function call are passed using,
► Stack
► Queue
► Binary Search
Tree
► AVL Tree
Question No: 9 (
Marks: 1 ) - Please choose one
Consider the following sequence of push operations in a stack:
stack.push(’7’);
stack.push(’8’);
stack.push(’9’);
stack.push(’10’);
stack.push(’11’);
stack.push(’12’);
►7 8 9 10 11 12
►9 8 11 10 7 12
►9 10 8 11 12 7
►9 10 8 12 7 11
Question No: 10 (
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: 11 (
Marks: 1 ) - Please choose one
Consider the following function:
void test_a(int n)
{
cout << n
<< " ";
if (n>0)
test_a(n-2);
}
What is printed by the call
test_a(4)?
► 4 2
► 0 2 4
► 0 2
► 2 4
Question No: 12 (
Marks: 1 ) - Please choose one
Queue follows,
► Last in First
out
► First in Last
out
► First in First out
► 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
Four statements about trees are below. Three of them are correct. Which one is INCORRECT?
►Trees are recursively defined multi-dimensional data
structures
►The order of a tree indicates a maximum number of
childen allowed at each node of the tree
►A search tree is a special type of tree where all
values (i.e. keys) are ordered
►If Tree1's size is greater than Tree2's size, then
the height of Tree1 must also be greater than Tree2's height.
Question No: 15 (
Marks: 1 ) - Please choose one
Below is a
binary search tree. If we delete the value 50 using the algorithm we discussed,
what value will be in the root of the remaining tree?
► 50
► 60
► 70
► 80
Question No: 16 (
Marks: 1 ) - Please choose one
_________ is a
data structure that can grow easily dynamically at run time without having to
copy existing elements.
► Array
► List
► Both of
these
► None of these
Question No: 17 (
Marks: 1 )
Give the names
of basic Queue Operations
Ans:
Definition: A collection of items
in which only the earliest added item may be accessed. Basic operations are add
(to the tail) or enqueue and delete (from the head) or
dequeue. Delete returns the item removed. Also known as "first-in,
first-out" or FIFO.
Question No: 18 (
Marks: 1 )
Give one benefit of using Stack.
In computer science, a stack is a last in, first out (LIFO)
abstract data type and data structure. A stack can have any abstract data type
as an element, but is characterized by only two fundamental operations: push
and pop. the
data structure itself enforces the proper order of calls.
Question No: 19 (
Marks: 2 )
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: 20 (
Marks: 3 )
Consider the following sequence of push operations in a stack:
stack.push(’1’);
stack.push(’2’);
stack.push(’3’);
stack.push(’4’);
stack.push(’5’);
stack.push(’6’);
You can insert as many stack.pop()’s as you like in
the above sequence of stack.push’s to get a desired output. Which of the
following cannot be an output?
A. 123456
B. 325416
C. 342561
D. 342615
E. 342165
Question No: 21 (
Marks: 5 )
Give short answers of the following questions:
1.
Why List wastes less memory as compared to Arrays.
Ans:
1. Linked lists do not need
contiguous blocks of memory; extremely large data sets stored in an array might
not be able to fit in memory.
2. Linked list storage
does not need to be preallocated (again, due to arrays needing contiguous
memory blocks).
3. Inserting or removing
an element into a linked list requires one data update, inserting or removing
an element into an array requires n (all elements after the modified index need
to be shifted).
Array is a collection of same data type. In linked list there are
two field one is address and other is pointer. In array elements are arranged
in a specific order
2.
Why we can change the size of list after its creation when we
can not do that in simple arrays.
Some how the answer will
be same as part 1 because Inserting or removing an element into a linked list
requires one data update, inserting or removing an element into an array
requires n (all elements after the modified index need to be shifted).
Array is a collection of same data type. The size of array is
mentioned with its declaration. in arrays the elements are in contiguous
position. one must after another. while in linked list we gave the address of
next element in the next part of node.
Question No: 22 (
Marks: 10 )
Convert the following infix expression into postfix expressions using stack (Show complete steps)
1-2 33-(4+5*6)*7
Step 1
|
Post fix
|
stack
|
1
|
1
|
|
-
|
-
|
|
2
|
2
|
|
12
|
-
|
|
No comments:
Post a Comment