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 ).
Comments
Post a Comment