Data Structures Exam Review – Computer Science 2025 – Comprehensive Q&A Guide for Java, Algorithms, and Complexity Analysis

  BLANK PAGE   "When creating a new array in Java to store objects, why are the array's initial values set to 'null'? - CORRECT ANSWER Because 'null' represents an uninitialized reference, indicating that the array slots do not yet point to any actual object." "Given the following Java code: int num = 10; double dblNum = num; Which type of casting is being demonstrated? - CORRECT ANSWER Widening casting" "How can you ensure that an array of objects of a user-defined class is properly initialized in Java? - CORRECT ANSWER Loop over all the objects in the array and instantiate each one." "In a dynamic collection based on arrays in Java, if the internal array reaches its maximum capacity and a new element is added, what is a common strategy to accommodate the new element? - CORRECT ANSWER Create a new, larger array and copy the elements from the old array to the new one." "In a doubly linked list, by adding a 'previous' reference, how does the memory requirement change? - CORRECT ANSWER It increases by about 33%" "Which of the following statements about Java objects is true? - CORRECT ANSWER Each object in Java is a reference to a location in memory." "In Java, how can you make the linked list class generic? - CORRECT ANSWER By using angle brackets " "You have an operation that requires constant-time complexity for both adding an element at the end and accessing an element by index. Which data structure would be more appropriate? - CORRECT ANSWER ArrayList." "In a doubly linked list, each node has: - CORRECT ANSWER Two references: one to the next node and one to the previous node." "Which of the following is a DISADVANTAGE of using recursion? - CORRECT ANSWER Recursive code can pose debugging and tracing challenges." "Why are base cases vital in recursive functions? - CORRECT ANSWER They ensure that the recursive function does not call itself endlessly and terminates." "boolean prime(int x, int y) { if (y == 1) { return true; } else if (x % y == 0) { return false; } else { return prime(x, y-1); } } What result does the prime function return when a number X is not a prime number? - CORRECT ANSWER It returns false." "Consider a recursive function that calculates the nth Fibonacci number. How many recursive cases does this function generally have? - CORRECT ANSWER 2" "A software engineer is deciding between using a recursive or iterative solution for a problem. The problem is guaranteed to have a large input size but has a naturally recursive pattern. What is a genuine concern the engineer should have regarding the recursive approach? - CORRECT ANSWER For large input sizes, the recursive solution might risk a stack overflow due to the deep recursion levels." "int paths(int n) { if (n == 1) { return 1; } if (n == 2) { return 2; } if (n == 3) { return 4; } return paths(n - 1) + paths(n - 2) + paths(n - 3); } Assume the rules of the game change, allowing for a 4-point play. Modify the paths function to accommodate this new rule. What is the new recursive relation, and how does this change affect the number of scoring combinations for n = 5? - CORRECT ANSWER The modified recursive relation would be return paths(n - 1) + paths(n - 2) + paths(n - 3) + paths(n - 4);. For n = 5, the number of scoring combinations would be the sum of combinations for n = 4, n = 3, n = 2, and n = 1, which results in 1 (for n=4, using the previous pattern before the rule change) + 4 + 2 + 1 = 8 scoring combinations." "Considering a recursive function that generates all permutations of a string, which structure does it most likely follow? - CORRECT ANSWER Single base case (when the string length is 1 or 0) and multiple recursive calls for each character in the string." "Considering Bubble Sort's mechanism of "bubbling up" the largest unsorted element during each pass, what can be inferred about the position of the Unknown node type: brUnknown node type: brnth largest element after Unknown node type: brUnknown node type: brn passes? - CORRECT ANSWER It will be in its correct final position." "As sorting algorithms are developed for incrementally larger arrays, what pattern becomes evident? - CORRECT ANSWER For every array size, the largest number is ensured to be at the end, followed by applying the same sorting logic to the remaining elements." "In the absence of efficient sorting, which of the following challenges is most likely to arise in a software application? - CORRECT ANSWER Slower retrieval and processing of data." "How does the generalized Bubble Sort algorithm handle an array of any size? - CORRECT ANSWER It repeatedly ensures the largest number ends up at the end and then applies the same process to the remaining elements." "After the first iteration of the Insertion Sort algorithm, what will be the order of the following array: [15, 10, 12, 14, 11]? - CORRECT ANSWER [10, 15, 12, 14, 11]" "Given the array [20, 18, 22, 19, 21] and the Selection Sort process has already sorted the smallest two numbers to the beginning, what will the array look like after the third smallest number is sorted? - CORRECT ANSWER [18, 19, 20, 22, 21]" "Which of the following series of operations correctly represents the Insertion Sort algorithm for the array [10, 9, 8, 11]? - CORRECT ANSWER Compare 10 and 9, swap them. Compare 9 and 8, swap them. Compare 10 and 11, no swap. Compare 10 and 8, swap them." "Consider the Selection Sort algorithm applied to the array [6, 3, 7, 5, 2]. Here are the steps: [2, 3, 7, 5, 6] [2, 3, 5, 7, 6] [2, 3, 5, 6, 7] [2, 3, 5, 6, 7] Which step is incorrect based on the Selection Sort algorithm? - CORRECT ANSWER Step 3" "Given the array [6, 3, 10, 8, 7, 5] where the first three numbers are already sorted using Selection Sort, which of the following pairs of numbers will be swapped next? - CORRECT ANSWER 8 and 5" "In a linear search algorithm, how does it determine the location of a target element in a list? - CORRECT ANSWER It starts at the beginning of the list and checks each element sequentially until it finds a match." "Consider a list where all elements are identical. If you're using linear search to find a target that matches the elements, which of the following is true? - CORRECT ANSWER The search will always result in a worst-case scenario." "How many iterations will it take for the linear search algorithm to determine that the number 8 is not present in the list [2, 4, 6, 10, 12]? - CORRECT ANSWER 5" "Which of the following best describes a fixed or static collection? - CORRECT ANSWER A collection whose number of variables is constant and the size remains consistent." "In the context of program performance, why is sequential memory access preferable to random memory access? - CORRECT ANSWER Sequential memory access allows the system to leverage cache lines, leading to fewer cache misses and improved program performance." "If a programmer chooses to pad each element in a dynamic collection with a fixed number of bits, what must remain consistent to locate the next piece of data effectively? - CORRECT ANSWER The padding size must remain consistent." "In what scenario might a fixed collection lead to wasted memory? - CORRECT ANSWER When the collection has a predetermined size, but not all of its allocated memory is used." "Why can random access to memory lead to a slowdown in program performance? - CORRECT ANSWER Random access can lead to frequent cache misses, requiring different cache lines to be loaded into the CPU cache." "In what scenario would a fixed or static collection be more appropriate than a dynamic collection? - CORRECT ANSWER When the exact number of data elements to be stored is known beforehand and won't change." "Which method is used in Java's List ADT to append an element to the end of a list? - CORRECT ANSWER add(E e)" "If you want to remove all elements in the second list from the first one, which method would you use in Java's List ADT? - CORRECT ANSWER removeAll(Collection? c)" "Which method is used in Java's List ADT to check if a specific element exists in the list? - CORRECT ANSWER contains(Object o)" Which notation describes the best-case complexity of an algorithm? - CORRECT ANSWER Big-Ω" "What factor primarily determines the execution time of the add (∫lhs,∫rhs) method, which simply adds two numbers? - CORRECT ANSWER The number of operations involved." "Which of the following is a concrete instance of an algorithm, specifically designed to run on a computer? - CORRECT ANSWER A program" "An algorithm has a space complexity of O(1) and a time complexity of O(N log N). Which statement about the algorithm is true? - CORRECT ANSWER The algorithm uses a constant amount of memory irrespective of the input size, but its execution time increases logarithmically with the input size." "Given an algorithm that processes a list of N items in such a way that for each new item added, the execution time doubles, how would you best describe the time complexity of this algorithm? - CORRECT ANSWER O(2^N)" "Given the following statements: Wanting to identify the sentiment (positive, negative, neutral) of a piece of text. A set of rules that analyzes word choice and frequency to determine sentiment. A Java code that implements these rules and outputs the sentiment of a text. Which sequence correctly categorizes these statements? - CORRECT ANSWER 1. Problem 2. Algorithm 3. Program" "If the space required by an algorithm grows proportionally to the square of the size of the input, how would the space complexity be best described? - CORRECT ANSWER O(N^2)" "When analyzing an algorithm's performance, why is it beneficial to focus on how many times certain statements run as a function of the input size? - CORRECT ANSWER It enables estimation of how long two invocations of the same method will take relative to each other based on input size." "Consider the scenario where you need to find the shortest path between two cities on a map. How would you categorize the following descriptions? The challenge of determining the shortest path. The step-by-step method you devise to find this path. The code you write in Python to implement this method. Match the descriptions with the appropriate concepts: - CORRECT ANSWER 1. Problem 2. Algorithm 3. Program" "Which statement best captures the underlying rationale for the importance of sorting in computer science and software engineering? - CORRECT ANSWER Sorting facilitates more efficient searching, data compression, and overall data organization, impacting various algorithms and computational tasks." "You have two lists. You need to ensure that the first list contains all the elements of the second list but without any duplicates. What sequence of methods should you use to ensure this? - CORRECT ANSWER Use containsAll(Collection? c) to check. If false, iterate through the second list, check each element with contains(Object o), and use add(E e) if not contained." "You have a large list and another smaller list of elements. You want to ensure that your large list does not contain any elements from the smaller list. Considering efficiency, what is the best approach? - CORRECT ANSWER Use removeAll(Collection? c) to remove all elements in the smaller list from the large list." "You need to determine if a certain element exists in a list, locate its last occurrence, and then check if another specified collection of elements is absent in the list. If all are true, you decide to add all elements of the specified collection to the end of the list. Which sequence of methods is correct? - CORRECT ANSWER contains(Object o), lastIndexOf(Object o), !containsAll(Collection? c), and addAll(Collection? extends E c)" "You want to merge the elements of one list into another list such that the elements are appended to the end of the current list. Which method should you use? - CORRECT ANSWER addAll(Collection? extends E c)" "You have a list, and you want to remove an element. However, you don't know its exact position, but you know its value. What method would you use? - CORRECT ANSWER remove(Object o)" "To locate both the first and last occurrence of an element in a list, which combination of methods would you use? - CORRECT ANSWER indexOf(Object o) and lastIndexOf(Object o)" "Why can't you directly create a generic array in Java? - CORRECT ANSWER Java does not allow arrays to be constructed using generic type parameters due to its limitations." "In Java, what does a dynamic collection allow you to do that a static array does not? - CORRECT ANSWER Adjust its size dynamically based on the elements it contains." "In the context of a hash table, what are the trade-offs involved in choosing a lower versus a higher load factor? - CORRECT ANSWER A lower load factor reduces the likelihood of collisions but can lead to under-utilization of space, while a higher load factor can optimize space usage but may increase the chance of collisions." "The Mid-Square Hash function involves squaring the key and using a portion of the resulting value as the index. What is a potential benefit of this hash function? - CORRECT ANSWER It can be useful when keys are not uniformly distributed." "How does quadratic probing differ from linear probing in resolving collisions in a hash table? - CORRECT ANSWER Quadratic probing searches for an empty slot by checking indices at quadratically increasing distances." "What is a potential effect of maintaining a high load factor in a hash table without rehashing? - CORRECT ANSWER It can lead to increased search, insertion, and deletion times due to more collisions." "public int findMax(int[] nums) { int max = Integer.MIN_VALUE; for (int num : nums) { if (num max) { max = num; } } return max; } What will the method findMax return when passed an empty array? - CORRECT ANSWER Integer.MIN_VALUE" "public int sumUpTo(int n) { int sum = 0; for (int i = 1; i = n; i++) { sum += i; } return sum; } What is the output of sumUpTo(5)? - CORRECT ANSWER 15" "public boolean areArraysEqual(int[] arr1, int[] arr2) { if (h != h) { return false; } for (int i = 0; i h; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } What does the `areArraysEqual` method correctly determine? - CORRECT ANSWER If both arrays contain the same elements in the same order" "public boolean isSorted(int[] arr) { for (int i = 0; i h - 1; i++) { if (arr[i] arr[i + 1]) { return false; } } return true; } What issue might occur in the isSorted method when the array is null? - CORRECT ANSWER It throws a NullPointerException." "public int[] resizeArray(int[] arr, int newSize) { int[] newArr = new int[newSize]; for (int i = 0; i h && i newSize; i++) { newArr[i] = arr[i]; } return newArr; } Identify the issue in the resizeArray method when newSize is smaller than h. - CORRECT ANSWER It loses elements from the original array" "int max = Integer.MIN_VALUE; for (int i = 0; i n; i++) { if (array[i] max) { max = array[i]; } } What is the time complexity of finding the maximum value in the array as shown in the above code snippet? - CORRECT ANSWER O(n)" "for (int i = 1; i n; i = i * 2) { // Some constant time operations } What is the time complexity of the above loop? - CORRECT ANSWER O(log n)" "for (int i = 0; i n; i++) { for (int j = 0; j i; j++) { // Some constant time operations } } What is the time complexity of the above code snippet? - CORRECT ANSWER O(n^2)" "int count = 0; for (int i = 0; i n; i++) { for (int j = 0; j n; j++) { for (int k = 0; k n; k++) { count++; } } } What is the time complexity of the above code snippet? - CORRECT ANSWER O(n^3)" "void recursiveFunction(int n) { if (n = 1) { return; } recursiveFunction(n - 1); recursiveFunction(n - 1); } Analyze and determine the time complexity of the above code snippet. - CORRECT ANSWER O(2^n)" "Which data structure would be most efficient for implementing a browser's back button functionality? - CORRECT ANSWER Stack" "If you need to implement a system to track the visited nodes in a breadth-first search of a graph, which data structure would be most appropriate? - CORRECT ANSWER Queue" "Explain the advantage of using a LinkedList over an ArrayList for an application that requires frequent insertion and deletion of elements at random positions. - CORRECT ANSWER True" "For a real-time multiplayer game that requires the tracking of players' locations on a map, which data structure would be most efficient and why, considering factors like concurrency and rapid update needs? - CORRECT ANSWER True" ""Given that tree data structures are inherently recursive, which ADVANTAGE of recursion is most directly relevant? - CORRECT ANSWER Recursive solutions often embody elegance and simplicity that make them easier to understand, especially when the code mirrors the structure of the problem." "Given the definition of a recursive function that lacks a base case, what might be a potential outcome when the function is called? - CORRECT ANSWER The function might result in infinite recursion, as there is no termination condition." "boolean isSubsetSum(int set[], int n, int sum) { if (sum == 0) { return true; // Base case 1 } if ((n == 0) && (sum != 0)) { return false; // Base case 2 } if (set[n - 1] sum) { return isSubsetSum(set, n - 1, sum); // Recursive case 1 } // Last recursive case return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]); } What is the return value of isSubsetSum(set, n, sum) when n == 0 and sum is not equal to 0? - CORRECT ANSWER false" "In scenarios where multiple recursive calls are required, what challenge may arise if not handled properly? - CORRECT ANSWER The potential for exponential growth in the number of calls, leading to inefficiency." "What type of graph best represents a social network where connections are bidirectional and every person can connect with any other person, but not all do? - CORRECT ANSWER Undirected Graph" "In which type of tree is every node arranged such that all nodes in the left subtree have values less than the node's value, and all nodes in the right subtree have values greater than the node's value? - CORRECT ANSWER Binary Search Tree" "In a pre-order traversal of a binary tree, which of the following is the correct order of operations? - CORRECT ANSWER Visit the root, traverse the left subtree, traverse the right subtree." "If the depth of the deepest leaf in a tree is 5, what is the minimum possible height of the tree? - CORRECT ANSWER 5" "When using DFS in a directed graph for detecting cycles, which specific aspect of DFS is crucial for this application? - CORRECT ANSWER The ability of DFS to backtrack and detect if a visited node is encountered again in the current path." "In a Binary Search Tree (BST), what is the most time-consuming scenario for a deletion operation and why? - CORRECT ANSWER Deleting a node with two children, as it requires finding and rearranging the in-order successor or predecessor" "In which type of tree data structure is the balance factor of any node (difference in height between left and right subtree) always kept between -1 and 1 to ensure a balanced tree height for efficient search operations? - CORRECT ANSWER AVL Tree" "A road network with multiple direct routes (like highways and backroads) between the same cities is best represented as which type of graph? - CORRECT ANSWER Multigraph" "Given an adjacency matrix for a graph with four vertices, what is the first step in converting it to an adjacency list? - CORRECT ANSWER Create an empty list for each vertex to hold its adjacent vertices." "Given the BFS pseudocode, what is the missing step immediately after dequeuing a vertex from the queue? BFS(graph, start): Initialize an empty queue Q Mark start as visited Enqueue start into Q while Q is not empty: vertex = Dequeue(Q) # Missing step here for each neighbor of vertex: if neighbor is not visited: Mark neighbor as visited Enqueue neighbor into Q - CORRECT ANSWER Visit vertex." "In a tree data structure, if a node is at a distance of two edges from the root, what is the depth of that node? - CORRECT ANSWER 2" "In a Binary Search Tree (BST), if a node has a value greater than all other nodes, where will it appear in an in-order traversal sequence? - CORRECT ANSWER It will appear last in the sequence." "Identify the traversal method based on this pseudocode: function traverse(node) { if (node != null) { traverse() visit(node) traverse() } } - CORRECT ANSWER In-Order Traversal" "How does a hash function in a hash map handle a key that is a string? - CORRECT ANSWER It transforms the string into a numeric index." "What is a collision in the context of a hash table? - CORRECT ANSWER It occurs when multiple keys hash to the same index." "What is the "load factor" in the context of a hash table? - CORRECT ANSWER It is the ratio of the number of stored entries to the total number of slots in the hash table." "In the context of hashing, how does a cryptographically secure hash function compare to simpler hash functions like the modulo operator in terms of key distribution and computation time? - CORRECT ANSWER Cryptographically secure hash functions offer more uniform key distribution but at the cost of higher computation time." "How does the load factor of a hash table influence the effectiveness of the chaining method for collision resolution? - CORRECT ANSWER A higher load factor can lead to longer chains, which may increase search time."