Data Structuers and Functions Flashcards
What are the two ways of collecting data items together?
Giving collection a name
Accessing the items individually or as a collection
What is a named collection of homogeneous items in which individual items are accessed by their place within the collection?
Array
What is the place within a collection?
Index
Where do most programming start?
They start a 0
What is the result of this code?
Integer numbers [10]
//Declares numbers to hold 10 integer values
Write “Enter 10 integer numbers, one per line”
Set Position to 0// set variable positions to 0
WHILE (position < 10)
Read in numbers [position]
Set position to position + 1
//continue with processing
Algorithm to put values into the places in an array
What is a heterogeneous group of items where individuals items are accessed by name?
A record
What can a record collection contain?
Integers, real values, strings or any other type of data
What are records a good choice for?
Bundling items together that relate to the same object
What looks at each item in turn and compares it to the one for which we are searching. If it matches, we have found the item. If not, we look at the next item?
Sequential Search
What are special Boolean operations?
AND, OR, and NOT
What is a binary search?
Look for an item in an array using a different strategy
What strategies does a binary search use?
Divide and conquer!
what is a selection sort?
It mirrors how we sort a list of values if we had to do it by hand
What operator returns true if both expressions are true and false otherwise?
AND operator
What operator returns false if both expressions are false and true otherwise?
OR operator
What operator changes the values of the expression?
NOT operator
What stops looking when we pass the place where it would be if it were present in the array?
Sequential search in a Sorted Array
What search type can use divide and conquer?
Binary search
True or False
In a binary search, it starts from the first point and then moves its way down the list, pushing things into the right order.
False
A binary seach beings in the middle of the array. If item is less than t
What sorts similarly as we would cards in a deck? As it starts the sort, it will move cards in order as it goes through the deck and moves it into the right spot as it gets to the next card.
Selection sort
What starts at the end of the array, swapping the items whenever the bottom element of the pair in smaller than the one above it?
Bubble Sort
What algorithm is the easiest to use?
Selection Sort
What sorts “bubbling up”? Swapping the inserted item into the correct spot?
Insert sort
What is a container whose properties (data and operations) are specified independently of any particular implementation?
Abstract Data type (ADT)
What is an implementation of a composite data field in an abstract data type?
Data Structures
Whose sole purpose is to hold other objects?
Containers
What is an abstract composite structure in which accesses are made at only one end?
Stacks
What process is referred to as last in first out (LIFO)?
Stacks
What says that the item removed is the item that has been in the stack the shortest time?
Stacks
Whose entire behavior is specified through the removal operation?
Last in, first out (LIFO)
What is an abstract structure in which items are entered at one end and removed from the other end?
Queues
What is First In, First Out (FIFO)?
Queues
What occurs as naturally in programming as they do in real life?
Lists
What items are homogeneous, the items are linear, and lists have varying lengths.
Lists
What does it mean when an item except the first has a unique component that comes before it, andeach item except the last has a unique component that comes after it?
Linear
What usually provides operations to insert an item?
Lists
What operator is used to insert an item in a list?
Insert
What operator is used to delete an item from a list?
Delete
What operator is used to check whether an item is there?
IsThere
What operator reports the number of items in a list?
GetLength
What operators have some mechanism for allowing the user to view each item in sequence?
Reset, GetNext, MoreItems
What should you not mistake for an array?
Lists
What is an implementation of a container where the items are stored together with information on where the next item can be found?
Linked Structure
What are actual language constructs?
Subprograms
What operator needs a value to insert into it?
Insert
What operation needs the list to reset?
Reset
What operator needs the list to see if more items remain to be returned?
MoreItems
What operator needs the list as input and returns the next item in the list?
GetNext
What is a list of identifiers or values with which the subprogram is to work?
Parameter List
What appears in parentheses beside the subprogram name?
Parameter
What is sometimes called formal parameters?
Parameters
What is it when a subprogram is called, the calling unit lists the subprogram name, followed by a list of identifiers in parentheses?
Arguments
What represents actual variables in the calling unit with which the subprogram is to work?
Arguments
What calling unit gives a copy of the argument to the subprogram?
A Value Parameter
What is the calling unit that gives the address of the argument to the subprogram?
A reference parameter
Fill in the blank.
To access a_________, the subprogram accesses the contents of the address listed on the message board.
Reference Parameter
Fill in the blank
To access a________, the subprogram accesses the contents of the message board.
A value parameter
Fill in the blank
When a parameter is a__________, the subprogram knows to manipulate the contents of the address on the message board.
Reference Parameter
What does this diagram represent?
The difference between value parameters and reference parameters
What is a collection of elements, each containing a reference to the next element?
Linked List
What describes a stack?
Last In First out (LIFO)
What is the primary characteristic of a queue?
It has FIFO access
What is a subprogram?
A sequence of program instructions that perform a specific task
In pseudocode, how would you call a function named CalculateSum with two parameters a and b?
1) Execute CalculateSum with a, b
2) Csum = CalculateSum(a, b)
3) CALL CalculateSum a b
4) CalculateSum(a, b)
What is the primary purpose of using subprograms in a program?
To allow for code reuse and better organization
Which operation is used to add an element to the top of a stack?
Push
