&* ;@ I

- i&

1ppendil

Model Question Papers

Ill

Time : 3 Hou rs
Instruction : Answer all Sect ions . Max Mar ks : 80

I SECTION--i<I
I. Answer any Eight questions. Each ques tion
carries 2 Mark s.
(8 x 2 = 16)
1. Define Data Stru cture s. List the Type s of Data
Stru cture s.
2. What are Asym ptoti c Nota tions ? List out the
type s of Asymptotic Notations.
3. What is Spar se Matrix? Give an exam ple.
4. Define Linked List. Give an exam ple.
5. List any four Strin g Oper ation s.
6. Define Stack.
7• Define Circular Queue. Give an exam ple.
8. Define Binary Tree and Bina ry Sear ch Tree .
9. What is B-Tree? Men tion its oper ation .
lO. Define Und irect ed and Dire cted Graph. Give
an example.

II. Answer any Four questions. Each question

carries 6 marks.
(4 x 6 = 24)
l 1. Briefly Explain Best Case, Average Case and
Wor st Case Efficiencies of an algorithm.
l2. Write an Algo rithm to Inse rt, Delete, Replace
Strings in Word Processing.
l3. Write a C Prog ram to Multiply Two Matrices.
14- Write an Algorithm to Inse rt a Node at the
Beginning and at the End of a Singly Linked LiS t
lS. Writ e an algo rithm for In Order, Pre Orde r
and Post Orde r Traversa\ of a Binary Tree.
16- Define Hashing? Explain the com pone
nts of Hashing with an example.
 I SECTION CI
.
Ill. Answ er any Five quest ions. Each quest ion carrie s 8 marks (5 )( 8 ::: 40)
ures.
Explain the Applic ations (or) Chara cterist ics (or) Impor tance of Data Struct
Write a C Progra m to find the length of a String.
18. Write a C Progra m to Perfor m Insert and Delete Opera tions on Array.
using Selection Sort.
19. (a) Show the steps to sort the eleme nts 25, 57, 48, 37, 12, 92, 86, 33
Collection.
(b) What is Garba ge Collection (GC)? Explain the Impor tance of Garba ge
tages and disadvantages.
20. (a) Explain Static Repre sentat ion of a Linked List. Menti on its advan
(b) Write Algor ithms for PUSH and POP Opera tions on a Linked Stack.
21. (a) Explai n Queue as ADT.
(b) Explai n the Worki ng of Deques.
22. (a) Explain the linked list repres entati on of binary tree.
30, 20,80,60,50}
(b) Const ruct a Binary Search Tree for the given eleme nts {10, 90, 40, 60,
graph by DFS and BFS.
23. (a) Consi der the graph shown below. Startin g at vertex '5' traver se the

(b) What are the Chara cterist ics of Good Hash Functi on?

□□□□
 MODEL QUESTION PAPER - 2
:; SECTION - .,q .
any Eight questions. Each question carries 2 Marks. (8X2=16)
I. Answer
Define Abstract Data Type.
1.
What is Linear Data Structure? Give an example.
2.
3_ Explain Arrays as ADT.
4. Define Doubly Linked List. Give an example.
s. Differentiate between Static Arrays and Dynamic Arrays.
6. Define Recursion.
7. Define Priority Queues.
s. Define (a) Predecessor or Ancestor (b) Successor or Descendant
9. What is AVL Tree? Give an example.
10. What is Hash Table? Give an example.
,; SECTION - 11 :.
II. Answer any Four questions. Each question carries 6 marks. (4 x 6 = 24)

11. What are Asymptotic Notations? Explain the types of Asymptotic Notations with examples.
12. Write an Algorithm to Insert and Delete an Element in an Array.
13. Write the Selection Sort Algorithm to Sort 'n' numbers.
14. Explain the types of Linked List with examples.
15. Write Algorithms for PUSH and POP Operations on a Linked Stack.
16, Explain Linked Representation of a Graph using Adjacency Matrix and Adjacency List.

Ill. Answer any Five questions. Each question carries 8 marks. (5 x 8 =40)
17. (a) What is Elementary Data Organization? Explain the Components of Elementary Data Organization
(b) Elxp ain the Operations on Data Structures. '
18. (a) Write a C Program to concatenate two strings.
(b) What is Word Processing? Explain Word Processing Operations with an example.
19• (a) Write an Algorithm to Insert a Node at the specific position of a Singly Linked List
(b) Explain Memory Allocation for Linked Lists with an example.
20• (a) Explain Dynamic Representation of a Linked List. Mention its advantages and disadvantages.
(b) Explain the Implementation of Recursive Procedures by Stack.
2
1. Explain the Types of Queues with Examples.
22 • (a) Build a max heap H from the given set of numbers: 45, 36, 54, 27, 63, 72, 61, and 18. Then
insert 15, 29, 90, 55 and delete 27, 36, 61.
(b) Write the procedure of inserting a new element into B Tree.
23. (a) What is Red Black Tree? Write the properties of Red Black Tree..
(b) Explain the Various Methods of Choosing a Hashing Function?.
□□□□
 Data Strudures

MODEL QUESTION PAPE R - 3

I. Answer any Eight question s. Each question carries 2 Marks. (8 x 2::

16 )
1. Defme Space and Time Complexity..
2. Define Big O Notation (0).
3. What is Garbage Collection (GC)?
4. What is Circular Linked List? Give an example.
5. List the different ways of Storing Strings.
6. What is Overflow and Underflow in a Stack?
7. Mention Two Applications of Stack.
8. Define Deques (Double-Ended Queues). Give an example.
9. Mention the types of Graph Traversal Methods.
10. What is Hash Function?
SECTION-'8
.
.
II. Answer any Four question s. Each question carries 6 marks. (4 x 6 =24)
11. Explain the Classification of Non-Primitive Data Structures.
12. Explain Memory Represen tations of Multidimensional Arrays.
13. Write C Program to Sort 'n' numbers using Insertion Sort.
14. Write an Algorithm to Search an Item in a Singly Linked List.
15. Evaluate the below Postfix Expression Using Stacks.
874*+ 3-2*
16. Explain the Different Cases of Deleting a Node in a Binary Search Tree.

I SECTION - C }
Ill. Answer any Five question s. Each question carries 8 marks.
(5 x 8 =40)
17. (a) Write a note on Orders of Growth.
(b) Given that f(n) =30n3 -2, Prove that f(n) =O(n 3).
18. Write C Program to Impleme nt Binary Search.
19. (a) Write an Algorithm to Multiply Two Matrices.
(b) Explain the Complexity of Linear and Binary Search.
20. (a) Write an Algorithm to search an item in a Singly Linked List.
(b) Explain the Types of a Header Linked List.
21. (a) Write an Algorithm for Tower of Hanoi Problem.
(b) Convert the expressio n ((a+(b*c))+(((d*e)+f)+g)) into Prefix and Postfix Notation.
22. (a) Explain AVL Rotations with an example.
(b) Explain the different methods of represen tation of binary trees.
23. (a) Write an algorithm for breath-fi rst search.
(b) Explain Linear Probing with an example.
□□□□
 MO DE L QU ES TI ON PA PE R - 4
SECTION - .,tl ~
Mar ks. (8 X 2 = 16)
. 1tn'I Eight ques tions . Each que stio n carr ies 2
3
. •
Aris"' • Prov e that f(n) = O(n ).
n3-2
1. f(n) == 30 '
Gi\fen that . . Data Stru ctur es? Give an exam ple.
1. priJJ1It1ve
w11atare L'nked List. Give an exam ple.
Z• ooubly 1
adva ntag es of Link ed List Ove r Arra ys?
3. oefine·onanytwO
4, tJenn . Array and Mul tidim ensi onal Arra y. Give an exam ple.
oefine Linear
s. I in stack as ADT.
~ EXP a. Postfix or Reverse Poli sh Nota tion ? Give an exam ple.
What 1s
7• . Two Applications of Que ues.
8 Menno n
• What Max Heap and Min Hea p?
is
9 n?
• What do you mean by Chai ning in Coll ision Reso lutio
10.
i''
SECTION - '8. t•. '

carr ies 6 mar ks. (4 x 6 = 24)

II. Answer any Four que stion s. Each que stio n
impo rtan t?
11. Explain Abstract Data Typ e with exam ples . Why it is
12. Write a C Program to Chec k Whe ther Given Matr
ix is Spar se Matrix or Not.
13. Explain the working of Bub ble Sort with an exam
ple.
14. Explain Linked List Rep rese ntati on of Stac ks and
Queues.

15. Write Pre-order, In-o rder , Post -ord er, Trav ersa
l for the given Tree.

16. Explai h
n t e Types of Deq ues with Examples.,.¥
~,

•' SECTION C ~
(S X 8 = 40)
Ill. An
swer an Y F'1ve ques
• - tion s. Each ques - 8 mark s.
- tion carr ies
17 p·
• Ind out th for the following algorithms.
... e spac e requ ired
a. 1v1atri ... . . b. Fact orial of a num ber
18. ( x iviult1phcation
a) Write a c p rogr am to com pare two strm .
(b) . gs.
algorithm). .
19, (a) W~ite Knu th-M orris -Pra tt Algorithm (KMP .
g recursion.
Wire a C-program to imp leme nt Binary sear ch usin ·• • Singly Linked List.
(b) Wr·t 1 e C Func tion to Dele te a Nod e at a Given Position ma
2o. (
LiSt
a)) Write an Algorithm for Trav ersin g a Singly Linked • ns using Stack.
(h W ·
rite an Algorithm for Evaluation of Postfix ExpresSIO
 Data Structures

21. (a) Write an Algorithm to insert an element in a Linked Queue.

(b) Create an AVL tree by inserting the following elements.
60.10,20,30,19,120,100,80,19
22. (a) Write an algorithm for constructing a binary search tree
(b) What is external searching? Give an example of B-Tree of order 5.
23. (a) Write the applications of Trees.
(b) Explain Hash Table as ADT..
□□□□
 MODEL QUESTIO N PAPER~ 5
I SECTION - .,q
Answer any
Eight questions. Each question carries 2 Marks. (8 X 2 =16)
1.
. N n-Linear Data Structure? Give an example.
1 What1s 0
• What is Time-Space Tradeoff?
:· What is Header Linked List. Give an example.
~ How Linear Arrays are represented in Memory.?
4
S. Mention the types of Circular Linked List.
_ What is Prefix Or Polish Notation? Give an example.
6
. List the types of Deques. Give an example for each.
7
8. What is Red Black Tree? Give an example.
9. What are Adjacent and incident vertices?
10. Define any two collision resolution methods in Hashing.

I SECTION - '8 J

11. Answer any Four questions. Each question carries 6 marks. (4 x 6 = 24)
11. Explain the different storage representations of strings.
12. Write C Program to Implement Linear Search.
13. Explain Representation of a Singly Linked List in Memory.
14. Write Algorithms for Push and Pop Operations on a Stack Using Arrays.
15. Explain the Working of Circular Queue with an Example.
l6. Write an Algorithm to Convert Infix Expression into Postfix Expression.

I SECTION - C ~
111 • Answer any Five questions. Each question carries 8 marks.
(5 x 8 = 40)
17. (a) Explain Algorithmic Notations with examples.
(b) Find out the time required to run the matrix multiplication using Operation counts and Step counts.
18• (a) What is Pattren Matching? Write Naive Pattern Searching algorithm.
(b) Write a Program to find the substring from the given string.
19 • (a) Compare Singly Linked List Vs Doubly Linked List Vs Circular Linked
List.
(b) Mention the Advantages and Disadvantages of Doubly Linked List.
20 • (a) Write an Algorithm to Delete a Node if Item is Given in a Singly Linked LiSt •
(b) Write an Algorithm to Convert Infix Expression into Prefix Expression.
21. (a) Write an Algorithm for Insert and Delete Operations on a Queue.
(b) Discuss the Applications of Queues.
 Da ta Strudures
it.
sert 81, 7, 49, 61 and 30 in
22. Consider the followi
ng 8-tree of order 5 and in

k Tree with an example.

Explain Insert and Delete Operations in a Red Blac
23. (a) .
Depth-First Search
(b) Write an algorithm for
□□□□

r
(
«>•.
r

0
0
-0
-<