Data Structure SQ–1 A (CS/IT-Sem-3)
1 Array and Linked List
(2 Marks Questions)
1.1. Define the term data structure. List some linear and non-
linear data structures stating the application area where
they will be used. AKTU 2017-18, Marks 02
Ans. It is a particular way of storing and organizing data in a computer so
that it can be used efficiently.
It can be classified into two types :
i. Linear data structures :
1. Array
2. Stacks
3. Queue
4. Linked list
ii. Non-linear data structures :
1. Tree
2. Graph
1.2. Name few terminologies used in data structure.
Ans. Few terminologies used in data structure are :
1. Data
2. Entity
3. Field
4. Record
5. File
1.3. What are the data types used in C ?
Ans. Data type used in C are :
1. Primitive data types
2. Non-primitive data types
1.4. Name some primitive data types.
Ans. Primitive data types are :
1. Integer data type
2. Floating point data type
3. Character data type
4. Void data type
1.5. Define an algorithm.
SQ–2 A (CS/IT-Sem-3) 2 Marks Questions
Ans. An algorithm is a step-by-step finite sequence of instruction, to
solve a well-defined computational problem.
1.6. Give the criteria that an algorithm must satisfy.
Ans. Every algorithm must satisfy the following criteria :
1. Input
2. Output
3. Definiteness
4. Effectiveness
5. Finiteness
1.7. What are the characteristics of an algorithm ?
Ans. Characteristics of an algorithm are :
1. It should be free from ambiguity.
2. It should be concise.
3. It should be efficient.
1.8. What are the different ways of analyzing an algorithm ?
Ans. Different ways of analyzing an algorithm :
1. Worst case running time
2. Average case running time
3. Best case running time
1.9. Define complexity.
Ans. The complexity of an algorithm M is the function f(n) which gives
the running time and/or storage space requirement of the algorithm
in terms of the size n of the input data.
1.10. Define time complexity and space complexity of an
algorithm. AKTU 2016-17, Marks 02
Ans. Time complexity : Time complexity is the amount of time it needs
to run to completion.
Space complexity : Space complexity is the amount of memory it
needs to run to completion.
1.11. What are the various asymptotic notations ? Explain the
Big-Oh notation. AKTU 2015-16, Marks 02
Ans. Various asymptotic notations are :
1. Theta notation (- notation)
2. Big-Oh (O - notation)
3. Omega notation ( - notation)
Big-Oh notation : It is used when there is only an asymptotic
upper bound. For a given function g(n), O(g(n)) is denoted by a set
of functions.
Data Structure SQ–3 A (CS/IT-Sem-3)
1.12. Define time-space tradeoff.
Ans. The time-space tradeoff refers to a choice between algorithmic
solutions of data processing problems that allows to decrease the
running time of an algorithmic solution by increasing the space to
store data and vice versa.
1.13. Write down the properties of Abstract Data Type (ADT).
Ans. Properties of Abstract Data Type (ADT) :
i. It is used to simplify the description of abstract algorithm to classify
and evaluate data structure.
ii. It is an important conceptual tool in OOPs and design by contract
methodologies for software development.
1.14. Differentiate linear and non-linear data structures.
AKTU 2016-17, Marks 02
Ans.
S. No. Linear data structure Non-linear data structure
1. It is a data structure whose It is a data structure who se
elements form a sequence. elements do not form a sequence.
2. Eve ry e le me nt in the There is no unique predecessor or
structure has a unique unique successor.
predecessor and unique
successor.
3. Examples of linear data Examples o f no n-line ar data
structure are arrays, linked structures are trees and graphs.
lists, stacks and queues.
1.15. What do you mean by an array ?
Ans. An array is a list of finite number of elements of same data type i.e.,
integer, real or strings.
1.16. What are the merits and demerits of array data
structures ? AKTU 2016-17, Marks 02
Ans. Merits of array :
1. Array is a collection of elements of similar data type.
2. Hence, multiple applications that require multiple data of same
data type are represented by a single name.
Demerits of array :
1. Linear arrays are static structures, i.e., memory used by them
cannot be reduced or extended.
2. Previous knowledge of number of elements in the array is
necessary.
SQ–4 A (CS/IT-Sem-3) 2 Marks Questions
1.17. Define pointer.
Ans. Pointers are variable which can hold the address of another variable.
Some of the examples of pointer declarations are :
int * ptr1;
float * ptr2;
unsigned int * ptr3;
1.18. Differentiate between array and pointer.
Ans.
S. No. Array Pointer
1. Array can be initialized at Pointer cannot be initialized at
definition. definition.
2. Static in nature. Dynamic in nature.
3. It cannot be resized. It can be resized.
1.19. Differentiate between overflow and underflow condition in
a linked list. AKTU 2018-19, Marks 02
Ans.
S. No. Overflow Underflow
1. Overflow condition occurs in Underflow condition occurs when
linked list when data are we delete data from empty linked
inserted into a list but there list.
is no available space.
2. In linked list overflow occurs In linked list underflow occurs when
when AVAIL = NULL and START = NULL and there is a
there is an inse rtio n deletion operation.
operation.
1.20. Write a function to reverse the list.
Ans. node * reverse (node * p){
node *q, *r;
q = (node*) NULL;
while (p != NULL)
{
r = q;
q = p;
p = p next;
p next = r;
}
return(q);
}
Data Structure SQ–5 A (CS/IT-Sem-3)
1.21. Given a 2D array A [– 100 : 100, – 5 : 50]. Find the address of
element A [99, 49] considering the base address 10 and each
element requires 4 bytes for storage. Follow row major order.
AKTU 2015-16, Marks 02
Ans. LOC(A[i][j]) =Base (A) + w [n (i – lower bound for row index) +
(j – lower bound for column index))
LOC (A[99][49]) = 10 + 4 [50 (99 – (– 100) + 49 – (– 5)]
= 10 + 4 [50 (199) + 54] = 40026
1.22. Explain the application of sparse matrices.
AKTU 2015-16, Marks 02
Ans. There are two applications of sparse matrix which are :
1. Triangular matrix : In this, all entries above the main diagonal
are zero or, equivalently, where non-zero entries can only occur on
or below the main diagonal.
2. Tridiagonal matrix : In this, all non-zero entries can occur only
on the diagonal or on elements immediately above or below the
diagonal.
SQ–6 A (CS/IT-Sem-3) 2 Marks Questions
2 Stacks and Queues
(2 Marks Questions)
2.1. What are the applications of stack ?
Ans. Applications of stack are :
i. Infix to postfix conversion.
ii. Implementing function calls.
iii. Page-visited history in a web browser.
iv. Undo sequence in a text editor.
2.2. Mention the limitations of stack using array.
Ans. Limitations of stacks using array :
i. The maximum size of the stack once defined cannot be changed.
ii. Trying to push a new element into a full stack causes an overflow
condition.
2.3. What are the notations used in evaluation of arithmetic
expressions using prefix and postfix forms ?
AKTU 2015-16, Marks 02
Ans. Notations used in evaluation of arithmetic expressions are :
i. Infix notation : In this notation, the operator symbol is placed
between its two operands.
For example : To add A to B we can write as, A + B or B + A
ii. Polish (Prefix) notation : Here the operator symbol is placed
before its two operands.
For example : To add A to B we can write as, + AB or + BA
iii. Reverse polish (Postfix) notation : In this notation, the operator
symbol is placed after its two operands.
For example : To add A and B we can write as : AB+ or BA+
2.4. If the Tower of Hanoi is operated on n = 10 disks, calculate
the total number of moves. AKTU 2015-16, Marks 02
OR
Calculate total number of moves for Tower of Hanoi for
n = 10 disks. AKTU 2017-18, Marks 02
Ans. For n number of disks, total number of moves = 2n – 1
For 10 disks, i.e., n = 10, total number of moves = 210 – 1
= 1024 – 1
= 1023
Therefore, if the Tower of Hanoi is operated on n = 10 disks, then
total number of moves are 1023.
Data Structure SQ–7 A (CS/IT-Sem-3)
2.5. Give the infix, postfix and prefix notation of (A + B) + C.
Ans. Infix notation : (A + B) + C
Postfix notation : (AB) ++ C = AB + C +
Prefix notation : + AB + C = ++ ABC
2.6. How do you push elements in a linked stack ?
AKTU 2016-17, Marks 02
Ans. To insert an element onto stack is known as PUSH operation.
Before inserting first we increase the top pointer and then insert
the element.
2.7. Differentiate between iteration and recursion.
Ans.
S. No. Iteration Recursion
i. It is a process of executing It is a te chnique of defining
state me nt until some anything in terms of itself.
spe cified condition is
satisfied.
ii. Iterative counterpart of a It is a worse option to go for simple
problem is more efficient problems.
in term of memory
utilization and execution
speed.
2.8. Discuss the steps for converting an infix expression to
postfix expression.
Ans. Steps for converting an infix expression to postfix
expression :
i. Parenthesize the expression starting from left to right.
ii. During parenthesizing the expression, the operands associated with
operator having higher precedence are first parenthesized.
iii. Once the expression is converted to postfix then remove the
parenthesis.
2.9. Write some applications of queue.
Ans. Application of queues are :
i. Operating systems schedule jobs in the order of arrival.
ii. Simulation of real world queues such as lines at a ticket counter.
iii. Multiprogramming.
iv. Waiting times for customers at call center.
2.10. Translate infix expression into its equivalent postfix
expression : A * (B + D)/E – F * (G + H/K).
AKTU 2015-16, Marks 02
Ans. Infix expression : A * (B + D)/E – F * (G + H/K)
A * (BD +)/E – F * (G + HK/)
SQ–8 A (CS/IT-Sem-3) 2 Marks Questions
A (BD +)*/E – F* (GHK/+)
(ABD + * E/) – (FGHK/+*)
ABD + * E/FGHK / + * –
Equivalent postfix expression is :
ABD + * E/FGHK / + * –
2.11. Convert the following arithmetic infix expression into its
equivalent postfix expression.
Expression : A – B/C + D*E + F AKTU 2017-18, Marks 02
Ans. (A – B/C + D*E + F)
Character Stack Postfix
( (
A ( A
– (– A
B (– AB
/ (– / AB
C (– / ABC
+ (–+ ABC /
D (–+ ABC / D
* (– + * ABC / D
E (– + * ABC /DE
+ (– ++ ABC / DE*
F (– ++ ABC / DE*F
) ( ABC / DE*F ++ –
2.12. Write the difference between stack and queue.
Ans.
S. No. Stack Queue
i. A stack is logically a LIFO A queue is logically a FIFO type of
type of list. list.
ii. No element other than the No element other than front and
top of stack element is rear element are visible.
visible.
2.13. What are the advantages of queue over stack ?
Ans. Advantages of queue over stack are :
i. An element that is inserted first in the queue will be the first
element to be removed.
ii. Insertion and deletion, both are possible only on one end in stack.
While in queue elements are inserted at one end and elements are
deleted at other end.
2.14. Write down the limitations of circular queue.
Data Structure SQ–9 A (CS/IT-Sem-3)
Ans. Limitations of circular queue are :
i. We cannot distinguish between full and empty queue.
ii. Front and rear indices are in exactly the same relative positions for
an empty and for a full queue.
2.15. What is the significance of priority queue ?
AKTU 2016-17, Marks 02
Ans. Priority queue is a data structure in which elements can be stored
as per their priorities. And therefore one can remove the elements
from such queue according to their priorities. Such type of queue is
useful to operating system in job scheduling algorithms.
2.16. Name the types of recursion.
Ans. Types of recursion are :
i. Direct recursion
ii. Indirect recursion
iii. Tail recursion
iv. Linear and tree recursion
2.17. Write the syntax to check whether a given circular queue is
full or empty. AKTU 2018-19, Marks 02
OR
Explain circular queue. What is the condition if circular
queue is full ? AKTU 2017-18, Marks 02
Ans. Circular queue : A circular queue is one in which the insertion of
a new element is done at the very first location of the queue if the
last location at the queue is full.
Syntax to check circular queue is full :
If ((front == MAX – 1) || (front == 0 && rear == MAX – 1))
Syntax to check circular queue is empty :
If (front == 0 && rear == – 1)
2.18. What is recursion ? Give disadvantages of recursion.
AKTU 2018-19, Marks 02
Ans. Recursion : Recursion is the process of expressing a function that
calls itself to perform specific operation.
Disadvantages of recursion :
1. Recursive solution is always logical and it is very difficult to trace,
debug and understand.
2. Recursion takes a lot of stack space, usually not considerable when
the program is small and running on a PC.
3. Recursion uses more processor time.
SQ–10 A (CS/IT-Sem-3) 2 Marks Questions
3 Searching and Sorting
(2 Marks Questions)
3.1. What do you mean by searching ?
Ans. Searching is a process of finding the location of given elements in
the linear arrays. The search is said to be successful if the given
element is found.
3.2. Name two searching techniques.
Ans. Two searching techniques are :
1. Linear (sequential) search
2. Binary search
3.3. Define sequential search.
Ans. In sequential search, each element of an array is read one-by-one
sequentially and it is compared with the desired element.
3.4. Define index sequential search.
Ans. In index sequential search, an index file is created, that contains
some specific group or division of required record when the index is
obtained, then the partial indexing takes place as it is loaded in a
specific group.
3.5. What do you mean by hashing ?
Ans. Hashing is a searching technique that is used to uniquely identify a
specific object from a group of similar objects.
3.6. Classify the hashing functions based on the various
methods by which the key value is found.
AKTU 2015-16, Marks 02
Ans. Hashing functions on various methods by which the key
value is founded are :
i. Division method ii. Multiplication method
iii. Mid square method iv. Folding method
3.7. What is collision ?
Ans. Collision is a situation which occur when we want to add a new
record R with key K to our file F, but the memory location address
H(k) is already occupied.
3.8. Discuss various collision resolution strategies for hash
table.
Data Structure SQ–11 A (CS/IT-Sem-3)
Ans. Collision resolution strategies for hash table are :
i. Chaining method : It hold the address of a table element by using
h(K) = key% table slots.
ii. Open addressing method : In this, all the elements of the dynamic
sets are stored in hash table itself.
3.9. What is sorting ? How is sorting essential for database
applications ? AKTU 2016-17, Marks 02
Ans. Sorting : It is an operation which is used to put the elements of list
in a certain order. i.e., either in decreasing or increasing order.
Sorting essential for database applications : Sorting is easier
and faster to locate items in a sorted list than unsorted. Sorting
algorithms can be used in a program to sort an array for later
searching or writing out to an ordered file or report. Sorted arrays/
lists make it easier to find things more quickly.
3.10. What do you understand by stable and in-place sorting ?
AKTU 2018-19, Marks 02
Ans. Stable sorting : Stable sorting is an algorithm where two objects
with equal keys appear in the same order in sorted output as they
appear in the input unsorted array.
In-place sorting : An in-place sorting is an algorithm that does
not need an extra space and produces an output in the same memory
that contains the data by transforming the input ‘in-place’. However,
a small constant extra space used for variables is allowed.
3.11. Differentiate between internal and external sorting.
Ans.
S. No. Internal sorting External sorting
i. The internal so rting Exte rnal sorting resides in
resides in main memory. secondary memory.
ii. It is independent of time It is dependent on time.
to read/write a record.
3.12. Give the worst case and best case time complexity of binary
search. AKTU 2016-17, Marks 02
Ans. Worst case : In each comparison, the size of the search area is
reduced by half. So, the efficiency of the binary search method at
the worst case is log2 n + 1, i.e., O(log2 n + 1) where n is the total
number of items that will be used for the binary search.
Best case : The best case of binary search occurs when the element
we are searching for is the middle element of the list/array because
in that case we will get the desired result in a single go. In this case,
the time complexity of the algorithm will be O(1).
SQ–12 A (CS/IT-Sem-3) 2 Marks Questions
4 Graphs
(2 Marks Questions)
4.1. What are the applications of graphs ?
Ans. Applications of graph are :
i. Representing relationship between components in electronic
circuits.
ii. Transportation network in highway network, flight network.
iii. Computer network in local area network.
4.2. Write down the applications of DFS.
Ans. Applications of DFS :
i. Topological sorting.
ii. Finding connected components.
iii. Finding strongly connected components.
iv. Solving puzzles such as mazes.
4.3. Write down the applications of BFS.
Ans. Applications of BFS :
i. Finding all nodes within one connected component.
ii. Finding the shortest path between two nodes.
4.4. Define connected and strongly connected graph.
AKTU 2015-16, Marks 02
Ans. Connected graph : A graph G is said to be connected if there is at
least one path between every pair of vertices in G.
Strongly connected graph : A graph G is said to be strongly
connected if there is at least one directed path from every vertex to
every other vertex.
4.5. What are the advantages of DFS over BFS ?
Ans. Advantages of DFS over BFS :
i. DFS has much lower memory requirement than BFS.
ii. DFS is better than BFS if the solution is at maximum depth.
4.6. How the graph can be represented in memory ? Explain
with suitable example. AKTU 2018-19, Marks 02
OR
List the different types of representation of graphs.
AKTU 2017-18, Marks 02
Data Structure SQ–13 A (CS/IT-Sem-3)
Ans. Graph can be represented in memory using :
1. Matrix representation
2. Linked representation
For example : Consider the following directed graph :
v1 v4
v2 v3
Fig. 1.
Matrix representation :
v1 v2 v3 v4
v1 0 0 0 1
v2 1 0 1 0
v3 0 0 0 1
v4 0 1 0 0
Linked representation :
v1 v4 /
v2 v1 v3 /
v3 v4 /
v4 v2 /
Fig. 2.
4.7. Discuss the disadvantages of Dijkstra’s algorithm.
Ans. Disadvantages of Dijkstra’s algorithm are :
i. It does a blind search thereby consuming a lot of time and wasting
necessarily resource.
ii. It cannot handle negative edges. This leads to acyclic graphs.
4.8. How many ways are there to implement Krus kal’s
algorithm ?
Ans. Ways to implement Kruskal’s algorithm :
i. By using disjoint sets : Using UNION and FIND operation.
ii. By using priority queue : Maintains weights in priority queue.
4.9. How Prim’s algorithm is similar to Dijkstra’s algorithm ?
Ans.
i. Similar to Dijkstra algorithm, in Prim’s algorithm we also keep
distance values and paths in distance table.
ii. The implementation of Prim’s algorithm is identical to that of
Dijkstra’s algorithm so the running time is O(|V|2) without heaps
and O(E log V) using binary heaps.
SQ–14 A (CS/IT-Sem-3) 2 Marks Questions
4.10. Prove that the number of odd degree vertices in a connected
graph should be even. AKTU 2016-17, Marks 02
Ans. Let V1 and V2 be the set of vertices of even and odd degrees
respectively. Thus, V1 V2 = and V1 V2 = V.
By Handshaking theorem,
2|E| = deg(v) = deg(v) + deg(v)
v V v V1 v V2
As both 2|E| and deg(v) are even. So, deg(v) must be
v V1 v V2
even.
Since, deg(v) is odd for all v V2. So, the number of odd degree
vertices in a connected graph must be even.
4.11. Number of nodes in a complete tree is 100000. Find its depth.
AKTU 2018-19, Marks 02
Ans. Number of nodes in a complete tree = 100000
We know that, n= 2h + 1 – 1
(n + 1) = 2h + 1
log2(n + 1) = h+1
log2(n + 1) – 1 = h
Putting n= 100000
h= log2(100000 + 1) – 1
h= 15 (approx)
Data Structure SQ–15 A (CS/IT-Sem-3)
5 Trees
(2 Marks Questions)
5.1. Define tree.
Ans. A tree T is a finite non-empty set of elements. One of these elements
is called the root, and the remaining elements, if any is partitioned
into trees is called subtree of T. A tree is a non-linear data structure.
5.2. Define the depth of a node.
Ans. The depth of a node is the length of the path from the root to the
node. A (rooted) tree with only one node (the root) has a depth of
zero.
5.3. Describe the properties of binary tree.
Ans. Properties of binary tree are :
i. The number of nodes n in a full binary tree is 2n+1 – 1.
ii. The number of leaf nodes in a full binary tree is 2h where h is the
height.
iii. The number of NULL links in a complete binary tree of n nodes is
n + 1.
5.4. Define complete binary tree. Give example.
AKTU 2016-17, Marks 02
Ans. A tree is called complete binary tree if tree satisfies following
conditions :
1. Each node has exactly two children except leaf node.
2. All leaf nodes are at same level.
3. If a binary tree contains m nodes at level l, it contains at most 2m
nodes at level l + 1.
Example :
A
B C
D E F G
H I J K L M N O
Fig. 1.
5.5. For tree construction which is the suitable and efficient
data structure and why ? AKTU 2015-16, Marks 02
SQ–16 A (CS/IT-Sem-3) 2 Marks Questions
Ans. Linked list is the most suitable and efficient data structure because
it is easily accessible due to the concept of pointer used in it.
5.6. Discuss the concept of “successor” and “predecessor” in
binary search tree. AKTU 2017-18, Marks 02
Ans. In binary search tree, if a node X has two children, then its
predecessor is the maximum value in its left subtree and its successor
is the minimum value in its right subtree.
5.7. Explain height balanced tree. List general cases to maintain
the height. AKTU 2017-18, Marks 02
Ans.
i. An AVL (or height balanced) tree is a balanced binary search tree.
ii. In an AVL tree, balance factor of every node is either –1, 0 or +1.
iii. Balance factor of a node is the difference between the heights of
left and right subtrees of that node.
Balance factor = height of left subtree – height of right subtree.
General cases to maintain the height are :
a. Left Left rotation (LL rotation)
b. Right Right rotation (RR rotation)
c. Left Right rotation (LR rotation) d. Right Left rotation (RL rotation)
5.8. Draw a binary tree for the expression : A * B – (C + D) * (P/Q)
AKTU 2018-19, Marks 02
Ans.
–
* *
A B + /
C D P Q
Fig. 2.
5.9. What is the maximum height of any AVL tree with 7 nodes ?
AKTU 2015-16, Marks 02
Ans. Maximum height of any AVL tree with 7 nodes is 3.
5.10. When does a graph become tree ?
AKTU 2016-17, Marks 02
Ans. A graph becomes a tree when there is exactly one path between
every pair of its vertices.
5.11. How can we traverse a binary tree ?
Ans. We can traverse a binary tree using :
1. Inorder traversing 2. Preorder traversing 3. Postorder traversing
