xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

数据结构算法代写-VERSION 1

时间：2021-04-26

VERSION 1 COMPSCI 220

THE UNIVERSITY OF AUCKLAND

SECOND SEMESTER, 2020

Campus: City

COMPUTER SCIENCE

Algorithms and Data Structures

(Time allowed: 50 minutes)

NOTE: There are 20 marks available in this test, which is worth 15% of your overall course mark.

FIRST: Enter your name and student ID into the Teleform sheet provided.

THEN: Attempt all questions and tick your answers on the Teleform sheet.

All questions have ONE correct answer and equal value.

DO NOT tick two answers as correct for the same question.

Keep your question book. Writing on it will not be marked.

Use of calculators is NOT permitted.

Good luck!

Page 1 of 8

VERSION 1 COMPSCI 220

1. The running time for the following code fragment is Θ(f(n)). What is f(n)?

for (int i = 0; i < n; i++)

for (int j = i− 10; j < i; j++)

for (int k = 1; k < n; k = 4 ∗ k)

System.out.println(i);

end for

end for

end for

A. n3

B. n2 log n

C. n log log n

D. n log n

E. n2

2. On which list does Quickselect achieve the minimum number of comparisons when finding the 2nd

order statistic?

A. [4, 1, 2, 6, 7]

B. All of the listed lists.

C. [2, 5, 6, 7, 1]

D. [4, 2, 1, 6, 7]

E. [5, 3, 2, 8, 12]

3. Choose the strongest true statement: Selection sort makes at least as many comparisons as insertion

sort

A. on every input

B. on reverse sorted input

C. on average for uniformly random input

D. for input with fewer inversions than average

E. in the worst case

4. Which of the following is NOT a property of mergesort?

A. Θ(n log n) worst-case sorting time.

B. Linear merge time.

C. In-place sorting.

D. Particularly good for sorting linked lists.

E. Θ(n log n) average-case sorting time.

Page 2 of 8

VERSION 1 COMPSCI 220

5. Which of the following statements about Treesort and BST is FALSE?

A. Insertion order 4,3,2,1 creates a BST of height 3.

B. Treesort on a list with n elements takes time in Θ(n log n) in the worst case.

C. Deleting an element of a BST can make the tree unbalanced.

D. A BST can be built using the quicksort algorithm.

E. The sorted list can be recovered from a BST by reading the keys according to an

inorder traversal.

6. Let T be a decision tree of a comparison based sorting algorithm for an input of n distinct elements.

Which of the following statements about T is FALSE?

A. Every node is connected to exactly two nodes on the next level.

B. T has n! leaves.

C. T is a binary tree.

D. The height of T is at least log2(n).

E. Every leaf corresponds to a possible final sorted list on n elements.

7. How many inversions are in the permutation 53412?

A. 10

B. 2

C. 8

D. 5

E. 3

8. The running time for the following code fragment is Θ(f(n)). What is f(n)?

for (int i = 1; i ≤ n; i = 2 ∗ i){

for (int j = 1; j ≤ i; j = 2 ∗ j){

// Do something elementary

}

}

A. log n log log n

B. log n

C. n log n

D. (log n)2

E. log logn

Page 3 of 8

VERSION 1 COMPSCI 220

9. Which of the following statements about f(n) = 5n3 log5 n + 20n

2 + 15n(log30 n)

2 is FALSE?

A. f(n) is Ω(n2 log n).

B. f(n) is Ω(n3 log n).

C. f(n) is Ω(n3).

D. f(n) is Ω(n3(log n)2).

E. f(n) is Ω(n(log n)2).

10. Which of the following statements about Heapsort is FALSE?

A. The idea of Heapsort is to build a binary heap and then delete elements of the highest

priority one-by-one until the heap is empty.

B. Consider an array heap implementation [9, 6, 8, 5, 4, 3]. After inserting a node with

key 10 the array will become [9, 6, 10, 5, 4, 3, 8].

C. Deleting all n elements of a heap takes time in Θ(n log n).

D. Heapifying is more efficient than building a binary heap by inserting nodes one-by-

one.

E. An array implementation of Heapsort moves the highest priority element in the heap,

after deletion, to the end of the active part of the array.

11. Which of these is NOT in Ω(n log n)?

A. n3/4(lnn)5

B. 0.001n2/ lg n

C.

√

n3 log10 n

D. n2(2− cos(n))

E. 17n lnn

12. The recurrence T (n) = 2T (n/2) + 1, T (1) = 0 has a solution that is in Θ(f(n)). What is f(n)?

A. n2

B. n

C. log n

D. 2n

E. n log n

Page 4 of 8

VERSION 1 COMPSCI 220

13. Which of the following lists can be used as an input list for Quickselect:

r = [1, 2, 3, 4, 5, 6], s = [6, 2, 3, 4, 1], t = [9, 6, 4, 2, 1, 0]

A. r and t.

B. All of them.

C. Only r.

D. Only s.

E. None of them.

14. A certain algorithm processes a list of size n by first inspecting each element, splitting the list into

2 sublists of equal size, then recursively processing the sublists. It gives rise to a recurrence for the

running time T (n) that looks like T (n) =***. What is ***?

A. T (n/2) + 1

B. 2T (n/2) + n

C. 2T (n/2) + 1

D. T (n/2) + n2

E. T (n/2) + n

15. Suppose that our best implementation of Algorithm A runs in time 10−10n2 nanoseconds and our

best implementation of Algorithm B runs in time 1010n nanoseconds. Choose the best answer.

A. Algorithm B is better than Algorithm A

B. Algorithm B is better than Algorithm A for inputs of size less than 1020

C. Algorithm B and Algorithm A are not comparable

D. Algorithm A is better than Algorithm B

E. Algorithm A is better than Algorithm B for inputs of size less than 1020

16. Which of the following trees is a binary heap?

A. B, D

B. B, C

C. A

D. B,C,D

E. B

Page 5 of 8

VERSION 1 COMPSCI 220

17. Which of the following inputs makes selection sort perform the largest number of comparisons?

A. all other choices result in the same number of comparisons

B. 5, 4, 3, 2, 1

C. 3, 5, 4, 1, 2

D. 2, 3, 5, 4, 1

E. 1, 2, 3, 4, 5

18. Which of the following trees is a BST?

A. B, C, D

B. A

C. B, D

D. B, C

E. C, D

19. Consider array-based quick sort Q, and array-based merge sort M , and suppose that both are being

run on random input data. Which of the following statements is true?

A. Q is faster than M because Q makes fewer comparisons than M

B. Q is faster than M even though Q makes more comparisons than M

C. Q is slower than M because Q makes more comparisons than M

D. Q is slower than M even though Q makes fewer comparisons than M

E. Q is asymptotically faster than M

20. An implementation of insertion sort spent 1 second to sort a list of 106 random records. How long

will it take to sort 107 random records?

A. 100 seconds

B. 600 seconds

C. 10 seconds

D. 60 seconds

E. 1000 seconds

Page 6 of 8

VERSION 1 COMPSCI 220

Working page 1

Page 7 of 8

VERSION 1 COMPSCI 220

Working page 2

Page 8 of 8

学霸联盟

THE UNIVERSITY OF AUCKLAND

SECOND SEMESTER, 2020

Campus: City

COMPUTER SCIENCE

Algorithms and Data Structures

(Time allowed: 50 minutes)

NOTE: There are 20 marks available in this test, which is worth 15% of your overall course mark.

FIRST: Enter your name and student ID into the Teleform sheet provided.

THEN: Attempt all questions and tick your answers on the Teleform sheet.

All questions have ONE correct answer and equal value.

DO NOT tick two answers as correct for the same question.

Keep your question book. Writing on it will not be marked.

Use of calculators is NOT permitted.

Good luck!

Page 1 of 8

VERSION 1 COMPSCI 220

1. The running time for the following code fragment is Θ(f(n)). What is f(n)?

for (int i = 0; i < n; i++)

for (int j = i− 10; j < i; j++)

for (int k = 1; k < n; k = 4 ∗ k)

System.out.println(i);

end for

end for

end for

A. n3

B. n2 log n

C. n log log n

D. n log n

E. n2

2. On which list does Quickselect achieve the minimum number of comparisons when finding the 2nd

order statistic?

A. [4, 1, 2, 6, 7]

B. All of the listed lists.

C. [2, 5, 6, 7, 1]

D. [4, 2, 1, 6, 7]

E. [5, 3, 2, 8, 12]

3. Choose the strongest true statement: Selection sort makes at least as many comparisons as insertion

sort

A. on every input

B. on reverse sorted input

C. on average for uniformly random input

D. for input with fewer inversions than average

E. in the worst case

4. Which of the following is NOT a property of mergesort?

A. Θ(n log n) worst-case sorting time.

B. Linear merge time.

C. In-place sorting.

D. Particularly good for sorting linked lists.

E. Θ(n log n) average-case sorting time.

Page 2 of 8

VERSION 1 COMPSCI 220

5. Which of the following statements about Treesort and BST is FALSE?

A. Insertion order 4,3,2,1 creates a BST of height 3.

B. Treesort on a list with n elements takes time in Θ(n log n) in the worst case.

C. Deleting an element of a BST can make the tree unbalanced.

D. A BST can be built using the quicksort algorithm.

E. The sorted list can be recovered from a BST by reading the keys according to an

inorder traversal.

6. Let T be a decision tree of a comparison based sorting algorithm for an input of n distinct elements.

Which of the following statements about T is FALSE?

A. Every node is connected to exactly two nodes on the next level.

B. T has n! leaves.

C. T is a binary tree.

D. The height of T is at least log2(n).

E. Every leaf corresponds to a possible final sorted list on n elements.

7. How many inversions are in the permutation 53412?

A. 10

B. 2

C. 8

D. 5

E. 3

8. The running time for the following code fragment is Θ(f(n)). What is f(n)?

for (int i = 1; i ≤ n; i = 2 ∗ i){

for (int j = 1; j ≤ i; j = 2 ∗ j){

// Do something elementary

}

}

A. log n log log n

B. log n

C. n log n

D. (log n)2

E. log logn

Page 3 of 8

VERSION 1 COMPSCI 220

9. Which of the following statements about f(n) = 5n3 log5 n + 20n

2 + 15n(log30 n)

2 is FALSE?

A. f(n) is Ω(n2 log n).

B. f(n) is Ω(n3 log n).

C. f(n) is Ω(n3).

D. f(n) is Ω(n3(log n)2).

E. f(n) is Ω(n(log n)2).

10. Which of the following statements about Heapsort is FALSE?

A. The idea of Heapsort is to build a binary heap and then delete elements of the highest

priority one-by-one until the heap is empty.

B. Consider an array heap implementation [9, 6, 8, 5, 4, 3]. After inserting a node with

key 10 the array will become [9, 6, 10, 5, 4, 3, 8].

C. Deleting all n elements of a heap takes time in Θ(n log n).

D. Heapifying is more efficient than building a binary heap by inserting nodes one-by-

one.

E. An array implementation of Heapsort moves the highest priority element in the heap,

after deletion, to the end of the active part of the array.

11. Which of these is NOT in Ω(n log n)?

A. n3/4(lnn)5

B. 0.001n2/ lg n

C.

√

n3 log10 n

D. n2(2− cos(n))

E. 17n lnn

12. The recurrence T (n) = 2T (n/2) + 1, T (1) = 0 has a solution that is in Θ(f(n)). What is f(n)?

A. n2

B. n

C. log n

D. 2n

E. n log n

Page 4 of 8

VERSION 1 COMPSCI 220

13. Which of the following lists can be used as an input list for Quickselect:

r = [1, 2, 3, 4, 5, 6], s = [6, 2, 3, 4, 1], t = [9, 6, 4, 2, 1, 0]

A. r and t.

B. All of them.

C. Only r.

D. Only s.

E. None of them.

14. A certain algorithm processes a list of size n by first inspecting each element, splitting the list into

2 sublists of equal size, then recursively processing the sublists. It gives rise to a recurrence for the

running time T (n) that looks like T (n) =***. What is ***?

A. T (n/2) + 1

B. 2T (n/2) + n

C. 2T (n/2) + 1

D. T (n/2) + n2

E. T (n/2) + n

15. Suppose that our best implementation of Algorithm A runs in time 10−10n2 nanoseconds and our

best implementation of Algorithm B runs in time 1010n nanoseconds. Choose the best answer.

A. Algorithm B is better than Algorithm A

B. Algorithm B is better than Algorithm A for inputs of size less than 1020

C. Algorithm B and Algorithm A are not comparable

D. Algorithm A is better than Algorithm B

E. Algorithm A is better than Algorithm B for inputs of size less than 1020

16. Which of the following trees is a binary heap?

A. B, D

B. B, C

C. A

D. B,C,D

E. B

Page 5 of 8

VERSION 1 COMPSCI 220

17. Which of the following inputs makes selection sort perform the largest number of comparisons?

A. all other choices result in the same number of comparisons

B. 5, 4, 3, 2, 1

C. 3, 5, 4, 1, 2

D. 2, 3, 5, 4, 1

E. 1, 2, 3, 4, 5

18. Which of the following trees is a BST?

A. B, C, D

B. A

C. B, D

D. B, C

E. C, D

19. Consider array-based quick sort Q, and array-based merge sort M , and suppose that both are being

run on random input data. Which of the following statements is true?

A. Q is faster than M because Q makes fewer comparisons than M

B. Q is faster than M even though Q makes more comparisons than M

C. Q is slower than M because Q makes more comparisons than M

D. Q is slower than M even though Q makes fewer comparisons than M

E. Q is asymptotically faster than M

20. An implementation of insertion sort spent 1 second to sort a list of 106 random records. How long

will it take to sort 107 random records?

A. 100 seconds

B. 600 seconds

C. 10 seconds

D. 60 seconds

E. 1000 seconds

Page 6 of 8

VERSION 1 COMPSCI 220

Working page 1

Page 7 of 8

VERSION 1 COMPSCI 220

Working page 2

Page 8 of 8

学霸联盟