Data Structures Chapter 2 Exercise Solutions

Short forms used DS -> Data structure

1. Explain the features of a good program.

A good program is one that has the following points covered
1. Runs Correctly
2. Easy to read and undersand 
3. is easy to modify

A good program that runs correctly but runs efficiently, that's important. So a program that takes less time to execute and occupies minimum storage space is a good program. And also meets other points mentioned above.

2. Define the terms: data, file, record, and primary key. 

Data : The term data means values or data sets 

Record : It is a collection of data items like name, address, phone number, etc..

File : File is a collection of related records. File may be of school students attendance records, or marks records etc

Primary Key : In a record that contains data items like name , id , phone number, age , etc.. , A primary key is the id field which is unique for each data item and cannot repeat , therefore using this as a key will serve identification of records, searching, sorting, etc... 

3. Define data structures. Give some examples.

Data structures are organised way of storing data, organising data.
Data structures is basically way of organising data, storing data, data management framework. It is group of data elements under one name.
They are everywhere ranging from 
Compiler design
Statistics
OS
AI
Examples of Data Structures include Stacks, Queues, Arrays, Linked List, Trees, Graphs, etc.. 

4. In how many ways can you categorise data structures? Explain each of them.

Data Structures are mainly classified into two categories 
1. Primitive Data Structures 
2. Non Primitive Data Structures

1. Primitive Data Structures
Data Structures like integers, characters, real, boolean are primitive data structures as they are not derived from any other data structure and also they fundamental in nature.
2. Non Primitive Data Structures
Data Structures like Stacks, queues, linked list, trees comes under this category because they are derived from primitive or basic data types. Further Non primitive data structures can be classified into linear and non linear data types

Linear Data Structures are those which store data elements in a linear order or sequential order. Examples are Arrays, linked list, queues, stacks.

Non Linear Data Structures are those which store data elements in a random non linear order, hence the name. 

5. Discuss the applications of data structures.

The Applications of data structures include OS Level memory operations, compiler design, Statistics, Number analysis, Programming language memory implementation, Databases used in websites, etc.

6. Write a short note on different operations that can be performed on data structures.

Operations that can performed on Data Structures are Insertion, Deletion, Sorting, Searching, Traversing, etc.. 

7. Compare a linked list with an array.

Array is a linear data structure in which data elements are stored in linear fashion with each data element is stored next to each other, subsequent manner. 
Linked List is also a linear data structure but each data element contains data item value, and a pointer that points to next block of linked list.

Arrays are static data storage systems whereas linked list is very flexible, dynamic data type which can store different data types in one linked list.

In arrays, only values are stored in each node whereas linked list stores two data items in a node i.e values and pointer 

In Arrays, insertion and deletion is very difficult and time consuming whereas in linked list, these operations are very fast and easy.

8. Write a short note on abstract data type.

ADT short for Abstract data type, its a type in which only what data type are there is written and implementation of it is ignored i,e how it works is not considered.
Stacks , queues are best examples of ADT. They show the user the strucute of database but does not care about the working of it 

The word Abstract in ADT means here in context of data strcuture is that considered apart from detailed implementation or specificaiton.

The word data type tells what type of data a variable can hold. ex int , char , etc..

The advantage of ADT is that it keeps the complexity of code aside and focuses on the overview of database, so that debugging, modificaiton to database gets a lot easier 

9. Explain the different types of data structures. Also discuss their merits and demerits

different types of DS include Arrays, stacks, queues, linked list, trees, graphs , hash tables, ADT ,etc..

Arrays -> Arrays are types of DS which has fixed size blocks of elements stored in linear way. They contain similiar data elements only. Arrays can be of integers, characters, real, boolean. This DS has limitations and drawbacks
Limitations : It is of fixed size, cannot be changed later during execution. Dynamic memory allocation is not there. programmeres has to face this issue of predeciding the size. 
2. It can only contain data elements of similiar data type, int array can store only integer data elements . 
3. Insertion and deletion of elements can be complex as it involves shifting of elements periodically.

Linked List ( LL )

Linked list solves the disadvantages of arrays by having Dynamic memory option, no fixed size, insertion and deletion of elements is easy and fast, its totally different from arrays as it has two data items in a node , 1. value of data 2. Pointer to next node . 

LL Helps programmers write robust programs 
Disadvantage : Slow search operation is observed because compiler has to traverse each node one by one until it gets the desired node. 

Stacks 

Stacks are the ADT of arrays, Linked list meaning They represent data , but hides the internal working of various things. Stacks are excellent when data management, debugging, development of database is concerned. Here LIFO Last In First Out concept is used. Stacks are linear DS. It supports three basic operations, push , pop, peep.

In this, top variable is there for pointing the position for push, pop operation. if top = NULL , stack is empty. If top = MAX - 1 , Stack is full

Disadvantage : Fixed size stack 
To extract first element in stack, takes too much time because it will be the last element in the stack 

Queues

A queue is FIFO First in first out linear DS in which element is inserted first is first to be removed. Front and rear variable is there to indicate the starting and ending of queue from which insert, delete operations can be performed. if rear = MAX - 1 , queue is full. if rear = 0, front = 0 , queue is empty.

Advantages : Due to FIFO , Elements that got first in , gets first out saves time as comparted to stack.

Trees 

Trees are Non Linear DS collection of nodes arranged in hierarichal order. there is a root node and if root node = NULL , Tree is empty. The simplest form of tree is binary tree where there is left sub tree and right sub tree. Each node contains a data value element , pointer to left sub tree and pointer to right sub tree.

Disadvandatge : Very complex 

Graphs 

Graphs are same like Trees except they dont have any root node. They have edges and vertices. edges represents conneciton between nodes and vertices are nodes itself. 

Advantage : real world modelling 

Disadvantage : Very slow and complex

10. Define an algorithm. Explain its features with the help of suitable examples.

Algorithm is a sequence of instructions for a computer program to solve a problem. It is considered a blueprint of a program to solve a computer problem.

The choice of selection of an algorithm depends upon space and time complexity.

11. Explain and compare the approaches for designing an algorithm.

Top down approach 

Bottom up Approach

A complex algorithm is often divided into modules. The process of diving algorithm into modules is modularization.

Advantages of modularization 

Easy to design, implement
Each module can be designed independently.

Top down approach 
the complex algorithm is divided into modules
The modules are further sub divided into sub modules 
this process is repeated until desired level of complexity is achieved.
Therefore in this approach, step wise refinement is done until simplicity is met.

Bottom up approach

In this approach, the very basic modules are built and developed first.

next, this basic modules are further integrated into higher level modules.

Next, this grouping takes place until the complete algorithm is obtained.

therefore, this approach is quite different in nature.

12. What is modularization? Give its advantages.

ANswered in quesiton 11

13. Write a brief note on trees as a data structure.

14. What do you understand by a graph?

Answered above 

MCQs

1. Which data structure is defined as a collection of

similar data elements?

(a) Arrays

(b) Linked lists

(c) Trees

(d) Graphs

Arrays 

2. The data structure used in hierarchical data model

is

(a) Array

(b) Linked list

(c) Tree

(d) Graph

Graph

3. In a stack, insertion is done at

(a) Top

(b) Front

(c) Rear

(d) Mid

TOP

4. The position in a queue from which an element is

deleted is called as

(a) Top

(b) Front

(c) Rear

(d) Mid

Front 

5. Which data structure has fixed size?

(a) Arrays

(b) Linked lists

(c) Trees

(d) Graphs

Arrays 

6. If TOP = MAX–1 , then that the stack is

(a) Empty

(b) Full

(c) Contains some data (d) None of these

FULL

7. Which among the following is a LIFO data

structure?

(a) Stacks

(b) Linked lists

(c) Queues

(d) Graphs

Stacks

8. Which data structure is used to represent complex

relationships between the nodes?

(a) Arrays

(b) Linked lists

(c) Trees

(d) Graphs

Graphs

9. Examples of linear data structures include

(a) Arrays

(b) Stacks

(c) Queues

(d) All of these

All of these 

10. The running time complexity of a linear time

algorithm is given as

(a) O(1)

(b) O(n)

(c) O(n log n)

(d) O(n 2 )

O ( n) 

11. Which notation provides a strict upper bound for

f( n )?

(a) Omega notation

(b) Big O notation

(c) Small o notation (d) Theta Notation

i dont know 

12. Which notation comprises a set of all functions

h(n) that are greater than or equal to cg(n) for all

values of n ≥ n 0 ?

(a) Omega notation

(b) Big O notation

(c) Small o notation (d) Theta Notation

13. Function in o (n 2 ) notation is

(a) 10 n 2

(b) n 1.9

2

(c) n /100

(d) n 2

TRUE OR FALSE 

1. Trees and graphs are the examples of linear data

structures.

FALSe - > they are Non linear DS

2. Queue is a FIFO data structure.

TRUE 

3. Trees can represent any kind of complex

relationship between the nodes.

False , Graphs do 

4. The average-case running time of an algorithm is

an upper bound on the running time for any input.

False , best case is 

5. Array is an abstract data type.

NO

6. Array elements are stored in continuous memory

locations.

TRUE

7. The pop operation adds an element to the top of

a stack.

FALSE, pop operation removes the topmost element

8. Graphs have a purely parent-to-child relationship

between their nodes.

FALSE, In trees it exists

9. The worst-case running time of an algorithm is a

lower bound on the running time for any input.

TRUE

10. In top-down approach, we start with designing

the most basic or concrete modules and

then proceed towards designing higher-level

modules.

FALSE, its the bottom-up approach 

11. o(g(n)) comprises a set of all functions h(n) that

are less than or equal to cg(n) for all values of

n ≥ n 0 .

Cant answer

12. Simply Ω means same as best case Ω.

13. Small omega notation provides an asymptotically

tight bound for f( n ).

14. Theta notation provides a non-asymptotically

tight lower bound for f(n).

15. n 3.001 ≠ ω( n 3 ).

1. DS is an arrangement of data either in the

computer’s memory or on the disk storage.

2. Insertion, deletion operation are used to manipulate the data contained

in various data structures.

3. In Linear DS, the elements of a data structure are

stored sequentially.

4. DAta type  of a variable specifies the set of values

that the variable can take.

5. A tree is empty if root = NULL.

6. Abstract means Overview.

7. The time complexity of an algorithm is the running

time given as a function of O (n ) .

8. Worst case analysis guarantees the average perfor-

mance of each operation in the worst case.

9. The elements of an array are referenced by an

index.

10. top is used to store the address of the topmost

element of a stack.

11. The pop operation returns the value of the

topmost element of a stack.

12. An overflow occurs when top > MAX - 1.

13. queue is a FIFO data structure.

14. The elements in a queue are added at rear and

removed from Front.

15. If the elements of a data structure are stored

sequentially, then it is a Linear DS.

16. Algorithms is basically a set of instructions that solve

a problem.

17. The number of machine instructions that a pro-

gram executes during its execution is called its

throughput of machine.

18. Average case specifies the expected behaviour of an

algorithm when an input is randomly drawn from

a given distribution.

19. The running time complexity of a constant time

algorithm is given as ______.

20. A complex algorithm is often divided into smaller

units called Modules.

21. Top down design approach starts by dividing the

complex algorithm into one or more modules.

22. Worst case is when the array is sorted in reverse

order.

23. ________ notation provides a tight lower bound

for f(n) .

24. The small o notation provides a _________ tight

upper bound for f(n) .

25. 540 n 2 + 10 ____ Ω ( n 2 ).