Resumos sobre a matéria de Algoritmos e Estruturas de Dados e Testebescolhasmultiplas PDF

Preview

Summary

Escolhas Múltiplas TESTE B AED1 many compares does mergesort—the pure version without any optimizations —make to sort an input array that is already sorted? constant -logarithmic-linear-linearithmic( It makes ~1/2 n log2 n compares, which is the best case for mergesort. We note that the optimized ve...

Description

Escolhas Múltiplas TESTE B AED

1.How many compares does mergesort—the pure version without any optimizations —make to sort an input array that is!already sorted? -constant! -logarithmic! -linear! -linearithmic( It makes ~1/2 n log2 n!compares, which is the best case for mergesort. We note that the optimized version that checks whether!a[mid]≤a[mid+1]!requires only!n−1compares.)

2.How many passes (over the input array) does bottom-up mergesort make in the worst case? -constant -logarithmic -linear! -linearithmic!

3. Under which of the following scenarios does the!NlgN!lower bound for sorting apply? Assume that the keys are accessed only through the compareTo() method unless otherwise specified. -five distinct keys! -no two keys are equal -keys in descending order! -keys are strings and accessed via charAt() instead of compareTo()!

4. Which of the following is a compelling reason to implement the Comparator interface instead of the!Comparable!interface in Java?

-easier to use"Comparator"with Arrays.sort()! -Comparator!supports multiple orderings of a given data type -easier to implement a total order with"Comparator"than"Comparable! -All of the above!

5. Given an array of points, which of the following approaches would be!least useful!for removing duplicate points? Assume the point data type has the following three orders: *A natural order that compares by!x-coordinate and breaks ties by!y-coordinate. *One comparator that compares by!x-coordinate; another by!y-coordiante. Note: quicksort is an efficient, but!unstable, sorting algorithm.

-quicksort by the natural order! -quicksort by x-coordinate; mergesort by"y-coordinate! -mergesort by!x-coordinate; quicksort by!y-coordinate

-mergesort by"x-coordinate; mergesort by"y-coordinate! 6.What is the expected running time of randomized quicksort to sort an array of!n!distinct keys when the array is!already sorted? -linear -linearithmic -quadratic

-exponential 7.What is the expected running time to find the median of an array of!n!distinct keys using!randomized quickselect? -constant! -linear

-linearithmic! -quadratic!

8.Using 3-way partitioning with quicksort is most effective when the input array has which of the following properties?

-all items distinct! -a few distinct items

-items in strictly increasing order! -items in strictly decreasing order! 9.Why does Arrays.sort() in Java use mergesort instead of quicksort when sorting reference types ?

-stability! -nlogn"guaranteed performance! -both A and B.

-neither A nor B!

10.Why does Arrays.sort()!in Java use quicksort instead of mergesort when sorting!primitive types!?

-uses less memory on typical inputs! -faster on typical inputs! -both A and B(

-neither A nor B! 11.What is the expected number of!array accesses!and!compares, respectively, to insert a random key into an ordered-array implementation of a priority queue?

-logarithmic and logarithmic -logarithmic and linear -linear and logarithmic (

-linear and linear 12.Which of the following arrays does!not!represent a max-oriented binary heap?

-19!18!17!16!15!14!13!12!11!10

-10!10!10!10!10!10!10!10!10!10 -34!30!29!27!25!17!16!19!22!24 -30!27!23!17!16!15!13!14!18!11

13.Suppose that an array!a[]!is a max-heap that contains the distinct integer keys!1,2,…,N!with N≥7. The key!N!must be in!a[1]!and the key!N−1must be in either!a[2]!or!a[3]. Where must the keyN−2!be?

-2 or 3 -4, 5, 6, or 7 -2, 3, 4, 5, 6, or 7 -1, 2, 3, 4, 5, 6, or 7 14.How many compares does bottom-up (sink-based) heap construction perform in the worst case when sorting an array of!n!keys?

-constant -logarithmic -linear

16.What is the maximum number of array accesses needed to search for a key in a symbol table that is implemented with a!sorted array?

-constant -logarithmic ( -linear -linearithmic

17.What is the maximum number of compares to determine the rank of a key in a symbol table that is implemented using a!sorted array? -constant -logarithmic ( -linear -linearithmic

18.Suppose that!n!distinct keys are inserted into a binary search tree in random order. What is the expected number of compares to search for one of the!n keys? -constant -logarithmic

-linear -linearithmic

19.A BST is uniquely defined by its!level-order traversal, a breadth-first traversal where the root is visited first, then all nodes at depth 1 (going from left to right), then all nodes at depth 2 (going from left to right), and so forth. What is the level-order traversal of the BST drawn below?

-A"C"E"H"M"P"R"S"X! -A"C"H"P"M"E"S"X"R! -R"E"C"A"M"H"P"X"S! -R!E!X!C!M!S!A!H!P(

20.What is the order of growth of the expected height of a binary search

tree with!n!keys after a long intermixed sequence of random insertions and random Hibbard deletions?

-logn -sqrt{n}

-n -nlogn

21.Suppose that you are inserting a new key into a 2–3 tree. Under which one of the following scenarios must the height of the 2–3 tree increase by one? -When the number of keys equals one less than a power of 2 -When the number of nodes equals one less than a power of 2 -When the final node on the search path from the root is a 3-node -When every node on the search path from the root is a 3-node

22 Suppose that you left rotate the node containing E in the BST below. Which

is the level-order traversal of the resulting red–black BST?

-

R!E!X!C!M!S!Y!A!H!P!F -R!M!X!E!H!S!Y!C!F!P!A -R!M!X!E!P!S!Y!C!H!A!F -R!C!X!A!E!S!Y!M!H!P!F

23.Suppose that you insert!n!keys in ascending order into a red–black BST. What is the height of the resulting tree?

-constant -logarithmic

-linear -linearithmic

24.What is the worst-case number of compares to perform a 1d range count if the keys are stored in an!ordered array!and the 1d range search is performed efficiently? -constant -logarithmic (

-linear -linearithmic 25.What is the worst-case running time of the sweep-line algorithm to find all R intersections among n orthogonal line segments? -constant + R -logn + R -nlogn฀+R -nlogn + Rlogn

26.Suppose that the point 11 is inserted into the kd-tree below. Where is the new node inserted?

-Right child of 6 -Left child of 7 -Left child of 10 -Right child of 10 • • • •

27.When performing nearest neighbor search, we organize the recursive method so that when there are two possible subtrees to go down, we always choose!the subtree that is on the same side of the splitting line as the query point!as the first subtree to explore. What is the main reason for doing so? -simplify code -ensure correctness -improve performance in practice

-improve performance in the worst case

28.What is the worst case running time of deleting an interval using an interval search tree? -constant -logarithmic -linearithmic -quadratic

29.What is the worst-case running time of the sweep-line algorithm to find all R intersections amongn rectangles? -constant + R -logn + R -nlogn + R -nlogN + R logn

30.Which of the following is not a property of Java's hashCode() for the String data type? -can return a negative integer -can take time proportional to the length of the string to compute -a string and its reverse will have the same hashCode() value

-two strings with different hashCode() values are different strings

31.What is the average running time of a random search miss in a separate-chaining hash table? Assume that your hash function satisfies the uniform hashing assumption and that there are m=n/8!chains. -constant

-logarithmic -linear -linearithmic

32.What is the average running time of delete in a linear-probing hash table? Assume that your hash function satisfies the uniform hashing assumption and that the hash table is at most 50% full. constant- (

-logarithmic -linear -linearithmic

33.Which is the main reason to use a hash table instead of a red–black BST? -supports more operations efficiently -better worst-case performance guarantee -better performance in practice on typical inputs

-implementation included in Java libraries

ST applications (optional) 34.Suppose that you implement a set using a red–black BST. Which of the following operations cannot be implemented in logarithmic time (or better) in the worst case? a-dd an element to the set (if it is not already in the set) -does the set contain a given element? -return the set of all elements contained in two given sets

-remove an element from the set (if it is in the set) 35.Among the following symbol-table implementations, which would be most suitable for use in the 𝙻𝚘𝚘𝚔𝚞𝚙𝙲𝚂𝚅 client ?Assume that the 𝙺𝚎𝚢 type implements the compareTo(), equals(), and hashCode() methods. -unordered array -ordered linked list -binary search tree -linear-probing hash table

36.Suppose that you are creating a book index which contains a set of keywords and there is a set of page numbers associated with each keyword (the pages on which the keyword appears). Which data type below would be the best choice to represent the book index?

-ST -ST

-SET -SET 37.Consider an n-by-n matrix A such that each row has 5 nonzero entries. Suppose that you represent A using a sparse matrix (each row is represented as a sparse vector). What is the running time of multiplying the matrix A with a dense vector x of length n?

-n

-nlogn -n^2 -n^3...