AKTU Data Structures: Important Short Questions for Success

Providing All Units ARRAYS AND LINKED LISTS, STACKS AND QUEUES, SEARCHING & SORTING, GRAPHS and TREES Data Structures Important short Questions with the solution – AKTU, Last year’s question paper with solutions, and many more study materials that will help students or bachelor’s exam

Dudes 🤔.. You want more useful details regarding this subject. Please keep in mind this as well.

Important Questions For Data Structures: 
*Unit-01     *Unit-02    
*Unit-03    *Unit-04 
*Unit-05    *Short-Q/Ans
*Question-Paper with solution 21-22 

Unit – 1 (Array and Linked List) Data Structures

Q1. Define the term data structure. List some linear and non linear data structures stating the application area where they will be used.

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

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

Q3. What are the data types used in C?

Ans. Data type used in C are:

• 1. Primitive data types
• 2. Non-primitive data types

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

Q5. Define an algorithm.

Ans. An algorithm is a step-by-step finite sequence of instruction, to solve a well-defined computational problem.

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

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

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

Q9. Define complexity.

Ans. The complexity of an algorithm M is the function fln) which gives

the running time and/or storage space requirement of the algorithm

in terms of the size n of the input data.

Q10. Define time complexity and space complexity of an algorithm.

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.

Q11. What are the various asymptotic notations ? Explain the Big-Oh notation.

Ans. Various asymptotie notations are:

1. Theta notation (0-notation)

2. Big-Oh (0 – notation)

3. Omega notation (Q notation)

Big-Oh notation: It is used when there is only an asymptotic upper bound. For a given function g(n), Ogtn)) is denoted by a set of functions.

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

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

Q14. Differentiate linear and non-linear data structures.

Ans. 

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

Q16. What are the merits and demerits of array data structures?

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.

Q17. Define pointer.

Ans. Pointers are variable which can hold the address of another variable.

Some of the examples of pointer declarations are :

int* ptrl;

float * ptr2;

unsigned int * ptr3;

Q18. Differentiate between array and pointer.

Ans. 

Q19. Differentiate between overflow and underflow condition in a linked list.

Ans. 

Q20. Write a function to reverse the list.

Ans. node * reverse (node * p){

node * q, *r;

= (node*) NULL;

while (p l= NULL)

{

r=q;

q=p;

p=p → next;

p → next = r;

}

return(q);

}

Q21. Given a 2D array A l- 100: 100, -5:501. 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.

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

Q22. Explain the application of sparse matrices.

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.

Unit – 2 (Stacks and Queues) Data Structures

Q1. What are the applications of stack?

Ans. Applications of stack are:

i. Intix to postix conversion.

ii. Implementing function calls.

ii. Page-visited history in a web browser.

iv. Undo sequence in a text editor.

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

Q3. What are the notations used in evaluation of arithmetie expressions using prefix and postfix forms?

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

ii. 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+

Q4. If the Tower of Hanoi is operated on n = 10 disks, caleulate the total number of moves.

Calculate total number of moves for Tower of Hanoi for n = 10 disks.

Ans. For n number of disks, total number of moves =2ⁿ -1

For 10 disks, i.e., n = 10, total number of moves      =2¹⁰ -1

                                                                                  =1024 – 1

                                                                                  =1023

Therefore, if the Tower of Hanoi is operated on n = 10 disks, then total number of moves are 1023.

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

Q6. How do you push elements in a linked stack?

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.

Q7. Differentiate between iteration and recursion.

Ans. 

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

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

ii. Multiprogramming.

iv. Waiting times for customers at call center.

Q10. Translate infix expression into its equivalent postfix

expression :A* (B + D/E – F* (G+ H/K).

Ans. Infix expression: A* (B+ D/E -F*(G + H/K)

         A (BD +E -F* (G+HK)

A (BD +”/E- F* (GHK/+)

(ABD +* E/) -(FGHK/+*)

ABD +* E/FGHK/+ *-

Equivalent postfix expression is:

ABD+* E/FGHK/+* –

Q11. Convert the following arithmetic infix expression into its

equivalent postfix expression.

Expression : A- B/C+ D*E +F

Ans. (A- B/C + D*E + F)

Q12. Write the difference between stack and queue.

Ans. 

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

Q14. Write down the limitations of circular queue.

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.

Q15. What is the significance of priority queue?

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.

Q16. Name the types of recursion.

Ans. Types of recursion are:

i Direct recursion

i. Indirect recursion

ii. Tail recursion

iv. Linear and tree recursion

Q17. Write the syntax to check whether a given circular queue is full or empty.

Explain circular queue. What is the condition if circular queue is full?

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)

Q18. What is recursion ? Give disadvantages of recursion.

Ans. Recursion: Recursion is the process of expressing a function calls that 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.

Unit – 3 (Searching and Sorting) in Data Structures

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

Q2. Name two searching techniques.

Ans. Two searching techniques are:

1. Linear (sequential) search

2. Binary search

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

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

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

Q6. Classify the hashing functions based on the various methods by which the key value is found.

Ans. Hashing functions on various methods by which the key

value is founded are:

i. Division method                        iii. Multiplication method

ii. Mid square method                  iv. Folding method

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

Q8. Discuss various collision resolution strategies for hash table.

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.

Q9. What is sorting ? How is sorting essential for database applications?

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.

Q10. What do you understand by stable and in-place sorting?

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.

Q11. Differentiate between internal and external sorting.

Ans. 

Q12. Give the worst case and best case time complexity of binary search.

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 log₂, n + 1, i.e., O(log₂, 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).

Unit – 4 (Graphs)

Q1. What are the applications of graphs?

Ans. Applications of graph are:

i. Representing relationship between components in electronic circuits.

iii. Transportation network in highway network, flight network.

ii. Computer network in local area network.

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

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

Q4. Define connected and strongly connected graph.

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.

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

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

Q7. How many ways are there to implement Kruskal’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.

Q8. 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|²) without heaps and O(E log V) using binary heaps.

Q9. Prove that the number of odd degree vertices in a connected graph should be even.

Ans.

Q10. Number of nodes in a complete tree is 100000. Find its depth.

Ans. Number of nodes in a complete tree = 100000

We know that, n = 2^h+2 -1

                  (n +1) = 2^h+2

          log₂(n + 1) = h +1

        log₂(n + 1)-1=h

Putting,            n = 100000

                      h = log₂(100000+1) – 1

                        h = 15 (approx)

Unit – 5 Trees, in Data structures

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

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

Q3. Describe the properties of binary tree.

Ans. Properties of binary tree are: 

i. The number of nodes n in a full binary tree is 2ⁿ⁺¹-1.

ii.  The number of leaf nodes in a full binary tree is 2^h where h is the height.

iii. The number of NULL links in a complete binary tree of n nodes is n+1.

Q4. Define complete binary tree. Give example.

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. Ifa binary tree contains m nodes at level l, it contains at most 2m nodes at level l + 1.

Q5. For tree construction which is the suitable and efficient data structure and why ?

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.

Q6. Discuss the concept of “successor” and “predecessor” in binary search tree.

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.

Q7. Explain height balanced tree. List general cases to maintain the height.

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)

Q8. Draw a binary tree for the expression :A* B-(C+D)* (PI)

Ans. 

Q9. What is the maximum height of any AVL tree with 7 nodes?

Ans. Maximum height of any AVL tree with 7 nodes is 3.

Q10. When does a graph become tree?

Ans. A graph becomes a tree when there is exactly one path between every pair of its vertices.

Q11. How can we traverse a binary tree?

Ans. We can traverse a binary tree using

1. Inorder traversing 2. Preorder traversing 3. Postorder traversing

Cracking AKTU B.Tech: Quantum Data Structures – Last Year’s Short Questions Paper

AKTU Important Links | Btech Syllabus

Important Links-Btech (AKTU)| Data Structures Syllabus