22317 Data Structure using ‘C’ External Oral / Viva Practice Questions with Answers
1) What is Data Structure?
Explain.
The data structure is a way that specifies how to organize and manipulate the data. It also defines the relationship between them. Some examples of Data Structures are arrays, Linked List, Stack, Queue, etc. Data Structures are the central part of many computer science algorithms as they enable the programmers to handle the data in an efficient way
2) Describe the types of
Data Structures?
Data Structures are mainly
classified into two types:
Linear Data Structure: A
data structure is called linear if all of its elements are arranged in the
sequential order. In linear data structures, the elements are stored in a
non-hierarchical way where each item has the successors and predecessors except
the first and last element.
Non-Linear Data Structure:
The Non-linear data structure does not form a sequence i.e. each item or
element is connected with two or more other items in a non-linear arrangement.
The data elements are not arranged in the sequential structure.
3) List the area of
applications of Data Structure.
Data structures are
applied extensively in the following areas of computer science:
Compiler Design,
Operating System,
Database Management
System,
Statistical analysis
package,
Numerical Analysis,
Graphics,
Artificial Intelligence,
Simulation
4) What is the difference
between file structure and storage structure?
Difference between file
structure and storage structure:
The main difference between
file structure and storage structure is based on memory area that is being
accessed.
Storage structure: It is
the representation of the data structure in the computer memory.
File structure: It is the representation of the storage structure in the auxiliary memory.
5) List the data
structures which are used in RDBMS, Network Data Modal, and Hierarchical Data
Model.
RDBMS uses Array data
structure
Network data model uses
Graph
Hierarchal data model uses
Trees
6) Which data structure is
used to perform recursion?
Stack data structure is
used in recursion due to its last in first out nature. Operating system
maintains the stack in order to save the iteration variables at each function
call
7) What is a Stack?
Stack is an ordered list in which, insertion and deletion can be performed only at one end that is called the top. It is a recursive data structure having pointer to its top element. The stack is sometimes called as Last-In-First-Out (LIFO) list i.e. the element which is inserted first in the stack will be deleted last from the stack.
8) List the area of
applications where stack data structure can be used?
Expression evaluation
Backtracking
Memory Management
Function calling and return
9) What are the operations
that can be performed on a stack?
Push Operations
Pop Operations
Peek Operations
10) Write the stack
overflow condition.
Overflow occurs when top = Maxsize -1
11) What is the difference
between PUSH and POP?
PUSH and POP operations
specify how data is stored and retrieved in a stack.
PUSH: PUSH specifies that
data is being "inserted" into the stack.
POP: POP specifies data
retrieval. It means that data is being deleted from the stack.
12) Write the steps
involved in the insertion and deletion of an element in the stack.
Push:
Increment the variable top
so that it can refer to the next memory allocation
Copy the item to the at
the array index value equal to the top
Repeat step 1 and 2 until
stack overflows
Pop:
Store the topmost element
into the an another variable
Decrement the value of the
top
Return the topmost element
13) What is a postfix
expression?
An expression in which
operators follow the operands is known as postfix expression. The main benefit
of this form is that there is no need to group sub-expressions in parentheses
or to consider operator precedence.
The expression "a + b" will be represented as "ab+" in postfix notation.
14)Write the postfix form
of the expression: (A + B) * (C - D)
AB+CD-*
15) Which notations are
used in Evaluation of Arithmetic Expressions using prefix and postfix forms?
Polish and Reverse Polish notations.
16)What is an array?
Arrays are defined as the
collection of similar types of data items stored at contiguous memory
locations. It is the simplest data structure in which each data element can be
randomly accessed by using its index number.
17) How to reference all
the elements in a one-dimension array?
It can be done by using an indexed loop such that the counter runs from 0 to the array size minus one. In this manner, you can reference all the elements in sequence by using the loop counter as the array subscript.
18) What is a
multidimensional array?
The multidimensional array
can be defined as the array of arrays in which, the data is stored in tabular
form consists of rows and columns. 2D arrays are created to implement a
relational database lookalike data structure. It provides ease of holding the
bulk of data at once which can be passed to any number of functions wherever
required.
19) How are the elements
of a 2D array are stored in the memory?
There are two techniques
by using which, the elements of a 2D array can be stored in the memory.
Row-Major Order: In
row-major ordering, all the rows of the 2D array are stored into the memory contiguously.
First, the 1st row of the array is stored into the memory completely, then the
2nd row of the array is stored into the memory completely and so on till the
last row.
Column-Major Order: In
column-major ordering, all the columns of the 2D array are stored into the
memory contiguously. first, the 1st column of the array is stored into the
memory completely, then the 2nd row of the array is stored into the memory
completely and so on till the last column of the array.
21) Define Linked List Data
structure.
Linked List is the collection of randomly stored data objects called nodes. In Linked List, each node is linked to its adjacent node through a pointer. A node contains two fields, i.e. Data Field and Link Field.
22) Are linked lists
considered linear or non-linear data structures?
A linked list is
considered both linear and non-linear data structure depending upon the
situation.
On the basis of data
storage, it is considered as a non-linear data structure.
On the basis of the access
strategy, it is considered as a linear data-structure.
23) What are the
advantages of Linked List over an array?
The size of a linked list
can be incremented at runtime which is impossible in the case of the array.
The List is not required
to be contiguously present in the main memory, if the contiguous space is not
available, the nodes can be stored anywhere in the memory connected through the
links.
The List is dynamically
stored in the main memory and grows as per the program demand while the array
is statically stored in the main memory, size of which must be declared at
compile time.
The number of elements in the linked list are limited to the available memory space while the number of elements in the array is limited to the size of an array.
24) Write the syntax in C
to create a node in the singly linked list.
struct node
{
int data;
struct node *next;
};
struct node *head,
*ptr;
ptr = (struct node
*)malloc(sizeof(struct node));
25) If you are using C
language to implement the heterogeneous linked list, what pointer type should
be used?
The heterogeneous linked list contains different data types, so it is not possible to use ordinary pointers for this. For this purpose, you have to use a generic pointer type like void pointer because the void pointer is capable of storing a pointer to any type.
26) What is doubly linked
list?
The doubly linked list is
a complex type of linked list in which a node contains a pointer to the
previous as well as the next node in the sequence. In a doubly linked list, a
node consists of three parts:
node data
pointer to the next node
in sequence (next pointer)
pointer to the previous node (previous pointer).
28) Define the queue data
structure.
A queue can be defined as
an ordered list which enables insert operations to be performed at one end
called REAR and delete operations to be performed at another end called FRONT.
29) List some applications
of queue data structure.
The Applications of the
queue is given as follows:
Queues are widely used as
waiting lists for a single shared resource like a printer, disk, CPU.
Queues are used in the
asynchronous transfer of data (where data is not being transferred at the same
rate between two processes) for eg. pipes, file IO, sockets.
Queues are used as buffers
in most of the applications like MP3 media player, CD player, etc.
Queues are used to
maintain the playlist in media players to add and remove the songs from the
play-list.
Queues are used in operating systems for handling interrupts.
30) What are the drawbacks
of array implementation of Queue?
Memory Wastage: The space
of the array, which is used to store queue elements, can never be reused to
store the elements of that queue because the elements can only be inserted at
front end and the value of front might be so high so that, all the space before
that, can never be filled.
Array Size: There might be situations in which, we may need to extend the queue to insert more elements if we use an array to implement queue, It will almost be impossible to extend the array size, therefore deciding the correct array size is always a problem in array implementation of queue.
32) What is a dequeue?
Dequeue (also known as double-ended queue) can be defined as an ordered set of elements in which the insertion and deletion can be performed at both the ends, i.e. front and rear.
33) What is the minimum
number of queues that can be used to implement a priority queue?
Two queues are needed. One queue is used to store the data elements, and another is used for storing priorities.
34) Define the tree data
structure.
The Tree is a recursive data structure containing the set of one or more data nodes where one node is designated as the root of the tree while the remaining nodes are called as the children of the root. The nodes other than the root node are partitioned into the nonempty sets where each one of them is to be called sub-tree.
35) List the types of
tree.
There are six types of
tree given as follows.
General Tree
Forests
Binary Tree
Binary Search Tree
Expression Tree
Tournament Tree
36) What are Binary trees?
A binary Tree is a special type of generic tree in which, each node can have at most two children. Binary tree is generally partitioned into three disjoint subsets, i.e. the root of the node, left sub-tree and Right binary sub-tree.
Other Questions
1. Explain the difference between file structure
and storage structure?
- File Structure: Representation of data into
secondary or auxiliary memory say any device such as hard disk or pen
drives that stores data which remains intact until manually deleted is known
as a file structure representation.
- Storage Structure: In this type, data is
stored in the main memory i.e RAM, and is deleted once the function that
uses this data gets completely executed.
- The difference is that storage structure has data stored in the memory of the computer system, whereas file structure has the data stored in the auxiliary memory.
2. How linear data structures differ from
non-linear data structures?
- If the elements of a data structure result in
a sequence or a linear list then it is called a linear data structure.
Whereas, traversal of nodes happens in a non-linear fashion in non-linear
data structures.
- Lists, stacks, and queues are examples of linear data structures whereas graphs and trees are the examples of non-linear data structures.
3. What is an array?
- Arrays are the collection of similar types
of data stored at contiguous memory
locations.
- It is the simplest data structure where the data element can be accessed randomly just by using its index number.
4. What is a multidimensional array?
- Multi-dimensional arrays are those data
structures that span across more than one dimension.
- This indicates that there will be more than
one index variable for every point of storage. This type of data structure
is primarily used in cases where data cannot be represented or stored
using only one dimension. Most commonly used multidimensional arrays are
2D arrays.
- 2D arrays emulates the tabular form structure
which provides ease of holding the bulk of data that are accessed using
row and column pointers.
5. What is a linked list?
A linked list is a data
structure that has sequence of nodes where
every node is connected to the next node by means of a reference pointer. The
elements are not stored in
adjacent memory locations. They are linked using pointers to form a chain.
This forms a chain-like link for data storage.
- Each node element has two parts:
- a data field
- a reference (or pointer) to the next node.
- The first node in a linked list is called the head and the last node in the list has the pointer to NULL. Null in the reference field indicates that the node is the last node. When the list is empty, the head is a null reference.
6. Are linked lists of linear or non-linear type?
Linked lists can be considered
both linear and non-linear data structures. This depends upon the application
that they are used for.
- When linked list is used for access strategies, it is considered as a linear data-structure. When they are used for data storage, it can be considered as a non-linear data structure.
7. How are linked lists more efficient than arrays?
- Insertion and Deletion
- Insertion and deletion process is expensive
in an array as the room has to be created for the new elements and
existing elements must be shifted.
- But in a linked list, the same operation is
an easier process, as we only update the address present in the next
pointer of a node.
- Dynamic Data Structure
- Linked list is a dynamic data structure that
means there is no need to give an initial size at the time of creation as
it can grow and shrink at runtime by allocating and deallocating memory.
- Whereas, the size of an array is limited as
the number of items is statically stored in the main memory.
- No wastage of memory
- As the size of a linked list can grow or
shrink based on the needs of the program, there is no memory wasted
because it is allocated in runtime.
- In arrays, if we declare an array of size 10 and store only 3 elements in it, then the space for 3 elements is wasted. Hence, chances of memory wastage is more in arrays.
8. What is a doubly-linked list (DLL)? What are its
applications.
- This is a complex type of a linked list
wherein a node has two references:
- One that connects to the next node in the
sequence
- Another that connects to the previous node.
- This structure allows traversal of the data
elements in both directions (left to right and vice versa).
- Applications of DLL are:
- A music playlist with next song and previous
song navigation options.
- The browser cache with BACK-FORWARD visited
pages
- The undo and redo functionality on platforms such as word, paint etc, where you can reverse the node to get to the previous page.
10. What is a stack? What are the applications of
stack?
- Stack is a linear data structure that follows
LIFO (Last In First Out) approach for accessing elements.
- Push, pop, and top (or peek) are the basic operations of a stack.
- Following are some of the applications of a
stack:
- Check for balanced parentheses in an
expression
- Evaluation of a postfix expression
- Problem of Infix to postfix conversion
- Reverse a string
11. What is a queue? What are the applications of
queue?
- A queue is a linear data structure that
follows the FIFO (First In First Out) approach for accessing elements.
- Dequeue from the queue, enqueue element to the queue, get front element of queue, and get rear element of queue are basic operations that can be performed.
- Some of the applications of queue are:
- CPU Task scheduling
- BFS algorithm to find shortest distance
between two nodes in a graph.
- Website request processing
- Used as buffers in applications like MP3
media player, CD player, etc.
- Managing an Input stream
12. How is a stack different from a queue?
- In a stack, the item that is most recently
added is removed first whereas in queue, the item least recently added is
removed first.
13. Explain the process behind storing a variable
in memory.
- A variable is stored in memory based on the
amount of memory that is needed. Following are the steps followed to store
a variable:
- The required amount of memory is assigned
first.
- Then, it is stored based on the data
structure being used.
- Using concepts like dynamic allocation ensures high efficiency and that the storage units can be accessed based on requirements in real time.
16. What is hashmap in data structure?
- Hashmap is a data structure that uses
implementation of hash table data structure which allows access of data in
constant time (O(1)) complexity if you have the key.
21. What is a priority queue?
- A priority queue is an abstract data type
that is like a normal queue but has priority assigned to elements.
- Elements with higher priority are processed
before the elements with a lower priority.
- In order to implement this, a minimum of two queues are required - one for the data and the other to store the priority.
23. What is a tree data structure?
- Tree is a recursive, non-linear data
structure consisting of the set of one or more data nodes where one node
is designated as the root and the remaining nodes are called as the
children of the root.
- Tree organizes data into hierarchal manner.
- The most commonly used tree data structure is
a binary tree and its variants.
- Some of the applications of trees are:
- Filesystems —files inside folders that
are inturn inside other folders.
- Comments on social media — comments, replies to
comments, replies to replies etc form a tree representation.
- Family trees — parents, grandparents,
children, and grandchildren etc that represents the family hierarchy.
24. What are Binary trees?
- A binary Tree is a special type of tree where each node can have at most two children. Binary tree is generally partitioned into three disjoint subsets, i.e. the root of the tree, left sub-tree and right sub-tree.
25. What is the maximum number of nodes in a binary
tree of height k?
- The maximum nodes are : 2k+1-1 where
k >= 1
28. What are tree traversals?
- Tree traversal is a process of visiting all
the nodes of a tree. Since root (head) is the first node and all nodes
are connected via edges (or links) we always start with that node. There
are three ways which we use to traverse a tree −
- Inorder Traversal:
- Algorithm:
- Step
1. Traverse the left subtree, i.e., call Inorder(root.left)
- Step
2. Visit the root.
- Step
3. Traverse the right subtree, i.e., call Inorder(root.right)
- Preorder Traversal:
- Algorithm:
- Step
1. Visit the root.
- Step
2. Traverse the left subtree, i.e., call Preorder(root.left)
- Step
3. Traverse the right subtree, i.e., call Preorder(root.right)
- Postorder Traversal:
- Algorithm:
- Step
1. Traverse the left subtree, i.e., call Postorder(root.left)
- Step
2. Traverse the right subtree, i.e., call Postorder(root.right)
- Step
3. Visit the root.
- Consider the following tree as an example,
then:
- Inorder Traversal => Left,
Root, Right : [4, 2, 5, 1, 3]
- Preorder Traversal => Root,
Left, Right : [1, 2, 4, 5, 3]
- Postorder Traversal => Left,
Right, Root : [4, 5, 2, 3, 1]
29. What is a Binary Search Tree?
- A binary search tree (BST) is a variant of binary
tree data structure that stores data in a very efficient manner such that
the values of the nodes in the left sub-tree are less than the value of
the root node, and the values of the nodes on the right of the root node
are correspondingly higher than the root.
- Also, individually the left and right
sub-trees are their own binary search trees at all instances of time.
30. What is an AVL Tree?
- AVL trees are height balancing BST.
AVL tree checks the height of left and right sub-trees and assures that
the difference is not
more than 1. This difference is called Balance Factor
and is calculates as. BalanceFactor = height(left subtree) −
height(right subtree)
31. Print Left view of any binary trees.
- The main idea to solve this problem is to
traverse the tree in pre order manner and pass the level information
along with it. If the level is visited for the first time, then we store
the information of the current node and the current level in the hashmap.
Basically, we are getting the left view by noting the first node of every
level.
- At the end of traversal, we can get the
solution by just traversing the map.
- Consider the following tree as example for
finding the left view:
32. What is a graph data structure?
Graph is a type of non-linear data structure that
consists of vertices or nodes connected by edges or links for storing data.
Edges connecting the nodes may be directed or undirected.
33. What are the applications of graph data
structure?
Graphs are used in wide varieties of applications.
Some of them are as follows:
- Social network graphs to determine the flow
of information in social networking websites like facebook, linkedin etc.
- Neural networks graphs where nodes represent
neurons and edge represent the synapses between them
- Transport grids where stations are the nodes
and routes are the edges of the graph.
- Power or water utility graphs where vertices
are connection points and edge the wires or pipes connecting them.
- Shortest distance between two end points algorithms.
34. How do you represent a graph?
We can represent a graph in 2 ways:
- Adjacency matrix: Used for sequential data representation
- Adjacency list: Used to represent linked data
35. What is the difference between tree and graph
data structure?
- Tree and graph are differentiated by the fact
that a tree structure must be connected and can never have loops whereas
in the graph there are no restrictions.
- Tree provides insights on relationship between nodes in a hierarchical manner and graph follows a network model.
36. What is the difference between the Breadth
First Search (BFS) and Depth First Search (DFS)?
- BFS and DFS both are the traversing methods
for a graph. Graph traversal is nothing but the process of visiting all
the nodes of the graph.
- The main difference between BFS and DFS is
that BFS traverses level by level whereas DFS follows first a path from
the starting to the end node, then another path from the start to end,
and so on until all nodes are visited.
- Furthermore, BFS uses queue data structure
for storing the nodes whereas DFS uses the stack for traversal of the
nodes for implementation.
- DFS yields deeper solutions that are not
optimal, but it works well when the solution is dense whereas the
solutions of BFS are optimal.
- You can learn more about BFS here: Breadth First Search and DFS here: Depth First Search.
37. How do you know when to use DFS over BFS?
- The usage of DFS heavily depends on the
structure of the search tree/graph and the number and location of
solutions needed. Following are the best cases where we can use DFS:
- If it is known that the solution
is not far from the root of the tree, a breadth first search (BFS) might
be better.
- If the tree is very deep and
solutions are rare, depth first search (DFS) might take an extremely
long time, but BFS could be faster.
- If the tree is very wide, a BFS
might need too much memory, so it might be completely impractical. We go
for DFS in such cases.
- If solutions are frequent but
located deep in the tree we opt for DFS.
38. What is topological sorting in a graph?
- Topological sorting is a linear ordering of
vertices such that for every directed edge ij, vertex i comes before j in
the ordering.
- Topological sorting is only possible for
Directed Acyclic Graph (DAG).
- Applications:
- jobs scheduling from the given
dependencies among jobs.
- ordering of formula cell
evaluation in spreadsheets
- ordering of compilation tasks to
be performed in make files,
- data serialization
- resolving symbol dependencies in
linkers.
40. What is a heap data structure?
Heap is a special tree-based non-linear data
structure in which the tree is a complete binary tree. A binary tree is said to
be complete if all levels are completely filled except possibly the last level
and the last level has all elements towards as left as possible. Heaps are of
two types:
- Max-Heap:
- In a Max-Heap the data element
present at the root node must be greatest among all the data elements
present in the tree.
- This property should be
recursively true for all sub-trees of that binary tree.
- Min-Heap:
- In a Min-Heap the data element
present at the root node must be the smallest (or minimum) among all the
data elements present in the tree.
- This property should be recursively true for all sub-trees of that binary tree.
Disclaimer:
Thankyou Javatpoint and Interviewbit for preparing this Questions, All Credit goes to Javatpoint and Interviewbit . We have used their content for
helping students in their VIVA / Oral / External Exam so they can score Great
Marks in it.