CC5 Data Structures 2021 PYQ NBU

 

UNIVERSITY OF NORTH BENGAL

B.Sc. Honours 3rd Semester Examination, 2021

CC6 - COMPUTER SCIENCE (31)

DATA STRUCTURES

1. (a) What is the use of dynamic data structures?

Dynamic data structures allow for efficient memory utilization by enabling the allocation and deallocation of memory during program execution. They adapt to the actual size of the data, providing flexibility and avoiding wasted memory.

(b) Are linked lists of linear or non-linear type? Justify.

A linked list is a linear data structure where elements are not stored at contiguous location. Instead, the elements are linked using pointers. In a linked list data is stored in nodes and each node is linked to the next node.

(c) Differentiate a dynamic array from a linked list.

A dynamic array is a resizable array that allocates memory in a contiguous block. In contrast, a linked list is a collection of nodes where each node points to the next one, allowing for dynamic memory allocation. Dynamic arrays have a fixed size, while linked lists can grow or shrink dynamically.

(d) Explain the difference between file structure and storage structure.

File structure refers to the way data is organized within a file, defining records, fields, and their relationships. Storage structure, on the other hand, deals with how data is stored in memory, involving choices like arrays, linked lists, or other data structures to efficiently manage and access data during program execution.

(e) Which data structures are applied when dealing with a recursive function? Why?

Recursion, which is basically a function that calls itself based on a terminating condition, makes use of the stack. Using LIFO, a call to a recursive function saves the return address so that it knows how to return to the calling function after the call terminates.

(f) How does dynamic memory allocation help in managing data?

Dynamic memory allocation allows programs to request and release memory during runtime. This flexibility aids in managing data efficiently by allocating memory as needed, preventing unnecessary consumption and improving overall memory utilization.

(g) What do you understand by data abstraction?

Abstraction is a process that displays only the information needed and hides the unnecessary information. We can say that the main purpose of data abstraction is data hiding.

(h) Is it true that all declaration statements result in a fixed reservation in memory?

No, not all declaration statements result in fixed memory reservation. For example, dynamic memory allocation using pointers in languages like C or C++ allows for memory reservation during runtime, providing flexibility in managing memory based on program requirements.

2. (a) Differentiate linear from a nonlinear data structure.

Linear data structures store elements in a sequential manner, where each element has a unique predecessor and successor. Examples include arrays and linked lists. Nonlinear data structures, such as trees and graphs, have elements with multiple predecessors and successors, forming a more complex structure.

(b) What do you understand by an ADT? Explain with an example.

ADT stands for Abstract Data Type, which is a high-level description of a set of operations that can be performed on a data structure, independent of the specific implementation. It defines what operations can be performed on the data, but not how they are implemented. 

An example of an ADT is a Stack. A stack is a collection of elements with two main operations: push, which adds an element to the top of the stack, and pop, which removes the top element from the stack. The order in which elements are added or removed is last in, first out (LIFO). Here's a simple interface for a stack ADT in Python:

class Stack:

    def __init__(self):

        # Create an empty stack

        pass

    

    def push(self, item):

        # Add an element to the top of the stack

        pass

    

    def pop(self):

        # Remove and return the element from the top of the stack

        pass

    

    def is_empty(self):

        # Check if the stack is empty

        pass

    

    def size(self):

        # Return the number of elements in the stack

        pass (code-box)

In this example, the actual implementation details are not specified. The focus is on the operations that can be performed on the stack (push, pop, is_empty, size). This allows different implementations of a stack (using arrays, linked lists, etc.) while ensuring that users of the stack adhere to the specified interface.

(c) How are linked lists more efficient than arrays?

Linked lists can be more efficient than arrays in certain scenarios. Unlike arrays, linked lists allow dynamic memory allocation, reducing wasted memory. Insertions and deletions are faster in linked lists because elements can be easily added or removed without shifting the entire structure. However, arrays provide faster access to elements through indexing.

(d) Compare and contrast a stack and a queue.

Stack:

• Follows Last In, First Out (LIFO) order.
• Operations: Push (insert), Pop (remove from the top).
• Applications: Function calls, expression evaluation.

Queue:

• Follows First In, First Out (FIFO) order.
• Operations: Enqueue (insert), Dequeue (remove from the front).
• Applications: Task scheduling, breadth-first search.

Both are abstract data types used for managing collections of elements, but they have different access patterns and use cases.

(e) How a complete binary tree is different from a full binary tree? Explain with

suitable example.

Complete Binary Tree:

• Every level is fully filled, except possibly the last level.
• Nodes are filled from left to right.

Example:

      1

     / \

    2   3

   / \  /

  4  5 6 (code-box)

Full Binary Tree:

• Every node has either 0 or 2 children.
• No node has only one child.

Example:

      1

     / \

    2   3

   / \

  4   5 (code-box)

In summary, a complete binary tree focuses on filling levels left to right, while a full binary tree emphasizes the number of children each node can have.

3. (a) A program S read 600 integers in the range [0 .... 100] representing the scores of

600 students. It then prints the frequency of each score above 50. What would be

the best way for S to store the frequency? Explain. Write down an algorithm to

convert a 2D array storage from row major to column major.

(b) Write down an algorithm to insert an item, delete item and display items of a

circular queue.

(c) Explain DFS algorithm for a graph and how does it work?

Depth-first search (DFS) is an algorithm for searching a graph or tree data structure. The algorithm starts at the root (top) node of a tree and goes as far as it can down a given branch (path), then backtracks until it finds an unexplored path, and then explores it. The algorithm does this until the entire graph has been explored.

Working of a Depth-First Search Algorithm:

Step 1: Create a stack with the total number of vertices in a graph.

Step 2: Select any node in a graph as the root note, start traversing through the vertices, and push the stack from one vertex to the other.

Step 3: Push the stack to a non-visited vertex adjacent to the visited one.

Step 4: Repeat the previous step as far as possible until the stack reaches the last vertex. 

Step 5: If there are no vertices left to visit, go back to the stack and pop a vertex from it.

Step 6: Repeat the previous three steps till the stack becomes empty.

(d) Write down an algorithm to convert an infix expression to its postfix equivalent

using stack.

1.  Push “(“ onto STACK, and add “)” to the end of X. 

2.  Scan X from left to right and REPEAT Steps3 to 6 for each element of X UNTIL the STACK is empty. 

3.  If an operand is encountered, add it to Y. 

4.  If a left parenthesis is encountered, push it onto STACK. 

5.  If an operator is encountered, then: 

(a) Repeatedly pop from STACK and add to Y each operator (on the top of STACK) which has the same precedence as or higher precedence than operator. 

(b) Add operator to STACK. 

/* End of If structure */ 

6.  If a right parenthesis is encountered, then: 

(a) Repeatedly pop from STACK and add to Y each operator (on the top of STACK) until a left Parenthesis is encountered. 

(b)  Remove the left parenthesis. (Do not add the left parenthesis to Y). 

/* End of If structure */  

7.  END.

Answers will be updated soon :)