Subject:CS3301-DataStructures

UNIT-I
PART-A

1. Whatiscalledasa Data Structure?

A Data Structure defines a way of representing or organizing all data that contains both
the data items and their relationship with each other.
2. Differentiatebetweendatatypeanddatastructures.
DataType:DataTypeofavariable isasetofvaluesthevariable mayassume. Eg. int,
char & real
Data Structures: Data structure mean the wayoforganizing data values with the help ofexisting
data types.
Eg.Array,stackqueue,&tree.
3. WhatarePrimaryData Structures?

 Integers
 Floating-pointnumbers.
 CharacterConstants

4. WhatarethetypesofSecondary DataStructures?
 Static Data structures
 DynamicDatastructures.

5. Whatarethestaticdatastructures?
 Arrays
 Structures

6. Whatare thetypesofdynamicdatastructures?
 Linear DataStructures
 Non-Linear DataStructures.

7. GiveexamplesofLinearandNon-LinearDataStructures.
 Linear DataStructures
i) LinkedLists(Singly&DoublyLinked Lists)
ii) CircularLinkedLists(Circular-singly&Circular-doubly
Linked Lists).
 Non-Linear DataStructures
i) Trees
ii) Graphs.
8. Whatdoyoumean byAbstractData Types?
 Classes encapsulate all the essential properties of the objects that are tobe created.
Since the classes use the concept of dataabstraction, they are known as Abstract Data Types
(ADT).
9. ListtheoperationofsetADT?
UnionandFind arethetwooperationsonsetADT

10. Givesomeapplicationsofstack.
 EvaluationofExpressions.
 Expressionconversion.
 Balancingofsymbols.
Function Calls.

11. DefineDequeue.
Adequeueisanorderedlistinwhichadditionsanddeletions maybecarriedoutateither end.

12. Statethedifferencebetweencursorand pointers.

Pointer:Pointerisavariable,whichstorestheaddressofanothervariable.
Usingpointers,memorycanbeallocateddynamically.
Cursor:Cursorisatemporarymemoryspace.Memoryallocatedis static.
13. Whatisanorderedlist
Anorderedlistisalinearlistwhichisbeenorderedbysomekey.
Eg.Analphabetizedlistofstudentsinaclass,alistofexam scoresindecreasingorder.

14. .Statethedifferencebetweenarrayandlinkedlist.

Array LinkedList
Contiguousmemorylocation Memorylocationneednotbe
necessarilycontiguous
Operations such as insertion and deletion Insertionanddeletionsareeasierand
are ineffective since the memory locations needsonly one pointer assignment.
needtobemovedupanddown
respectively.
Inefficientuseofmemoryspace. Asmallamount ofmemoryis beenwasted
forstoringapointer,whichisbeen
associated witheachnode.
15. Whataretheadvantagesanddisadvantagesoflinkedlist?
Advantages:
a. Memory location for a linkedlistis dynamic,that ismemory allocation is done during run
time. So memory will not be wasted.
b. Datamovementsduringinsertionanddeletionwillbeeliminated.Sotimewillnotbewasted.
c. Memoryallocationforeachnodeofalinkedlistneednotbe continuous.
Disadvantages:
d. Nodesof alinkedlistcannotbeaccesseddirectly.Toaccessaparticularnodeaccessing should start
only from the beginning.
e. To store a single data, along with data, memory mustbe allocated for a pointer also, which
wastes memory.
16. Writethestepsrequiredto evaluatethepostfixexpression.
 Repeatedlyread charactersfrompostfixexpression
 Ifthecharacterreadisanoperand,pushthevalueassociated withitintothestack
 Ifitisanoperator,popthetoptwovalues fromstack, applytheoperatortothem and
push the result back onto the stack.

17. DefineSinglyLinkedList.
Asinglylinked list isa list structureinwhicheachnodecontainsasinglepointerfield that
points to the next node in the list, along with a data field.

18. DefineDoublyLinkedList.
Adoublylinked list isa list structureinwhicheachnodecontainstwopointerfields along
with a data field namely,
BLINK – Points to the previous node in the list
FLINK–Pointstothesuccessive nodeinthelist

PART-B

1. Designaroutinetodeleteanelementinalinkedlist.
2. Developanalgorithmforinsertionoperationinasinglylinkedlist.
3. DescribeindetailaboutPolynomialmanipulationinlinkedlist.
4. Whatisalinkedlist?Describethesuitableroutinesegmentsfor anyfouroperations.
5. Examinethealgorithmstoimplement thedoublylinked list andperformallthe
operations on the created list.
6. Identifythearrayimplementationoflistandshowallitsoperation.
7. Discussthecreationofadoublylinked list andappendingthe list.Giverelevant coding in C
8. WriteCcodeforsinglylinked list withinsert,delete,displayoperationsusingstructure
pointer.
9. Differentiatesinglelinkedlistanddoublylinkedlistwithanexample.
10. Explaintheapplicationoflinkedlistindetail.
11. ConsideranarrayA[1:n]Givenaposition, writeanalgorithmto insert anelement inthe
Array.If the position is empty, the element is inserted easily. If the position is already
occupied the element should be inserted with the minimum number ofshifts.(Note: The
elementscanshift tothe left orto the right to make the minimumnumber of moves).
 12. AnalyzeandwriteCcodeforcircular linked list withcreate,insert,delete,display
operations.
13. ExplainthevariousoperationsofthelistADT withexamples.
14. Analyzethedoublylinkedlistandcircular linkedlist.Mentionitsadvantagesand
disadvantages.
15. Explainthestepsinvolvedininsertionanddeletionintoasinglylinkedlist.
16. Recommend an algorithm to add two polynomialswhenthepolynomialsare
represented singly linked lists.
17. ComposeanalgorithmtoReversetheelementsofa single linked lists,countthenumberof
nodes ina given singly linked list. Searching the element from linked list.
18. Givenanlist 10,20,30,40,generalizethestepsto deleteanodefromthebeginningofthe linked
list, deletionof last node inadeletionof middle node ina list.
19. DevelopaCprogramto split a linked list intosublistscontainingoddandevenordered
elements in them respectively.
UNIT-2
PART-A

1. Definestack?
Stackisanorderedcollectionofitems into whichnew items maybe insertedand from which
items may be deleted at one end, called the topofstack.

2. DefineCircularQueue.
In array based implementation of queue, inefficiency arises only when the value of the rear
pointer exceeds maximumsize during insertion. Thiscanbe rectified ifwe logicallyconsiderthe
queue to be circular.
Incircular queue, once the rearpointer reaches the maximumsize, the next locationIthe first
one (index 0), provided the first location is vacant. The specificlocation is calculated by mod
(%)operator.
3. Converttheinfix(a+b)*(c+d)/fintopostfix&prefixexpression
Postfix :ab+cd+*f/
4. DistiPnrgeufiixsh betwee:n/s*ta+cak ban+dc qdufeue.
STACK QUEUE
Insertionanddeletionaremadeatoneend. Insertionatoneendrearanddeletionat other
end front.
Theelementinsertedlastwouldbe removed Theelementinsertedfirstwouldbe removed
first. So LIFO structure. first. So FIFO structure.
Fullstackcondition: Fullstackcondition:
If(top==Maxsize) If(rear==Maxsize)
PhysicallyandLogicallyfullstack Logicallyfull. Physicallymayor maynot
befull.
5. Define Dequeue.
A dequeue is an ordered list in which additions and deletions may be carried out at either end.

6. What is top of stack?

The end of stack, at which the items are added or deleted, is called top of stack.

7. Whatarethelimitationsinthestack,whenarrayused ashomeofstack?
The Array is finite collection of elements and in stack the number of elements is
unlimited.Asthestackdynamicallychangestheattemptsto insert moreelementsthanthe array size
cause overflow

8. DefineModularization?
Modularizationistheconcept ofisolatingthecompleximplementationinto setof
independent and easilyidentifiable units, to make the programeasilyunderstandable and
modifiable.

9. What aretheerrorconditionsthat couldoccurinstack implementation?Howcouldthey be

rectified?
Overflow
Underflow
Toavoidoverflow,thestackshould becheckedwhether it isfullornot beforeeverypush
operation.
Toavoidunderflow,thestackshould bechecked foremptinessbeforeevery
popoperation.

10. Whatisoverflowinstack?
Whenarrayisusedashomeofstack, andwhenthestackcontainsas manyelementsas array, and
as attempt is to pushanother element onstack, it cause overflow.

11. Whyinfixexpressionshould beconvertedtoPrefix/ Postfix?

InInfix,operatorprecedencecanbesetonlyafterscanningtheexpressionforseveral times.
But, conversion ofInfix to Postfix or Prefix with use ofstack, help to set precedence based on
order of arrangementin a single scanning

12. Convert((A+B)*C–(D–E))$(F+G)To PostfixandPrefix notation? Prefix:

$ - * + ABC – DE + FG.
Postfix: AB +C*DE--FG + $

13. DefineQueue?
Aqueue isanorderedcollectionofitems fromwhichitems maybe insertedatoneend called
rear end and into which items may be deleted at theother end called the front end.

14. Whyqueueiscalled FIFOlist?

Inaqueue,thefirst element insertedatrearendwillbethe first elementtobedeletedat front end.
So, queue is called First-in First-out list.
 15. What arethebasicoperationsthat could beperformedonaQueue?
Insertion – insert (q, x) inserts x at the rear end.
Removal– x=remove (q) remove the element in front end.
Empty(q)–Checkswhether queuehasanyelementsornot.

16. Whatarethe limitationsoflinearqueue?Howtheycanberectified?

Whenanelement isremoved fromlinearqueue,the locationremainsunused.Evenifthe queue
is empty, new elements cannot be inserted. To avoid this, consider queue as a circle, having the
first element immediately following the last element.

17. DefinePriorityQueue?
Priorityqueue isadatastructureinwhichthe intrinsicorderingoftheelements determines
the results ofthe basic operations like insertion and removal.

18. What arethetwotypesofpriorityqueues?Brieflyexplain?

Two types of priority queues are,
i) Ascendingpriorityqueue–Inthisqueue,the itemscanbe insertedarbitrarily and
only the smallest item will be removed.
ii) Descendingpriorityqueue-Thisallows insertionofitemsarbitrarily,andonly the
maximum element from queue will be removed first.

19. Whatisthedifferencebetweenqueueandpriorityqueue?
Inqueuetheelementscanbe insertedonlyat rearendand canberemovedonlyat front end. But
in priorityqueue, elements can be arbitrarily inserted. But the complete queue is searched for
removal of high priority element.

20. Whatarethelimitationsinpriorityqueue?Howitcouldbe rectified?

Deletion of elements makes a location empty. The search of items includes the empty
spacestoo.Thistakesmoretime. To avoidthis, useanemptyindicatororshift elementsforward when
each element is deleted. We can also maintain priority queue as an array of ordered elements, to
avoid risk in searching.

24. .WhataretheapplicationofStack?
Twoapplications
Recursion
Expression
PART-B

1. DescribeaboutstackADTusingarrayindetail.
2. i)Giveanalgorithmforpushandpopoperationsonstackusinga linked list withan
example.
3. ii)Describethefunctiontoexaminewhether thestackis full()orempty().
4. i)Discusstheprocessofevaluatingpostfixexpressionwithanexample.
5. ii) Writeanalgorithmthat checks ifexpressioniscorrectlyparenthesizedusing stack.
6. Giveanalgorithmto convert aninfixexpressionto apostfixexpressionusingstack with
suitable example.
 a. Tracethealgorithmtoconvertthe infixexpression“3-(4/2) +(1*5)+6”to a
postfix expression using stack.
b. Showthesimulationusingstackforthe followingexpressiontoconvert infixto
postfix :p*q+ (r-s/t).
8. Explainhowtoevaluatethefollowingarithmeticexpressionsusing stacks.

a. 6523+8*+3+*231*+9-
9. Brieflydescribetheoperations ofqueuewithexample.
10. Describeabout implementationofqueueADTusinglinkedlist.Giverelevant examples and
diagrammatic representations.
11. DiscussandwriteaCprogramtoimplementqueuefunctionsusing arrays.
12. Explainapplicationofqueue withsuitable example.
13. Explaincircularqueueanditsimplementation.
14. Analyzetheimplementationofpriorityqueue.
15. Prepareanalgorithmtoperformtheoperations ina doubleendedqueue.DevelopaC
program for linked listimplementation of stack.
16. A circular queue has a size of 5 and has 3 elements 10,20 and 40 where F=2 and
R=4.After inserting 50 and 60,what is the value ofF and R.Trying to insert 30 at this
stagewhat happens?Delete2elements fromthequeueand insert 70,80&90.Assessthe
sequence of steps with necessary diagrams with the value ofF & R.
17. Generalizeanddevelopa functionto insert anelement into aqueueanddeletean
elementfromaqueue,inwhichthequeueis implemented as a linked list.
UNIT-III
PART-A
1. DefineTree.
A Tree is a collection ofone or more nodes with a distinct node called the root , while
remaining nodesarepartitioned asT1,T2,..,Tk,K≥0 eachofwhicharesubtrees,theedgesof T1,T2,…,Tk
are connected the root.

2. GivesomeapplicationsofTrees.
 Implementingthefile systemofseveraloperatingsystems.
 Evaluationofarithmetic expression.
Set representation.
Gaming/Decision making problems.
3. Define node, degree, siblings, depth/height, level.
 Node:Anode isan itemofinformationwithbranches tootheritems.
Degree: Thenumberofsubtreesofanodeiscalled is degree.
Siblings:Thechildrenofthesameparentissaidtobe siblings.
Level:The levelofanode isdefinedrecursively byassumingthe leveloftherootto beone and if a
node is at level l, then its children at level l+1.
Depth/Height:Thedepth/height ofatreeisdefinedto bethe levelofa nodewhichis maximum.
4. Define apathinatree.
A path in a tree is a sequence ofdistinctnodes in which successive nodes are connected
by edges in the tree.
5. Defineterminalnodesina tree.
Anodewhichhasno childreniscalledaterminalnode.It isalso referredasa leaf node.these
nodes have a degree as zero.
6. Definenonterminalnodesina tree
Allintermediatenodesthattraversethegiventreefromitsrootnodetotheterminal nodes are
referred as terminal nodes.
7. efineaBinaryTree.
ABinaryTree isatree,which hasnodeseither emptyor not morethantwochild nodes,each of
which may be a leaf node.
8. Defineafullbinarytree.
Afull binarytree,isa tree inwhichallthe leavesareonthesame leveland everynon-leaf node
has exactly two children.
9. Defineacompletebinarytree.
A completebinary treeisatree in which every non-leaf nodehasexactly twochildren not
necessarily to be on the same level.
10. Definearight-skewedbinarytree.
Aright-skewedbinarytreeisatree,whichhasonlyrightchildnodes.
11. StatethepropertiesofaBinaryTree.
 MaximumNo. ofnodesonlevelnofabinarytreeis2^(n-1),wheren>=1.
 MaximumNo.ofnodesinaBinarytreeofheightis2^(n-1),where n>=1.
 For anynon-emptytree,nl=nd+1 where nlisthe number ofleafnodesand nd isthe no.of
nodes of degree 2.
12. Whatarethedifferentwaysofrepresenting aBinaryTree?
 LinearRepresentationusing Arrays.
 LinkedRepresentationusing Pointers.
13. Statethemeritsoflinearrepresentation ofbinary trees.
 Storemethodsiseasyandcanbeeasilyimplementedinarrays.
 Whenthelocationofthe parent/childnodeisknown,otheronecanbedeterminedeasily.
 Itrequiresstatic memoryallocationso it iseasilyimplementedinallprogramming
languages.
Insertionsanddeletionsaretougher.
14. State the DISADVANTAGES of linear representation of binary trees.
  Processingconsumesexcessoftime.
 Slowdatamovementsupand downthe array.

15. DefineTraversal.
Traversalisanoperationwhichcanbeperformed onabinarytreeis visitingallthe nodes
exactly once.
Inorder:traversingtheLST,visitingtherootandfinallytraversingtheRST.
Preorder:visitingroot,traversingLSTandfinallytraversingRST.
Post-order:traversingLST,thenRST andfinallyvisitingroot.

16. Whatarethetasksperformed whiletraversingabinarytree?

 Visitinganode
 Traversetheleftstructure
 Traversetherightstructure.

17. Whatarethetasksperformed duringpreordertraversal?


Processtherootnode

Traversetheleftsubtree

Traversetherightsubtree.
Ex : +AB
18. Whatarethetasksperformed duringinordertraversal?
 Traversetheleftsubtree
 Processtherootnode
 Traversetherightsubtree.
Ex : A+B

19. Whatarethetasksperformed duringpostordertraversal?

 Traversetheleftsubtree
 Traversetherightsubtree.
 Processtherootnode.
Ex : AB+

20. Givethepre&postfixformoftheexpression(a+((b*(c-e))/f).

21. DefineaBinarySearchTree.
ABinarySearchTree isaspecialbinarytree,whichiseitheremptyorifitis empty it
should satisfy the conditions given below:
 Every node has a value and no two nodes should have the same value(Values should be
distinct).
The value in any left subtree is less than the value of its parent node.
The value in any right subtree is greater than the value of its parent node.
22. Whatdoumean byGeneraltrees?
GeneralTreeisatreewithnodeshaving anynumberofchildren.

23. DefineForest.
Aforest isacollectiononN(N>0) disjoint treeorgroupoftreesarecalled forest.Ifthe root is
removed from the tree that tree becomes a forest.
24. Definebalancedsearchtree.
Balancedsearchtreehavethe structureofbinarytreeandobeybinarysearchtreeproperties withthat
it always maintains the height as O(log n) bymeans ofa specialkind ofrotations. Eg. AVL, Splay,
B-tree.

25. DefineAVLtree.
Anemptytreeisheight balanced. IfT isanon-emptybinarytreewithTLand TRas Itsleft
and right subtrees, then T is height balanced if
1.
TLandTRareheightbalanced.
2.
|hL -hR|≤1.
WherehlandhraretheheightofTLandTRrespectively.

26. WhatarethedrawbacksofAVLtrees?
The drawbacksofAVLtrees are
 Frequentrotations
 Theneedtomaintainbalancesforthetree’snodes
 Overallcomplexity,especiallyofthedeletionoperation.

27. Whatis aheap?

Aheap isapartiallyordereddatastructure, and canbedefinedasabinarytree assigned to its
nodes, one keyper node, provided the following two conditions
aremet
 The tree’s shape requirement-The binary tree is essentially complete, thatis
alltheleavesarefullexcept possiblythe last level, whereonlysomerightmost leaves
will be missing.
 The parentaldominance requirement-The keyat each node is greater thator equal
to the keys of its children

28. Whatisthemainuse of heap?

Heaps are especially suitable for implementing priorityqueues. Priority queue is a set of
items with orderable characteristic called an item’s priority, with the following operations
 Findinganitemwiththehighestpriority
 Deletinganitemwithhighestpriority
 Addinga newitemtothe set
29. Give three properties of heaps?
The properties of heap are
Thereexistsexactlyoneessentiallycompletebinarytreewith‘n’nodes.Itsheightisequalto log2n
Therootoftheheapisalwaysthelargestelement
Anodeofaheapconsideredwithallitsdescendantsisalsoaheap

30. Givethemainpropertyofaheapthatisimplementedasanarray.

A heap can be implemented as an array by recording its elements in the top-down, left-to-
rightfashion.
It is convenient to store the heap’s elements in positions 1 through n of such an array. In such a
representation
 The parental node keys will be in the first n/2 positions of the array, while the leaf keys will
occupy the last n/2 positions
The children of a key in the array’s parental position ‘i’ (1in/2) will be in positions 2i and
2i+1and correspondingly, the parent of the key in position ‘i’ (2in) will be in position i/2.
31. What are the two alternatives that are used to construct a heap?
The two alternatives to construct a heap are
Bottom-up heap construction
Top-downheapconstruction
32. Give the pseudocode for Bottom-up heap construction.

ALGORITHM HeapBottomUp(H[1..n])
//Constructs a heap from the elements of the given array
//Input An array H[1..n] of orderable elements
//OutputAheapH[1..n] for
In/2 downto 1 do
kI;vH[k]heapfalsewhilenotheapand2*kndoj2*kifj<n if H[j] < H[j+1]
jj+1
if vH[j]
heaptrue
elseH[k]H[j];kj H[k]v
 33. Whatisthealgorithmto deletetheroot’skeyfromthe heap?
ALGORITHM
 Exchangethe root’skeywiththelastkeyKofthe heap
 Decreasetheheap’ssizebyone
 “Heapify” the smaller tree by sifting K down the tree exactly in the same way as
bottom-upheapconstruction. Verifytheparentaldominance for K: ifit holdsstop the
process, if not swap K with the larger of its children and repeat this operation
untilthe parental dominance holds for K in its new position.

34. Whodiscovered heapsortand howdoesitwork?

HeapsortwasdiscoveredbyJ.W.J.Williams.Thisisatwostageprocessthat works as
follows
 Stage1Heapconstruction: construct aheapforagivenarray.
 Stage 2Maximum deletions:Apply the rootdeletion operation n-1times to the
remaining heap

35. Whatis amin-heap?

A min-heap is a mirror image of the heap structure. It is a complete binary tree in which
every element is less than or equal to its children. So the root of the min-heap contains the
smallest element.A B-tree of order m in an m-way search tree that is either empty or is of height
≥1 and

1. The root node has at least 2 children

2. All nodes other than the root node and failure nodes have at least m/2 children.

3. All failure nodes are at same level.

38. Define Binary Heap?

A Binary Heap is a complete binary tree in which the key value of any node must be
lesserthanitschildreniscalledminheap.Ifthekeyvalueofanynodeisgreaterthanitschildren is called
max heap.Binary heap is also called as partially ordered tree.

39. Explain array implementation of Binary Heap.

Foranyelementinthearrayposition‘i’,theleftchildisattheposition‘2i’,theright child is at
the position ‘2i+1’ and parent is at the position ‘i/2’.
40. DefineMax-heap.
Maxheap: A heap in which the parent has a larger keythat the child’s key values then
it is called Maxheap.

41. ExplainAVLrotation.
Manipulation of tree pointers is centered at the pivot node to bring the tree back into
height balance. The visualeffect ofthis pointer manipulationso to rotatethe subtree whose root is
the pivot node. This operation is referred as AVL rotation.

42.Whatarethedifferent typeofRotation inAVLTree?

Twotypesofrotationare
1. singlerotation
2. doublerotation.

PART-B

1. Writeanalgorithmforpreorder,inorderand postordertraversalofabinarytree.
2. Explainthefollowingoperationsonabinarysearchtree withsuitable
algorithms
a. Finda node
b. Findtheminimumandmaximumelementsofbinarysearchtree.
3. Writeanalgorithmforinsertinganddeletinganodeinabinarysearchtree.
4. Describetheconceptofthreadedbinarytree withexample.
5. Discussindetailthe various methods inwhichabinarytreecanberepresented. Discuss
theadvantage and disadvantageofeach method.

6. Consider the following list of

numbers14,15,4,9,7,18,3,5,16,4,20,17,9,14,5.Usingthatconstructabinarysearchtree.
7. Construct B Tree of order m=5 for the following keys
1,12,8,2,25,5,14,28,17,7,52,16,48,68,3,26,29,53,55,45.Deletethekeys8and55.Statethe
rulesfordeletion.
8. DiscusshowtoinsertanelementinaAVLtreeandexplainwithalgorithm.
9. ExplainhowdeletioncantakeplaceinAVLtreeswithsuitablealgorithm
10. What are AVL trees? Describe the different rotations defined for AVL tree.
11. Analyze the operations of B-tree using 2-3 tree with example
13.Explaintheconstructionofexpressiontreewithexample.Givetheapplicationsoftrees
14.Illustratetheconstructionofbinomialheapsanditsoperationswithasuitableexample.
15.Illustrate how the delete operation is performed on binary heap?
16.Write suitable operations for percolate up and percolate down operations in a binary heap.
 UNIT-4

PART-A

1. DefineGraph.
AGraph G, consists ofa set ofvertices V, and a set ofedges E.V is a finite non-emptyset
consistingofverticesofverticesofthegraph. ThesetofedgesE consistsofapair ofvertices from the
vertex set.

2. Whatisundirectedgraph.
Ifan edge between any two nodes in a graph is not directionally oriented, a graph is called as
undirected graph. It is also called as unqualified graph.
3. Whatisdirectedgraph.
If an edge between any two nodes in a graph isdirectionally oriented, a graph is called as
directed graph.It is also called as digraph.
4. Defineacycleinagraph.
Acycle is a path containing atleast thee vertices such that the starting and the ending vertices
are the same.
5. Defineaweaklyconnectedgraph.
A directed graph is said to be a weakly connected graph if any vertex doesnt have a directed
path to any other vertices.
6. Defineaweightedgraph.
A graph is said to be weighted graph if every edge in the graph is assigned some weight or
value.Theweight ofanedge isapositivevaluethatmayberepresentingthedistance betweenthe
vertices or the weights of the edges along the path.
2
5 11
7. Define parallel edges
Insomedirectedaswellasundirectedgraphcertainpairofnodesarejoinedbymore than
oneedge, such edges are called parallel edges.
8. List some representation of Graphs?
Physically a graph can be represented as,
-adjacency matrix
-Incident matrix
-Adjacency list
-Adjacency multilist
-Circular adjacency list
8. DefineAdjacencyMatrix.
Adjacency Matrixis arepresentation used torepresenta graph with zeros and ones.A graph
containing n vertices can be represented using n rows and n columns

9. What is meant by Traversing a Graph?

Itmeansvisitingallthenodesinthegraph

10. Defineundirected graph/directedgraph.

IfG=(V,E) isagraph. Theedgebetweenv1andv2isrepresented as(v1, v2). Iftheedgesofthe
form(v1, v2) and (v2, v1) are treated asthe same edge, thenG is said to be anundirected graph.
Incaseofadirected graph,theedge<v1,v2>and<v2,v1>aredifferent.

11. Defineoutdegreeofagraph.
Inadirectedgraph, foranynodev,thenumberofoutgoingedges fromvarecalledoutdegree of a node
v. Ex : out degree of c =2

12. Define Indegreeofagraph.

Inadirectedgraph, for anynodev,thenumberofincomingedgesto varecalledIndegreeofa node v.
Ex : In degree of c =1

13. Definetotaldegreeofagraph.
The sum of the In degree and out degree of a node is called the total degree ofthe node. Ex:
total degree of a node c = 1 +2 =3

14. Defineapathinagraph.
Apathinagraphisdefinedasasequenceofdistinctverticeseachadjacenttothe next,except possibly the
first vertex and last vertex is different.
Thepathinagraph istheroutetakento reachtheterminalnode fromastarting node. The path
from ato eare
P1=((a,b),(b,e))
P2=((a,c),(c,d),(d,e))

15. WhatisacompleteGraph.
Acompletegraphisa graphinwhichthereisanedgebetweeneverypairofvertices.
16. GivetheadjacencylistrepresentationforthefollowingABCD
0111
0001
0001
1110
17. List out the graph traversals of graph search?
The two methods of traversal is,
-Depth First Search (DFS)
-Breadth First Search (BFS)
18. Defineminimumcostspanning tree?
Aspanningtreeofa connectedgraphG,isa treeconsistingofedgesandallthe vertices of
G.
InminimumspanningtreeT,fora givengraphG,the totalweightsoftheedgesofthe
spanningtreemustbeminimumcompared toallother spanningtreesgenerated fromG.
-Prim’sandKruskalisthealgorithmforfindingMinimumCostSpanningTree.

19. DefineShortestpathproblem?
For a givengraphG=(V, E), withweights assigned to the edges ofG, we have to find the
shortest path(pathlength isdefined assumoftheweightsofthe edges) fromanygivensource vertex to
all the remaining vertices of G.

20. Definetopologicalsort?
Atopologicalsortisanorderingofvertices inadirectedacyclicgraph, suchthat ifthere isa path
from vito vjappears after viin the ordering.

21. WhatistheuseofKruskal’salgorithmandwhodiscovered it?

Kruskal’salgorithm isoneof thegreedy techniquestosolvetheminimum spanning
treeproblem. It was discovered byJosephKruskalwhen he was a second-year graduate student.

22. WhatistheuseofDijksra’salgorithm?
Dijkstra’s algorithm is used to solve the single-source shortest-paths problem: for a
givenvertexcalledthesourceinaweightedconnectedgraph,findtheshortestpathtoall itsother
vertices. The single-source shortest-paths problem asks for a family of paths, each leading from
thesourcetoadifferent vertexinthegraph, thoughsomepaths mayhaveedges in common.

23. Prove that the maximumnumberofedges that a graph withn Vertices is

n*(n-1)/2.
Chooseavertexanddrawedges fromthisvertextotheremainingn-1vertices. Then, from these
n-1 vertices, choose a vertex and draw edges to the rest of the n-2 Vertices. Continue this
process till it ends with a single Vertex.
Hence,thetotalnumberofedgesadded ingraphis (n-
1)+(n-2)+(n-3)+…+1 =n*(n-1)/2.
24. Defineconnectedandstronglyconnectedgraph.
TwoVerticesuand varesaidto beconnectedifthereexistsapathfromuto vinthegraph. A directed
graph is said to be connected ifeverypair ofvertices in the graph is connected.
Adirectedgraphissaidto bestronglyconnected ifforeverypairofdistinct vertices viandvj, there
exists two disjoint paths, one fromvito vj and the other fromvjto vi.
PART-B
1. Examinetopologicalsorting ofagraphGwithsuitableexample.
2. Differentiatedepth-firstsearchandbreadth-firstsearchtraversalofagraphwithsuitable
examples.
3. Explain with algorithm, How DFS be performed on a undirected graph.
4. Showthealgorithmforfindingconnectedcomponentsofanundirectedgraphusing DFS,
and derive the time complexity of the algorithm.
5. DiscussanalgorithmforBreadthfirstSearchonagraph.
6. Discussanytwoapplications ofGraphwithexample.
7. Explainthedepthfirst approachoffindingarticulationpoints inaconnectedgraphwith
necessaryalgorithm.
8. WriteshortnotesonBi-connectivity.

9. DiscusshowtofindEuler circuitwithanexample.

UNIT-V
PART-A

1. Definesorting
Sortingarrangesthenumericalandalphabeticaldatapresent ina list inaspecificorder
orsequence. Therearea number ofsortingtechniquesavailable. Thealgorithmscanbe
chosen based on the following factors
– Sizeofthedatastructure
– Algorithmefficiency
– Programmer’sknowledgeofthetechnique.
Mentionthetypesofsorting
2. x Internal sorting
x Externalsorting

3. Whatdoyou meanbyinternaland externalsorting?

An internal sort is any data sorting process that takes place entirely within the main
memoryofacomputer.This ispossiblewhenever thedatato besortedissmallenough to all
be held in the main memory.
External sorting is a term for a class of sorting algorithms that can handle massive
amountsofdata.Externalsorting isrequiredwhenthedatabeingsorteddo notfitintothe main
memory of a computing device (usually RAM) and instead they must reside in the
slower external memory (usually a hard drive)

4. Definebubblesort
Bubblesort isasimplesortingalgorithmthat worksbyrepeatedlysteppingthroughthe list
tobesorted, comparingeachpair ofadjacent itemsand swappingthemiftheyare in the
wrong order. The pass throughthe list is repeated until no swaps are needed, which
indicates that the list is sorted. The algorithm gets its name from the waysmaller
elements "bubble" to the top of the list.
5. How theinsertionsortisdonewiththearray?
Itsortsalistofelementsbyinsertingeachsuccessiveelementinthepreviousl ysorted sublist.
Consider an array to be sorted A[1],A[2],….A[n]
b. Pass2:A[3] iscomparedwithbothA[1]andA[2] and insertedat anappropriate place.
This makes A[1], A[2],A[3] as a sorted sub array.
c. Passn-1:A[n]iscomparedwitheachelementinthesubarray A[1],A[2],
……A[n-1]andinsertedatanappropriate position.

6. What are the steps for selection sort?

xThealgorithmdividestheinputlistintotwoparts:thesublistofitemsalreadysorted, which is
built up from left to right at the front (left) of the list, and the sublist of items
remaining to be sorted that occupy the rest of the list.
x Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. x
The algorithm proceeds by finding the smallest (or largest, depending on sorting
order) element in the unsorted sublist, exchanging it with the leftmost unsorted
element(puttingitinsortedorder),andmovingthesublistboundariesoneelementto the
right.
7. What is meant by shell sort?
Shell sort, also known as Shell sort or Shell's method, is an in-place comparison sort. It
can either be seen as a generalization of sorting by exchange (bubble sort) or sorting
by insertion (insertion sort).[1] The method starts by sorting elements far apart from
each other and progressively reducing the gap between them. Starting with far apart
elements can move some out-of-place elements into position faster than a simple
nearest neighbor exchange. Donald Shell published the first version of this sort in
1959.TherunningtimeofShellsortisheavilydependentonthegapsequenceituses
8. Whatarethe stepsinquicksort?
Thestepsare:
a. Pickanelement,calledapivot,fromthelist.
b. Reorderthe list sothatallelementswithvalueslessthanthepivotcomebefore the
pivot, while all elements with values greater than the pivot come after it
(equalvaluescango eitherway). Afterthispartitioning, thepivot is inits final
position. This is called the partition operation.
c. Recursivelyapplytheabovestepstothesub-listofelementswithsmaller values and
separately to the sub-list of elements with greater values.

9. Defineradixsort
RadixSort isa clever and intuitive little sorting algorithm. Radixsort isa non-
comparative integer sorting algorithm that sorts data with integer keys by grouping
keysbythe individualdigitswhichsharethesame significant positionand value. Radix
Sort putsthe elements in order bycomparing the digits of the numbers.

10. What aretheadvantagesofinsertionsort

Advantages
a. Simplestsortingtechniqueandeasytoimplement
b. Itperformswellinthecaseofsmallerlists.
c. Itleveragesthepresenceofanyexistingsort patterninthelist
Disadvantages
xEfficiencyofO(n)isnotwellsuitedforlargesizedlists x It
requires large number of elements to be shifted
11. Define searching
Searching refers to determining whether an element is present in a given list of
elementsornot.Iftheelementispresent,thesearchisconsideredassuccessful,otherwiseit is
considered as an unsuccessful search. The choice of a searching technique is based on the
following factors
a. Order of elements in the list i.e., random or sorted
b. Size of the list
 12. Mentionthe typesofsearching
Thetypesare
x Linearsearch
x Binarysearch

13. What ismeantbylinearsearch?

Linearsearch or sequentialsearch isa method forfinding a particular value ina list
that consists of checking every one of its elements, one at a time andin sequence, until
the desired one is found.

14. What isbinary search?

Forbinarysearch,thearrayshouldbearrangedinascendingordescendingorder.
Ineachstep,thealgorithmcomparesthesearchkeyvaluewiththe middleelement of the
array. Ifthe key match, thena matching element hasbeen found and its index, or
position, is returned.
Otherwise, if the search key is less than themiddle element, then the algorithm repeats
itsactiononthesub-arraytothe left ofthe middle element or, ifthe searchkeyisgreater, on the
sub-array to the right.

15. Definehashingfunction
Ahashing functionisakey-to-transformation, whichactsuponagivenkeyto compute the
relative position of the key in an array.
Asimplehash function
HASH(KEY_Value)=(KEY_Value)mod(Table-size)

16. Whatisopenaddressing?
Openaddressing is also called closed hashing, which is analternative to resolve the
collisionswithlinked lists.Inthishashingsystem,ifacollisionoccurs,alternative cells are
tired until an empty cell is found.
Therearethreestrategiesinopenaddressing: x
Linear probing
xQuadraticprobing x
Double hashing
 17. Whatarethecollisionresolutionmethods?
Thefollowingarethecollisionresolutionmethods x
Separate chaining
x Openaddressing
x Multiplehashing

18. Defineseparatechaining
It is an open hashing technique. A pointer field is added to each record location,
whenanoverflowoccurs, thispointerissetto point tooverflow blocks makinga
linked list.
In this method, the table can never overflow, since the linked lists are only
extended upon the arrival of new keys.
19. Whataretheuseofhashtable?
1. Compilerscanusehashtabletokeeptrackofdeclaredvariableinsource code.
2. Ahashtable isusefulfor anygraphtheoryproblemwhere nodeshaver real
names instead of numbers
3. Athirduseofhashtableisinprogramthatplaygames.
4. Onlinespellcheckers
20, Explain Hashing.
Hashing isatechniqueusedto identifythe locationofanidentifier‘x’inthe memoryby some
arithmetic functions like f(x), which gives address of‘x’ inthe table.

21. ExplainHashFunction.
HashFunctiontakesanidentifierandcomputestheaddressofthat identifier inthehash table.

22. MentionDifferenttypesofpopularhashfunction.
1. Divisionmethod
2. Squaremethod
3. Foldingmethod

23. DefineCollision.
Whentwodifferent keyscompute inthesame locationoraddress inthehashtable through
anyone ofthe hashing function then itis termed as collision.

24. MentionDifferenttypesofcollisionresolvingtechniques.
The collision resolving techniques are:
1. Separate chaining.
2. OpenAddressing
Linear Probing
Quadratic Probing
Double Hashing.
 PART-B
1. Describeaboutselectionsortwithsuitableexample.
2. ExaminethealgorithmforInsertionsortandsortthe followingarray:77, 33, 44, 11,
88, 22, 66, 55
3. List thedifferent typesofhashing techniques?Explainthemin detailwith
example.
4. Showtheresult ofinsertingthekeys2,3,5, 7,11,13,15, 6,4into aninitially
emptyextendible hashing data structure with M = 3.
5. WriteaCprogramto searchanumber withthegivenset ofnumbersusing binary
search.
6. Interpretanalgorithmto sortasetof‘N’numbersusing bubblesort and
demonstrate the sorting steps for the following set of numbers:
88,11,22,44,66,99,32,67,54,10.
7. Discussthevariousopenaddressing techniquesinhashingwithanexample.
8. SortthegivenintegersandShowtheintermediateresultsusing
shellsort:35,12,14,9,15,45,32,95,40,5.
9. Writeanalgorithmtosortanintegerarrayusing shellsort.
10. Illustratewithexampletheopenaddressingandchaining methodsoftechniques
collision resolution techniques in hashing.
11. Compareworkingofbinarysearchandlinearsearchtechniquewithexample.
12. Analyzeextendiblehashinginbrief.
13. Explain indetailaboutseparatechaining.
14. Formulatetherehashingtechniquewithsuitableexample.
15. Prepareanalgorithmtosorttheelementsusing radixsortexample.
16. MentionthedifferentSorting methodsandExplainabout methodindetailed
Manner.
17. Sortthesequence96,31,27,42,76,61,10,4usingshellsort andradixsortand
prepare the required steps.
18. Giveninput{4371,1323,6173,4199,4344,9679,1989}andahashfunction
h(x) =x mod10 Prepare the resulting for the following:
a. Separatechaininghashtable.
b. ii)Openaddressinghashtableusinglinearprobing.
c. Openaddressinghahtableusingquadratic probing.
d. Openaddressing hashtablewithsecondhashh2(x)=7-(xmod 7).
19. Writeandexplainnon-recursivealgorithmforbinarysearch.
20. Usingbinarysearch,searchthenumber26fromthelistofnumbersandgive the
steps. 10,7,17,26,32,92
Civil