C H A P T E R
13
Data Storage Strutures
Solutions for the Pratie Exerises of Chapter 13
Pratie Exerises
13.1
Answer:
a. Although moving reord 6 to the spae for 5 and moving reord 7 to the
spae for 6 is the most straightforward approah, it requires moving the
most reords and involves t he most aesses.
b. Moving reord 7 to the spae for 5 moves fewer reords but destroys any
ordering in the le.
. Marking the spae for 5 as deleted preser ves ordering and moves no
reords, but it requires additional overhead to keep trak of all of the
free spae in t he le. This method may lead to too many holes in the
le, whih if not ompated from time to time, will aet performane
beause of the redued availability of ontiguous free reords.
13.2
Answer:
We use
~
i
to denote a pointer to reord
i
.
a. See Figure 13.101.
b. See Figure 13.102. Note that the free reord hain ould have alter na-
tively been from the header to 4, from 4 to 2, and nally from 2 to 6.
. See Figure 13.103.
75
评论0