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
less
powerful but safer than
the pointer type
inherited from C.
The
name C++ reference
may
cause confusion, as in
computer science a reference
is a general concept
datatype, 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 of
memory 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 or
millions.
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.
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.
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.
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.
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 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.
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
On
The 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 as
the 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
by
reference and call
by pointer. We saw the use
of stack when a function is
called by value, by reference or by
pointer. 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
the
usage 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 are
sending 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
by
value or by reference like C++. You
might have heard of ALGOL,
this language had provided another
way
of 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?
If
Not then redraw is so
that it becomes AVL
No comments:
Post a Comment