11/8 Homework: BSTs and Heaps | Legion of Learners

Complete the review by next week, but complete the BSTs and Heaps anytime in the next 3 weeks (we will have the local contest next week, then thanksgiving break, and then the next class).

Review:

Since this is for studying for the local contest, I'll post many different problems along with their answers. Do as many as you think you need to be ready. There are 5 total questions and 30 minutes to do them so if you will have 6 minutes on average to do each question. The topics that will be on the local contest are computer number systems (2 questions), recursive functions (2 questions), and What does this program do (1 question).

Topics to know:

How to count in binary, octal, hex

Converting from binary, octal, or hex to decimal

Converting from decimal to binary, octal, or hex

Converting from octal or hex to binary (without going to decimal)

Converting from binary to octal or hex (without going to decimal)

Addition, subtraction, multiplication, and division in binary

Doing calculations with mixed bases

Solving recursive functions with 1 or 2 variables

How to analyze code involving if statements (What does this program do will not involve loops or arrays)

Computer number systems (the number in brackets indicates the base):

How many 1's are in the binary representation of 16743(8)?

Convert 3F6A(16) to octal

Which of these has the most 1's in its binary representation? 414(8) 1B5(16) 178(10) 200(16) 600(8)

How many 1's are in the solution to this expression? (743(8) – AF(16) + 110100101000(2) ) * 256(10)

What is the solution to this expression in hexadecimal? (23(8) + A3(16) )/ 2(10)

Which is the largest? F1(16) 375(8) 10F(16) 264(10) 11111000(2)

Simplify the following and convert the answer to binary: 101(2) * 3(10) + 11(16) – 52(8) / 6(10)

Answers:

37552

1B5

10F

11001

Recursive functions:

Find f(12)

Find f(9)

Find f(10,2)

Find f(100)

Find f(1,10)

Answers:

What does this program do?

Answers:

304

BSTs and Heaps:

Make a binary search tree and a heap out of the word KEYBOARD. In the replies, tell me the depth, internal path length, external path length, how many external nodes there are, and which nodes are leaf nodes for both the BST and the heap.

In case you need a refresher, overviews of all topics can be found here: http://www.categories.acsl.org/wiki/index.php?title=Main_Page