Sardar Patel University 2007 B.E Computer Science CP303: DATA STRUCTURES AND ALGORITHMS(Internal ) - Question Paper

ADIT / BVM / GCET
CP303: DATA STRUCTURES AND ALGORITHMS

Time: 2:00 – 3:00 p.m Date: 10 / 03 / 2008
Total Marks: 20
Note: Answers should be brief and to the point.
Write assumptions clearly if any.



Q-1 Answer the subsequent ques..

1. What is the importance of Data structures?
Ans: Data structures involve data + operations on that data. There are different kinds of data and different kinds of operations can be performed on them. various applications require various data structures. To address the application properly, knowledge of data structures should be sound.

2. List applications of Stack in computer science.
Stack is used internally by a compiler to avoid the use of paranthesis and thereby avoiding explicit specification of precedence and associativity
The internet explorer browser has a back button. It explicitly maintains a stack of pages, wherein by clicking on the back button, previous page is retrieved.

3. Prove that in any binary tree number of nodes at level l is 2l
where l >=0.
For l =0, N =1(root node only)
For l=1, N= 21(Two children of root)
For l = 2, N= 4(Two children of every at earlier level)
For any level l, it is 2l
3. Justify why in circular queue 1 memory location is left unused.
Ans: To avoid conflict ranging from the conditions of queue full and queue empty, 1 memory location is left empty. (Suitable example is appreciated)




































































Q-2 ans the subsequent ques.

[ A ] 1. Convert subsequent infix expression into postfix expression
with Stack trace.

Ans. ( A + B ) * C + D / (E + F * G) + H

symbol postfix string opstk
( (
A A (
+ A (+
B AB (+
) AB+
• AB + *
C AB +C
+ AB+C * +
D AB+C*D +
/ AB+C*D +/
( AB+C*D +/(
E AB+C*DE +/(
+ AB+C*DE +/(+
F AB+C*DEF +/(+
• AB+C*DEF +/(+*
G AB+C*DEFG +/(+*
) AB+C*DEFG*+ +/
+ AB+C*DEFG*+/ ++
H AB+C*DEF*+/H++


2) Discuss implementation of priority queue using array
Ans. Array implementation of priority queue using queue:
- Involves holes while deletion require compaction
- Insertion may involves searching and deletion may involve shifting.
- Use of empty indicators.

3) Write an algorithm to delete a node which is before the provided node.
Ans.
Let q be provided node.
P points to the beginning of the list.
while( p -> next -> next !=q)
{
p = p->next
}
p->next =q

4) List advantages of doubly linked list over singly linked list. discuss any 1 in detail with specific application
Ans.

i) Inserting a node before a provided node.
ii) Deletion a node whose location is provided.

Above operation are easier with doubly linked list. Explanation is subjective.


[ B ] Write an algorithm for deleting a 1st node in a circular doubly linked list
with header node.
Ans.
Let p point to header node

q = p -> right
r = q -> right
p -> right = q -> right
r -> left = q -> left














Q-3 Perform subsequent operations of a Binary Search Tree (BST)

Insert H, I, K, A, D, C Delete H
For the resulting tree provide preorder, post order and in order traversals.
Ans.
Step1:









Step2:
















Preorder: DACIK
Postorder: CAKID
Inorder: ACDIK

Earning:   Approval pending.