Data Structures Answers..

Q1. A professor keeps the following list for a class Name,major,student

number,test score,final grade. a)state the entities ,attributes and entity sets of the
list. b) Describe the field value ‘s, records and file. c)which attributes can serve as
primary key

ANS: a) entities in this case are:

1). Student
Attributes: Name
Major
Student
Test score
Final grade
Entity sets: they are collection of entities of same type. In this case:
Entity set:
Students

b). Field Value : a field value is a single data entry for a specific
attribute of an entity.. for example , for the “name” attribute field value
could be “john”, for “Test score” attribute field value could be “70”.
Records: a record is a collection of field values that represent a
single entity. In the context of the list, a record would be collection of
attributes that represent a student, including their name, major,
student number, test score and final grade.

File: a File is a collection of records. In this context, a file would be an

collection of student records, where each record contains attributes
related to student’s information.
c) primary key- it is a unique identifier for each entity in database. In
this case, “student number” could likely serve as primary key. It is a
unique identifier for each student and ensures that each student can be
uniquely identified within the class.

Q2. write algorithm for linear search and show its implementation for the
following array name = { mary, jane, diane, susan, Karen, edith }

ANS. Algorithm written in book..

Q3. Classify data structures according to their types ,explain your answer.

ANS.
Q4. Explain the concept of priority Queue:
ANS.
Q5. Translate the following infix expression to postfix. a) (A+B^D)/(E-F)+G
b) A*(B+D)/E-F*(G+H/K)

ANS. Method given in book..

Q6. What is the key prerequisite applying binary search algorithm on a list of
numbers?

ANS.
The key prerequisite for applying the binary search algorithm on a list of numbers
is that the list must be sorted in ascending (or descending) order. Binary search is
a highly efficient search algorithm that works by repeatedly dividing the search
range in half. For this algorithm to work correctly and efficiently, the list must
meet the following requirement:
Prerequisite: The list must be sorted.
If the list is not sorted, the binary search algorithm may produce incorrect results.
Sorting the list is essential because it allows the algorithm to make informed
decisions about which half of the remaining list might contain the target element,
thereby reducing the search range at each step.

Q7. Discuss whether a queue or stack is appropriate structure for determine

the order in which data are processed for following situation(explain why)
a)contract employees have for promotion on basis of seniority
b) batch processing in operating system
c) recursive functions
ANS.
a). In this scenario, the order in which contract employees are processed for
promotion is based on seniority. Seniority implies "first come, first served". This
behavior aligns well with a queue.
Appropriate Data Structure: Queue
Explanation: A queue is suitable because it follows the principle of processing
items in the order they were added, which aligns with the seniority-based
promotion process.
b). Appropriate Data Structure: Deque
Explanation: A deque (double-ended queue) provides the flexibility to insert and
remove elements from both the front and the back. This is useful in batch
processing, where jobs might have different priorities and need to be inserted
and executed at different positions in the sequence.
c). Appropriate Data Structure: Stack
Explanation: A stack is suitable for recursive functions because it mirrors the call
stack of the program. As each function is called, its state is pushed onto the stack.
When the function completes, its state is popped off the stack, allowing the
program to continue where it left off.

Q8. .explain the terms space and time complexity with suitable example..
ANS.
Space complexity: An algorithm’s space complexity is amount of space required
to solve a problem and produce an output. Similar to Time complexity, Space
complexity is also expressed in Big O notation. For an algorithm , space is required
for following purpose:
1. To store program instructions
2. To store constant values
3. To store variable values
4. To track function calls, jumping statements,etc.

Q9. Explain overflow underflow with respect to 1)array 2)stacks 3)queue 4)linked list
ANS.

1. Array:
• Overflow: An overflow in an array occurs when an attempt is made to
insert more elements into the array than its allocated size can
 accommodate. This can lead to data corruption or unexpected
behavior.
• Underflow: An underflow in an array happens when an attempt is
made to remove an element from an empty array. This can result in
undefined behavior or errors.
2. Stacks:
• Overflow: A stack overflow occurs when an attempt is made to push
an element onto a full stack. This can happen if the stack's capacity is
limited and has been reached.
• Underflow: A stack underflow happens when an attempt is made to
pop an element from an empty stack. This occurs when there are no
elements left in the stack to pop.
3. Queue:
• Overflow: A queue overflow occurs when an attempt is made to
enqueue (add) an element into a full queue. This can occur if the
queue's capacity has been reached.
• Underflow: A queue underflow happens when an attempt is made to
dequeue (remove) an element from an empty queue. This occurs
when there are no elements left in the queue to dequeue.
4. Linked List:
• Overflow: In the context of linked lists, overflow can occur when
memory allocation fails while adding new elements to the list. This
might happen if there is insufficient memory available for the new
node.
• Underflow: A linked list underflow can happen when trying to access
or remove an element from an empty linked list. This occurs when
the list is empty, and there are no nodes to access or remove.
 Q10. Explain the term memory allocation and garbage collection:
ANS.
Memory allocation is the process of reserving a portion of a computer's memory
to store data or program instructions. In programming, memory allocation
involves requesting and assigning memory blocks to store variables, data
structures, or other objects during the execution of a program.
There are two main types of memory allocation:
1. Static Memory Allocation: Memory is allocated at compile-time and
remains fixed throughout the program's execution.
2. Dynamic Memory Allocation: Memory is allocated during runtime, allowing
programs to adapt to changing memory needs.

Garbage collection is the process of automatically identifying and reclaiming

memory that is no longer in use by a program. In languages with automatic
memory management, like Java, C#, and Python, garbage collection helps prevent
memory leaks and reduces the burden on programmers to manually manage
memory deallocation.

Q11. Explain the following algorithms 1)Push pop 2) enqueue and Dequeue 3)
insertion deletion into linked list:
ANS. Algorthims written in book..

Q12. Write an algorithm for binary search. Analyse its worst case complexity
and its limitations:
ANS.
Worst Case Complexity:
The worst-case time complexity of the binary search algorithm is O(log n), where
'n' is the number of elements in the sorted array. This logarithmic complexity
indicates that with each step, the search space is effectively halved, making binary
search efficient for large datasets. Some Limitations of Binary search are:
1. Sorted Data Requirement: Binary search requires the data to be sorted in
ascending or descending order.
2. Duplicate Values: Binary search may not behave as expected when dealing
with duplicate values in the data.
3. Lack of Index Information: Binary search doesn't provide direct access to
element indices during the search.
4. Memory Overhead: Binary search requires additional memory for recursive
calls or iterative variables, which can be a limitation in memory-constrained
environments.

Q13. Write an algorithm for evaluation of postfix expression. Solve the

following – 9, 17 ,5 ,+ , *, 24, 8, /, -
ANS. Algorithm given in book..

Q14. write algorithm for converting infix to postfix and explain with eg
ANS. Algorithm given in book..

Q15. write algorithm for converting evaluating a postfix and expression with
eg:
ANS. Algorithm given in book..
Q16. explain Array representation and one way list representation of Priority
queue:
ANS.
Priority queues are data structures that store elements along with their
associated priorities and allow efficient access to the element with the highest (or
lowest) priority.
a) In the array representation, a priority queue is implemented using an
array. Each element of the array stores both the data and its corresponding
priority. The array is typically organized in a way that maintains the priority
order. It is simple to implement.
b) In the one-way linked list representation, each node of the linked list holds
the data, the priority, and a reference to the next node in the list. The list is
ordered by priority, with the highest priority at the head (or tail, depending
on the implementation). No need for resizing like in the array
representation.

Q17. expalin polish notation ?what are its uses?

ANS.

Basically it is a mathematical notation in which every operator follows all of its

operands. Uses of polish notation are:
Reduced Ambiguity: Polish notation eliminates the need for parentheses in
mathematical expressions.
Stack-Based Evaluation: Polish notation can be efficiently evaluated using a stack-
based approach.
Simpler Parsing and Evaluation: When using Polish notation, parsing and
evaluating mathematical expressions becomes more straightforward for
computers.

Q18. . Explain the algorithm for Quick sort. Discuss working with the help of
example (show each pass).
ANS.

Show passes done in assignment..

Q19. WRITE algorithm for various operation on header list one way list
Q20. Define Data Structure? Discuss its types:
Q21. What are the various operations that can be performed on different Data
Structures?
ANS.
Arrays:
• Access: Retrieve an element by its index.
• Insertion: Add an element at a specific index.
• Deletion: Remove an element from a specific index.
• Search: Find the index of a specific element.
• Update: Modify the value of an element at a specific index.
• Length: Get the number of elements in the array.

Stacks:
• Push: Add an element to the top of the stack.
 • Pop: Remove and return the top element of the stack.
• Peek: Get the top element without removing it.
• IsEmpty: Check if the stack is empty.
• Size: Get the number of elements in the stack.

Queues:
• Enqueue: Add an element to the rear of the queue.
• Dequeue: Remove and return the front element of the queue.
• Peek: Get the front element without removing it.
• IsEmpty: Check if the queue is empty.
• Size: Get the number of elements in the queue.
Q 22. How is an Array different from Linked List?
ANS.

• The size of the arrays is fixed, and Linked Lists are Dynamic in size. ·
• Inserting and deleting a new element in an array of elements is
expensive, Whereas both insertion and deletion can easily be done in
Linked Lists.
• Random access is not allowed on Linked Listed. · Extra memory space
for a pointer is required with each element of the Linked list. · Arrays
have a better cache locality that can make a pretty big difference in
performance.
Q23. Define Stack and where it can be used?
ANS.
The stack data structure is linear data structure that accompanies a principal known
as LIFO(last in first out). Real life examples of stack are deck of cards, piles of books,
piles of money, and many more.
They are used in a variety of applications, including:
Expression Evaluation: Stacks can be used to evaluate arithmetic expressions,
especially those involving parentheses.
Undo/Redo Functionality: Many software applications use stacks to implement
undo and redo functionality.
Memory Management: Stacks are used in memory management systems to
allocate and deallocate memory for function calls and local variables.

Q24. Define Linked List and What are its types?

ANS.

Q25. What does data abstraction mean?

ANS.
Data abstraction is a fundamental concept in computer science and data
structures that refers to the process of simplifying complex systems by breaking
them down into smaller, more manageable components, and hiding the
unnecessary details while exposing the essential features. In the context of data
structures, data abstraction involves defining a set of operations that can be
performed on a data structure while hiding the internal implementation details.

Q26. What do you understand by LIFO,FIFO?

ANS.
LIFO: LIFO stands for "Last-In-First-Out." It's a strategy where the last element
added to a collection is the first one to be removed. Think of it as a stack of items,
where you can only access or remove the topmost item. This principle is often
used in data structures like stacks.
FIFO: FIFO stands for "First-In-First-Out." It's a strategy where the first element
added to a collection is the first one to be removed. It's like a queue where you
join at the back of the line and the person at the front of the line is the first to be
served. This principle is often used in data structures like queues.

Q27. List out the primary advantages of linked list.

Q28. How does the variable declaration affect memory allocation?

ANS.
The declaration of variables in a programming language can have a significant impact
on memory allocation, as it determines how much memory is reserved for a variable
and how that memory is managed. The specifics can vary depending on the
programming language and the type of variable being declared.
Here are some key points to consider:
1. Data Type: The data type of a variable has a direct impact on memory
allocation.
2. Static vs. Dynamic Allocation: Variables can be allocated memory either
statically or dynamically.
3. Scope and Lifetime: The scope and lifetime of a variable can also affect
memory allocation.
4. Garbage Collection: In some programming languages like Java, C#, and
Python, memory management is handled by a garbage collector.

Q30. Define recursion , properties of recursion ,need of recursion ,classify cases of

recursion with example
ANS.
Recursion is a programming and mathematical concept where a function calls
itself to solve a problem or perform a task. In a recursive function, the problem is
divided into smaller, similar subproblems, and each subproblem is solved by
invoking the same function recursively. The recursion process continues until a
base case is reached, at which point the function returns a result without making
further recursive calls.
Recursion is particularly useful for solving problems that can be naturally divided
into smaller, similar subproblems. It simplifies code and makes it more elegant for
certain types of algorithms and data structures. Recursion is commonly used in
scenarios such as tree traversal, searching, sorting, and solving problems with
recursive mathematical structures (e.g., Fibonacci sequence).