Cauvery College for Women (Autonomous)
Department of Computer Applications
Scheme of Valuation
Course Title: Data Structures Course Code: 22UCA2CC3
Semester : II Marks : 75
SECTION A (20 X 1=20)
Choose the best answer
1. b) domain
2. a) Last in first out
3. d) n
4. b) L = I + 1
5. b) File
Fill in the blanks
6. Data
7. Expression
8. Data
9. Labelled
10. Binary
State True or False
11. True
12. False
13. True
14. False
15. False
Answer in One or Two Sentences
16. What is mean by data type?
A data type is a term which refers to the kind of data that may appear in computation.
17. State the different ways of representing expression.
Prefix, Infix and Postfix.
18. What is node?
A node is a collection of data and links.
19. Define Inverse Adjacency List.
To keep another set of lists in addition to the adjacency lists. This set of lists called
inverse adjacency list.
20. How many number of ways to search an element in a given array?
Two
SECTION B (5 X 5=25)
Answer ALL the Questions
21. a) Implementation of Data Structures
Phase1 : how a data structure can be stored in a computer memory.
Phase2 : algorithmic notation of various operations of the classic data structure
A functions for manipulating a data structure is expressed in terms of algorithms so
that the details of the operation can be understood easily and the reader can implement
them with the help of programming language.
Example
(OR)
b) Advantages of One-Dimensional Array
Fast Element Access
Contiguous Memory Allocation
Simple Structure
Foundation for Other Data Structures
Easy Traversal:
22. a) Various Operations on Stack
A stack is an ordered list in which all insertions and deletions are made at one end,
called the top.
Associated with the object stack there are several operations that are necessary:
CREATE (S) which creates S as an empty stack;
ADD (i,S) which inserts the element i onto the stack S and returns the new stack;
DELETE (S) which removes the top element of stack S and returns the new stack;
TOP (S) which returns the top element of stack S;
ISEMTS (S) which returns true if S is empty else false;
(OR)
b) Evaluation of Expression
To convert infix expression to postfix expression, we will use the stack data structure.
The rule will be that Operators are taken out of the stack as long as their in-stack
priority, isp, is greater than or equal the in-coming priority, icp of the new operator.
By scanning the infix expression from left to right, when we will get any operand,
simply add them to the postfix form, and for the operator and parenthesis, add them in
the stack maintaining the precedence of them.
procedure EVAL (E)
top 0 // initialize STACK//
loop
x NEXT-TOKEN (E)
case
: x = '∞ ' : return //answer is at top of stack//
: x is an operand: call ADD(x,STACK,n,top)
:else: remove the correct number of operands for operator x from STACK,
perform the operation and store the result, if any, onto the stack
end
forever
end EVAL
23. a) Polynomial Addition
Polynomial is of the form:
A(x) = amxem + ... + a1xe1
where the ai are non-zero coefficients with exponents ei such that em > em-1 > ... >
e2 > e1 >= 0.
Each term will be represented by a node.
A node will be of fixed size having 3 fields which represent the coefficient and
exponent of a term plus a pointer to the next term
procedure PADD(A,B,C)
//polynomials A and B represented as singly linked lists are
summed to form the new list named C//
1 p ← A; q ← B //p,q pointers to next term of A, B//
2 call GETNODE(C); d ← C //initial node for C, returned
later//
3 while p = 0 and q = 0 do //while there are more terms in
A and B//
4 case
5 : EXP(p) = EXP(q): //equal exponents//
6 x ← COEF(p) + COEF(q)
7 if x 0 then call ATTACH(x, EXP(p),d)
8 p ← LINK(p); q ← LINK(q) //advance to next
terms//
9 : EXP(p) < EXP(q):
10 call ATTACH(COEF(q),EXP(q),d)
11 q ← LINK(q) //advance to next term//
12 : else: call ATTACH(COEF(p),EXP(p),d)
13 p ← LINK(p) //advance to next term of A//
14 end
15 end
16 while p = 0 do //copy remaining terms of A//
17 call ATTACH(COEF(p),EXP(p),d)
18 p ← LINK(p)
19 end
(OR)
b) Deletion of Linked List
Let X be a pointer to some node in a linked list T. Let Y be the node preceding X. Y =
0 if X is the first node in T (i.e., if X = T). The following algorithm deletes node X
from T
procedure DELETE(X, Y, T)
if Y= 0 then T LINK(T) //remove the first node//
else LINK(Y) LINK(X) //remove an interior node//
call RET(X) //return node to storage pool//
end DELETE
24. a) Representation of Binary Tree
•A full binary tree of depth k is a binary tree of depth k having 2k - 1 nodes.
•Sequential representation of binary trees results from sequentially numbering the
nodes, starting with nodes on level 1, then those on level 2 and so on. Nodes on any
level are numbered from left to right.
•The nodes may now be stored in a one dimensional array, TREE, with the node
numbered i being stored in TREE(i).
Complete Binary Tree:
If a complete binary tree with n nodes (i.e depth = [log2n]+1) is represented
sequentially then for any node with index i, l ≤ i ≤ n
i) PARENT(i) is at ⌞i/2⌟, if i≠1. When i =1, i is the root and has no parent ex:
PARENT(D)=4/2=2
ii) LCHILD(i) is at 2i, if 2i ≤ n. If 2i>n, then i has no left child
iii) RCHILD(i) is at 2i+1, if 2i+1 ≤ n. If 2i+1>n, then i has no right child
(OR)
b) Breadth-First Traversal
Starting at vertex v and marking it as visited, breadth first search differs from depth
first search in that all unvisited vertices adjacent to v are visited next. Then unvisited
vertices adjacent to these vertices are visited and so on.
A breadth first search beginning at vertex v1 of the graph in figure would first visit v0
and then v1 and v2. Next vertices v3, v4, v5 and v6 will be visited and finally v7.
procedure DFS(v)
VISITED (v) 1
for each vertex w adjacent to v do
if VISlTED(w) = 0 then call DFS(w)
end2 Marks)
25. a) Advantages of Sequential Search
Simplicity and Ease of Implementation:
No Sorting Required:
Effectiveness for Small Datasets:
Flexibility
(OR)
b) Insertion sort
The basic step in this method is to insert a record R into a sequence of ordered
records, R1,R2, ...,Ri, (K1 <=K2, ...,<= Ki) in such a way that the resulting sequence
of size i + 1 is also ordered.
procedure INSERT (R,i)
j i
while K < Kj do
Rj+1 Rj; j j - 1
end
Rj+1 R
end INSERT
SECTION C (3 X 10=30)
Answer any Three Questions
26. Initialization of Two Dimensional Arrays
Two-dimensional arrays are a collection of homogeneous elements where the
elements are ordered in a number of rows and columns.
An example of an m*n matrix, where m denotes the number of rows and n denotes the
number of columns.
27. Add and Delete Procedure for Queue
A queue is an ordered list in which all insertions take place at one end, the rear, while
all deletions take place at the other end, the front.
The restrictions on a queue require that the first element which is inserted into the
queue will be the first one to be removed. So queues are known as First In First Out
(FIFO) lists
Procedure ADD(item,Q,n,rear)
If rear = n then call Queue_Full
rear rear+1
Q(rear) item
End ADDQ
Procedure DELETE(item,Q,front,rear)
If front=rear then call Queue_Empty
front front+1
item Q(front)
End DELETEQ
28. Algorithm for Linked Stacks and Queues
Add Procedure for Linked Stack
procedure ADDS(i, Y)
call GETNODE(X)
DATA(X) Y //store data value Y into new node//
LINK(X) T(i) //attach new node to top of i-th stack//
T(i) X //reset stack pointer//
end ADDS
Delete Procedure for Linked Stack
procedure DELETES(i, Y)
if T(i) = 0 then call STACK__EMPTY
X T(i) //set X to top node of stack i//
Y DATA(X) //Y gets new data//
T(i) LINK(X) //remove node from top of stack i//
call RET(X) //return node to storage pool//
Add Procedure for Linked Queue
procedure ADDQ(i,Y)
call GETNODE(X)
DATA(X) Y: LINK(X) 0
if F(i) = 0 then [F(i) R(i) X] //the queue was empty//
else [LlNK(R(i)) X;R(i) X] //the queue was
not empty//
end ADDQ
Delete Procedure for Linked Queue
procedure DELETEQ(i, Y)
if F(i) = 0 then call QUEUE__EMPTY
else [X F(i); F(i) LINK(X)
//set X to front node//
Y DATA(X); call RET(X)] //remove data
and return node//
end DELETEQ
29. Preorder Traversal of a Binary Tree
First "visit a node, traverse left and continue again.
When you cannot continue, move right and begin again or move back until you can
move right and resume."
procedure PREORDER (T)
//T is a binary tree where each node has three fields LCHILD,
DATA,RCHILD//
if T ≠ 0 then [print (DATA(T))
call PREORDER(LCHILD(T))
call PREORDER(RCHILD(T))]]
end PREORDER
30. Heap Sort
Heap sort may be regarded as a two stage method. First the tree representing the file is
converted into a heap. A heap is defined to be a complete binary tree with the
property that the value of each node is at least as large as the value of its children
nodes.
procedure ADJUST (i,n)
R=Ri; K=Ki; j=2i
while j<= n do
if j < n and Kj < Kj+1 then j= j + 1
if K >Kj then exit
R[j/2] Rj; j 2j
end R[j/2] R
end ADJUST
procedure HSORT (R,n)
for i =n/2 to 1 by -1 do
call ADJUST (i,n)
end
for i =n - 1 to 1 by -1 do
T Ri+1;
Ri+1 R1; R1 T
call ADJUST (1,i)
end
end HSORT
Example
