Software Development Part 2

Question 1

sequential file structure

Answer 1

• contains consecutive records and is read starting from beginning
• typical of data on magnetic tape

Question 2

indexed sequential file

Answer 2

• a file with a separate index file to help locate records more quickly random file structure

Question 3

-random file structure

Answer 3

• allows access to any record without starting at beginning of file

Question 4

indexing

Answer 4

a means of specifying the order of records without actually changing their physical order

Question 5

index file (key file or keyword file)

Answer 5

ordered list of items with references to the complete record

Question 6

key field (record index)

Answer 6

field in the record that is indexed

Question 7

sorting routine

Answer 7

• places data in ascending or descending numerical or alphabetical order

Question 8

sorting routine

Answer 8

• 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

Question 9

successive minima

Answer 9

• 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

Question 10

bubble sort

Answer 10

• 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

Question 11

insertion sort

Answer 11

• 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

Question 12

linear search (sequential search)

Answer 12

• 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

Question 13

binary search

Answer 13

• 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

Question 14

hashing function

Answer 14

• 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

Question 15

collision

Answer 15

• occurs when hashing function assigns same record number to different keys
• chaining, linear probing, and double hashing are techniques used to resolve such collisions

Question 16

database

Answer 16

• 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

Question 17

indexed file

Answer 17

= 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

Question 18

flat file

Answer 18

• only one file (no separate index file)

- has only one key field by which records are located

Question 19

linked list

Answer 19

• 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

Question 20

binary tree structure

Answer 20

• 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)

Question 21

hierarchical database

Answer 21

• 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

Question 22

relational database

Answer 22

• 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

Question 23

artificial intelligence (AI)

Answer 23

• the capacity of a machine to
• -> absorb and organize new data
• -> learn new concepts
• -> reason logically
• -> respond to inquiries

Question 24

expert systems

Answer 24

• 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

Question 25

testability

Answer 25

determines: - ability to detect and correct errors - verify limiting operation - determine functionality

Question 26

software fault tolerance

Answer 26

designed into a system by - synchronizing operations - implementing checkpoints - logging - programming recovery techniques