Chapter 21 Questions
Multiple Choice
1. A file contains ______ that are organized into blocks.
a. records
b. locations
c. names
d. addresses
2. The number of records in a block is a function of what?
a. the programming language
b. the size of the records in the file
c. the brand of the computer
d. implementation of the data structure
3. A location which temporarily stores data is called a
a. bucket
b. bag
c. buffer
d. record
4. When considering an algorithm’s efficiency when working with external data, what is the
dominant factor?
a. the brand of the computer
b. the programming language
c. the skill of the programmer
d. the time required for block access
5. Which of the following is the most appropriate for sorting external data?
a. merge sort
b. radix sort
c. selection sort
d. bubble sort
6. Hashing implementation is not good for which of the following operations on external data?
a. retrieval
b. sorted traversal
c. addition
d. removal
7. An external data collection can be organized as a balanced search tree. What are the pointers to
the child pointers?
a. search keys
b. index values
c. block numbers
Chapter 21 Questions
d. hash numbers
8. If searching an external data collection organized as a balanced search tree, what is actually
organized as the external search tree?
a. the data file
b. the hash index
c. the blocks
d. the index file
9. If a node N in a search tree is to have m children, how many key values must the node contain?
a. m – 1
b. m + 1
c. 2m – 1
d. log2 (n – 1)
10. What is a good motivation for having multiple index files for external data?
a. to save external file space
b. allows multiple data organizations
c. splits up the data easier
d. save internal data storage
Chapter 21 Questions
True or False
1. External storage exists after program execution.
2. Generally there is less external storage than internal memory.
3. Without direct access files, it would be impossible to support the data-management operations
efficiently in an external environment.
4. A file of integer records will have less records per block than a file of student records.
5. According to the text, you can read and write a block of records, but you cannot read or write an
individual record.
6. To need to operate on only a single record of the file, there is no need to access an entire block
from the file.
7. Some programming languages have commands that make it appear that you are accessing one
record at a time, not a whole block.
8. Even if records are stored in a sorted file, it is still not possible to use a binary search algorithm to
retrieve a specified record.
9. An index to a data file is conceptually similar to an index to an array.
10. In general an index record is larger than a data record.
11. It is possible (and can be useful) to keep multiple index files on a single data file.
12. Use of an index file increases the number of required block accesses of the data file, especially
for adds and removals.
13. When external hashing is used, you hash the index file instead of the data file.
14. It is not possible to organize an index file as an external 2-3 tree.
Chapter 21 Questions
15. In an external environment, the advantage of keeping a search tree short far outweighs the
disadvantage of performing extra work, such as comparisons, at each node.
16. Never access the search keys of the index records without accessing the data record.
17. If a traversal must display the entire data record (and not just the search key), the B-tree
implementation is less attractive.
Chapter 21 Questions
Short Answer
1. What are the two general ways that files are accessed for processing?
2. You wish to access a specific data entry in a file. Contrast the ways this must be done in
sequential access and direct access.
3. Suppose a sequential file is being updated with adds and removals. Remembering that multiple
records are stored in blocks, what may require costly file accesses?
4. If using an index file, why don’t you need to keep the data file in any particular order?
5. Although you do not need to organize the data file, why must you organize the index file?
6. Enumerate the steps required for addition of a record when an index file uses external hashing as
specified in the text.
7. What are the characteristics of a B-tree of degree m ?
8. What are the steps for removal of a multiply indexed record where one of the index files is by
name, the other is by social security number.