Data Structures - Module 1: Viva Questions & Answers

Q1. What is an abstract data type (ADT)?

A1. ADT is a model that defines data and operations without specifying implementation. Examples: List,

Stack, Queue.

Q2. What are the differences between arrays and linked lists?

A2. Arrays are fixed-size and stored contiguously. Linked lists are dynamic and stored non-contiguously

using pointers.

Q3. How does a singly linked list differ from a doubly linked list?

A3. Singly linked lists have one pointer (next), while doubly linked lists have two pointers (next and prev).

Q4. What is a circular linked list?

A4. In a circular linked list, the last node links back to the first node, forming a circle.

Q5. Define stack and mention its operations.

A5. Stack is a LIFO structure. Basic operations: push, pop, and peek.

Q6. How can a stack be implemented?

A6. A stack can be implemented using arrays or linked lists.

Q7. What is a queue and its applications?

A7. Queue is a FIFO structure used in scheduling, buffering, and resource sharing.

Q8. What are the types of queues?

A8. Simple queue, circular queue, priority queue, and double-ended queue (deque).
 Data Structures - Module 1: Viva Questions & Answers

Q9. How are sets represented using bit strings?

A9. Each bit represents the presence (1) or absence (0) of an element in the universal set.

Q10. What are the operations supported on bit string sets?

A10. Union, intersection, difference, and membership tests using bitwise operations.

Q11. What is hashing?

A11. Hashing is a technique to map data to fixed-size indices in a table using hash functions.

Q12. Name two simple hash functions.

A12. Division method (key % table_size) and mid-square method.

Q13. What is a collision in hashing?

A13. A collision occurs when two keys hash to the same index.

Q14. Explain linear probing as a collision resolution method.

A14. Linear probing checks the next index sequentially until an empty slot is found.

Q15. What is double hashing?

A15. Double hashing uses a second hash function to calculate the probe step during collision resolution.

Q16. What is amortized analysis?

A16. It averages the cost of operations over a sequence, ensuring low average time per operation.

Q17. What are the three methods of amortized analysis?

 Data Structures - Module 1: Viva Questions & Answers

A17. Aggregate, accounting, and potential methods.

Q18. Explain aggregate method with multipop stack.

A18. If n operations are done, total time is O(n), hence amortized cost is O(1) per operation.

Q19. Describe accounting method using incrementing binary counter.

A19. Assign extra cost to cheap operations to pay for expensive ones, ensuring consistent amortized cost.

Q20. What is the idea behind potential method?

A20. It maintains a potential function representing stored energy that can be used for future operations.

Q21. What is a disjoint set?

A21. A collection of non-overlapping sets with operations like Find and Union.

Q22. How is Find operation implemented in disjoint sets?

A22. It returns the representative (root) of the set containing the element, possibly with path compression.

Q23. What is path compression in disjoint sets?

A23. It flattens the tree structure during Find to make future operations faster.

Q24. What is union by rank?

A24. When merging sets, the tree with smaller rank (height) is attached under the root of the tree with larger

rank.

Q25. What is the time complexity of union-find with optimizations?

 Data Structures - Module 1: Viva Questions & Answers

A25. Nearly constant time O((n)), where is the inverse Ackermann function.
 Data Structures - Advanced Tree Structures: Q&A

Q1. What is a Balanced Binary Search Tree?

A1. A Balanced BST is a binary search tree where the height of the two subtrees of any node differ by at

most one, ensuring operations like insertion, deletion, and search are performed in O(log n) time.

Q2. Why is balancing important in binary search trees?

A2. Balancing maintains O(log n) time complexity for operations. Without balancing, the tree can become

skewed, leading to O(n) operations.

Q3. Name some types of balanced BSTs.

A3. AVL Tree, Red-Black Tree, Splay Tree, and B-Trees are common types of balanced BSTs.

Q4. What is the time complexity for insertion and deletion in a balanced BST?

A4. O(log n)

Q5. How is height balancing achieved in AVL trees?

A5. By maintaining a balance factor for each node and performing rotations during insertion/deletion when

balance is disturbed.

Q6. What is the balance factor in AVL trees?

A6. The balance factor is the difference between the height of the left and right subtrees. Valid values are -1,

0, or +1.

Q7. Compare AVL trees and Red-Black trees in terms of balancing.

A7. AVL trees are more strictly balanced than Red-Black trees, offering faster lookups but slower

insertions/deletions due to more frequent rotations.

Q8. What is the worst-case height of a balanced binary search tree with n nodes?

A8. O(log n)

Q9. Give an application where a balanced BST is used.

A9. Balanced BSTs are used in databases and memory management systems for efficient searching and

sorting.

Q10. In what case does a BST degenerate into a linked list?

Page 1
 Data Structures - Advanced Tree Structures: Q&A

A10. When nodes are inserted in sorted order without any balancing mechanism.

Q11. What is a Red-Black Tree?

A11. A Red-Black Tree is a self-balancing binary search tree with an extra bit for denoting the color of each

node (red or black).

Q12. List the properties of Red-Black Trees.

A12. 1. Each node is either red or black.

2. The root is always black.

3. Red nodes cannot have red children.

4. Every path from a node to its descendant NIL nodes has the same number of black nodes.

5. NIL leaves are considered black.

Q13. What is the maximum height of a Red-Black Tree with n nodes?

A13. 2 * log(n + 1)

Q14. Why are Red-Black Trees preferred in some applications?

A14. They offer a good balance between fast insertions/deletions and reasonably balanced trees with

guaranteed O(log n) operations.

Q15. What are the types of rotations in Red-Black Trees?

A15. Left Rotation and Right Rotation.

Q16. When is rotation used in Red-Black Trees?

A16. Rotations are used during insertion and deletion to maintain the trees properties and rebalance it.

Q17. Describe the insertion process in a Red-Black Tree.

A17. Insert the node like a BST node, color it red, and then fix violations using rotations and color changes.

Q18. What happens if a red node has a red child after insertion?

A18. It violates the Red-Black property and must be corrected using rotations and color flips.

Q19. Describe deletion in a Red-Black Tree.

A19. After deletion, the tree might lose black-height balance, which is fixed through recoloring and rotations.

Page 2
 Data Structures - Advanced Tree Structures: Q&A

Q20. What is the black height of a node?

A20. The number of black nodes on the path from the node to a leaf (excluding the node itself).

Q21. What is a B-Tree?

A21. A B-Tree is a self-balancing search tree used for storing data on disk that maintains sorted data and

allows searches, sequential access, insertions, and deletions in logarithmic time.

Q22. What is the degree of a B-Tree?

A22. The minimum degree (t) of a B-Tree defines the minimum and maximum number of keys a node can

have:

- Minimum: t - 1

- Maximum: 2t - 1

Q23. What is the time complexity of insertion and deletion in B-Trees?

A23. O(log n)

Q24. Describe the insertion process in a B-Tree.

A24. Find the correct leaf node, insert the key; if the node overflows, split it and promote the median key to

the parent.

Q25. What is the primary application of B-Trees?

A25. Used in databases and file systems where large blocks of data are read/written to disk.

Q26. What is a Splay Tree?

A26. A self-adjusting binary search tree where recently accessed elements are moved to the root using

rotations.

Q27. What is the main benefit of Splay Trees?

A27. Frequently accessed elements are quicker to access again, improving performance over time.

Q28. What are the splaying operations?

A28. Zig, Zig-Zig, and Zig-Zag rotations performed to bring a node to the root.

Q29. What is a Suffix Tree?

Page 3
 Data Structures - Advanced Tree Structures: Q&A

A29. A compressed trie containing all suffixes of a given text used in fast string matching and pattern

searching.

Q30. What is the time complexity of constructing a Suffix Tree?

A30. O(n), where n is the length of the string.

Page 4
 Data Structure (Module 3) Viva Questions

1. What is the time complexity of merging two binary heaps ?

Ans : O(n)
2. Which of the following data structures is best suited for mergeable heaps ?
Ans : Binomial Heap
3. Which operation is usually the most time-consuming in mergeable heaps ?
Ans : Extract-Min
4. A mergeable heap is typically implemented using which of the following ?
Ans : Binomial or Fibonacci Heap
5. A Binomial Heap is made up of ?
Ans : Binomial Trees
6. What is the height of a binomial tree with degree k ?
Ans : k
7. How many binomial trees are there in a binomial heap with n nodes ?
Ans : log n
8. What is the worst-case time complexity of inserting a node in a binomial heap?
Ans : O(log n)
9. The degree of each node in a binomial heap is ?
Ans : Based on its number of children
[Link] time complexity of find-min in a binomial heap is:
Ans : O(log n)
[Link] many nodes are there in a binomial tree of degree k?
Ans : 2^k
[Link] is the structure of a binomial tree of degree 0?
Ans : A single node
[Link] is the merge operation in a binomial heap performed?
Ans : By linking binomial trees of the same degree, similar to binary addition.
[Link] is the space complexity of storing n elements in a Fibonacci heap ?

Ans : O(n)

[Link] data structure is commonly used to store the roots of the binomial trees in a
binomial heap ?

Ans : A linked list.

[Link] is the time complexity of storing n elements in a Fibonacci heap ?

Ans : O(n)

[Link] operation in a binomial heap involves finding the minimum root and merging
the remaining trees?

Ans : Extract-Min.

[Link] types of problems benefit from using mergeable heaps?

Ans : Graph problems like Dijkstra’s and Prim’s algorithm, or any problem requiring
efficient merging of heaps.
[Link] the difference between mergeable heaps and standard heaps in terms of
flexibility ?
Ans : Mergeable heaps support combining heaps efficiently; standard heaps do not.

[Link] are Fibonacci heaps not widely used in practice?

Ans : They are complex to implement and have high constant overheads.

[Link] is the purpose of marked nodes in Fibonacci heap?

Ans : To track nodes that have lost one child and may trigger cascading cuts.

[Link] is a cascading cut in Fibonacci heaps?

Ans : A chain of cuts triggered when marked nodes lose additional children.

[Link] many binomial trees can a heap with n elements have?

Ans : At most log₂(n) trees.

[Link] is a binomial heap?

Ans : A collection of binomial trees that satisfy the heap and binomial tree properties.

[Link] is a mergeable heap?

Ans : A heap that supports efficient merging of two heaps while maintaining the heap
property.

Adithyan P
23C021
 Data Structures - Advanced Graph Structures: Q&A

Q1. What are the different ways to represent a graph in memory?

A1. Graphs can be represented using:

- Adjacency Matrix

- Adjacency List

- Incidence Matrix

Q2. What is the difference between Depth First Search (DFS) and Breadth First Search (BFS)?

A2. DFS explores as far as possible along each branch before backtracking.

BFS explores all neighbors at the current depth before moving to the next level.

Q3. What are the applications of BFS and DFS?

A3. BFS: Shortest path in unweighted graphs, peer-to-peer networks.

DFS: Topological sorting, cycle detection, solving puzzles.

Q4. What is Topological Sorting?

A4. A linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v,

vertex u comes before v.

Q5. Can topological sorting be applied to undirected graphs?

A5. No, topological sorting is only applicable to Directed Acyclic Graphs (DAGs).

Q6. What are Strongly Connected Components (SCC)?

A6. In a directed graph, a strongly connected component is a maximal group of vertices such that each vertex

is reachable from every other vertex in the same group.

 Data Structures - Advanced Graph Structures: Q&A

Q7. How can we find Strongly Connected Components?

A7. Using algorithms like Kosaraju's or Tarjan's algorithm.

Q8. What is a Biconnected Component?

A8. In an undirected graph, a biconnected component is a maximal subgraph such that the removal of any

single vertex does not disconnect it.

Q9. What is a Minimum Cost Spanning Tree (MST)?

A9. A spanning tree of a connected, weighted graph that has the smallest possible total edge weight.

Q10. How does Prim's Algorithm work?

A10. Starts with a single vertex and grows the MST by adding the minimum weight edge from the tree to a

vertex outside it.

Q11. What is the time complexity of Prim's Algorithm?

A11. With Priority Queue (Binary Heap): O(E log V)

With Adjacency Matrix: O(V)

Q12. How does Kruskal's Algorithm work?

A12. Sorts all edges in increasing order of weight and adds them to the MST if they don't form a cycle (uses

Union-Find).

Q13. What is the time complexity of Kruskal's Algorithm?

A13. O(E log E), due to sorting of edges.

 Data Structures - Advanced Graph Structures: Q&A

Q14. When should we prefer Kruskal's over Prim's Algorithm?

A14. Kruskal's is preferred when the graph has fewer edges (sparse graphs), while Prim's is better for dense

graphs.

Q15. What is Dijkstra's Algorithm used for?

A15. It finds the shortest paths from a single source to all other vertices in a graph with non-negative edge

weights.

Q16. How does Dijkstra's Algorithm work?

A16. It maintains a set of visited nodes and updates the shortest distance to each unvisited node using a

priority queue.

Q17. What is the time complexity of Dijkstra's Algorithm?

A17. With Priority Queue (Binary Heap): O((V + E) log V)

With Adjacency Matrix: O(V)

Q18. Can Dijkstra's Algorithm handle negative edge weights?

A18. No, it may produce incorrect results if the graph contains negative edge weights.

Q19. What algorithm can be used instead of Dijkstra's for graphs with negative weights?

A19. Bellman-Ford Algorithm can be used, which works even with negative edge weights.

Q20. What is the key difference between Prim's and Dijkstra's Algorithms?

A20. Prim's: Finds Minimum Spanning Tree (no specific source).

 Advanced Data Structures Module 5 (Blockchain)

Q1. What is blockchain architecture?

A1. Blockchain architecture is a structured design that defines how blockchain components like nodes, data,

consensus, and contracts interact in a decentralized system.

Q2. What are the two common models of blockchain architecture?

A2. The five-layer architecture model and the three-layer architecture model.

Q3. What are the five layers in the layered blockchain architecture?

A3. Application Layer, Consensus Layer, Network Layer, Data Layer, and Infrastructure Layer.

Q4. What is the role of the Application Layer in blockchain?

A4. It interfaces with users and includes smart contracts, user interfaces, and decentralized applications

(DApps).

Q5. What does the Consensus Layer do in blockchain?

A5. It ensures agreement among network nodes by validating transactions using consensus algorithms like

Proof of Work.

Q6. What is the function of the Network (P2P) Layer?

A6. It handles data transmission and communication between blockchain nodes.

Q7. What is stored in the Data Layer of a blockchain?

A7. All blockchain data including transaction records, block headers, and metadata.

Q8. What is the purpose of the Infrastructure Layer?

A8. It provides the hardware and system resources required to operate the blockchain.

Q9. What are the layers in the three-tier blockchain architecture?

A9. Transaction Layer, Contract Layer, and Application Layer.

Q10. What is the focus of the Transaction Layer?

A10. It handles transaction data and ensures immutability and uniqueness of transactions.
Q11. What is the Contract Layer in blockchain used for?

A11. It enables the deployment and execution of smart contracts with programmable logic.

Q12. What is the purpose of the Application Layer in the three-tier model?

A12. It supports decentralized applications and integrates blockchain with real-world use cases like

governance and identity.

Q13. What is a block in the blockchain?

A13. A block is a data unit containing a list of transactions and a block header with metadata like hash and

Merkle root.

Q14. What is a Merkle Tree used for in blockchain?

A14. To efficiently verify the integrity of transactions using hierarchical hashing.

Q15. What is the function of a Merkle Root?

A15. It provides a single hash that represents all transactions in a block, ensuring data consistency.

Q16. What is a hash pointer in blockchain?

A16. It links each block to its predecessor by storing the previous block's hash, ensuring tamper-resistance.

Q17. What is the structure of a transaction in blockchain?

A17. It includes transaction inputs, outputs, timestamps, digital signatures, and addresses.

Q18. What are the two main data models in blockchain?

A18. Transaction-based model and Account-based model.

Q19. What is the transaction-based model in blockchain?

A19. It tracks inputs and outputs linked to previous transactions, commonly used in Bitcoin.

Q20. What is the account-based model in blockchain?

A20. It tracks balances and states for each user account, commonly used in Ethereum.

Q21. What is a smart contract?

A21. A digital protocol that automatically executes rules and logic when specific conditions are met on the

blockchain.
Q22. What are the stages in the lifecycle of a smart contract?

A22. Contract generation, contract publication, and contract execution.

Q23. What is entity identification in blockchain data analysis?

A23. It refers to identifying users or organizations behind blockchain addresses using heuristics and

transaction patterns.

Q24. What is transaction pattern recognition?

A24. Analyzing transaction flows to detect trends, behaviors, or suspicious activities like money laundering.

Q25. What are some problems to be solved in blockchain data analysis?

A25. Entity identification, privacy risks, transaction visualization, illegal activity detection, and market effect

analysis.