Answers are corrected... Previously wrong answers were given to students fellow by others uploaders...
VUHELP Face book Group.
Paper # 1
Today MIDTERM EXAMINATION
Spring 2011
CS301- Data Structures
Question No:1 ( Marks: 1 ) - Please choose one
Which one of the following calling methods does not change the original value of the argument in the calling function?
º None of the given options
º Call by passing the value of the argument
º Call by passing reference of the argument
º Call by passing the address of the argument
Question No: 2 ( Marks: 1 ) - Please choose one
Which one is a self- referential data type?
º Stack
º Queue
º Link list
º All of these
Question No: 3 ( Marks: 1 ) - Please choose one
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: 4 ( 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: 5 ( Marks: 1 ) - Please choose one
“+” is a _________operator.
º Unary
º Binary
º Ternary
º None of the above
Question No: 6 ( Marks: 1 ) - Please choose one
“--” is a _________operator.
º Unary
º Binary
º Ternary
º None of the above
Question No: 7 ( 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: 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
_________ is a binary tree where every node has a value, every node's left sub tree 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: 11 ( 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: 12 ( 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: 21 | ( Marks: 2 ) |
Define Complete Binary tree Answer:
"A complete binary tree is a binary tree with the additional property that every node must have exactly two children if an internal node, and zero children if a leaf node."
| Question No: | ( Marks: 2 ) |
Write APPLIICATION OF BST Answer:
Binary tree is useful structure when two-way decisions are made at each point. Suppose we want to find all duplicates in a list of the following numbers: 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5 This list may comprise numbers of any nature. For example, roll numbers, telephone numbers or voter’s list. In addition to the presence of duplicate number, we
may also require the frequency of numbers in the list. As it is a small list, so only a cursory view may reveal that there are some duplicate numbers present in this list. Practically, this list can be of very huge size ranging to thousands or millions.
| Question No: | ( Marks: 3 ) |
What normally is the sequence of operations while constructing an AVL tree?
Answer:
Basic operations of an AVL tree involve carrying out the same actions as would be carried out on an unbalanced binary search tree, but modifications are precede or followed by one or more operations called tree rotations, wh
| Question No: | (Marks: 3) |
Define the following
The Height of the Tree:
The definition of height of a tree is:
The height of a binary tree is the maximum level of its leaves (also called the depth).
The balance of a node:
The balance of a node is defined as:
The balance of a node in a binary tree is defined as the height of its left subtree minus height of its right subtree.
| Question No: | ( Marks: 5) |
Define
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
| 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?
function.
t that activates the function. the object that activates the function.
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 | page 53 |
► 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
7 12
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?
Question No: 14 ( Marks: 1 ) - Please choose one
Four statements about trees are below. Three of them are correct. Which one is INCORRECT?
-dimensional data structures
the tree
e ordered
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.
Posts
No comments:
Post a Comment