Study Questions for quiz #3
Practice Questions for Quiz
#3.
Heap
Questions:
Text Chapter 21
questions:
21.1, 21.2, 21.3,
21.6, 21.8, 21.10, 21.11,
21.12
B-Trees
Questions:
Use the definition
of a B-Tree given below for the next two
questions.
A B-tree of order M
is a M-ary tree, M >= 2 with the following
properties:
1. The root has
at least two subtrees unless it's a
leaf.
2. Each non-root holds k-1
keys, and each non-root and non-leaf also holds
k pointers to subtrees,
where the ceiling of m/2 <= k <=
m.
3. All leaves are on the same
level.
4. The keys in each node
are in non-decreasing order.
5.
The children are in order:
the
keys in the first i children are less than or equal to the ith
key
the keys in the last m-i
children are greater than or equal to the ith
key
Question 1. What is the
maximum number of keys that a B-Tree of order 6 (at most five keys per node)
and of height 4 hold? How many disk accesses in the worst case would be
required to find any key, assuming one block on disk can hold one node? How many
keys can a B-Tree of order m and of height h
hold?
Question 2.
Construct a B-Tree of order 3 (at most two keys per node) first for the
insertion sequence 1, 5, 3, 7, 2, 4, 6 and then for the insertion sequence 1, 2,
3, 4, 5, 6, 7. Which sequence of insertions is preferable?
Why?
External Merge
Sorting
Suppose that there are
32 records to be sorted and the data is stored on external memory. Using an I/O
model where reading or writing one record counts as one external memory access
answer the following
questions.
a) How many external
memory accesses (reads and writes) are used to sort the data using a 2-way merge
sort? Assume that all you can do in internal memory is compare two numbers and
output the smallest.
b) How
many external memory accesses (reads and writes) are used to sort the data using
a 4-way merge sort? Assume that all you can do in internal memory is compare
four numbers and output the
smallest.
c) What if we have
enough internal memory to make initial runs of 8 sorted records. How many
external memory accesses (reads and writes) are used to sort the data using a
2-way merge sort? 4-way merge
sort?
d) Illustrate how
the 2-way and 4-way merge sorts of part c) would work using the following set of
random integers.
41 40 35 6
74 8 87 89 99 24 2 8 44 19 93
23
63 91 4 5 70 57 38
59 3 4 83 83 46 18 53 17
Posted: Mon - March 28, 2005 at 08:20 PM