Question 17. Sorting a data set is an important sub-problem in data science. Given the size n of a data set, which statements are correct? a) Bubble Sort has worst-case run-time complexity O(n). b) Bubble Sort has worst-case run-time complexity O(n log N ). c) Bubble Sort has worst-case run-time complexity O(n2). d) Merge Sort has worst-case run-time complexity O(n). e) Merge Sort has worst-case run-time complexity O(n log N ). f) Merge Sort has worst-case run-time complexity O(n2). g) Quick Sort has worst-case run-time complexity O(n). h) Quick Sort has worst-case run-time complexity O(n log N ). i) Quick Sort has worst-case run-time complexity O(n2).
Question 17. Sorting a data set is an important sub-problem in data science. Given the size n of a data set, which statements are correct?
a) Bubble Sort has worst-case run-time complexity O(n).
b) Bubble Sort has worst-case run-time complexity O(n log N ).
c) Bubble Sort has worst-case run-time complexity O(n2). d) Merge Sort has worst-case run-time complexity O(n).
e) Merge Sort has worst-case run-time complexity O(n log N ). f) Merge Sort has worst-case run-time complexity O(n2).
g) Quick Sort has worst-case run-time complexity O(n).
h) Quick Sort has worst-case run-time complexity O(n log N ).
i) Quick Sort has worst-case run-time complexity O(n2).
Question 18. C1 and C2 are classes written in an object-oriented programming language (such as Java, C#, or
C++). Which of the following statements are correct if C1 is a superclass of C2? a) C1 is always an abstract class.
b) C2 contains all public features defined by C1.
c) Each C2 object may be replaced by a C1 object.
d) C2 is a subclass of C1.
Question 19. The following function f uses recursion:
return n else
5
Let n be a valid input, i.e., a natural number. Which of the following
a) def
return b else
for i in 1..n c <- a + ba <- b
b <- c return b
f(n): a <- 0 i <- n while i > 0 a <- a + i + (i-1) return a f(n): arr[0] <- 0 arr[1] <- 1 if n <= 1 return arr[n] else for i in 2..n arr[i] <- arr[i-1] + arr[i-2] return arr[n] f(n): arr[0..n] <- [0, ..., n] if n <= 1 return arr[n] else a <- 0 for i in 0..n a <- a + arr[i] return ab) def
c) def
d) def
2.3 Logic and Databases
Question 20. If A, B, and C are Boolean variables, which of the following statements are correct? a) A∧(B∨C)=(A∧B)∨(A∧C)
b) A∨(B∧C)=(A∨B)∧(A∨C)
c) (A∧B)∨C=C∨(B∧A)
Question 21. A large retail company keeps sales data local to the individual branches where sales transactions were performed. To compute overall sales statistics, the company wants to avoid sending the full sales data set to a central server. Instead, only aggregated sales information (sum, average, minimum, variance,
a) The overall sum can be derived from the sums per branch. 6
b) The overall average can be derived from the averages per branch.
c) The overall minimum can be derived from the minimums per branch.
d) The overall variance can be derived from the variances per branch.
e) The overall median can be derived from the medians per branch.
f) The overall maximum can be derived from the maximums per branch.
Question 22. Consider the following table in a relational database.
Last Name Smith Jones Smith Doe
Rank Manager Custodian Custodian Clerical
Room Shift 234 Morning
33 Afternoon
33 Evening 222 Morning
According to the data shown in the table, which of the following could be candidate keys of the table? a) {Last Name}
b) {Room}
c) {Shift}
d) {Rank, Room} e) {Room, Shift}
Question 23. The database interface of a library allows searching only for a single attribute (such as Title or Author ) in each query. Your friend decided to extend it’s functionality and wrote an algorithm that allows searching for books that satisfy multiple predicates over single attributes in conjunction. He tells you the algorithm reuses the already implemented query functionality and works by intersecting the results ( book id’s ) of queries over single attributes.
Which of the following assumptions on your friend’s algorithm are plausible?
-
a) Its worst-case run-time necessarily increases exponentially with respect to the number of attributes in the query.
-
b) Its worst-case run-time depends on the length of the longest result of the single-attribute queries.
-
c) It might be implemented using an join.
-
d) It might be implemented using sorting.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps