Data Structures and Algorithms Exam Questions PDF

## Data Structures and Algorithms Exam #### Domanda 1 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **Which is the algorithmic paradigm adopted by the following algorithms we have discussed in class?** | Algorithm | Paradigm | |---|---| | Djikstra algorithm | Greedy | | Prim's algorithm...

## Data Structures and Algorithms Exam #### Domanda 1 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **Which is the algorithmic paradigm adopted by the following algorithms we have discussed in class?** | Algorithm | Paradigm | |---|---| | Djikstra algorithm | Greedy | | Prim's algorithm | Greedy | | Floyd-Warshall algorithm | Dynamic Programming | | Mergesort | Divide & Conquer | | Rod cutting | Dynamic Programming | | Longest Common Subsequence | Dynamic Programming | La risposta corretta è: Djikstra algorithm → Greedy, Prim's algorithm → Greedy, Floyd-Warshall algorithm → Dynamic Programming, Mergesort → Divide & Conquer, Rod cutting → Dynamic Programming, Longest Common Subsequence → Dynamic Programming #### Domanda 2 **Parzialmente corretta** Punteggio ottenuto 0.80 su 1.00 Indicate which structure would be a more suitable choice for each of the following applications: | Application | Structure | |---|---| | A program to maintain the routes in an airline.| Graph | | A program to implement the "undo" function in a text editor.| Stack | | A program to keep track of family relationships.| Tree | | An electronic address book ordered by name.| Binary Search Tree | | A program to serve clients as they check into a post office| Queue | La risposta corretta è: A program to maintain the routes in an airline. → Graph, A program to implement the "undo" function in a text editor. → Stack, A program to keep track of family relationships. → Tree, An electronic address book ordered by name. → Binary Search Tree, A program to serve clients as they check into a post office. → Queue #### Domanda 3 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **Associate the correct worst-case running time to the sorting algorithm.** | Sorting Algorithm | Worst-Case Running Time | |---|---| | Selection sort | O(n^2) | | Heapsort | O(n*log(n)) | | Insertion sort| O(n^2) | | Mergesort| O(n*log(n)) | La risposta corretta è: Selection sort → O(n^2), Heapsort → O(n*log(n)), Insertion sort → O(n^2), Mergesort → O(n*log(n)) #### Domanda 4 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called ... ?** La risposta corretta è: **Divide and Conquer** #### Domanda 5 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **In BFS, how many times is a node visited?** La risposta corretta è: **Equivalent to number of in-degree of the node** #### Domanda 6 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **Suppose that a certain Binary Search Tree has keys that are integers between 1 and 10, and we search for 5. Which sequence below cannot be the sequence of keys examined?** La risposta corretta è: **2, 7, 3, 8, 4, 5** #### Domanda 7 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **Consider you want to get a longest common subsequence of two char sequences x[1 .. m] and y[1.. n]. The algorithm that checks every subsequence of x to see if it is also a sequence of y, in a worst-case scenario, requires:** La risposta corretta è: **Exponential running time** #### Domanda 8 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **In dynamic programming, the technique of storing the previously calculated values is called:** La risposta corretta è: **Memoization** #### Domanda 9 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **Which of the following methods can be used to search an element in a linked list?** La risposta corretta è: **Iterative linear search** #### Domanda 10 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **Which of the following scenarios leads to expected linear running time for a random search hit in a linear probing hash table?** La risposta corretta è: **All keys hash to the same index.** #### Domanda 11 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **Consider an undirected graph G=(V,E) represented with an adjacency list. What is the time complexity to find if there is an edge between 2 particular vertices?** La risposta corretta è: **O(V)** #### Domanda 12 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **Suppose that you have to store a fixed and immutable sequence of integers. Which one amongst the following data structures guarantees the best access time?** La risposta corretta è: **Array** #### Domanda 13 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **Associate the correct worst-case running time to the sorting algorithm.** | Sorting Algorithm | Worst-Case Running Time | |---|---| | Selection Sort | O(n^2) | | Heapsort | O(n*log(n)) | | Insertion Sort | O(n^2) | | Mergesort | O(n*log(n)) | La risposta corretta è: Selection sort → O(n^2), Heapsort → O(n*log(n)), Insertion sort → O(n^2), Mergesort → O(n*log(n)) #### Domanda 14 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **Which of the following algorithms should be preferred so that the number of swap operations are minimised in general?** La risposta corretta è: **Selection sort** #### Domanda 15 ** Risposta errata** Punteggio ottenuto 0.00 su 1.00 **Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted in the table using linear probing? Note that '_' denotes an empty location in the table.** La risposta corretta è: **1, 8, _, 10, _, _, 3** #### Question 1 **Correct** Flag question **What is the complexity of T(n) = 2T(n/2) + n² log2n ?** La risposta corretta è: **Θ(n²log2n)** #### Question 2 **Incorrect** Flag question **What is the running time of the following algorithm?** ```python int recursive (int n) { if (n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); } ``` La risposta corretta è: **O(2^n )** #### Question 3 **Correct** Flag question **Consider the following recurrence:** T(n) = 3T(n/5) + log2n * log2n **Using the Master Theorem, what is the value of T(n)?** La risposta corretta è: **Θ(n^(log5 (3)))** #### Question 4 **Incorrect** Flag question **What is the complexity of fun()?** ```python int fun(int n) { int count = 0; for (int i = n; i > 0; i = i / 2) for (int j = 0; j < i; j++) count += 1; return count; } ``` La risposta corretta è: **O(n)** #### Question 5 **Incorrect** Flag question **What is the additional space required to merge two sorted arrays in the mergesort algorithm?** La risposta corretta è: **O(n) ** #### Question 6 **Correct** Flag question **What will be the best case time complexity of merge sort?** La risposta corretta è: **O(n*log n)** #### Question 7 Correct Flag question **Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes? ** La risposta corretta è: **512** #### Question 8 **Correct** Flag question **Consider an array of elements arr[5]= {5,4,3,2,1), what are the steps of insertions done while doing insertion sort in the array? ** La risposta corretta è: 1. **4 5 3 2 1** 2. **3 4 5 2 1** 3. **2 3 4 5 1** 4. **1 2 3 4 5** #### Question 9 **Correct** Flag question **Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?** La risposta corretta è: **25,14,16,13,10,8,12** #### Question 10 **Incorrect** Flag question **A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the *keys* 44, 45, 79, 63 into a table indexed from 0 to 6. What will be the location of key 18?** La risposta corretta è: **3** #### Question 11 **Correct** Flag question **The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?** La risposta corretta è: **15, 10, 23, 25, 20, 35, 42, 39, 30** #### Question 12 **Incorrect** Flag question **Complete the following code implementing the Floyd-Warshall algorithm** ```python n=rows [W] D(0)=W for k=1 to n do for i=1 to n do for j=1 to n do dij (k) = min(dij (k-1), dik (k-1) + dkj (k-1)) return D(n) ``` La risposta corretta è: **dij (k) = min(dij (k-1), dik (k-1) + dkj (k-1))** #### Question 13 **Incorrect** Flag question **Consider a single linked list where F and L are pointers to the first and last elements, respectively, of the linked list. The time for performing which of the given operations depends on the length of the linked list?** La risposta corretta è: **Add an element at the end of the list** #### Question 14 **Correct** Flag question **In Depth First Search, how many times is a node visited?** La risposta corretta è: **Equivalent to the number of indegree of the node** #### Question 15 **Correct** Flag question **Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4). Entry Wij in the matrix W below is the weight of the edge (i, j). What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in tree T?** ``` 0 1 8 1 4 1 0 12 4 9 W = 8 12 0 7 3 1 4 7 0 2 4 9 3 2 0 ``` La risposta corretta è: **10** #### Question 1 **Correct** Flag question **What is the complexity of T(n) = 2T(n/2) + n² log2n** La risposta corretta è: **Θ(n²log2n)** #### Question 2 **Incorrect** Flag question **What is the running time of the following algorithm?** ```python int recursive (int n) { if (n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); } ``` La risposta corretta è: **O(2^n )** #### Question 3 **Correct** Flag question **Consider the following recurrence:** T(n) = 3T(n/5) + log2n * log2n **Using the Master Theorem, what is the value of T(n)?** La risposta corretta è: **Θ(n^(log5 (3)))** #### Question 4 **Incorrect** Flag question **What is the complexity of fun()?** ```python int fun(int n) { int count = 0; for (int i = n; i > 0; i = i / 2) for (int j = 0; j < i; j++) count += 1; return count; } ``` La risposta corretta è: **O(n)** #### Question 5 **Incorrect** Flag question **What is the additional space required to merge two sorted arrays in the mergesort algorithm?** La risposta corretta è: **O(n) ** #### Question 6 **Correct** Flag question **What will be the best case time complexity of merge sort?** La risposta corretta è: **O(n*log n)** #### Question 7 Correct Flag question **Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes? ** La risposta corretta è: **512** #### Question 8 **Correct** Flag question **Consider an array of elements arr[5]= {5,4,3,2,1), what are the steps of insertions done while doing insertion sort in the array? ** La risposta corretta è: 1. **4 5 3 2 1** 2. **3 4 5 2 1** 3. **2 3 4 5 1** 4. **1 2 3 4 5** #### Question 9 **Correct** Flag question **Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?** La risposta corretta è: **25,14,16,13,10,8,12** #### Question 10 **Incorrect** Flag question **A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the *keys* 44, 45, 79, 63 into a table indexed from 0 to 6. What will be the location of key 18?** La risposta corretta è: **3** #### Question 11 **Correct** Flag question **The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?** La risposta corretta è: **15, 10, 23, 25, 20, 35, 42, 39, 30** #### Question 12 **Incorrect** Flag question **Complete the following code implementing the Floyd-Warshall algorithm** ```python n=rows [W] D(0)=W for k=1 to n do for i=1 to n do for j=1 to n do dij (k) = min(dij (k-1), dik (k-1) + dkj (k-1)) return D(n) ``` La risposta corretta è: **dij (k) = min(dij (k-1), dik (k-1) + dkj (k-1))** #### Question 13 **Incorrect** Flag question **Consider a single linked list where F and L are pointers to the first and last elements, respectively, of the linked list. The time for performing which of the given operations depends on the length of the linked list?** La risposta corretta è: **Add an element at the end of the list** #### Question 14 **Correct** Flag question **In Depth First Search, how many times is a node visited?** La risposta corretta è: **Equivalent to the number of indegree of the node** #### Question 15 **Correct** Flag question **Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4). Entry Wij in the matrix W below is the weight of the edge (i, j). What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in tree T?** ``` 0 1 8 1 4 1 0 12 4 9 W = 8 12 0 7 3 1 4 7 0 2 4 9 3 2 0 ``` La risposta corretta è: **10** #### Domanda 1 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **What is the complexity of T(n) = 2T(n/2) + n² log2n** La risposta corretta è: **Θ(n²log2n)** #### Domanda 2 **Incorrect** Punteggio ottenuto 0.00 su 1.00 **What is the running time of the following algorithm?** ```python int recursive (int n) { if (n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); } ``` La risposta corretta è: **O(2^n )** #### Domanda 3 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **Consider the following recurrence:** T(n) = 3T(n/5) + log2n * log2n **Using the Master Theorem, what is the value of T(n)?** La risposta corretta è: **Θ(n^(log5 (3)))** #### Domanda 4 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **What is the complexity of fun()?** ```python int fun(int n) { int count = 0; for (int i = n; i > 0; i = i / 2) for (int j = 0; j < i; j++) count += 1; return count; } ``` La risposta corretta è: **O(n)** #### Domanda 5 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **What is the additional space required to merge two sorted arrays in the mergesort algorithm?** La risposta corretta è: **O(n)** #### Domanda 6 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **What will be the best case time complexity of merge sort?** La risposta corretta è: **O(n*log n)** #### Domanda 7 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?** La risposta corretta è: **512** #### Domanda 8 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **Consider an array of elements arr[5]= {5,4,3,2,1), what are the steps of insertions done while doing insertion sort in the array? ** La risposta corretta è: 1. **4 5 3 2 1** 2. **3 4 5 2 1** 3. **2 3 4 5 1** 4. **1 2 3 4 5** #### Domanda 9 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?** La risposta corretta è: **25, 14, 16, 13, 10, 8, 12** #### Domanda 10 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?** La risposta corretta è: **3** #### Domanda 11 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?** La risposta corretta è: **15, 10, 23, 25, 20, 35, 42, 39, 30** #### Domanda 12 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **Complete the following code implementing the Floyd-Warshall algorithm ** ```python n=rows [W] D(0)=W for k=1 to n do for i=1 to n do for j=1 to n do dij (k) = min(dij (k-1), dik (k-1) + dkj (k-1)) return D(n) ``` La risposta corretta è: **dij (k) = min(dij (k-1), dik (k-1) + dkj (k-1))** #### Domanda 13 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **Consider a single linked list where F and L are pointers to the first and last elements, respectively, of the linked list. The time for performing which of the given operations depends on the length of the linked list?** La risposta corretta is **Add an element at the end of the list** #### Domanda 14 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **In Depth First Search, how many times is a node visited?** La risposta corretta è: **Equivalent to the number of indegree of the node** #### Domanda 15 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4). Entry Wij in the matrix W below is the weight of the edge (i, j). What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in tree T?** ``` 0 1 8 1 4 1 0 12 4 9 W = 8 12 0 7 3 1 4 7 0 2 4 9 3 2 0 ``` La risposta corretta è: **10** #### Domanda 1 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **What is the complexity of T(n) = 2T(n/2) + n² log2n** La risposta corretta è: **Θ(n²log2n)** #### Domanda 2 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **The Breadth First Search traversal of a graph will result into?** La risposta corretta è: **Tree** #### Domanda 3 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **If a DFS of a directed graph contains a back edge, any other DFS of the same graph will also contain at least one back edge.** La risposta corretta è: **Vero** #### Domanda 4 **Risposta corretta** Punteggio ottenuto 1.00 su 1.00 **Consider a binary search tree. For a node u, let: key(u) be its key; left(u) be its left child; and right(u) be its right child. Which of the following properties is true?** La risposta corretta è: **key(left(u)) <= key(u) <= key(right(u))** #### Domanda 5 **Risposta errata** Punteggio ottenuto 0.00 su 1.00 **In a heap data structure, what is the location of a parent node for any arbitrary node i?** La risposta corretta è:: **floor(i/2) position**