Data structure interview question set 2/Data structure Interview Questions and Answers for Freshers & Experienced

Advantage: The problem of primary clustering is eliminated.
Disadvantage: There is no guarantee of finding an unoccupied cell once the table is nearly half full.

List The Applications Of Set Adt?

<> Maintaining a set of connected components of a graph.
<> Maintain list of duplicate copies of web pages.
<> Constructing a minimum spanning tree for a graph.

What Do You Mean By Disjoint Set Adt?

A collection of non-empty disjoint sets S=S1,S2,….,Sk i.e;each Si is a non-empty set that has no element in common with any other Sj. In mathematical notation this is: Si∩Sj=Ф. Each set is identified by a unique element called its representative.

Define Indegree Of A Graph?

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

What Is An Acyclic Graph?

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

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.

When Is 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.

Define Graph Traversals?

Traversing a graph is an efficient way to visit each vertex and edge exactly once.

Advantages Of A Macro Over A Function?

Actually macro and function are used for different purposes. A macro replaces its expression code physically in the code at the time of preprocessing. But in case of function the control goes to the function while executing the code. So when the code is small then it is better to use macro. But when code is large then function should be used.

List The Two Important Key Points Of Depth First Search?

i) If path exists from one node to another node, walk across the edge – exploring the edge.
ii) If path does not exist from one specific node to any other node, return to the previous node where we have been before – backtracking.

Define Biconnectivity?

A connected graph G is said to be biconnected, if it remains connected after removal of any one vertex and the edges that are incident upon that vertex. A connected graph is biconnected, if it has no articulation points.

What Do You Mean By Shortest Path?

A path having minimum weight between two vertices is known as shortest path, in which weight is always a positive number.

State The Advantages Of Using Infix Notations?

<> It is the mathematical way of representing the expression.
<> It is easier to see visually which operation is done from first to last.

List Out The Basic Operations That Can Be Performed On A Stack ?

The basic operations that can be performed on a stack are

Push operation.
Pop operation.
Peek operation.
Empty check.
Fully occupied check.

1. It is not necessary to specify the number of elements in a linked list during its declaration.
2. Linked list can grow and shrink in size depending upon the insertion and deletion that occurs in the list.
3. Insertions and deletions at any place in a list can be handled easily and efficiently.
4. A linked list does not waste any memory space.

List Some Of The Static Data Structures In C?

Some of the static data structures in C are arrays, pointers, structures etc.

When Can You Tell That A Memory Leak Will Occur?

A memory leak occurs when a program loses the ability to free a block of dynamically allocated memory.

If You Are Using C Language To Implement The Heterogeneous Linked List, What Pointer Type Will You Use?

The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.

What Is Precision?

Precision refers the accuracy of the decimal portion of a value. Precision is the number of digits allowed after the decimal point.

Which Process Places Data At The Back Of The Queue?

Enqueue is the process that places data at the back of the queue.

Why Is The Isempty() Member Method Called?

The isEmpty() member method is called within the dequeue process to determine if there is an item in the queue to be removed i.e. isEmpty() is called to decide whether the queue has at least one element. This method is called by the dequeue() method before returning the front element.

What Member Function Places A New Node At The End Of The Linked List?

The appendNode() member function places a new node at the end of the linked list. The appendNode() requires an integer representing the current data of the node.

What Are The Major Data Structures Used In The Following Areas : Rdbms, Network Data Model & Hierarchical Data Model?

. RDBMS Array (i.e. Array of structures)
. Network data model Graph
. Hierarchical data model Trees.

Difference Between Calloc And Malloc ?

malloc: allocate n bytes.
calloc: allocate m times n bytes initialized to 0.

Does The Minimal Spanning Tree Of A Graph Give The Shortest Distance Between Any 2 Specified Nodes?

No! Minimal spanning tree assures that the total weight of the tree is kept at its minimum. But it doesn’t mean that the distance between any two nodes involved in the minimal-spanning tree is minimum.

What Is A Spanning Tree?

A spanning tree is a tree associated with a network. All the nodes of the graph appear on the tree once. A minimum spanning tree is a spanning tree organized so that the total edge weight between nodes is minimized.

In Rdbms, What Is The Efficient Data Structure Used In The Internal Storage Representation?

B+ tree. Because in B+ tree, all the data is stored only in leaf nodes, that makes searching easier. This corresponds to the records that shall be stored in leaf nodes.

There Are 8, 15, 13, 14 Nodes Were There In 4 Different Trees. Which Of Them Could Have Formed A Full Binary Tree?

In general: There are 2n-1 nodes in a full binary tree. By the method of elimination:

Full binary trees contain odd number of nodes. So there cannot be full binary trees with 8 or 14 nodes, so rejected. With 13 nodes you can form a complete binary tree but not a full binary tree. So the correct answer is 15.

If You Are Using C Language To Implement The Heterogeneous Linked List, What Pointer Type Will You Use?

The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.

What Are The Major Data Structures Used In The Following Areas : Network Data Model & Hierarchical Data Model?

RDBMS – Array (i.e. Array of structures)
Network data model – Graph
Hierarchical data model – Trees

Parenthesis Is Never Required In Postfix Or Prefix Expressions, Why?

Parenthesis is not required because the order of the operators in the postfix /prefix expressions determines the actual order of operations in evaluating the expression.

What Are The Disadvantages Of Circular List?

i) We can’t traverse the list backward.
ii) If a pointer to a node is given we cannot delete the node.

How do you detect a loop in a linked list?

Using Floyd's cycle-finding Algorithm
Using hashing
Using the visited nodes method

List a few queue data structure applications.

As the name suggests, the queue is used whenever you need to manage a group of objects in the order FIFO. A few of the queue data structure applications are listed below:

1. Serving requests on a single shared resource, like CPU task scheduling, printer, etc.
2. Handling interruptions in real-time systems.
3. Buffers in apps like CD player and MP3 media players
4. In maintaining a playlist in media players, like adding or removing songs.

Are linked lists considered non-linear or linear data structures?

It depends on where you plan to use Linked lists. You can consider a linked list for both non-linear and linear data structures. When used for data storage, it is regarded as a non-linear data structure. When used for access strategies, it is considered a linear data structure.

A linked list is a series of data structures connected via links. In simple words, it's a sequence of links that contain items. After the array, the linked list is the second most used data structure. The essential terms to understand the linked list are:

Basic operations supported by a linked list:

Insertion - Inserts an element at the list beginning.
Deletion - Deletes an element at the list beginning.
Display - Displays the complete list.
Search - Searches an element using the given key.
Delete - Deletes an element using the given key.

What operations can be performed on a stack?

Mainly the following operations are performed on a stack:

1. Push operation: To add an item to the stack. If the stack is complete, then it is in an overflow condition.
2. Pop operation: It is used to remove an item from the stack. If it's an empty stack, then it is in underflow condition.
3. isEmpty operation: If the stack is empty returns true, else false.
4. Peek or Top operation: This returns the top element of the stack.

What is the difference between storage structure and file structure?

The main difference between storage structure and file structure depends on the memory area that is accessed.

Storage structure: It's a data structure representation in computer memory.
File structure: It's a storage structure representation in the auxiliary memory.

Which Data Structure is used to implement LRU cache?

To implement the LRU cache, you should use two data structures: a hashmap and a doubly linked list.

A hashmap helps with the lookup of cached keys, and a doubly-linked list helps maintain the eviction order.

How would you implement a queue using a stack?

Using two stacks, you can implement a queue. The purpose is to complete the queue's en queue operation so that the initially entered element always ends up at the top of the stack.

1. First, to enqueue an item into the queue, migrate all the elements from the beginning stack to the second stack, push the item into the stack, and send all elements back to the first stack.

2. To dequeue an item from the queue, return the top item from the first stack.

Is it possible to implement a stack using a queue?

Yes, you can implement a stack using two queues. Any data structure to act like a stack should have a push() method to add data on top and a pop() method to remove the top data.

Can you tell me the minimum number of queues that are needed to implement a priority queue?

The minimum number of queues that are needed is two. Out of which, one queue is intended for sorting priorities and the other queue is meant for the actual storage of data.

Can you tell me the minimum number of nodes that a binary tree can have?

A binary tree is allowed or can have a minimum of zero nodes. Further, a binary tree can also have 1 or 2 nodes.

Explain how new data can be inserted into the tree?

The following are the steps that you need to follow to insert the data into the tree:

1. First of all, check whether the data is unique or not ( i.e. check whether the data that you are going to insert doesn’t already exist in the tree).

2. Then check if the tree is empty. If the tree is empty then all you need to do is just insert a new item into the root. If the key is smaller than that of a root’s key then insert that data into the root’s left subtree or otherwise, insert the data into the right side of the root’s subtree.

Give names of All the Trees

There are six types of tree given as follows.

1) General Tree
2) Forests
3) Binary Search Tree
4) Tournament Tree
5) Binary Tree
6) Expression Tree

What do you Understand by a Spanning tree? What is the Maximum Number of Spanning Trees a Graph can Have?

A spanning tree is a subset of a graph that has all the vertices but with the minimum number of edges necessary.

The maximum number of spanning tree a graph have depend on the way the graph is linked. A complete undirected graph containing n number of nodes may have a maximum of nn-1 number of spanning trees.

Can you Explain a few Approaches to Write an Algorithm?

There are 3 widely used approaches to develop the algorithms-

Greedy approach − Seeking a solution by picking the next best possible alternative.

Divide and conquer − Bringing the problem to a minimal feasible sub-problem and separately solving it.

Dynamic programming − Bringing the problem to a minimal possible sub-problems and solve them together.

Explain the Concept of a Queue. How can you Differentiate it from a Stack?

A queue is a type of linear structure which is used to access components that support the FIFO (First In First Out) method. Dequeue, enqueue, front, and rear are key queue functions. Unlike a stack, the arrays and linked lists are used to enforce a queue.

The element most recently added is removed first in a stack. However, in the event of a queue, the element least recently added is removed first.

What do you Understand by Stack? Please Explain some of its Applications.

Stack is a linear data structure to access components that implement either LIFO (Last In First Out) or FILO (First In Last Out) method. The common functions of a stack are push, pop, and peek.

Discuss the Different Operations that can be Carried out on Data Structures?

Following are the different operation that are generally carried out in Data Structures:

Insert– Add a new data item in the already existing set of data items.

Delete– Remove an existing data item from the given data item set.

Traverse– Access each piece of data precisely once so that it can be processed.

Search– Figure out where the data item resides in the specified data item set.

Sort– Arrange the data objects in certain order i.e. in ascending or descending order for numerical data and in dictionary order for alphanumeric data.