Cs301- current midterm paper (NOV 2009,10,11,12,)
Subjective Part
Define Reference Variable, Dangling Reference & Const
Answer:
In the C++ programming language, a reference is a simple reference datatype that is lesspowerful but safer than the pointer type inherited from C. The
name C++ reference maycause confusion, as in computer science a reference is a general conceptdatatype, with pointers andC++ references being specific reference datatype implementations
Dangling Reference &Const
Dangling pointers and wild pointers in computer encoding are pointers that do not point to a valid object of the suitable type. These are special cases of violations ofmemory safety
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."
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 ormillions.
What normally is the sequence of operations while constructing an AVL tree? Answer:
Basic operations of an AVL tree involve carrying outthe same actions as would be carried out on an
unbalanced binary search tree, butmodifications are precede or followed by one or more operations called tree rotations.
Define thefollowing
The Height of the Tree:
The definition of height of a tree is:
The height of a binary tree isthe maximum level of its leaves (also called the depth).
The balanceof a node:
The balance of anode is defined as:
The balance of a node in a binary tree is defined as the height of its left subtree minus height ofits right subtree.
Give the names ofbasic Queue Operations
Ans:
Definition: A collection of items in which onlythe 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.
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 onlytwo fundamental operations: push and pop. the data structure itself enforces the proper order of calls.
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
Give shortanswers of the following questions:
1. Why List wastes lessmemory as compared to Arrays. Ans:
1. Linked lists do notneed contiguous blocks ofmemory; 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 becauseInserting 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.
What would the state of a stack be after the following operations?
create stack
push A onto stack push F onto stack push X onto stack pop item from stack push B onto stack pop item from stack pop item from stack
A Remening OnThe Stack
What are the applications of Binary Tree. 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
What is difference between call by reference and call by value? Answer:
One application is to find duplicates in a list of numbers.
Let a given list be" 12 34 56 89 33 11 89
the first number in the list is placed in a node that is established asthe root of a binary tree. Each number is compared with the node in the root, if the number is larger, we search the right sub-tree else we search the left sub-tree. If the sub-tree is empty, the number is not a duplicate and this will be added as a new node.
2. Binary trees can be used for sorting a given list such that, if we take the first number as
root, the numbers less than that number will be transfered to left sub-tree and the greater numbers to right sub-tree.
3. Binary trees are also used for developing the huffman codes.
What is the functionality of the following method of BST class
TreeNode<int>* function(TreeNode<int>* tree)
{
if( tree == NULL )
return NULL;
if( tree->getLeft() == NULL)
return tree; // this is it.
return function( tree->getLeft() );
}
a) Write a C++ statement that declares a valid reference of int i;
b) What is the benefit of reference and where can we use it?
In the last lecture we were discussing about reference variables, we saw three examples; call by value, call byreference and call by pointer. We saw the use of stack when a function is called by value, by reference or bypointer. The arguments passed to the function and local variables are pushed on to the stack. There is one important point to note that in this course, we are using C/C++ but theusage of stack is similar in most of the computer languages like FORTRAN and Java . The syntax we are using here is C++ specific, like we aresending a
parameter by pointer using & sign. In Java, the native data types like int, float are passed by
value and the objects are passed by reference. In FORTRAN, every parameter is passed by reference. In PASCAL, you can pass a parameter byvalue or by reference like C++. You might have heard of ALGOL, this language had provided another wayof passing parameter called call by name. These kinds of topics are covered in subjects like
Determine what the following recursive “mystery” function computes when given a pointer to the root node of a binary tree.
struct bt_s { int key; struct bt_s *left, *right; } bt_t;
int MFunc (bt_t *T) {
int N1, N2;
if (T == NULL) return -1; N1= MFunc(T->left);
N2 = MFunc(T->right);
return (N1 > N2 ? N1 : N2) + 1;
}
Is the given tree is an AVL tree? IfNot then redraw is so that it becomes AVL
