Definitions Flashcards
Define Data
It represents a value or a set of values that does not carry any meaning.
What is information?
The processed data that carry information is called as information.
Define: Data Structures
It is a way of organizing data, such that accessing of data becomes easier. It also plays a vital role in creating efficient programs.
What are the applications of Data Structures?
- Compiler design
- Operating System
- Statistical Analysis package
- DBMS
- Numerical analysis
- Simulation
- Artificial Intelligence
- Graphics
What is an efficient program? And when is the program considered as a good program?
A program is said to be efficient when it executes in minimum time and with minimum memory space. A good program is defined to be a program that runs correctly, is easy to read and understand, is easy to debug and is easy to modify.
What are some examples of Data Structures?
Stacks, Queue, Array, Linked list, Binary trees and Hash tables.
Define ADT
ADT or Abstract Data Type is a set of operations that tells us what to do rather than how to do. Hence, it is easy to maintain, extend and update at later years.
What are the operations of DS?
Inserting, Deleting, Searching, Traversing and Merging.
What are the two classifications of DS?
Primitive (int, char, float, double, etc.,) and Non-Primitive (Linear: Array, linked list, stack, queue| Non-Linear: Trees, Graphs and Tables)
What is an array?
An array is a collection of data items of similar data type.
What is a Linked List?
It is a linear data structure that consists of several nodes, each with two parts. First part is the data field and the next part is the address of the next node.
What is a circularly linked list?
It is a collection of nodes, each having two fields. The data field and the address field. In a circularly linked list, the address field of the last node points to the address of the first node.
What is a stack?
A stack is a linear data structure in which elements are inserted and deleted at only one end called top of the stack. Elements are inserted and deleted or removed by the LIFO principle (Last In, First Out).
What are the two fundamental operations of a stack?
Push: Add elements to the stack and Pop: Remove elements from the stack. Some additional operations are Peek (Top): Retrieve the top element without removing it, isEmpty(): Checks whether the stack is empty and isFull(): Checks whether the stack is full.
Define underflow.
The underflow condition in a stack occurs when a pop or peek operation is attempted on an empty stack.
Define overflow.
The overflow condition in a stack occurs when a push operation is attempted on a full stack, that is, a stack that has reached it’s maximum capacity.
Define Queue.
Queue is a linear data structure in which elements are inserted in one end called ‘rear’ and deleted in the other end called ‘front’. Other name is FIFO (First In, First Out)
What are the two operations in Queue?
Enqueue: process of inserting an element into the queue and Dequeue: process of deleting an element from the queue.
Define trees.
It is a non-linear data structure which is a collection of nodes with one distinct node called root node, while the remaining nodes are partitioned as t1, t2,…, tk where k>=0 each of which are sub trees and the edges of t2 to tk are connected to the root.
What is a binary tree?
In a binary tree, each node can have at most two children. A binary tree is either empty or consists of a root node with a left and right subtree.
Define full binary tree.
A binary tree in which it has two children or no child.
Define complete binary tree.
It is a binary tree with every level except possibly the last is completely filled and all nodes in the last level are as far left as possible.
What is called as a perfect binary tree?
It is a binary tree where all the leaf nodes are at the same level.
What is an expression tree?
It is a binary tree used to represent algebraic and Boolean expression. It is a tree with leaves as operands and nodes as operators.
Define Binary Search Tree or BST.
BST is a binary tree in which every parent node key value is greater than it’s left subtree and lesser than the right subtree.
What are the operations that can be performed in a BST?
Insertion, deletion and Searching.
Define Heap tree.
It is a binary tree that satisfies the following two properties:
- Structure property: It is a complete binary tree, that is, all the nodes are filled with children, except the bottom level, where it is filled from left to right.
- Heap order property: For any node, it’s parent node key value is smaller, except the root node which does not have a parent.
How does the Heap Order property change when it comes to Max Heap?
In max heap, the heap order property is that, for any node, it’s parent node value is greater.
What is an AVL tree?
AVL tree or Adelson-Velsky Landis tree is a binary search tree with a balancing factor -1, 0 and 1.
What is the formula for balancing factor?
Balancing factor = height of left subtree - height of right subtree.
When the balancing factor is greater than two, what is done?
If the balancing factor becomes greater than two, then the following four rotations are done.
> Left-Left
> Left-Right
> Right-Right
> Right-Left
What is a B-tree?
B-tree is a self-balancing tree data structure that keeps data sorted and allow searches, sequential access, insertion and deletion.
What is a B+ tree?
A B+ tree is a balanced tree in which every path from the root of the tree to a leaf is of the same length and each non-leaf node has between n/2 and n children, where n is fixed for a particular time.
Define graph.
It is a non-linear data structure with a set of vertices and edges connecting the vertices.
What are the types of graphs?
- Directed graph/ Digraph
- Undirected graph
-Weighted graph - Unweighted graph
- Connected graph
- Cyclic graph
- DAG or Directed Acyclic Graph
How do you represent graphs?
There are two types: Adjacency matrix and Adjacency list.
What is an Adjacency Matrix?
The graph is represented using rows and columns. Each cell is marked with one if edge exist and zero if there is no edge.
What is an Adjacency List?
Graph is represented in a linked list form. Every nodes adjacent nodes are linked with each other.
Define Topological Sorting.
Topological sorting is the ordering of vertices in a directed graph with a property that if there is a path from vi to vj then vi must come before vj in the ordering.
In which case is topological sorting impossible?
Topological sort is impossible in cyclic graphs, but possible for DAG.
What is graph traversal?
The process of visiting each and every vertex at least once is called as graph traversal.
Define Breadth First Search or BFS.
BFS produces a spanning tree as the result. Queue data structure is used to implement BFS.Def
Define Depth First Search or DFS.
It produces spanning tree as the result. It uses stack with maximum size as the total number of vertices in the graph.
Define searching.
Searching is the process done to find whether a particular value is present in an array or not. If the value is present in the array, then searching is said to be successful and gives the location of that value in the array.
What is Linear Search?
Linear Search, also called as Sequential search, is a simple method used for searching an array for a particular value. It works by comparing the search element with every element in the array, one by one until a match is found. It works on unordered list.
What is Binary search?
Binary search is a searching algorithm that works efficiently on a sorted list. It compares the target with the middle element of the array. If they are not equal, then the half in which the search element cannot lie is eliminated and the search continues in the other half.
Define sorting.
Sorting means arranging the elements of an array so that they are placed in some relevant order which maybe ascending or descending.
Explain Internal Sorting.
It deals with sorting the data stored in the computer’s memory. It is applicable when the number of elements in the list is small. Example: Bubble sort, Insertion sort, Shell sort, Quick sort, Selection sort, Radix sort.
What is External sorting?
External sorting deals with sorting data stored in files. It is applied when there is voluminous data that cannot be stored in the memory. Eg: Merge sort
