Uah Cs221 Final Exam

Front 1

Five steps in software development

Back 1

1. Requirements specification

2. Analysis

3. Design

4. Implementation

5. Development

Front 2

5 types of software testing (in order)

Back 2

1. Statement

2. Unit

3. Integration

4. Acceptance

5. Regression

Front 3

Big-O Notation

Back 3

constant O(1)

logarithmic O(log n)

linear O(n)

n log n O(n log n)

quadratic O(n^2)

cubic O(n^3)

exponential O(2^n)

exponential O(10^n)

Front 4

statement of work

Back 4

The document, usually received from a customer, that states specifically the customer's requirements for a software product. The SOW is created during the Requirements Specification phase of software engineering

Front 5

requirements definition document

Back 5

A statement of what is to be provided by a computer system or software product

Front 6

software requirements specification

Back 6

define in detail exactly what the software must do

Front 7

software design document

Back 7

a detailed plan for the organization of the software including a description of any new algorithms and a detailed description of how the code will be organized and how each unit of code will be tested

Front 8

software test plan

Back 8

The document which is a detailed, organized plan for testing a piece of software. The STP includes a description of all tests to be performed, the procedure for performing the test, the inputs for the test, and the expected outputs. The STP is created during the Testing phase of software engineering, but the normal approach is to begin working on a rough draft of the STP during the design phase so that every part of the system included in the design has a test or tests included in the STP

Front 9

abstract data type

Back 9

A data type whose properties (domain and operations) are specified independently of any particular implementation. Examples: List, Stack, Queue, Tree, Graph, Set.

Front 10

acceptance testing

Back 10

use the RSD to guide the testing of requirements

Front 11

algorithm

Back 11

an outline of the procedure for solving a problem. This includes (1) the actions which are to be taken, and (2) the order in which the actions are to be performed.

Front 12

analysis of algorithm

Back 12

A measure of the amount of resources necessary to execute a section of code. The efficiency or running time of an algorithm stated as a function relating the input size/length to the number of steps (time complexity) or storage locations (space complexity)

Front 13

Best fit memory allocation

Back 13

makes the best use of memory space but slower in making allocation

Front 14

binary search

Back 14

finds the position of a target value within a sorted array

Front 15

bottom up program design

Back 15

The process of program design in which the problem is defined in terms of low level simple objects that interact in some way. Design progresses from the simple objects and how they interact upward to more complex interactions. Also called object oriented programming. Focus is on the data objects in the software system.

Front 16

call by reference

Back 16

A function calling method in which the address or reference to the actual arguments are passed to a function.

Front 17

call by value

Back 17

A function calling method in which only copies of the values stored in arguments to the function are passed into the function.

Front 18

data abstraction

Back 18

The separation of a data type's logical properties from its' implementation. Another term for Data Encapsulation

Front 19

driver function for software testing

Back 19

A special function written to use as a testing function. It passes known inputs to selected functions and reports the returned values. * used to test lower level functions

Front 20

dynamic memory allocation

Back 20

Allocating memory for a variable, structure, or class instance after a program has started running

Front 21

encapsulation

Back 21

The separation of the representation of data from the applications that use the data at a logical level. A programming language feature that enhances information hiding. Another term for Data Abstraction

Front 22

first fit memory allocation

Back 22

the operating system begins at the start of primary memory and allocates memory from the first hole it encounters large enough to satisfy the request-to reduce amt of time spent analyzing available spaces

Front 23

fragmentation(referring to the heap)

Back 23

memory space being wasted-to avoid heap fragmentation memory management if performed by the person versus the OS

Front 24

greedy algorithm

Back 24

one that attempts to find the best solution by the shortest means possible

Front 25

heap

Back 25

A complete binary tree with values stored so that no child has a key value greater than its parent.

Front 26

information hiding

Back 26

The practice of hiding the details of a function, class, or data structure with the goal of controlling access to the details of the implementation of a class or structure

Front 27

integration testing

Back 27

replace all stubs and drivers with the real functions

Front 28

object oriented programming

Back 28

"Bottom-up program design"

Front 29

procedural programming

Back 29

functional decomposition

"top-down program design"

Front 30

recursion

Back 30

the ability of a function to call itself

Front 31

regression testing

Back 31

testing done after bug fixes

Front 32

sequential search

Back 32

each element of the array is compared to the key, in the order they occur in the array, until the first element matching the key is found

Front 33

software validation

Back 33

the process of determining the degree to which the software does, in fact, produce the result results that satisfy the original requirement

Front 34

software verification

Back 34

the process of determining the degree to which software functions correctly

Front 35

static memory allocation

Back 35

Memory that is allocated at program start up or when a function is called. Variable declarations in a program result in static memory allocation.

Front 36

stepwise refinement

Back 36

The process in software design of starting off at a high level of abstraction and working down through an interative process to add more and more detail to the design

Front 37

stub function for software testing

Back 37

A special function written to use as a testing function. A stub returns known outputs to a calling function to determine how the calling function handles the returned values. Used to test higher level functions

Front 38

top-down program design

Back 38

functional decomposition/procedural programming

Front 39

unit testing

Back 39

use separate tests for each possible path through a function

Front 40

2-3 tree

Back 40

each node may contain 1 or 2 keys and have 2-3 subtrees

Front 41

AVL tree

Back 41

For any node in the tree the height (longest distance from root to leaf) of its left sub-tree is the same as the height of its right sub-tree, or it differs at most by 1

Front 42

B-tree

Back 42

each node may contain a large number of keys

Front 43

binary tree

Back 43

A tree structure in which each node is an empty tree or a node that has left and/or right children which are binary trees. The key in the parent node is greater than the key in the left child and less than the key in the right child

Front 44

child node

Back 44

node whose parent is the root

Front 45

complete binary tree

Back 45

Trees with all their leaves on one level, or two adjacent levels with the bottom most leaves as far left as possible. A full binary tree is a complete binary tree.

Front 46

internal node

Back 46

A node in a binary tree that is neither the root nor a leaf

Front 47

leaf node

Back 47

a node in a binary tree that has no children

Front 48

parent node

Back 48

a node having children

Front 49

root

Back 49

the first node of a tree

Front 50

sub-tree/branches

Back 50

internal nodes beneath the root

Front 51

trie

Back 51

ordered tree data structure

Front 52

adjacent vertices

Back 52

two nodes which share a common link

Front 53

adjacency set

Back 53

a way of implementing a graph in memory and connections between nodes are represented in a linked list of connections for each node

Front 54

adjacency matrix

Back 54

a way of implementing a graph in memory in which the connections between nodes are represented in a 2D array

Front 55

connected components

Back 55

a subset of nodes of a graph for which there is a path from any one to all others in the subset

Front 56

connected vertices

Back 56

when there exists a path between two vertices they are said to be this

Front 57

cycle

Back 57

a path that begins and ends on the same node

Front 58

degree of a vertex

Back 58

the number of links in a graph for which a given node is one of the endpoints

Front 59

directed graph

Back 59

a graph in which the links between nodes go only in one direction

Front 60

edges

Back 60

the connections between nodes in a graph

Front 61

minimal spanning tree of a graph

Back 61

determining the shortest path to visit every vertex in the graph

Front 62

path

Back 62

a list of nodes indicating those that must be visited in order to get from one node to another

Front 63

predecessors of a vertex

Back 63

all nodes in a graph from which a given node has links coming from the other nodes to the given node

Front 64

simple cycle

Back 64

a path of three or more nodes that starts and ends on the same node and never visits any node more than once, except the starting node

Front 65

successors of a vertex

Back 65

all nodes in a graph to which a given node has links going from the given node to the other nodes

Front 66

vertices

Back 66

the nodes in a graph which may be represented by a structure or a class object

Front 67

weighted graph

Back 67

a graph in which the links between nodes have some value associated with them

Front 68

component(base) type

Back 68

the data type of the items composing the set

Front 69

subset

Back 69

a set X is a subset of Y if each item of X is also in Y

Front 70

universal set

Back 70

the set containing all of the values of the component type

Front 71

empty set

Back 71

a set with no members

Front 72

cardinality

Back 72

number of items in a set

Front 73

set intersection

Back 73

returns a set made up of all of the items in both of the input sets

Front 74

set difference

Back 74

returns a set made up of all items that are in the first set but not the second

Front 75

symmetrical difference

Back 75

returns a set made up of all items that are in the first or second set but not both

Front 76

set union

Back 76

returns a set made up of all items that are in either of the input sets

Front 77

cluster

Back 77

a series of adjacent filled entries in a hash table

Front 78

collision

Back 78

when 2 keys hash to the same index in a hash table

Front 79

hash table

Back 79

an array of data structures or a large number of records stored in a file on disk.

Front 80

hash function

Back 80

the technique used to calculate a unique index into the hash table from a key.

Front 81

buckets

Back 81

hash table is divided up into equal sized groups of locations and hash indices are calculated for the number of groups, thus each index in the hash table can hold several records

Front 82

chaining

Back 82

a linked list of all records is hashing to the same index are created from the first record in that index

Front 83

linear probing

Back 83

a scheme for resolving hash collisions by sequentially searching the hash table for a free location

Front 84

load factor

Back 84

the ratio of the number of filled entries in a hash table to the number of entries in the table

Front 85

perfect hash function

Back 85

a hash function that maps keys uniformly and randomly into the table without collisions

Front 86

class

Back 86

A structured type in a programming language containing variables and the functions which operate on those variables. Used to represent an abstract data type.

Front 87

constructor function

Back 87

Functions that create an abstract data type

Front 88

destructor function

Back 88

called when objects are destroyed/deallocated

Front 89

function overloading

Back 89

The ability to have two or more functions in a class with the same name but different number and/or types of arguments

Front 90

implementation file

Back 90

the file that implements the class/cpp file

Front 91

instantiation

Back 91

The process of dynamically allocating memory for an object

Front 92

polymorphism

Back 92

ability to process objects differently depending on their data type or class; ability to redefine methods for derived classes

Front 93

private

Back 93

Variables and functions in a structure or class which can only be accessed from within the object.

Front 94

protected

Back 94

Variables and functions in a structure or class which may be accessed only from other functions within the class or from functions in objects that are sub-classes of the class.

Front 95

public

Back 95

Variables and functions in a structure or class which are global and may be accessed from anywhere if there is access to the object. Default state for member variables of structures.

Front 96

show how to define a data structure containing an int stockNum, double price, and char array called desc of 128 characters

Back 96

struct InvItem

{

int stockNum;

double price;

char desc [128];

}; ** don't forget this semicolon!

Front 97

declare a pointer called sPtr to a structure called InvItem, then dynamically allocate memory for the struct and set sPtr pointing to it

Back 97

InvItem *sPtr;

InvItem = new sPtr;

sPtr = new InvItem();

Front 98

copy the values 54321, 9.95 and "left-handed widget" into stockNum, price, and desc fields of a new data struct sPtr points to

Back 98

sPtr -> stockNum = 54321;

sPtr -> price = 9.95;

strcpy(sPtr ->desc, "left-handed widget");

Front 99

write the setID function of the simple class InventoryItem containing the variable m_iID of type int

Back 99

void InventoryItem::setID(int x)

{

m_iID = x;

}

Front 100

declare a pointer called ItmPtr to a class of type InventoryItem; dynamically instantiate an instance of the class and set the pointer ItmPtr pointing to it; call setID in the instance that ItmPtr is pointing to it and pass it the value 12345

Back 100

InventoryItem *ItmPtr;

ItmPtr = new InventoryItem;

ItmPtr -> setID(12345);

Front 101

create a vector called strVec to hold strings

add the string "testing" to the vector

remove the last item from the vector

Back 101

vectorstrVec;

strVec.push_back("testing");

strVec.pop_back;

Front 102

write a function that traverses a binary tree; call a function called doSomething(TreeNode *thisNode) for each node in the tree

Back 102

void MyTree::Traverse(TreeNode *rt)

{

if (rt !=Null)

{

traverse (rt -> left)

doSomething (rt)

traverse (rt -> right)

}

}

Front 103

write a recursive function called SumIt which calculates a sequence of numbers; the function takes 2 arguments which are ints and returns an int

Back 103

int SumIt(int m, int n)

{

if (m==n)

return m+m;

else

return (m+m) + SumIt (m+1, n);

}

Front 104

using set template do the following:

create set of string objects called names

add the name jason to the set

declare an iterator called itr to items in the set names;

locate the name jason in names and set the iterator itr to reference it

Back 104

setnames;

names.insert ("jason");

set ::iterator itr;

itr = names.find ("jason");

Front 105

Bubble sort

Back 105

A type of transposition sorting; the simplest sorting method (scanning a swapping)

As you repeatedly scan the array of records making comparisons, the lower key values gradually move to the start of the array

Front 106

Insertion sort

Back 106

type of Insert and Keep sort;

Done by moving items out of a set of unsorted records into a set of sorted records;

Front 107

Tree sort

Back 107

type of insert and keep sort;

is already in order if an in-order traversal is made;

uses insertNode function and performs an in-order traversal to list records in sorted order

Front 108

Selection sort

Back 108

type of priority queuing sort:

divides array into sorted/unsorted sections and repeatedly removes the record with the largest key from unsorted section and moves it to the front of the sorted section

Front 109

Heap sort

Back 109

type of priority queuing sort:

repeatedly dequeuing structures from the heap and moving them into an array will give a sorted array

Front 110

quick sort

Back 110

type of Divide and conquer:

partitions data into 2 smaller groups arbitrarily and places all keys <= "pivot key" on the left side of the array and all keys >= "pivot key" on the right side; recursively calls QuickSort() to the left and right halves then merges the two arrays

Front 111

merge sort

Back 111

type of divide and conquer:

frequently used to sort very large collections of data; divide array into 2 parts and recursively call mergeSort() to sort the first half of the array and same to second half respectively; merge the two arrays

Front 112

shell sort

Back 112

type of diminishing increment sort:

subdivides the array of structures into smaller pieces by selecting every nth record then sorting that group of structures

Front 113

proxmap sort

Back 113

type of address calculation sort;

conceptually similar to hashing; uses a variation on hashing with buckets of different sizes

Front 114

radix sort

Back 114

type of address calculation sort;

uses keys that must be integers of some standard length or keys that can be mapped to this; sort to all 0s,1s,2s etc. then arrange groups into ascending order; repeat this sorting with the 10s, 100s, 1000s etc.

Front 115

define how an adjacency set works

Back 115

a linked list represents vertices and another linked list represents edges

Front 116

define how an adjacency matrix works

Back 116

an array of structs or classes represents vertices while a 2D array of int represents edges

Front 117

declare static instance of a structure and declare a pointer to that structure statically then dynamically

Back 117

struct Name

{ int x;

char c;

char array[50];}

//static instance

Name instance1;

Name *sptr;

Name *sptr = &instance 1;

//dynamically

Name *sptr;

sptr = newName;

Front 118

declare variables and pointers to those variables

Back 118

int iVar;

double dVar;

char cVar;

//pointers

int *iptr = &iVar;

double *dptr = &dVar;

char *cptr = &cVar;