Question 1: Describe a real-world example where a stack data structure would be used. Explain why a stack is suitable for this scenario.

Answer: A common example is a web browser's back button feature. The browser uses a stack to keep track of pages visited; when the user clicks back, the last page visited is retrieved from the top of the stack. This is suitable because stacks follow Last-In-First-Out (LIFO), matching the order in which pages are visited and retraced.

Question 2: Explain the difference between an array and a linked list. Include at least two key differences in your answer.

Answer: An array allocates a fixed size block of memory where elements are stored contiguously, allowing quick access via index. A linked list consists of nodes, each containing data and a reference to the next node, which can be stored anywhere in memory. Key differences include: arrays have fixed size and allow constant-time access, while linked lists are dynamic in size and require traversal to access elements.

Question 3: Complete the truth table for a AND logic gate with two inputs, A and B. Fill in the output column based on standard AND gate behavior.

Answer: A | B | Output ---|---|------- 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1

Question 4: Draw the logic circuit for an OR gate using standard logic gate symbols. Label all parts clearly.

Answer: A correct sketch would show two inputs entering an OR gate symbol (a curved shape with inputs on the left and output on the right). The OR gate symbol is distinct from AND and NOT gates, with a curved input side. Both inputs connect to the gate, which outputs the OR result.

Question 5: What is the main difference between a queue and a stack? Provide an example use case for each.

Answer: A queue follows First-In-First-Out (FIFO), where the first element added is the first to be removed. A stack follows Last-In-First-Out (LIFO). An example of a queue is a line of people waiting for a service; an example of a stack is a pile of plates where the last plate placed on top is removed first.

Question 6: Sketch a simple linked list with four nodes, showing how they are connected. Label each node and the links between them.

Answer: A correct sketch would display four boxes (nodes), each labeled with a data value, connected with arrows pointing from one to the next, illustrating the links. The first node is the head, and the last node points to null, indicating the end of the list.

Question 7: Explain how a boolean AND gate can be used to control access to a secure system. Include what conditions need to be met for access to be granted.

Answer: An AND gate outputs true only when both inputs are true. In a secure system, two conditions (such as correct password and biometric verification) can be inputs to an AND gate. Access is granted only if both conditions are true, ensuring multiple security checks are satisfied.

Question 8: Describe a scenario where a queue data structure would be more appropriate than a stack. Why?

Answer: A queue is more appropriate for managing customer service calls, where the first caller should be served first. This FIFO order ensures fairness, unlike a stack which would serve the most recent caller first, which is unsuitable for this scenario.

Question 9: Draw a simple diagram of a binary tree with three levels. Label the root, left child, right child, and their children.

Answer: A correct diagram would show a top node labeled 'Root', with two branches: one leading to a left child and one to a right child. Each child node may have their own left and right children, forming the second and third levels, respectively.

Question 10: What is a hash table, and how does it improve data retrieval efficiency? Provide a brief explanation.

Answer: A hash table is a data structure that stores data in an array using a hash function to generate an index from the data's key. It allows for very fast data retrieval (average constant time) because the hash function directly maps the key to the data's location, reducing search time compared to other structures like lists.