AKTU Data Structures: Unit-1 Important Questions

This is Btech, MCA, and BCA’s common subject, “data structures.” Providing Last year’s question paper with solutions and many more study materials that will help student 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 

Q1. Define the data structure. Describe its need and types. Why do we need a data type? 

Ans. Data structure:

1. A data structure is a way of organizing all data items that considers not only the elements stored but also their relationship to each other.

2. Data structure is the representation of the logical relationship existing between individual elements of data.

3. Data structure is define as a mathematical or logical model of particular organization of data items.

Data structure is needed because :

1. It helps to understand the relationship of one element with the other.

2. It helps in the organization of all data items within the memory.

The data structures are divided into following categories :

1. Linear data structure:

a. A linear data structure is a data structure whose elements form a sequence, and every element in the structure has a unique predecessor and unique successor.

b. Examples of linear data structure are arrays, linked lists, stacks and queues.

2. Non-linear data structure:

a. A non-linear data structure it is a data structure whose elements do not form a sequence. There is no unique predecessor or unique successor.

b. Examples of non-linear data structures are trees and graphs.

Need of data type: The data type is needed because it determines what type of information can be stored in the field and how the data can be formatted.

Q2. How do you find the complexity of an algorithm? What is the relation between the time and space complexities of an algorithm? Justify your answer with an example.

Ans.1. 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.

2. The storage space required by an algorithm is simply a multiple of the data size n.

3. Following are various cases in complexity theory:

a. Worst case: The maximum value of f(n) for any possible input.

b. Average case: The expected value of f(n) for any possible input.

c. Best case: The minimum possible value of f(n) for any possible input.

Types of complexity:

1. Space complexity: The space complexity of an algorithm is the amount of memory it needs to run to completion.

2. Time complexity: The time complexity of an algorithm is the amount

of time it needs to run to completion.

Relation between the time and space complexities of an algorithm: 

1. The time and space complexities are not related to each other.

2.They are used to describe how much space/time our algorithm takes based on the input.

3. For example, when the algorithm has space complexity of:

a. O(1) i.e., constant then the algorithm uses a fixed (small) amount of space which does not depend on the input. For every size of the input the algorithm will take the same (constant) amount of space.

b. O(n), O(n²), O(log (n)) – these indicate that we create additional objects based on the length of our input.

4. In contrast, the time complexity describes how much time our algorithm consumes based on the length of the input.

5. For example, when the algorithm has time complexity of

a. O(1) ie., constant then no matter how big is the input it always takes a constant time.

b. O(n), O(n²), O(log (n)) – again it is based on the length of the input.

For example:

function(list /) {               function(list 2) {

for (node in 1) {              print(I got a list”); }

print(node);

           }

}

In this example, both take O(1) space as we do not create additional objects which shows that time and space complexity might be different.

Q3. What do you understand by time and space trade-off? Define the various asymptotic notations. Derive the O-notation for linear search.

Ans. Time-space trade-off:

1. The time-space trade-off 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.

2. Time-space trade-off is basically a situation where either space efficiency (memory utilization) can be achieved at the cost of time or time efficiency (performance efficiency) can be achieved at the cost of memory.

For Example: Suppose, in a file, if data stored is not compressed, it takes more space but access takes less time. Now if the data stored is compressed the access takes more time because it takes time to run decompression algorithm.

Various asymptotic notation:

1. θ-Notation (Same order)

2. Oh-Notation (Upper bound)

3. Ω-Notation (Lower bound) 

4. Little-Oh notation (o)

5. Little omega notation (ω)

Derivation:

Best case: In the best case, the desired element is present in the first position of the array, i.e., only one comparison is made.

So,                                        T(n) O(1).

Average case: Here we assume that ITEM does appear, and that is equally likely to occur at any position in the array. Accordingly the number of comparisons can be any of the number 1,2, 3,., n and each number occurs with the probability p = 1/n. Then

                    T(n) = 1. (1/n) +2. (1/n) +3.(1/n)… +n .(1/n)

                            = (1+2 + 3+ ……….+ n). (1/n)

                            =n. n + 1/2. (1/n)

                            = (n + 1)/2

                            = O((n + 1)/2) = O(n)

Worst case: Worst case occurs when ITEM is the last element in the array or is not there at all. In this situation n comparison is made

So,                                 T(n) O(n +1) = O(n)

Q4. What do you understand by time-space trade-off? Explain best, worst and average case analysis in this respect with an example.

Ans. Time-space trade-off:

1. The time-space trade-off 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.

2. Time-space trade-off is basically a situation where either space efficiency (memory utilization) can be achieved at the cost of time or time efficiency (performance efficiency) can be achieved at the cost of memory.

For Example: Suppose, in a file, if data stored is not compressed, it takes more space but access takes less time. Now if the data stored is compressed the access takes more time because it takes time to run decompression algorithm.

Best, worst and average case analysis: Suppose we are implementing an algorithm that helps us to search for a record amongst a list of records. We can have the following three cases which relate to the relative success our algorithm can achieve with respect to time:

1. Best case:

a. The record we are trying to search is the first record of the list.

b. If f(n) is the function which gives the running time and/or storage space requirement of the algorithm in terms of the size n of the input data, this particular case of the algorithm will produce a complexity Cn) =1 for our algorithm fn) as the algorithm will run only 1 time until it finds the desired record.

2. Worst case:

a. The record we are trying to search is the last record of the list.

b. If f(n) is the function which gives the running time and/or storage space requirement of the algorithm in terms of the size n of the input data, this particular case of the algorithm will produce a complexity C(n)=n for our algorithm f(n), as the algorithm will run n times until it finds the desired record.

3. Average case:

a. The record we are trying to search can be any record in the list.

b. In this case, we do not know at which position it might be.

c. Hence, we take an average of all the possible times our algorithm may run.

d Hence assuming for n data, we have a probability of finding any one of them is 1/n.

e. Multiplying each of these with the number of times our algorithm might run for finding each of them and then taking a sum of all those multiples, we can obtain the complexity C(n) for our algorithm f(n) in case of an average case as following:

Hence in this way, we can find the complexity of an algorithm for

average case as

                                                    C(n) = O((n + 1/2)

Q5. What are doubly linked lists? Write C program to create doubly linked list.

Ans. Doubly linked list:

1. The doubly or two-way linked list uses double set of pointers, one pointing to the next node and the other pointing to the preceding node.

2. In doubly linked list, all nodes are linked together by multiple links which help in accessing both the successor and predecessor node for any arbitrary node within the list.

3. Every node in the doubly linked list has three fields:

4. LPT will point to the node in the left side (or previous node) i.e., LPT will hold the address of the previous node, RPT will point to the node in the right side (or next node) i.e., RPT will hold the address of the next node.

5. INFO field store the information of the node.

6. A doubly linked list can be shown as follows

  7. The structure defined for doubly linked list is:

struct node

{

                          int info;

                          struct node *rpt;

                          struct node *lpt;

}                         node;

Program:

       #include<stdio.h>

       # include<conio.h>

       # include<alloc.h>

       struct node

          {

        int info;

        struct node *lpt ;

        struct node *rpt;

          } ;

        struct node *first;

        void main ()

        {

        create );

        getch ();

         }

        void create ()

        {

        struct node *ptr, *cpt;

        char ch ;

        ptr = (struct node *) malloc (size of (struct node)) ;

        printf(“Input first node information”);

        scanf (“%d”, & ptr → info);

        ptr → lpt =NULL;

        first = ptr ;

        do

        {

        cpt = (strut node *) malloc (size of (struct node)) ;

        printf(“Input next node information”);

        scanf (“%d”, & cpt-> info);

        ptr → rpt =cpt; 

        cpt → lpt = ptr;

        ptr = cpt;

        printf (“Press <Y/N> for more node”);

        ch = getch () ;

        }

        while (ch == “Y);

        ptr → rpt = NULL;

         }

Q6. Write an algorithm to insert a node at the end in a  circular linked list.

• Ans.
  1. If PTR = NULL
• 2. Write OVERFLOW
• 3. Go to Step 1
• (END OF IFT
• 4. SET NEW_NODE = PTR
• 5. SET PTR = PTR-> NEXT
• 6. SET NEW_NODE -> DATA = VAL
• 7. SET NEW_NODE -> NEXT = HEAD
• 8. SET TEMP = HEAD
• 9 Repeat Step 10 while TEMP-> NEXT = HEADD
• 10. SET TEMP = TEMP-> NEXT
•     [END OF LOOP]
• 11. SET TEMP-> NEXT = NEW_NODE
• 12. EXIT

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