Software Development Part 2 Flashcards
1
Q
sequential file structure
A
- contains consecutive records and is read starting from beginning
- typical of data on magnetic tape
2
Q
indexed sequential file
A
- a file with a separate index file to help locate records more quickly random file structure
3
Q
-random file structure
A
- allows access to any record without starting at beginning of file
4
Q
indexing
A
a means of specifying the order of records without actually changing their physical order
5
Q
index file (key file or keyword file)
A
ordered list of items with references to the complete record
6
Q
key field (record index)
A
field in the record that is indexed
7
Q
sorting routine
A
- places data in ascending or descending numerical or alphabetical order
8
Q
sorting routine
A
- puts dat in order
- -> from highest from lowest numerically
- -> from lowest to highest numerically
- -> alphabetically
- -> reverse alphabetically
common methods
- successive minima
- bubble sort
- insertion sort
9
Q
successive minima
A
- list is searched to find smallest element
- smallest element is brought to top of list
- process is repeated for remaining elements
- n(n-1)/2 comparisons needed to sort n items
- when n is large n^2/2 is sometimes used as approximation
10
Q
bubble sort
A
- first and second elements in list are compared
- if first is larger, positions are switched
- second and third elements are the compared, and so on
- process continues till end of list is reached, constituent one pass through data
- process repeated until one pass through the data results in no exchanges
- so called because smaller elements “bubble” to top of list
- on average, n^2/2 comparisons needed
11
Q
insertion sort
A
- elements are ordered by rewriting them in proper sequence
- after the proper position of an element is found, all elements below that position are bumped down one places
- the vacancy is filled by the inserted element
- About n^2/ 2 comparisons are needed at most
- average number of comparisons is about n^2 /4
12
Q
linear search (sequential search)
A
- finds an element if a group of records is randomly organized
- at best, one comparison is required
- at worst, n comparisons are required in a list of n elements
- average of n/2 comparisons
13
Q
binary search
A
- faster than linear search if records are in ascending or descending order
- checks middle element, then removes half of list from consideration
- checks middle element from remainder of list, and so on
- maximum number of required comparisons in a list of n elements is log2 (2 is subscript down) n= log n/ log 2
14
Q
hashing function
A
- procedure by which a numeric or nonnumeric key is converted into a record number
- for example, may convert each customer’s name into an integer, so that records for that customer are stored at that location number
15
Q
collision
A
- occurs when hashing function assigns same record number to different keys
- chaining, linear probing, and double hashing are techniques used to resolve such collisions