## DSA_2_MARK

**UNIT-I**

##### PART A

**1.****Write down the definition of data structures?**

A data structure is a mathematical or logical way of organizing data in the memory that consider not only the items stored but also the relationship to each other and also it is characterized by accessing functions.

**2.****Give few examples for data structures?**

Stacks, Queue, List, Trees, graphs and sets. The list ADT has find, insert and delete operatins associated with it.

**3.****List the operation performed by the data structure.**

Create and destroy the data structure

Insert element into the data structure

Delete elements from the data structure

Access elements in the data structure.

**4.****What are the different types of data structures?**

i) Primitive data structure

ii) Non primitive data structure.

**5.****What do you mean by primitive data structure?**

Primitive data structure is concerned with structuring of data at their most primitive level within a computer, that is the data structures are directly operated upon by machine-level instructions.

eg) Integers, real number, characters

**6.****Define non-linear data structure**

Data structure, which is capable of expressing more complex relationship than that of physical adjacency, is called non-linear data structure.

**7.****Give some examples for linear data structures?**

- Stack
- Queue
- List

**8.****What are the two methods for using the data structures?**

i) Computed address method

ii) Link addressing method.

**9.****List down any four applications of data structures?**

- Compiler design
- Operating System
- Database Management system

**10. ****What is meant by an abstract data type?**

An ADT is a set of operation. Abstract data types are mathematical abstractions.Eg.Objects such as list, set and graph along their operations can be viewed as ADT’s.

Nowhere in the definition of ADT’s there is any mention of how the set of operations is implemented.

**11. ****Define list.**

General list of the form a1, a2, a3… an and the size of the list is ‘n’. Any element in the list at the position i is defined to be ai, ai+1 the successor of ai and ai-1 is the predecessor of ai.

**12. ****What are the various operations done under list ADT?**

- Print list
- Insert
- Delete
- FindPrevious
- Find kth
- Find
- Make empty
- IsLast
- IsEmpty

**13. ****What are the different ways to implement list?**

- Array implementation of list
- Linked list implementation of list
- cursor implementation of list

**14. ****What are the advantages in the array implementation of list?**

- Print list operation can be carried out at the linear time
- Find Kth operation takes a constant time

**15. ****What are the disadvantages in the array implementation of list?**

The running time foe insertions and deletions is so slow and

the list size must be known in advance.

**16. ****When cursor implementation of list is used?**

If the linked lists are required and pointers are not available then cursor implementation of list is used.

**17. ****What is a pointer?**

Pointer is a variable, which stores the address. In the linked list the pointer in a node contains the address of the next node.

**18. ****Define node.**

A simple node consists of two fields namely an information field called

INFO and a pointer field called LINK. The INFO field is used to store the data and the LINK field is used to store the address of the next field.

**19. ****What is a linked list?**

Linked list is series of nodes, which are not necessarily adjacent in memory. Each node contains the element and a pointer to the next node.

**20. ****What is a doubly linked list?**

In a simple linked list, there will be one pointer named as ‘NEXT POINTER’ to point the next element, where as in a doubly linked list, there will be two pointers one to point the next element and the other to point the previous element location.

**21. ****Name the three fields of Doubly Linked list?**

Information field

forward link

back link

**22. ****Define circularly linked list?**

In a Singly linked list, if the last node points to the first element of the list, then it is a circularly linked list.

**23. ****Define double circularly linked list?**

In a doubly linked list, if the last node forward link points to the first element of the list, and the first node back link points to the last node of the list, then it is double circularly linked list.

**24. ****Mention the disadvantages of circular list?**

The disadvantage of using circular list are

- It is possible to get into an infinite loop.
- We are not able to detect the end of the list.

**25. ****What is the need for the header?**

Header of the linked list is the first element in the list and it may store the number of elements in the list. It points to the first data element of the list.

Without header

- Insertion at the front of the list needs updating of the linked list address.
- Deletion at the front of the list also needs updating of the linked list address and and also code for deletion of a node requires a previous node address.

The header node solves all the above problems.

**26. ****List three examples that uses linked list?**

- Polynomial ADT
- Radix sort
- Multi lists

**27. ****Define Stack**

A Stack is an ordered list in which all insertions and deletion are made at one

end, called the top. In a stack S = (a1,…an), a1 is the bottom most element and element ai is on top of element ai-1. Stack is also referred as Last In First Out (LIFO) list.

The operations of the stack are Push and Pop. Push adds an element to one end of the stack. Pop deletes an element from the same end of the stack

**28. ****What are the various Operations performed on the Stack?**

The various operations that are performed on the stack are

CREATE(S) – Creates S as an empty stack.

PUSH(S,X) – Adds the element X to the top of the stack.

POP(S) – Deletes the top most element from the stack.

TOP(S) – returns the value of top most element from the stack.

ISEMTPTY(S) – returns true if Stack is empty else false.

ISFULL(S) – returns true if Stack is full else false.

**29. ****How do you test for an empty stack?**

The condition for testing an empty stack is top =-1, where top is the pointer pointing to the topmost element of the stack.

**30. ****Name two applications of stack?**

1) Stack is used to explain the processing of subroutine calls and their returns.

2) Recursive procedures can be implemented using stack.

3) Conversion of Infix to Postfix expression can be implemented using stack.

4) Evaluation of Postfix expression can be implemented using stack.

**31. ****Define a suffix expression.**

The notation used to write the operator at the end of the operands is called suffix notation.

Suffix _ operand operand operator

**32. ****What do you meant by fully parenthesized expression? Give eg.**

A pair of parentheses has the same parenthetical level as that of the operator to which it corresponds. Such an expression is called fully parenthesized expression.

Ex: (a+((b *c) + (d * e))

**33. ****Write postfix from of the expression –A+B-C+D?**

## A-B+C-D+

**34. ****What are the postfix and prefix forms of the expression?**

A+B*(C-D)/(P-R)

Postfix form: ABCD-*PR-/+

Prefix form: +A/*B-CD-PR

**35. ****Explain the usage of stack in recursive algorithm implementation?**

In recursive algorithms, stack data structures is used to store the return address when a recursive call is encountered and also to store the values of all the parameters essential to the current state of the procedure.

**36. ****Define Queues.**

A Queue is an ordered list in which all insertions take place at one end called the rear, while all deletions take place at the other end called the front. Queue is also referred as First In First Out (FIFO) list.

**37. ****What are the various operations performed on the Queue?**

The various operations that are performed on the queue are

CREATE(Q) – Creates S as an empty Queue.

Enqueue(Q,X) – Adds the element X to the Queue.

Dequeue(Q) – Deletes a element from the Queue.

ISEMTPTY(Q) – returns true if Queue is empty else false.

ISFULL(Q) – returns true if Queue is full else false.

**38. ****How do you test for an empty Queue?**

The condition for testing an empty queue is rear=front-1.

**39. ****Define Dqueue.**

Double entered Queue. It is a linear list in which insertions and deletion are made from either end of the structure.

**40. ****Define Circular Queue.**

Another representation of a queue, which prevents an excessive use of memory is to arrange elements Q[1], Q[2],…..Q[n] in a circular fashion. That is, it is the queue, which wraps around upon reaching the end of the array

**UNIT-II**

###### PART A

**1.****Define tree?**

Recursive definition of the tree

A tree is a collection of nodes. The collection can e empty; otherwise, a tree consists of a distinguished node r, called root, and zero or more non-empty (sub) tress T1, T2,….,Tk. Each of whose roots are connected by a directed edge from r.

**2.****Define leaf node?**

In a directed tree any node, which has out degree 0, is called a terminal node or a leaf.

**3. ****Define directed tree and forest?**

A directed tree is an acylic digraph which has one node called its root with in

degree 0 while all other nodes have in degree 1. In a directed tree any node which has out degree 0 is called a terminal node or a leaf all others nodes are called branch nodes. A set of disjoint tree is a forest.

**4. ****Write the definition of simple path and elementary path?**

A path in a digraph in which the edges are distinct is called a simple path. A path in which all the nodes through which it traverses are distinct is called an elementary path.

**5.****Write the recursive preorder algorithm?**

Procedure Preorder

Process the root node

Process the left sub tree

Process the right sub tree

**6.****Write the recursive postorder algorithm?**

Procedure postorder** **

Process the left sub tree

Process the right sub tree

Process the root node

**7.****Write the recursive inorder algorithm?**

Procedure inorder** **

Process the left sub tree

Process the root node

Process the right sub tree

**8.****What is a forest ?**

A forest may be defined as an acyclic graph in which every node has one or no predecessors.A tree may be defined as a forest in which only a single node called root has no predecessors.

**9.****What is meant by directed tree?**

Directed tree is an acyclic diagraph which has one node called its root with indegree 0 while all other nodes have indegree 1.

**10. ****What is an ordered tree?**

In a directed tree if the ordering of the nodes at each level is prescribed then such a tree is called ordered tree.

**11. ****What is a Binary tree?**

A Binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other two subsets are themselves binary trees called the left and right subtrees.

**12. ****Define Strictly binary tree?**

If every nonleaf node in a binary tree has nonempty left and right subtrees, the tree is termed as a strictly binary tree.

**13. ****Define complete binary tree?**

A complete binary tree of depth d is the strictly binary tree all of whose are at level d.

**14. ****What is an almost complete binary tree?**

A binary tree of depth d is an almost complete binary tree if

- Each leaf in the tree is either at level d or at level d-1
- For any node nd in the tree with a right descendant at level d,all the left descendants of nd that are leaves are at level d.

**15. ****What are the applications of binary tree?**

Binary tree is used in data processing.

a. File index schemes

b. Hierarchical database management system

**16. ****What is traversing?**

Traversing a tree means processing it in such a way, that each node is visited only once.

**17. ****What are the different types of traversing?**

The different types of traversing are

a. Pre-order traversal -yields prefix from of expression.

b. In-order traversal -yields infix form of expression.

c. Post-order traversal -yields postfix from of expression.

**18. ****What are the two methods of binary tree implementation?**

Two methods to implement a binary tree are,

a. Linear representation.

b. Linked representation

**19. ****Define pre-order traversal?**

Pre-order traversal entails the following steps

a. Process the root node

b. Process the left subtree

c. Process the right subtree

**20. ****Define post-order traversal?**

Post order traversal entails the following steps

a. Process the left subtree

b. Process the right subtree

c. Process the root node

**21. ****Define in -order traversal?**

In-order traversal entails the following steps

a. Process the left subtree

b. Process the root node

c. Process the right subtree

**22. ****Define AVL Tree**

An AVL tree is a binary search tree except that for every node in the tree, the height of the left and right subtrees can differ by atmost 1.

**23. ****What is a balance factor in AVL trees?**

Balance factor of a node is defined to be the difference between the heights of the node’s left subtree and the height of the node’s right subtree.

**24. ****What is the length of the path in a tree?**

The length of the path is the number of edges on the path. In a tree there is exactly one path form the root to each node.

**25. ****Define expression trees?**

The leaves of an expression tree are operands such as constants or variable names and the other nodes contain operators.

**UNIT-III**

**26. ****What is the need for hashing?**

Hashing is used to perform insertions, deletions and find in constant average time.

**27. ****Define hash function?**

Hash function takes an identifier and computes the address of that identifier in the hash table using some function.

**28. ****What are the problems in hashing?**

a. Collision

b. Overflow

**29. ****What is collision?**

When two keys compute in to the same location or address in the hash table through any of the hashing function then it is termed collision.

**30. ****Define collision resolution**

The process of finding another position for the collide record. Various techniques are

- Separate chaining
- Open addressing

**31. ****Define Binary heap?**

A heap in which the parent has a smaller key than the child’s is called a min heap. **********

###### UNIT-IV

###### PART A

**1. ****Write the definition of weighted graph?**

A graph in which weights are assigned to every edge is called a weighted graph.

**2. ****Define in degree, out degree and total degree?**

In a directed graph for any node V the numbers of edges which have V as their initial node is called the out degree of the node V. The number of edges which have as their terminal node is called the in degree of V and the sum of the out degree and in degree of a node V is called its total degree.

**3.****Define Graph?**

A graph G consist of a nonempty set V which is a set of nodes of the graph, a set E which is the set of edges of the graph, and a mapping from the set of edges E to set of pairs of elements of V. It can also be represented as G=(V, E).

**4. ****Define adjacency matrix?**

The adjacency matrix is an n x n matrix A whose elements aij are given by

Aij = 1 if (vi, vj) E

0 otherwise

**5.****Define adjacent nodes?**

Any two nodes, which are connected by an edge in a graph, are called adjacent nodes. For example, if an edge xÎE is associated with a pair of nodes

(u,v) where u, v ÎV, then we say that the edge x connects the nodes u and v.

**6.****What is a directed graph?**

A graph in which every edge is directed is called a directed graph.

**7.****What is an undirected graph?**

A graph in which every edge is undirected is called an undirected graph.

**8.****What is a loop?**

An edge of a graph, which connects to itself, is called a loop or sling.

**9.****What is a simple graph?**

A simple graph is a graph, which has not more than one edge between a pair of nodes.

**10. ****What is a weighted graph?**

A graph in which weights are assigned to every edge is called a weighted graph.

**11. ****Define out degree of a graph?**

In a directed graph, for any node v, the number of edges, which have v as their initial node, is called the out degree of the node v.

**12. ****Define path in a graph?**

The path in a graph is the route taken to reach terminal node from a starting node.

**13. ****What is a simple path?**

A path in a diagram in which the edges are distinct is called a simple path.

It is also called as edge simple.

**14. ****What is a cycle or a circuit?**

A path which originates and ends in the same node is called a cycle or circuit.

**15. ****What is an acyclic graph?**

A simple diagram, which does not have any cycles, is called an acyclic graph.

**16. ****What is meant by strongly connected in a graph?**

An undirected graph is connected, if there is a path from every vertex to every other vertex. A directed graph with this property is called strongly connected.

**17. ****When a graph said to be weakly connected?**

When a directed graph is not strongly connected but the underlying graph is connected, then the graph is said to be weakly connected.

**18. ****Name the different ways of representing a graph?**

a. Adjacency matrix

b. Adjacency list

**19. ****What is an undirected acyclic graph?**

When every edge in an acyclic graph is undirected, it is called an undirected acyclic graph. It is also called as undirected forest.

**20. ****What is meant by depth?**

The depth of a list is the maximum level attributed to any element with in the list or with in any sub list in the list.

**21. ****What is the use of BFS?**

BFS can be used to find the shortest distance between some starting node and the remaining nodes of the graph. The shortest distance is the minimum number of edges traversed in order to travel from the start node the specific node being examined.

**22. ****Write DFS algorithm**

Procedure DFS (index, count)

1. Update the depth first search number, set and mark current node

2. Set up loop to examine each neighbor of current node

3. If node has been marked label it and make recursive call

4. Return to point of all

**23. ****Write BFS algorithm**

1. Initialize the first node’s dist number and place in queue

2. Repeat until all nodes have been examined

3. Remove current node to be examined from queue

4. Find all unlabeled nodes adjacent to current node

5. If this is an unvested node label it and add it to the queue

6. Finished.

**24. ****Define biconnected graph?**

A graph is called biconnected if there is no single node whose removal causes the graph to break into two or more pieces. A node whose removal causes the graph to become disconnected is called a cut vertex.

**25. ****Write the time complexly of BFS algorithm**

The time analysis for the BFS algorithm is O(n + e) Where e is the number of edges and n is the number vertices.

**26. ****What are the two traversal strategies used in traversing a graph?**

a. Breadth first search

b. Depth first search

**27. ****What is a minimum spanning tree?**

A minimum spanning tree of an undirected graph G is a tree formed from graph edges that connects all the vertices of G at the lowest total cost.

**28. ****What is NP?**

NP is the class of decision problems for which a given proposed solution for a given input can be checked quickly to see if it is really a solution.

**UNIT V**

**1.****What is divide and conquer?**

Given a function to compute on ‘n’ inputs the divide and conquer strategy suggests splitting the n inputs into k subsets yielding k subproblems. These sub problems are solved independently and then a solution must be found to combine the sub solutions into a solution of the whole.

**41. ****State the importance of dynamic programming.**

Instead, a mathematical way of thinking about it is to look at what you should do at the end, if you get to that stage. So you think about the best decision with the last potential partner (which you must choose) and then the last but one and so on. This way of tackling the problem backwards is Dynamic programming.

**42. ****Where is dynamic programming used?**

Dynamic programming is used when the problem is to be solved in a sequence of intermediate steps. It is particularly relevant for many optimization problems, i.e. frequently encountered in Operations research.

**43. ****Write down the algorithm for solving Towers of Hanoi problem?**

1. Push parameters and return address on stack.

2. If the stopping value has been reached then pop the stack to return to previous level else move all except the final disc from starting to intermediate needle.

3. Move final discs from start to destination needle.

4. Move remaining discs from intermediate to destination needle.

5. Return to previous level by popping stack.

**44. ****Write the general algorithm for solving the Tower of Hanoi problem?**

a. Only one disc may be moved at a time.

b. A disc may be moved from any needle to any other

c. At no time may a larger disc rest upon a smaller disc.

**45. ****Write the steps in the general algorithm for recursive procedure?**

i) Prologue- save the parameters, local variables and return address

ii) Body – If the base criterion has been reached then perform the final computation and go to step3, otherwise perform the partial computation and go to step1.

iii) Epilogue –Restore the most recently saved parameters local variables and return address. Go to return address.

**46. ****Define Space Complexity**

The Space complexity of an algorithm is the amount of memory it needs to run to completion

**47. ****Define Time Complexity**

Time complexity of an algorithm is the amount of computer time it needs to run to completion

**48. ****What are asymptotic notations?**

The notations that enables us to make meaningful statements about the time and space complexity of a program is called asymptotic notations.