Chapter 8--abstract Data Types & Subprograms

Question 0

Data structure?

Answer 0

The implementation of a composite data field in an abstract data type

Question 1

Abstract data type?

Answer 1

A container whose properties are specified independently of any particular implementation

Question 2

Discuss stacks.

Answer 2

LIFO. Adding an item is called a “push”. Removal is called a “pop”.

We do need operations that check if a stack is empty, because popping an empty stack would cause an error.

Question 3

Give the multiple names for adding and removing queue items.

Answer 3

Enqueue, enque, enq, enter, insert.

Dequeue, deque, deq, delete, remove

Question 4

List the 3 properties of lists.

Answer 4

The items are homogeneous, linear, and lists have varying lengths

Question 5

Name some common list operations.

Answer 5

Insert, delete, check if an item is there (IsThere), and get number of total list items (GetLength). Also viewing items in sequence (Reset, GetNext, MoreItems).

Question 6

Linked structure?

Answer 6

An implementation of a container where the items are stored together with information on where the next item is.

A list can be thought of as a linked structure. Linked structures contain nodes, which contain 2 things–the user’s data and info on where to find the next node.

Question 7

What does the end of a list consist of?

Answer 7

A link that contains “null”, which is indicated by a /

Question 8

What is a binary tree node that has no children called?

Answer 8

A leaf node

Question 9

Binary search tree?

Answer 9

The value in any node is greater than any value in its left sub tree, and less than any value in its right subtree

Question 10

“Parameter list”?

Answer 10

A list of identifiers or values with which the Subprogram is to work. It appears in parenthesis beside the Subprogram name.

It is a mechanism for communicating between two parts of a Subprogram.

Question 11

Parameters? Give alternate name as well.

Answer 11

A.K.A. formal parameters. They are identifiers that appear in parentheses beside the Subprogram name.

Question 12

Arguments?

Answer 12

The identifiers listed in parenthesis on the Subprogram call; a.k.a. actual parameters.

Question 13

What is the most common way that arguments are substituted for parameters on a Subprogram call?

Answer 13

Position

Question 14

Define/name the two types of called parameters.

Answer 14

Value parameters/arguments cannot be changed by the Subprogram, b/c the Subprogram only is given their value.

Reference parameters/arguments CAN be changed by the Subprogram, because the Subprogram is given their address.

Question 15

Define “put on the message board”.

Answer 15

Passed by the calling unit

Question 16

Graph?

Answer 16

A data structure that consists of a set of nodes with edges that relate the nodes to each other

Question 17

Directed graph?

Answer 17

A graph in which each edge is directed from one vertex to to another (or the same) vertex

Question 18

Undirected graph?

Answer 18

A graph in which the edges have no direction

Question 19

Another name for an edge in a graph?

Answer 19

Arc

Question 20

Lists, stacks, queues, and trees are all just _________?

Answer 20

Holding containers

Question 21

Starting point of a binary tree?

Answer 21

Root

Question 22

Every node in a binary search tree has ______?

Answer 22

One parent