University of Sargodha
MSc. 3rd Term Examination 2019.
Subject: I.T Paper: Data Structures and Algorithms(CMP: 3112)
Objective Part
Q. No 01: Write short answers of the following in 2-3 lines each on your answer sheet
i. Define Structure of node used in doubly linked list?
ANSWER:
Node of a double link list contains three portions. First, previous that maintains the link to the previous node. Second portion is data element to store data. And last one is next to maintaining link to the next node.
i.i Write the name of two nonlinear data structures
ANSWER:
1. Tree
2. Graph
iii. Which data structure is used in recursion and why.
ANSWER: Stack data structure is used to implement recursion. During recursion, function has to return in reverse order. To maintain the reverse order stack helps in natural way.
vi. Write the name of two prominent operations performed on queue.
ANSWER:
1. enqueue: insertion at the back of the line.
2. dequeue: removal of the item from the front of the line.
v. What is Postfix expression of A+B*C
ANSWER:
Postfix Expression: ABC*+
vi. Write the name of two collision resolution techniques used in hashing
ANSWER:
- Linear Probing
- Quadratic Probing.
vii. What are two necessary conditions for recursion?
ANSWER:
· Base criteria: There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively.
· Progressive approach: the recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.
viii. Write the name of two recursive algorithms used in sorting.
ANSWER:
- Merge Sort
- Quick sort
ix. What is strictly binary tree?
ANSWER: A binary tree that has exactly two or no child of a node is called strictly binary tree. In a strictly binary a node has no child as it is a leaf node or it is a parent then it must have two children. Every non-leaf node in a binary tree has nonempty left and right sub trees.
x. Write the total number of nodes in a strictly binary tree having 9 leaves.
ANSWER: There are 17 number of leaves in a strictly binary tree having 9 leaves.
xi. What is height of tree? Give an example.
ANSWER:
The height of a tree is the number of edges on the longest downward path between the root and a leaf. In other words, the height of a tree is the height of its root.
xii. Define merging.
ANSWER: Merging is a process of combining nodes from two halves in a single array. All the nodes are arranged in their logical order during merging.
xiii. In which sorting algorithm there is more number of swaps. Selection or Bubble.
ANSWER: Bubble Sort has many more swaps than Selection sort.
xiv. Write the name of sorting algorithm in which a pivot element is selected to sort array.
ANSWER: Quick sort
xv. What is special in binary search tree?
ANSWER: The binary search tree satisfies the search order property; that is, for every node X in the tree, the values of all the keys in the left subtree are smaller than the key in X and the values of all the keys in the right subtree are larger than the key in X.
xvi. How many references are maintained in a queue?
ANSWER: In a queue each node maintains a single reference with its previous node.
Q.2. (a) Suppose a link list is empty, Write a function to add a node at the start of the list.
ANSWER:
public void addNode(int d)
{
Node newNode = new Node (d);
newNode.next = null;
head.next = newNode;
lastCurrentNode = currentNode;
currentNode= newNode;
size++;
}
(b) Write a code to delete a node from circular Queue.
ANSWER:
public int dequeue( )
{
if( isEmpty( ) )
throw new RuntimeException( “ListQueue dequeue” );
int returnValue = front.data;
front = front.next;
size–;
return returnValue;
}
Q.3. Convert the following Infix expression to postfix form using a stack and show each step used. ((A+B)/(C+D)$(E/F))+(G+H)/K
Reading Character | Postfix | Stack |
( |
| ( |
( |
| (( |
( |
| ((( |
A | A | ((( |
+ | A | (((+ |
B | AB | (((+ |
) | AB+ | (( |
/ | AB+ | ((/ |
( | AB+ | ((/( |
C | AB+C | ((/( |
+ | AB+C | ((/(+ |
D | AB+CD | ((/(+ |
) | AB+CD+ | ((/ |
$ | AB+CD+ | ((/$ |
( | AB+CD+ | ((/$( |
E | AB+CD+E | ((/$( |
/ | AB+CD+E | ((/$(/ |
F | AB+CD+EF | ((/$(/ |
) | AB+CD+EF/ | ((/$ |
) | AB+CD+EF/$/ | ( |
( | AB+CD+EF/$/ | (( |
G | AB+CD+EF/$/G | (( |
+ | AB+CD+EF/$/G | ((+ |
H | AB+CD+EF/$/GH | ((+ |
) | AB+CD+EF/$/GH+ | ( |
/ | AB+CD+EF/$/GH+ | (/ |
K | AB+CD+EF/$/GH+K | (/ |
) | AB+CD+EF/$/GH+K/ |
|
The Postfix Expression: AB+CD+EF/$/GH+K/
Q.4. Make a BST for the following sequence of number.
45,32,90,34,68,72,15,24,30,66,11,50,10
ANSWER:
BST:
Pre Order Traversal: 45, 32, 15, 11, 10, 24, 30, 34, 90, 68, 66, 50, 72
In Order Traversal: 10, 11, 15, 24, 30, 32, 34, 45, 50, 66, 68, 72, 90
Post Order Traversal: 10, 11, 30, 24, 15, 34, 32, 5, 66, 72, 68, 90, 45
Q.5. (a) Write down a function to implement insertion sort.
ANSWER:
void insertion_Sort( AnyType [ ] a ) { for( int p = 1; p < a.length; p++ ) { AnyType tmp; int j = p; while(j >= 1 && tmp.compareTo( a[ j – 1 ] ) < 0) { tmp = a[ p ]; a[ j ] = a[ j – 1 ]; a[ j ] = tmp; j– |
}
}
(b) write a recursive function to add 10first 10 integers from 1 to 10
int addNumbers() {
int n=10;
if (n != 0)
return n + addNumbers(n – 1);
else
return n;
}
Q.7. Suppose there are 8 keys with numbers 25, 3, 51, 37, 30, 79, 5, 23. There are 10 hash address are available. Try to accommodate them in available slots using linear probing technique. The Hashing function used is h (k) = key%9
ANSWER:
Hash function = h(k) = key%9
h(25) = 25%9 = 7
h(3) = 3%9 = 3
h(51) = 51%9 = 6
h(37) = 37%9 = 1
h(30) = 30%9 = 3
h(79) = 79%9 = 7
h(5) = 5%9 = 5
h(23) = 23%9 = 5
| 37 |
| 3 | 30 | 5 | 51 | 25 | 79 | 23 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
