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
16
Q
database
A
- can be implemented as
- indexed file
- linked list
- tree structure
- records are written in and remain in order of entry
- various methods use to locate needed records
17
Q
indexed file
A
= keeps all data in one data file
- maintains one separate key file for each key field (may be one or more key fields)
- searches in key file to find record number corresponding to a given piece of data
- updates key files each time records are added to data file
18
Q
flat file
A
- only one file (no separate index file)
- has only one key field by which records are located
19
Q
linked list
A
- a technique for locating records in a flat file
- each record contains pointer to next record in key sequence
- two pointers change whenever a record is added or deleted
20
Q
binary tree structure
A
- each record contains two pointers, to next higher and next lower record in key sequence
-records are referred to as nodes; first record is root node - node above is called parent; node below is child or offspring
- number of comparisons needed is
1 + (log n / log 2)
21
Q
hierarchical database
A
- contains records in an organized, structured format
- organizes records according to one or more indexing schemes
- each field within a record not normally directly accessible
22
Q
relational database
A
- stores all information in the equivalent of a matrix
- no index files, pointers, and so on needed to find, read, edit or select information
- information can be accessed directly by referring to field name or field value
23
Q
artificial intelligence (AI)
A
- the capacity of a machine to
- -> absorb and organize new data
- -> learn new concepts
- -> reason logically
- -> respond to inquiries
24
Q
expert systems
A
- learn rules from sets of events that are entered whenever they occur
- once the rules are learned, can give advice, make predictions and diagnoses, or draw conclusions
25
testability
determines:
- ability to detect and correct errors
- verify limiting operation
- determine functionality
26
software fault tolerance
designed into a system by
- synchronizing operations
- implementing checkpoints
- logging
- programming recovery techniques
