I UNIT-Linear structures
(LINKED LISTS, STACKS & QUEUES)
1. Define algorithm.
An algorithm is a step-by-step recipe for solving an instance of a problem. It is a precise procedure for solving a problem in finite number of steps. An algorithm states the actions to be executed and the order in which these actions are to be executed. An algorithm is also defined as a well-ordered collection of clear and simple instructions of definite and effectively computable operations that, when executed, produces a result and stops executing at some point in a finite amount of time rather than just going on and on infinitely.
2. List the properties of an algorithm.
The properties of an algorithm includes,
· An algorithm takes zero or more inputs.
· An algorithm results in one or more outputs.
· All operations can be carried out in a finite time.
· An algorithm should be efficient and flexible.
· It should use less memory space as much as possible.
· An algorithm must terminate after a finite number of steps.
· Each step in the algorithm after a finite number of steps.
· Each step in the algorithm must be easily understood for someone reading it.
· An algorithm should be concise and compact to facilitate verification of their correctness.
3. Define efficiency of an algorithm.
Efficiency of an algorithm denotes the rate at which an algorithm solves a problem of size n. it is measured by the amount of resources it uses, the time and the space. The time refers to the number of steps the algorithm executes while the space refers to the number of unit memory storage it requires.
4. Define run time. What is its impact in calculating time complexity?
Run time is the time to execute the compiled program. The run time of an algorithm depends upon the number of instructions present in the algorithm. The run time is in the control of the programmer, as the compiler is going to compile only the same number of statements, irrespective of the type of compiler used.
5. Define time complexity of an algorithm.
Time complexity of an algorithm is the amount of time (or the number of steps) needed by a program to complete its task.
6. Define worst case of an algorithm.
Worst case is the longest time that an algorithm will use over all instances of size n for a given problem to produce a desired result.
7. Define space complexity of an algorithm.
Space complexity of a program is the amount of memory used at once by the algorithm until it completes its execution.
8. State the different memory spaces occupied by an algorithm.
The following are the different spaces considered for determining the amount of memory used by the algorithm, instruction space, data space and environment space.
9. Define divide and conquer algorithm.
Divide and conquer is based on dividing the problem into several, smaller sub instances, solving them independently and then combining the sub instance solutions so as to yield a solution for the original instance.
10. Mention some of the problems that implements divide and conquer algorithm.
Problems that implements divide and conquer algorithm are quick sort, binary search, merge sort and strassen’s matrix multiplication.
11. Define data structures.
Data structure defines a way of organizing all data items that consider not only the elements stored but also stores the relationship between the elements.
12. Define static data structures.
A data structure formed when the number of data items are known in advance is referred as static data structure or fixed size data structure.
13. List some of the static data structures in C.
Some of the static data structures in C refer to arrays, pointers, structures, etc.,
14. Define dynamic data structures.
A data structure formed when the number of data items are not known in advance is known as dynamic data structure or variable size data structure.
15. List some of the dynamic data structures in C.
Some of the dynamic data structures in C refers to linked lists, stacks, queues, trees. Etc.,
16. What are the different types of data structure?
· Linear data structure.
· Non-linear data structure
17. Define linear data structures.
Linear data structures are data structures having a linear relationship between its adjacent elements. Linked lists are examples of linear data structures.
18. Define non-linear data structures.
Non-linear data structures are data structures that don’t have a linear relationship between its adjacent elements but have a hierarchical relationship between the elements. Trees and graphs are examples of non-linear data structures.
19. State the different types of linked lists.
The different types of linked list include single linked list, double linked list and circular linked list.
20. State the different types of circular linked lists.
The different types of circular linked list include circular singly linked list and circular doubly linked list.
21. List the basic operations carried out in a linked list.
The basic operations carried out in a linked list includes,
· Searching an element in a list.
· Finding the successor element of a node.
· Finding the predecessor element of a node.
· Appending a linked list to another existing list.
· Splitting a linked list in to two lists.
· Arranging a linked list in ascending order.
22. List the advantages in using a linked list.
The advantages in using a linked list are,
· It is not necessary to specify the number of elements in a linked list during its declaration.
· Linked list can grow and shrink in size depending upon the insertion and deletion that occurs in the list.
· Insertions and deletions at any place can be handled easily and efficiently.
· A linked list does not waste any memory space.
23. List out the disadvantages in using a linked list.
The disadvantages in using a linked list are,
· Searching a particular element in a list is difficult and time consuming.
· A linked list will use more storage space than an array to store the same number of elements (therefore each element in a list needs additional memory space for storing the address of the next node).
24. Define Abstract Data Type(ADT).
An abstract data type is a set of operations for which the implementation of the data structure is not specified anywhere in the program.
25. State the difference between arrays and linked list.
Arrays linked list
Size of any array is fixed. Size of a list is variable.
It is necessary to specify the number it is not necessary to specify the in an array number of, elements during declaration. Number of elements in during declaration.
Insertion and deletions are somewhat Insertions and deletions are carried in an difficult out easily. Array.
It occupies less memory than a linked list It occupies more memory. for the same number of elements.
26. What are the applications of Arrays?
· Parallel Arrays to store records
· Sparse Matrices
· Matrix operations
27. Mention some of the application of linked list.
Some of the applications of linked lists are,
· Polynomial Manipulation
28. Define a stack.
Stack is an ordered collection of elements in which insertions and deletions are restricted to one end. The end from which elements are added and/or removed is referred to as top of the stack. Stacks are also referred as “piles” and “push-down lists”.
29. List out the basic operations that can be performed on a stack and a queue.
The basic operations that can be performed on a stack and queue are,
· Push operation
· Pop operation
· Peek operation
· Empty check
· Full occupied check
· Count no. of nodes.
· View contents.
30. State the different ways of representing expressions.
The different ways of representing expressions are,
· Infix Notation
· Prefix Notation
· Postfix Notation
31. State the advantages of using infix notations.
The advantages of using infix notations are,
· It is the mathematical way of representing the expression.
· It’s easier to see visually which operation is done from first to LAST.
32. State the advantages of using postfix notations.
The advantages of using postfix notations are,
· You need not worry about the rules of precedence.
· You need not worry about the rules for right to left associativity.
· You need not need parenthesis to override the above rules.
33. State the rules to be followed during infix to postfix conversions.
The rules to be followed during infix to postfix conversions are,
· Fully parenthesize the expression starting from left to right (During parenthesizing, the operators having higher precedence are first parenthesized).
· Move the operators one by one to their right, such that each operator replaces their corresponding right parenthesized).
· The part of the expression, which has been converted into postfix, is to be treated as single operand.
· Once the expression is converted into postfix form, remove all parentheses.
34. State the difference between stacks and linked lists.
The difference between stacks and linked lists is that insertions and deletions may occur anywhere in a linked list, but only at the top of the stack.
35. Mention the advantages of representing stacks using linked lists than arrays.
The advantages of representing stacks using linked lists than arrays.
· It is not necessary to specify the number of elements to be sorted in a stack during its declaration (since memory is allocated dynamically at run time when an element is added to the stack).
· Insertions and deletions can be handled easily and efficiently.
· Linked list representation of stacks can grow and shrink in size without wasting memory space, depending upon the insertion and deletion that occurs in the list.
· Multiple stacks can be represented efficiently using a chain for each stack.
36. Define a queue.
Queue is an ordered collection of elements in which insertions and deletions are restricted to one end. The end from which elements are added and/or removed is referred to as the rear end, and the end from which deletions are made is referred to as the front end.
37. Define a priority queue.
Priority queue is a collection of elements, each containing a key referred as the priority for that element. Elements can be inserted in any order (ie. of alternating priority), but are arranged in order of their priority value in the queue. The elements are deleted from the queue in the order of their priority (i.e., the elements with the highest priority is deleted first). The elements with the same priority are given equal importance and processed accordingly.
38. State the difference between queues and linked lists.
The difference between queues and linked lists is that insertions and deletions may occur anywhere in linked list, but in queues insertions can be made only in the front end.
39. Define a dequeue.
Dequeue(Double-ended queue) is another form of a queue in which insertions and deletions are made at both the front and rear ends of the queue. There are two variations of a dequeue, namely, input restricted dequeue and output restricted dequeue. The input restricted dequeue allows insertion at one end (it can be either front or rear) only. The output restricted dequeue allows deletion at one end (it can be either front or rear) only.
40. What are the applications of Queue?
· Job Scheduling
41. Define Input Restricted Queue.
A queue which satisfies the following properties
· Insertion takes place at one end
· Deletion is allowed at both ends
42. Define Output Restricted Queue.
A queue where deletion is allowed at one end and insertion takes place at both ends.
43. What are the steps to be involved while deleting a node in a singly linked list.
· Find the position P before which the node has to be deleted i.e., find previous(X,L).
· Change the link of the previous node to the link of the node to be deleted.
44. What are the applications of priority queue?
· Operating system
· External sorting
· Greedy algorithms
· Event simulation
II UNIT-TREE STRUCTURES
1. Define a tree.
A tree is a non-linear, two-dimensional data structure, which represents hierarchical relationship between individual data items.
2. Define the height of a Tree.
The height of a tree is the length of the longest path from the root to a leaf.
3. Define a path in a tree.
A path in a tree is a sequence of distinct nodes in which successive nodes are connected by edges in the tree.
4. Define terminal nodes in a tree.
A node that has no children is called as a terminal node. It is also referred as a leaf node. These nodes have degree has zero.
5. Define non-terminal nodes in a tree.
All intermediate nodes that traverse the given tree from its root node to the terminal nodes are referred as a non-terminal node.
6. Define a binary tree.
A binary tree is a tree in which all the leaves are on the same level and every non-leaf node has exactly two children.
7. Define a full binary tree.
A full binary tree is a tree in which all leaves are on the same level and every non-leaf node has exactly two children.
8. Define a complete binary tree.
A complete binary tree is a tree in which every non-leaf node has exactly two children not necessarily to be on the same level.
9. Define a right-skewed binary tree.
A right-skewed binary tree is a tree, which has only right child nodes.
10. State the properties of a binary tree.
The properties of a binary tree includes,
· The maximum number of nodes on level n of a binary tree is 2n-1, where n≥1.
· The maximum number of nodes in a binary tree of height n is 2n-1,where n≥1.
· For any non-empty tree, nl=nd+1 where nl is the number of leaf nodes and nd is the number of nodes of degree 2.
11. What are the different ways of representing a binary tree?
The different ways of representing a binary tree includes,
· Linear representation using arrays.
· Linked representation using pointers.
12. What is meant by binary tree traversal?
Traversing a binary tree, means moving through all the nodes in the binary tree, visiting each node in the tree only once.
13. What are the different binary tree traversal techniques?
The different binary tree traversal techniques are,
· Preorder traversal
· Inorder traversal
· Postorder traversal
· Levelorder traversal
14. What are the tasks performed while traversing a binary tree?
The tasks performed while traversing a binary tree are,
· Visiting a node.
· Traverse the left subtree
· Traverse the right subtree.
15. What are the tasks performed during preorder traversal?
The tasks performed during preorder traversal,
· Process the root node
· Traverse the left subtree
· Traverse the right subtree.
16. What are the tasks performed during inorder traversal.
The tasks performed during inorder traversal,
· Traverse the left subtree.
· Process the root node.
· Traverse the right subtree.
17. What are the tasks performed during postorder traversal?
The tasks performed during postorder traversal,
· Traverse the left subtree
· Traverse the root node.
· Traverse the right subtree.
18. What are the tasks performed during levelorder traversal?
The tasks performed during level order traversal,
· Process the root node at level1
· Traverse the next level(i.e., level 2), below the root node.
· Process the nodes from left to right in that level.
· Similarly traverse the next level and process the nodes from left to right and continue till the end of levels.
19. State the merits and demerits of linear representation of binary trees.
The merits of linear representation of binary trees includes
· Storage method is easy and can be easily implemented in arrays.
· When the location of a parent/child node is known other one can be determined easily.
· It requires static memory allocation so it is easily implemented in all programming language.
The demerits of linear representation of binay trees includes,
· Insertions and deletions in a node, taker an excessive amount of processing time, due to data movement up and down the array.
20. State the merits and demerits of linked representation of a binary tree.
The merits of linked representation of binary trees includes
· Insertions and deletions in a node, involves no data movement except the rearrangement of pointers, hence less processing time.
The demerits of linked representation of binary trees includes,
· Given a node structure, it is difficult to determine its parent node.
· Memory spaces are wasted for storing null pointers for the nodes, which have one or no subtrees.
· It requires dynamic memory allocation, which is not possible in some programming languages.
21. What do you mean by general trees.
General trees are a tree with nodes having any number of children.
22. How do you convert general trees to binary trees?
General trees can be converted to binary trees using leftmost child and right siblings representation.
23. Define a binary search tree.
A binary search tree is a special binary tree, which is either empty or if it is empty it should satisfy the following characteristics.
· Every node has a value and no two nodes should have the same value(i.e., the values in the binary search tree are distinct.
· The values in any left subtree is less than the value of its parent node.
· The values in any right subtree is greater than the value of its parent node.
· The left and right subtrees of each node are again binary search trees.
24. What are the basic operations performed in a binary search tree.
The basic operations performed in a binary search tree are,
· Creation of a binary search tree
· Insertion of a node
· Deletion of a node.
· Searching a node
· Modification of a node.
· View the contents of the binary search tree.
25. What are the basic operations performed while creation of a binary search tree.
The basic operations performed while creating a binary search tree are,
· Creating a node.
· Read details for the node from the user
· Insert the node in the binary search tree.
26. What are the various positions from which nodes can deleted?
The various positions from which nodes can be deleted are,
· Deleting the leaf node.
· Deleting the node with only one child.
· Deleting the node with two children.
27. Define threaded binary tree.
In linked representation of binary trees, we can see that all leaf nodes and some non-leaf nodes have NULL values. Instead of storing NULL values in the left and right pointer fields, we can store some useful information such as inorder predecessor in the left pointer field and inorder successor in the right pointer field. These links are considered as threads. A binary tree, which implements these threads are referred to as threaded binary tree.
28. What are the different types of threaded binary tree?
The different types of threaded binary trees are,
· Left-inorder threaded binary tree.
· Right-inorder threaded binary tree.
· Fully-inorder threaded binary tree.
29. Define Left-inorder threaded binary trees.
If you use only the left pointer fields (for storing inorder predecessor) as threads, then the binary tree is referred to as left in-threaded binary tree.
30. Define Right-inorder threaded binary trees.
If you use only the right pointer fields (for storing inorder successor) as threads, then the binary tree is referred to as right in-threaded binary tree.
31. Define Fully-inorder threaded binary trees.
If you use only the right pointer fields as threads, then the binary tree is referred to as fully in-threaded binary tree.
32. Define balance factor of a node in an AVL tree.
Balance factor of a node in an AVL tree is defined as the difference between the height of the left subtree and the height of the right subtree of that node.
33. Define an AVL tree.
If the balance factors of all node in a tree are 1, 0 and -1, then the tree is referred to as AVL tree, is also referred to as balanced tree. The word AVL is an acronym for the Russian mathematicians, Adel’son-Vel’skii and Landis, who first defined balanced trees.
34. What are the various ways of balancing an unbalanced tree?
The various ways of balancing an unbalanced tree are,
· Left to Left rotation
· Left to Right rotation
· Right to Right rotation
· Right to Left rotation
35. When do you apply left-to-left rotations in an unbalanced tree?
We apply left-to-left rotations in an unbalanced tree, if the new node is inserted at left subtree of left child to the pivot node.
36. When do you apply left-to-right rotations in an unbalanced tree?
We apply left-to-right rotations in an unbalanced tree, if the new node is inserted at right subtree of left child to the pivot node.
37. When do you apply right-to-left rotations in an unbalanced tree?
We apply right-to-left rotations in an unbalanced tree, if the new node is inserted at left subtree of right child to the pivot node.
38. When do you apply right-to-right rotations in an unbalanced tree?
We apply right-to-right rotations in an unbalanced tree, if the new node is inserted at right subtree of left child to the pivot node.
39. Define a binary heap.
A binary heap is an array that is viewed as a complete binary tree. A complete binary tree is completely filled on all levels except possibly the lowest, and the lowest level is filled from the left. The root of the tree is stored in an array element 0. The parent of the node n is stored at node (n/2). The right child is stored at node 2n, and the left child at node is stored at 2n+1.
40. Define a min-heap.
The heap which satisfies the min-heap property, i.e., if for every node n except the root, has a value greater than its parent is referred to as min heap.
41. Define max-heap.
The heap which satisfies the max-heap property, i.e., if for every node n except the root, has a value lesser than its parent is referred to as max heap.
UNIT III-HASHING AND SETS
1. What is Hashing?
The implementation of hash table where the data structure is an array of some fixed size containing the keys.
2. Give a simple hash function when the input keys are integers.
Hash function=Key mod Tablesize
3. Compare the various hashing techniques.
Technique Load Factor
Separate chaining - close to 1
Open Addressing - should not exceed 0.5
Rehashing - reasonable load factor
UNIT IV- GRAPHS
1. Define a graph.
A graph is a non-linear data structure that represents less relationship between its adjacent elements. There is no hierarchical relationship between the adjacent elements in case of graphs.
2. List the two types of graphs.
· Directed graph
· Undirected graph
3. Define undirected graph.
If an edge between any two nodes in a graph is not directionally oriented a graph is called as undirected graph. It is also referred as unqualified graph.
4. Define directed graph.
If an edge between any two nodes in a graph is directionally oriented, a graph is called as directed graph; it is also referred as a digraph.
5. Define a path in a graph.
A path in a graph is defined as a sequence of distinct vertices each adjacent to the next, except possibly the first vertex and last vertex is different.
6. Define a cycle in a graph.
A cycle is a path containing at least three vertices such that the starting and the ending vertices are the same.
7. Define a strongly connected graph.
A directed graph is said to be strongly connected if, for every pair of distinct vertices there is a directed path from every vertex to every other vertex. It is also referred as a complete graph.
8. Define a weakly connected graph.
A directed graph is said to be weakly connected graph, if any vertex doesn’t have a directed path to any other vertices.
9. Define a weighted graph.
A graph is said to be weighted graph if every edge in the graph is assigned some weight or value. The weight of an edge is a positive value that may be representing the distance between the vertices or the weights of the edges along the path.
10. Define incidence matrix.
Incidence matrix is a representation used to represent a graph with zeros and ones. A graph containing n vertices can be represented by a matrix with m rows and n columns. The matrix is formed by storing 1 in its ith row and jth column corresponding to the matrix, if there exists a ith vertex, connected to one end of the jth edge and a 0, if there is no ith vertex, connected to any end of the jth edge of the graph.
11. Define adjacency matrix.
Adjacency matrix is a representation used to represent a graph with zeros and ones. A graph containing n vertices can be represented by a matrix with n rows n columns. The matrix is formed by storing 1 in its ith row and jth coilumn of the matrix, if there exists an edge between ith and jth vertex of the graph, and a 0, if there is no edge between ith and jth vertex of the graph.
12. Define adjacency list.
A graph containing m vertices and n edges can be represented using a linked list, referred to as adjacency list.
13. Define path matrix.
A graph containing n vertices can be represented by a matrix with n rows and n columns. The matrix is formed by storing 1 in its ith row and jth column of the matrix, if there exists an edge between ith and jth vertex of the graph, and a 0, if there is no edge between ith and jth vertex of the graph, such a matrix is referred to as path matrix.
14. What is meant by traversing a graph? State the different ways of traversing a graph.
Traversing a graph means visiting all the nodes in the graph. In many practical applications traversing a graph is important, such that each vertex is visited once systematically by traversing through minimum number of paths. The two important graph traversal methods are,
· Depth-first traversal(or) Depth-first search(DFS)
· Breath-first traversal(or)Breath-first search(BFS)
15. What is meant by topological sorting?
Topological sorting is an ordering of the vertices in a directed acyclic graph, such that if there is a path from x to y, then y appears after x in the ordering. As each vertices is visited, push the vertex in to the stack. Finally print the stack elements in order.
16. What is the use of Dijkstra’s algorithm?
Dijkstra’s algorithm is a greedy algorithm to find the minimum distance from a node to all other nodes. Our aim is to visit any two nodes, with a minimum weight, such that the distance travelled is minimum. One such algorithm is referred as Dijkstra’s shortest path algorithm. This is very much used in travelling salesman problem.
17. Define spanning trees?
A spanning tree of a graph is just a sub graph that contains all the vertices of the graph, but uses sufficient edges to form a tree. A graph may have spanning trees.
18. Define minimum spanning trees?
A minimum spanning tree is one of the spanning trees of the graph which has the smallest sum of weights amongst all spanning trees.
19. How can you minimum spanning trees from graphs?
You can create minimum spanning trees from graphs using two different greedy algorithms. They are,
· Prim’s algorithm
· Kruskal’s algorithm
20. How can you create minimum spanning tree using prim’s algorithm?
In Prim’s algorithm, for creating minimum spanning tree, start with any node and include the other node in the spanning tree, on the basis of its weight of their edges connected to that node, and move on until it includes all the n vertices are connected by n-1 edges. The resulting tree contains all the vertices present in the given graph, such that the weight of the edges in the resulting tree is minimum. The tree produced by the above algorithm, is the minimum spanning tree.
21. How can you create minimum spanning tree using Kruskal’s algorithm?
In Kruskal’s algorithm, for creating minimum spanning tree, sort the edges in the graph on increasing order by its weight. Take the first edge from the ordered list and add the source vertex to form a tree. Check whether the destination vertex to the tree. If it already exists, move to the next edge in the ordered list. Repeat the steps until the tree contains all the n vertices. The tree produced by the above algorithm, is the minimum spanning tree.
22. Define NP-completeness?
NP-completeness is a type of many important problems that can’t be solved quickly. Knowing these problems is hard, and trying to solve them, and do something better. NP stands for “nondeterministic polynomial time” where nondeterministic is just a fancy way of talking about guessing a solution. A problem is in NP if you can quickly(in polynomial time)test whether a solution is correct(without about how it might be to find the solution0. Problems in NP are still relatively easy. If only we could guess the right solution, we could then quickly test it.
23. What is a Sink node?
The node has no directed edge that comes out of the node, then it is said to be sink node.
24. Explain the following terms i)Degree ii)indegree iii)outdegree
i) Degree-it denotes the number of edges for a node
ii) In degree-Number of edges entering from the vertex
iii)he number of edges exiting from the vertex.
25. What is the Source node?
The node which is used to shares the information is called as source node.
26. What is Acyclic graph?
If there is no path from any node back to itself then the graph is said to be acyclic graph.
27. List the 2 important representations of graph.
· Matrix representation
· List structure
28. Give any three examples for shortest path problem.
· In computer networking such as LAN, WAN, Inter Networking.
· In telephone cabeling graph theory is effectively used.
· Job Scheduling algorithms.
29. List the applications of MST.
· Connecting of computers in the lab with the minimum length of wire.
· Telephone networking companies.
· It provides way for clustering points in space in to natural graphs.
30. Define the term Prim’s Algorithm.
In a graph a pair with the minimum weight is to be chosen. Then adjacent to these vertices is the edge having minimum weight is selected ie., in each stage, one node is picked as the root, then add an edge and thus an associated vertex to the tree.
31. Define DFS.
DFS means Depth First search it is like a preorder traversal of a tree. It is continuous searching for the unvisited nodes in the forward direction based on the recursive process.
32. What is called Biconnectivity?
A connected undirected graph is biconnected if there are no vertices whose removal disconnects the rest of the graph.
33. What do you mean by Complete Graph?
In a graph if there exists the path from any vertex to any other vertex, then the graph is called as Complete Graph.
1. Define greedy algorithm.
Greedy algorithm is a method that always takes the best immediate or local, solution while finding an answer. The greedy algorithm repeatedly executes a procedure, until it can’t be done any more with the hope that the outcome will lead to desired outcome for the global problem.
2. Mention some of the problems that implements greedy algorithm.
The problems that implements greedy algorithm are, coin change, Egyptian fractions, Map coloring and Knapsack problem.
3. Define dynamic programming algorithm.
Dynamic programming is a general class of algorithms, which solve problems by solving smaller versions of the problem, saving the solutions to the small problems and then combining them to solve the larger problem.
4. Define backtracking algorithm.
Backtracking is an algorithm for solving a series of sub-problems each of which may have multiple possible solutions and where the solution chosen for one sub-problem may effect the possible solutions of later sub-problems. The problems that implements backtracking algorithm are, Towers of Hanoi and 8 Queens problem.
5. What are the factors affecting the efficiency of an algorithm?
· Redundant computation
· Referencing array elements
· Late termination
6. List any two example for NP-Complete problems
· Hamiltonian Cycle.
· Traveling Salesman Problem
· Knapsack problem
· Bin Packing
IF YOU HAVE PROBLEM TO VIEW THE ABOVE CONTENT CLICK HERE TO SEE