WorksheetsMastering Data Structures
Total questions: 20
Worksheet time: 10mins
What is the primary difference between an array and a linked list?
The primary difference is that arrays use contiguous memory for storage, while linked lists use nodes with pointers to connect elements.
Linked lists store elements in a single block of memory, while arrays use multiple blocks.
Arrays can grow dynamically in size, while linked lists have a fixed size.
Arrays allow for faster access to elements than linked lists due to their structure.
How do you insert an element into a stack?
Use the 'pop' operation to insert an element into a stack.
Insert the element at the bottom of the stack.
Replace the top element with the new element.
Use the 'push' operation to insert an element into a stack.
What is a queue and how does it differ from a stack?
A queue is a data structure that only allows insertion at the front.
A queue is a LIFO data structure, while a stack is a FIFO data structure.
A queue allows random access, while a stack does not.
A queue is a FIFO data structure, while a stack is a LIFO data structure.
Explain the concept of a binary tree.
A binary tree is a type of graph where all nodes are connected in a circle.
A binary tree can have an unlimited number of children for each node.
A binary tree is a hierarchical data structure where each node has at most two children.
A binary tree is a linear data structure with nodes arranged in a single line.
What is the time complexity of searching in a hash table?
O(1) average, O(log n) worst case
O(n) average, O(1) worst case
O(log n) average, O(n) worst case
O(1) average, O(n) worst case
Describe the structure of a binary search tree.
A binary search tree allows duplicate values in any node.
A binary search tree is a linear structure where each node can have any number of children.
A binary search tree is a circular structure where nodes are connected in a loop.
A binary search tree is a hierarchical structure where each node has at most two children, with left children having lesser values and right children having greater values than the parent node.
What is a heap and how is it used in priority queues?
A heap is a type of database used for storing large datasets.
A heap is a graphical representation of data used in machine learning.
A heap is a linear data structure used for sorting elements.
A heap is a tree-based data structure used in priority queues to efficiently manage and retrieve elements based on their priority.
How do you traverse a graph using depth-first search?
Start at the end node and work backwards to the start node.
Only traverse the graph in a straight line without backtracking.
Start at a node, mark it as visited, explore adjacent unvisited nodes recursively, and backtrack when necessary.
Visit all nodes in a random order without marking them as visited.
What are the advantages of using linked lists over arrays?
Fixed size allocation
Slower access time for elements
Higher memory overhead for small data sets
Advantages of linked lists over arrays include dynamic size, efficient insertions and deletions, and better memory management.
What is the purpose of a stack in programming?
To store data in a FIFO manner for quick access.
The purpose of a stack in programming is to manage data in a LIFO manner, facilitating function calls and temporary storage.
To manage data in a random access manner.
To permanently save data in the database.
How can you implement a queue using two stacks?
Implement a queue using three stacks for better efficiency.
Use a single stack to store all elements and dequeue directly from it.
Use two stacks: one for input and one for output. Transfer elements from input to output when dequeuing.
Transfer elements from output to input when enqueuing.
What is the difference between a binary tree and a binary search tree?
A binary search tree is a type of binary tree that allows for duplicate values.
Both trees are identical in structure and function.
A binary tree can only have two children, while a binary search tree can have more.
A binary tree has no specific ordering, while a binary search tree has a defined order based on node values.
Explain how to perform an in-order traversal of a binary search tree.
Visit the right subtree first, then the left subtree, and finally the current node.
In-order traversal visits nodes in ascending order: left subtree, current node, right subtree.
Traverse the tree in a random order without following any specific pattern.
Only visit the current node and ignore the subtrees.
What is a hash function and why is it important?
A hash function is a type of encryption used to secure passwords.
A hash function is a programming language used for data analysis.
A hash function is an algorithm that converts input data into a fixed-size hash code, important for data integrity and security.
A hash function is a method for compressing files into smaller sizes.
Describe the process of inserting a node in a binary search tree.
Insert the new node at the root regardless of its value.
Delete the node with the smallest value before inserting the new node.
Insert the new node in the correct position based on its value.
Always insert the new node as a left child.
What are the different types of heaps?
Heap Sort
Max Heap, Min Heap, Binary Heap, Fibonacci Heap, Binomial Heap
Tree Structure
Graph Algorithm
How do you remove the highest priority element from a priority queue?
Call the 'delete' function.
Call the 'dequeue' or 'pop' method.
Use the 'remove' method.
Access the element directly by index.
What is the significance of the 'load factor' in hash tables?
The load factor determines the maximum number of collisions allowed in a hash table.
The load factor measures the speed of data retrieval in a hash table.
The load factor is used to calculate the average size of the data stored in a hash table.
The load factor indicates the efficiency of a hash table and guides resizing to optimize performance.
Explain the breadth-first search algorithm for graphs.
Breadth-first search (BFS) algorithm only explores the deepest nodes first.
Breadth-first search (BFS) algorithm visits all nodes in a single pass without using any data structure.
Breadth-first search (BFS) algorithm explores nodes randomly using a stack.
Breadth-first search (BFS) algorithm explores nodes level by level using a queue.
What are the common applications of trees in computer science?
Network protocols
Data compression algorithms
Image processing techniques
Common applications of trees in computer science include file systems, databases, search algorithms, and hierarchical data representation.
