CSD Part 1 – study guide and foundational course review material

CSD Part 1 – study guide and foundational course review material


a - ANS ✔✔Question 1

Marks: 1

After two passes of a sort algorithm, the following array:

47 3 21 32 56 92

has been rearranged as shown below:

3 21 47 32 56 92

Which sorting algorithm is being used?

Choose one answer.

a. all of them.

b. insertion sort.

c. selection sort.

d. bubble sort.



D - ANS ✔✔Which of the following Sorting algorithms use Divide and Conquer strategy?

Choose one answer.

a. Heap sort

b. Radix sort

c. Bubble sort

d. Quick sort



b - ANS ✔✔Question 1

Question 3

Marks: 1

Suppose the frequencies of use of characters is given by:

,A [10%], B [20%], C [70%]

What is the average length of the Huffman codes?

Choose one answer.

a. 2

b. 1.3

c. 1.5

d. 1



b - ANS ✔✔Question 4

Marks: 1

What type of the hash functions that can be used in an English - Vietnamese dictionary?

Choose one answer.

a. Radix transformation

b. Extraction

c. Mid-square function

d. Folding



a - ANS ✔✔Question 5

Marks: 1

A recursive method may be eliminated by using .................

Choose one answer.

a. Iteration statements

b. Stacks

c. All of the others.



b - ANS ✔✔Question 7

, Marks: 1

How many recursive calls to calculate the 5th Fibonacci number?

Choose one answer



a. 22

b. 15

c. 9

d. 32,



d - ANS ✔✔Question 8

Marks: 1

Consider the following algorithm on binary search tree in Java:

--------------------------------------------------------

public static int ABC(BSTNode p){

if (p != null){

return 1 + java.lang.Math.max(ABC(p.left), ABC(p.right));

}

return 0;

}

--------------------------------------------------------

The above algorithm will _______

Choose one answer.

a. None of the others.

b. count number of non-terminal nodes in the tree.

c. count number of nodes in the tree.

d. determine the height of the tree.