CS-242 - DATA STRUCTURES - TEST #2 - Feb. 28, 2002
PLEDGE: I have not violated the Honor Code in completing this test. _____________________
READ THESE NOTES
Sign the pledge above and initial each sheet. Show all of your work.
You may omit any ONE question but you must indicate which one you want omitted by writing OMIT next to it and circling the question number.
Do not spend an excessive amount of time on any one question. All questions count the same.
If you have trouble with a question, skip it and come back to it later.
You may explain your answers if you choose to.
This is a Take-Home Test. You MUST place the completed test in my mailbox or under my office door before Sat., March 2, 2002.
- An older disk drive has the following specifications.
- Number of Surfaces = 20
- Number of tracks per surface = 2000
- Number of sectors per track = 400
- Number of bytes per sector = 1024
- Number of sectors per cluster = 16
- Rotational Speed = 7200 rpm
- Interleave Factor = 2
- Track to Track Seek Time = 20 ms
- Average Seek Time = 80 ms
- What is the total storage? ______________
- What is the average latency time? ______________
- On average how long does it take to read a 1 Mb file? ________________
Be sure to account for seek times, latency time, etc. You MUST show your work.
- What is the consequence of having only one I/O buffer?
- Why is it better to have two input buffers and two output buffers rather than one of each?
- A) What is the purpose of interleaving sectors?
B) What is the advantage of a small cluster size and what is the advantage of a large cluster size?
- A disk drive has a cluster size of 16 kb and each file is required to occupy at least one cluster. Most files on the disk are from 1 kb to 4 kb in size. This results in much wasted space and is referred to as ________________________________________
- A disk drive is 90% full. Most newly created files are not able to occupy contiguous space but rather broken into clusters that are linked together throughout the disk. This can lead to _________________________________________
- Disk I/O accounts for 98% of the time required for a particular external sort of a transaction file for Macrohard Software Inc. (MSI). The remaining 2% of time is consumed by replacement selection, merge and other internal algorithms. Simple two-way merges are used. A sort of the transaction file typically produces about 500 sorted run files and takes about 100 minutes. MSI is considering several different strategies to speed up the sort. Approximately, how much time (in minutes or seconds) may be saved by employing each of the following? Show your work!
- Replace existing main memory with memory that is about 50% faster and replace the CPU with a CPU that is 50% faster.
- Double the amount of memory using memory of the same speed.
- Switch from a 5400 rpm disk drive to a 7200 rpm disk drive that also has a 40% improvement in seek time.
- How much time might be saved by using a 10-way merge rather than a two-way merge for sorting MSI's transaction file described above? Show your work.
-
| _ 75 _ | _ 35 _ | _ 41 _ | _ 90 _ | _ 85 _ | _ 28 _ | _ 66 _ | _ 50 _ | _ 30 _ | _ 16 _ | _ 81 _ | _ 19 _ |
The list of integers above is given to replacement selection with a priority queue of size 3. Give the runs that are generated. Separate the runs with X.
- The read/write head of a disk drive is currently located over the first track of a platter with 1000 tracks. On average how many tracks will it cross to get to a random sector of data? _________________
- The read/write head of a disk drive is currently located over the middle track of a platter with 1000 tracks. On average how many tracks will it cross to get to a random sector of data? _________________
- A tiny, hypothetical computer has 10 pages of virtual memory (on disk) numbered 0 to 9 and 5 pages of physical memory (RAM) numbered 0 to 4. The following sequence of page requests are processed
| Strategy/Page | 0 | 2 | 5 | 0 | 2 | 5 | 6 | 9 | 9 | 2 | 6 | 0 | 1 | 5 | 4 | 0
|
| FIFO | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___
| ___ | ___ | ___ | ___
|
| LFU | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___
| ___ | ___ | ___ | ___
|
| LRU | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___
| ___ | ___ | ___ | ___ |
For each of the page replacement strategies given above, in each of the spaces write the number of disk reads required up to that point in time.
- In lab we compared three different versions of Insert for InsertSort.
Version 1 of Insert inserted a new element by swapping it with larger elements until it swapped into its correct position.
Version 2 of Insert used a linear search to determine where the new element belonged and then shifted down the larger elements to make room.
Version 3 of Insert used a binary search to determine where the new element belonged and then shifted down the larger elements to make room.
- One of the versions was almost 3 or more times faster than the others when applied to small data sets. Which version was it and why was it 3 times faster?
- One of the versions was slower than the others on small data sets but faster on very large data sets. Which version was it and why was it faster on large data sets?
- Explain why sequential file access is usually much faster than random file access.
- Memory locations that have been requested recently are likely to be requested again. This concept is known as ______________________________________________________.
Top of this page 
Home page 
