Asian School of Management and Technology

How queue can be considered as an ADT?
An ADT is a set of value, well defined set of properties of values and set of operation needed for the processing of these values. A queue can be expressed as an ADT as :

Values: order list and item.
Properties: Items are added or deleted
Operations: If queue is empty add items and if queue is full delete items

Define bio O notation.
When we have only asymptotic upper bound then we use O notation. A function f(x)=O(g(x)) iff there exists two positive constant C and X₀.

Differentiate between iteration and recursion.

Recursion	Iteration
Recursion achieves repetition through repeated method calls	iteration explicitly uses repetition structure
Recursion terminates when a base case is recognized.	Iteration terminates when the loop continuation condition fails
Return value to the calling function	Does not returns value.

Define heapify operation with example.

Rearrange a heap to maintain the heap property, that is, the key of the root node is more extreme (greater or less) than or equal to the keys of its children. If the root node’s key is not more extreme, swap it with the most extreme child key, then recursively heapify that child’s subtree. The child subtrees must be heaps to start.

Define slack with suitable example.

The slack of edge (s,a)=2
The slack of edge (s,b)=0
Write the partition strategy of quick sort.

Set left pointer at beginning and right pointer at end
Increment left pointer until the element of pointer location is not greater then pivot or end of list.
Decrease the right pointer until the element at pointer location is not less than pivot
If L<R interchange elements at L and R position.
If L>R interchange pivot with right pointer.

What is tree traversal?
The tree traversal is a way in which each node in the tree is visited exactly once. There are three method of tree method of tree traversal.

Preorder traversal
In-order traversal
Post order traversal

Write the advantages of binary search over the linear search.

It is fast technique, all the elements should not access.
Less time consuming process and less step required.

What is shortest path problem? Explain.
The problem of finding the shortest path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.
Define transport network with suitable example.
Transport network is a connected directed graph G=(V,E) that doesnot contains any loops such that:

Exactly two distinguished vertices source and destination.
There is non-negative real value function.

Group B

Exercise Problems:

Write a java class to implement stack with push and pop functions.

class stack{
int data, maxsize=10;
int item[]=new int[maxsize];
stack top;
stack(){
top=-1;
}
}
void pushoperation(int data)
{
if (top==maxsize=1)
{
System.out.println(“Stack is full”);
}
else
{
top=top+1;
item[top]=data;
}
}
void popoperation(int data)
{
if(top==-1)
{
System.out.println(“Stack is empty”);
}
else
{
data=item[top];
top=top-1;
System.out.println(“Deleted element is:”+data);
}
}
Write a method to insert a node in circular doubly linked list end. Also make appropriate assumptions.
Assumption:
prev – point to previous node
next – points to next node
first – first node of linked list
last – last node of linked list

void insertatlast(int data)
{
CDLL newnode=new CDLL();
{
newnode.info=data;
if(first==null)
{
first=newnode;
last=newnode;
newnode.next=newnode;
newnode.prev=newnode;
}
else
{
last.next=newnode;
newnode.prev=last;
newnode.next=first;
first.prev=newnode;
last=newnode;
}
}
}

Write a method or algorithm to implement the enqueue and dequeue operation in circular queue.

void enqueue(int data)
{
if (front==[rear+1]%size)
System.out.println(“Quequ is full”);
}
else
{
rear=([rear+1]%size);
item[rear]=data;
}
}
void dequeue(int data)
{
if (front==rear)
{
System.out.println(“Queue is empty”);
else
{
front=[front+1]%size;
data=item[front];
System.out.println(“Deleted data is:”+data);
}
}

Write a java function or algorithm for finding the minimum spanning tree using kruskal’s algorithm.

Algorithm:
step1: T=Φ
step2: while T contains fewer than n-1 edges
E= Φ
do{
step3: choose an edges (v,w) from E of lowest cost.
step4: Delete (v,w) form E
step5: If adding edge (v,w) to T does not form cycle then add edge (v,w) to T.
Else
Discard (v,w)
}

Write a java method or function for insertion sort.

void insertionsort (int[], int n)
{
int i, key, j;
for(i=1; i<=n; i++)
{
key=a[i];
j=i-1;
while(j>=0 and a[j]>key)
{
a[j+1]=a[j];
j=j+1;
}
}
a[j+1]=key;
}

Group C

Long Answer Questions
What is B-tree ? What are advantages of B-tree? Expalain the procedure to insert element in B-tree of order 5 for following data values:
10,70,60,20,110,40,80,130,100,50,190,90,180,240,30,120,140,200,210,160 and delete 180 and 80.
B tree is self balancing tree data structure that keeps data sorted and which allows searches, insertions and deletions in logarithmic time.

All leaves are at same level
B-tree nodes may contain more than just a single element

The advantages of B-tree are:

Dynamic sort
Evaluate arithmetic expression
Fast search

What is collision in hasing? List out the collision resolution technique and explain any of them with appropriate example.

Hashing is used to convert element into table index. During hashing function the two elements cannot have same index when this situation arises in process of hashing then it is said to be collision in hasing.
The Resolution technique of hasing :

Separate Chaining: Separate linked list of elements is maintained that have the same index. To search an element we first obtain the index using the applied hash function then corresponding list is traversed to get the required element.

let the hash function h(x) is defined as h(x)=x%10

Opening Addressing: The opening addressing hasing system tried until on empty cell is found ie. h₀(x), h₁(x)……… are tried in succession.

where, hi(x)=h(x)+f(i) with f(0)=0
Linear Probing: It is the function of h(x) ie. h(x)= x%10 in the linear called linear probing ie.
f(x)=(h(x)+f(i))%10 where f(i)=i
Quadratic Probing: In these method, function is in quadratic.
Function is h_i(x)=(h(x)+f(x))%10 where f(x)=i²

CAB

Section A
Define left skewed tree.
A tree is called a left skewed tree if all the nodes of a tree are attached to left side only and does not have any children in its right children.
What is Balance Factor?
Balance Factor is the difference between the height of the left sub tree and the right sub tree.
What are the disadvantages of recursive function?
Slower than non-recursive functions
May require lot of memory to hold intermediate results on the system stack.
Difficult to write and decode.
List any two properties of Big-oh notation.
Transitivity: f(x) = O(g(x)) & g(x)=O(h(x)) then f(x)=O(h(x)),
Reflexivity: f(x) = O(f(x))
What is strictly binary tree?
If every non-leaf(internal) node in a binary tree has nonempty- left and right sub-trees, then such a tree is called a strictly binary tree.
What is a linked list?
Linked list is a data structure where every node consists of two fields’ data(info) and the link which point to the next or previous node.
How is a B-tree different from Binary search tree?
In a binary search tree, the node can only consists of only one value while in B-tree the nodes can contain more than one value.
When does stack overflow condition occur?
Stack overflow occurs when the stack is full and no more elements can be pushed onto the stack.
Define expression tree.
A binary tree with each leaf node contains the operands and internal node contain the operators of given expression is called expression tree.
How is priority queue different from simple queue?
The elements are taken out with respect to their priority in priority irrespective to where they are place in the queue whereas in simple queue, the elements are only queued from the first.

Section B

Construct a B-Tree of order 5 from the given data.
1, 7, 6, 2, 11, 4, 8, 13, 5, 19, 9, 18, 24

Section C

Write a complete program to show the push, pop and view operations in a stack.

13 b

Write a program to convert decimal binary using recursive function.
Evaluate the following postfix expression.
5 7 6 – 1 7 + 8 / * –

Write a java function to delete the last node of a doubly linked list.
Write algorithm and show tracing to short the given data using bubble sort.
à Algorithm:
1. Start comparing a[0] to a[1]
2. If a[0] > a[1] then swap numbers
3. Compare a[1] and a[2] and repeat till you compare last pair
4. This is referred to as one pass and at the end of first pass largest number is at last.
5. Repeat this comparison again starting from a[0] but this time going till second last p pair only.
Tracing: