Definitions

Question 1

Define Data

Answer 1

It represents a value or a set of values that does not carry any meaning.

Question 2

What is information?

Answer 2

The processed data that carry information is called as information.

Question 3

Define: Data Structures

Answer 3

It is a way of organizing data, such that accessing of data becomes easier. It also plays a vital role in creating efficient programs.

Question 4

What are the applications of Data Structures?

Answer 4

• Compiler design
• Operating System
• Statistical Analysis package
• DBMS
• Numerical analysis
• Simulation
• Artificial Intelligence
• Graphics

Question 5

What is an efficient program? And when is the program considered as a good program?

Answer 5

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.

Question 6

What are some examples of Data Structures?

Answer 6

Stacks, Queue, Array, Linked list, Binary trees and Hash tables.

Question 7

Define ADT

Answer 7

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.

Question 8

What are the operations of DS?

Answer 8

Inserting, Deleting, Searching, Traversing and Merging.

Question 9

What are the two classifications of DS?

Answer 9

Primitive (int, char, float, double, etc.,) and Non-Primitive (Linear: Array, linked list, stack, queue| Non-Linear: Trees, Graphs and Tables)

Question 10

What is an array?

Answer 10

An array is a collection of data items of similar data type.

Question 11

What is a Linked List?

Answer 11

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.

Question 12

What is a circularly linked list?

Answer 12

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.

Question 13

What is a stack?

Answer 13

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).

Question 14

What are the two fundamental operations of a stack?

Answer 14

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.

Question 15

Define underflow.

Answer 15

The underflow condition in a stack occurs when a pop or peek operation is attempted on an empty stack.

Question 16

Define overflow.

Answer 16

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.

Question 17

Define Queue.

Answer 17

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)

Question 18

What are the two operations in Queue?

Answer 18

Enqueue: process of inserting an element into the queue and Dequeue: process of deleting an element from the queue.

Question 19

Define trees.

Answer 19

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.

Question 20

What is a binary tree?

Answer 20

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.

Question 21

Define full binary tree.

Answer 21

A binary tree in which it has two children or no child.

Question 22

Define complete binary tree.

Answer 22

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.

Question 23

What is called as a perfect binary tree?

Answer 23

It is a binary tree where all the leaf nodes are at the same level.

Question 24

What is an expression tree?

Answer 24

It is a binary tree used to represent algebraic and Boolean expression. It is a tree with leaves as operands and nodes as operators.

Question 25

Define Binary Search Tree or BST.

Answer 25

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.

Question 26

What are the operations that can be performed in a BST?

Answer 26

Insertion, deletion and Searching.

Question 27

Define Heap tree.

Answer 27

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.

Question 28

How does the Heap Order property change when it comes to Max Heap?

Answer 28

In max heap, the heap order property is that, for any node, it's parent node value is greater.

Question 29

What is an AVL tree?

Answer 29

AVL tree or Adelson-Velsky Landis tree is a binary search tree with a balancing factor -1, 0 and 1.

Question 30

What is the formula for balancing factor?

Answer 30

Balancing factor = height of left subtree - height of right subtree.

Question 31

When the balancing factor is greater than two, what is done?

Answer 31

If the balancing factor becomes greater than two, then the following four rotations are done. > Left-Left > Left-Right > Right-Right > Right-Left

Question 32

What is a B-tree?

Answer 32

B-tree is a self-balancing tree data structure that keeps data sorted and allow searches, sequential access, insertion and deletion.

Question 33

What is a B+ tree?

Answer 33

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.

Question 34

Define graph.

Answer 34

It is a non-linear data structure with a set of vertices and edges connecting the vertices.

Question 35

What are the types of graphs?

Answer 35

- Directed graph/ Digraph - Undirected graph -Weighted graph - Unweighted graph - Connected graph - Cyclic graph - DAG or Directed Acyclic Graph

Question 36

How do you represent graphs?

Answer 36

There are two types: Adjacency matrix and Adjacency list.

Question 37

What is an Adjacency Matrix?

Answer 37

The graph is represented using rows and columns. Each cell is marked with one if edge exist and zero if there is no edge.

Question 38

What is an Adjacency List?

Answer 38

Graph is represented in a linked list form. Every nodes adjacent nodes are linked with each other.

Question 39

Define Topological Sorting.

Answer 39

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.

Question 40

In which case is topological sorting impossible?

Answer 40

Topological sort is impossible in cyclic graphs, but possible for DAG.

Question 41

What is graph traversal?

Answer 41

The process of visiting each and every vertex at least once is called as graph traversal.

Question 42

Define Breadth First Search or BFS.

Answer 42

BFS produces a spanning tree as the result. Queue data structure is used to implement BFS.Def

Question 43

Define Depth First Search or DFS.

Answer 43

It produces spanning tree as the result. It uses stack with maximum size as the total number of vertices in the graph.

Question 44

Define searching.

Answer 44

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.

Question 45

What is Linear Search?

Answer 45

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.

Question 46

What is Binary search?

Answer 46

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.

Question 47

Define sorting.

Answer 47

Sorting means arranging the elements of an array so that they are placed in some relevant order which maybe ascending or descending.

Question 48

Explain Internal Sorting.

Answer 48

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.

Question 49

What is External sorting?

Answer 49

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