Data structure and algorithm with JAVA
- What is data structure
→ A data structure is a specialized format for organizing and storing data. General data structure types include the array, the file, the record, the table, the tree, and so on. Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ways.
- Why is Big Oh notation used
→ Big Oh notation is used to find best case
- Why are link list preferred over arrays
→ Link list are preferred over arrays because we can store in any memory location
- What is linear queue
→ Linear queue is a queue in which we should put data on front and the data which we put first extract at first. I.e. first in first out
- Define activation record
→ An activation record is another name for Stack Frame. It’s the data structure that composes a call stack. It is generally composed of: Locals to the called. Return address to the caller.
- What is binary tree
→ A data structure in which a record is linked to two successor records, usually referred to as the left branch when greater and the right when less than the previous record.
- What is B tree
→ An organizational structure for information storage and retrieval in the form of a tree in which all terminal nodes are the same distance from the base, and all non-terminal nodes have between n and 2 n sub trees or pointers (where n is an integer).
- List out the method that can be used to represent graph in memory
→ The method that can be used to represent graph in memory
- Adjacency matrix
- Linked list
- Adjacency list
- What is sorting
→ The process of arranging data from ascending to descending or vice-versa is known as shorting
- For which purpose Kruskal’s algorithm is used
→ For finding minimal spinning tree we use Kruskal’s algorithm
ASOM2073[SET-B]
- Define queue as ADT
→ An abstract data type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.
- How can you measure time complexity of an algorithm? Explain
→ We can time complexity of an algorithm by using Big Oh notation
- Differentiate between recursive and non-recursive function
→ The function which call it’s self is recursive function where as other iteration are non-recursive function
- What is heap? Explain the types of heap in DSA
→ A heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of node P is greater than the key of node C. A heap can be classified further as either a “max heap” or a “min heap”.
- Define expression tree with example
→ A binary expression tree is a specific kind of a binary tree used to represent expressions. Two common types of expressions that a binary expression tree can represent are algebraic and boolean. These trees can represent expressions that contain both unary and binary operators.
- What is AVL tree
→ AVL tree is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child sub trees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.
- Give the working principles of binary search algorithm
→ A BST is a binary tree of nodes ordered in the following way:
- Each node contains one key (also unique)
- The keys in the left sub tree are < (less) than the key in its parent node
- The keys in the right sub tree > (greater) than the key in its parent node
- Duplicate node keys are not allowed.
- What is minimum spanning tree
→ A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight
- What is divided and conquer paradigm? Give the name of algorithm that follows this paradigm
→ Divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
- List the various types of binary trees
→ The various types of binary trees are
- Strictly binary tree
- Complete binary tree
- Almost complete binary tree
- Define tail and non-tail with example
NCCS2016[SET A]
- List out the different types of hash function
→
- Division
- Folding
- Mid-square
- Extraction
- Radix transformation
- Universal
- Define coalesced chaining
→ Coalesced hashing, also called coalesced chaining, is a strategy of collision resolution in a hash table that forms a hybrid of separate chaining and open addressing.
- What difference do you find between directed graph and undirected graph
→ Directed graph has source vertex and sink vertex whereas undirected graph do not have. Directed graph has direction to specific path whereas undirected graph do not have
- What is cut vertex
→ A cut vertex is a vertex that when removed (with its boundary edges) from a graph creates more components than previously in the graph. A cut edge is an edge that when removed (the vertices stay in place) from a graph creates more components than previously in the graph.
- What do you understand by topological sort
→ A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
- What is searching difficult in a heap compared to binary search tree
→ Min-heap is searching difficult in a heap compared to binary search tree
- Define expression tree
→ A binary expression tree is a specific kind of a binary tree used to represent expressions. Two common types of expressions that a binary expression tree can represent are algebraic and boolean. These trees can represent expressions that contain both unary and binary operators.
- Why are linked lists preferred over arrays
→ Link list are preferred over arrays because we can store in any memory location
NCCS2016[SET B]
- Differentiate between linear search and binary search
→ Linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.
A binary search, also called a dichotomizing search, is a digital scheme for locating a specific object in a large set. Each object in the set is given a key. The number of keys is always a power of 2. If there are 32 items in a list, for example, they might be numbered 0 through 31 (binary 00000 through 11111).
- What is coalesced chaining
→ Coalesced hashing, also called coalesced chaining, is a strategy of collision resolution in a hash table that forms a hybrid of separate chaining and open addressing.
- How does graph differ from a tree
→ Graph has cycle but tree do not have it
- Define articulation point
→ For a disconnected undirected graph, an articulation point is a vertex removing which increases number of connected components.
- What is a minimum spanning tree
→A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight
- Why searching is the key process in a binary search tree
→ Searching is the key process in a binary search tree because data are in hybrid structure
- Why is balancing done in a tree
→ Balancing done in a tree because in order to make data structure in system
- What do you understand by time and space complexity
→ We can time complexity of an algorithm by using Big Oh notation
Orchid2073[SET A]
- What do you mean by computational complexities
→ Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.
- How does double linked list differs from singly linked list
→ a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes
Singly Linked Lists are a type of data structure. It is a type of list. In a singly linked list each node in the list stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node.
Singly Linked Lists are a type of data structure. It is a type of list. In a singly linked list each node in thelist stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node.
- What is indirect recursion
→ Indirect recursion occurs when a method invokes another method, eventually resulting in the original method being invoked again.
- Define a binary search tree
→ A binary search tree (BST), also known as an ordered binary tree, is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree.
- What is a minimum spanning tree
→A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight
- What do you mean by tree traversal
→ tree traversal (also known as treesearch) is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited
- Define Splay tree
→ A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time.
- What is topological sort
→ A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
Orchid 2073[SET B]
- What is theta notation
→ First let’s understand what big O, big Theta and big Omega are. They are all sets of functions. Big O is giving upper asymptotic bound, while big Omega is giving a lower bound. Big Theta gives both.
- How does linear queue differs from priority queue
→ Linear queue is based on FIFO but priority queue is based on priority
- What is nontail recursion
→ A tail call [tail recursion] is a kind of goto dressed as a call. A tail call happens when a function calls another as its last action, so it has nothing else to do. For instance, in the following code, the call to g is a tail call: function f (x) return g(x) end.
- Define an AVL tree
→ AVL tree is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.
- Define hashing
→ a hash table (hash map) is a data structure which implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
- Define DSW algorithm
→ The Day–Stout–Warren (DSW) algorithm is a method for efficiently balancing binary search trees — that is, decreasing their height to O(log n) nodes, where n is the total number of nodes. … First, the tree is turned into a linked list by means of an in-order traversal, reusing the pointers in the (threaded) tree’s nodes.
- What is a decision tree
→ A decision tree is a decision support tool that uses atree-like graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm.
- What is a network in graph
→ A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines. …Graphs are one of the prime objects of study in discrete mathematics. Refer to the glossary of graph theory for basic definitions in graph theory.
TIC2016
- What is BST
→ A binary search tree (BST), also known as an ordered binary tree, is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree.
- What is self-adjusting tree
→ A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time.
- What is the underflow condition of stack
→ When this happens it often causes the program to crash. … If the stack is empty and yet a POP operation is attempted, this is called an ‘stack underflow’ and can cause a program to crash.
- How double linked list differs from singly linked list
→ a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes
Singly Linked Lists are a type of data structure. It is a type of list. In a singly linked list each node in the list stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node.
- What is the degree of a node
→ The number of children is the degree of a node
- What is splaying
→ A splay tree is a self-adjusting binary search treewith the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time.
- What is strictly binary tree
→ If every non-leaf node in a binary tree has nonempty left and right sub trees, the tree is termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary tree are of degree zero or two, never degree one. A strictly binary tree with N leaves always contains 2N – 1 nodes.
- Arrange the following complexity function from slower to faster: n5, n , n , nn
→ nn,n2.5, n , n
ASOM2073[SET-A]
- Define ADT with example
→ An abstract data type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.
- What is Big-O notation
→ Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm
- Differentiate between linear queue and circular queue
→ In linear queue the start node and end node are empty but there is no provision of it in circular queue
- How double linked list differs from singly linked list
→ a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes
Singly Linked Lists are a type of data structure. It is a type of list. In a singly linked list each node in the list stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node.
- What is skip list
→ a skip list is a data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one
- Define an AVL tree with suitable example
→ AVL tree is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child sub trees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.
- Define adjacency matrix with example
→ an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertice0s are adjacent or not in the graph. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal
- What is splaying
→ A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time.
Data Structure and Algorithm with Java
Brief Answer Question
- Define ADT with example.
A useful tools for specifying the logical properties of a data type is called abstract data type. An ADT have both set of values of a given type and the set of operations that can be performed on those values.
Example: Array, List, Queue, etc.
- Define max-heap with suitable example.
A max-heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node.
- Differentiate between linear and circular queue.
| LINEAR QUEUE | CIRCULAR QUEUE |
| Organizes the data elements and instructions in a sequential order one after the other. | Arranges the data in the circular pattern where the last element is connected to the first element. |
| The new element is added from the rear end and removed from the front. | Insertion and deletion can be done at any position. |
- How doubly linked list differs from singly linked list ?
In a single linked list, node only points towards next node, and there is no pointer to previous node, which means you can not traverse back on a singly linked list. On the other hand doubly linked list maintains two pointers, towards next and previous node, which allows you to navigate in both direction in any linked list.
- What is skip list ?
A skip list is a data structure that is used for storing a sorted list of items with a help of hierarchy of linked lists that connect increasingly sparse subsequences of the items.
- Define decision tree with suitable example.
Binary tree can be used to locate item based on comparision, in this situatuation each comparision tells us to visit either left-subtree and right-subtree. A rooted tree where internal vertices corresponding a decision and sub-tree at these vertices of possible outcomes of the decision made is called decision tree.
- Define binary search tree with example.
A binary search tree (BST), also known as an ordered binary tree, is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree. The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node.
- What is complete binary tree ?
A complete binary tree with n nodes and of depth d is a strectly binary tree, an of whose terminal nodes are at level d.
- What is splaying ?
A splaying is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again.
- Define tail recursion with example.
The tail recursive functions considered better as the recursive call is at the last statement so there is nothing left to do in the current function. It saves the current function’s stack frame is of no use.
Example: Recursive Function TOH with Tail Recursion
void TOH(int n,char x,char y,char z)
{
if(n>0)
{
TOH(n-1,x,z,y);
printf("\n%c-> %c",x,y);
TOH(n-1,z,y,x); //tail recursion
}
}