SY.Bsc.Cs Sem-3 Based on Mumbai Unversity
Data Structures (Uint-1,2,3) Short Answer Question Bank Answer:-
### Unit I
1. **Stack vs. Queue**:
- Stack: Follows Last In First Out (LIFO) principle.
- Queue: Follows First In First Out (FIFO) principle.
- Stack allows insertion and deletion from one end, while queue allows insertion at the rear and deletion from the front.
2. **Array vs. Linked List**:
- Array has fixed size and contiguous memory allocation, while linked list has dynamic size and uses scattered memory allocation.
- Array allows direct access by index, while linked list requires traversal for access.
- Insertions and deletions in an array are costly compared to a linked list.
3. **Types of Expressions Using Stack**:
- Infix: Operators are between operands (e.g., A + B).
- Prefix: Operators precede operands (e.g., +AB).
- Postfix: Operators follow operands (e.g., AB+).
4. **ADT for Stack**:
- Operations: `push(element)`, `pop()`, `peek()`, `isEmpty()`, `isFull()`.
5. **ADT for Queue**:
- Operations: `enqueue(element)`, `dequeue()`, `front()`, `rear()`, `isEmpty()`, `isFull()`.
6. **ADT for Singly Linked List**:
- Operations: `insert(element, position)`, `delete(position)`, `search(element)`, `traverse()`, `isEmpty()`.
### Unit II
1. **Tree Traversal Methods**:
- Preorder: Root → Left → Right
- Inorder: Left → Root → Right
- Postorder: Left → Right → Root
- Level Order: Visit nodes level by level.
2. **Applications of Tree**:
- Hierarchical data structures (e.g., file systems),
- Expression parsing,
- Decision-making structures like binary search trees.
3. **Applications of Priority Queue**:
- Scheduling processes in operating systems,
- Dijkstra’s shortest path algorithm,
- Huffman coding in data compression.
4. **Binary Tree Types**:
- Binary Binary Tree: General binary tree with two children at most.
- Skewed Binary Tree: All nodes have either only left or only right children.
- Strict Binary Tree: Every node has either two children or no children.
5. **ADT for Doubly Linked List**:
- Operations: `insertFront(element)`, `insertRear(element)`, `deleteFront()`, `deleteRear()`, `traverseForward()`, `traverseBackward()`.
6. **ADT for Tree**:
- Operations: `insert(element)`, `delete(element)`, `search(element)`, `preorder()`, `inorder()`, `postorder()`.
### Unit III
1. **Graph Definition**:
A graph is a collection of nodes (vertices) connected by edges. Example: A social network graph where nodes represent people and edges represent connections.
2. **Hashing and Hash Table**:
- Hashing: A technique to map data to fixed-size indexes.
- Hash Table: A data structure that stores key-value pairs using a hash function.
3. **Adjacency Matrix Representation**:
A matrix used to represent a graph where each cell `(i, j)` holds 1 if there’s an edge between vertex `i` and `j`, otherwise 0.
4. **Adjacency List Representation**:
Each vertex has a list of adjacent vertices, reducing space for sparse graphs.
5. **Names of Hash Functions**:
- Division method,
- Multiplication method,
- Mid-square method,
- Folding method.
6. **Collision in Hashing**:
A collision occurs when two keys hash to the same index. Methods to resolve:
- Chaining,
- Open addressing (linear probing, quadratic probing, double hashing).
Comments
Post a Comment