Data structures

Question 1

abstract data type

Answer 1

Logical description of how we view the data and possible operations

Question 2

4 operations of a queue

Answer 2

Add item to the rear of the queue
Remove item from the front of the queue
Check if the queue is empty
Check if the queue is full

Question 3

Dynamic data structure

Answer 3

Allocates and deallocates memory from the heap
Excessive allocation of memory with our deal location may cause overflow
Python- list

Question 4

Static data structure

Answer 4

Cannot grow shrink or be freed during execution
An array is a static data structure

Question 5

4 operations of stack

Answer 5

Add an item to the top
Remove an item from the top
Check if the stack is full
Check if the stack is empty

Question 6

Pseudo code for stack

Answer 6

Push - adds item to the top of the stack
Pop - removes and returns the item on the top of the stack
Is full - checks if the stack is full
Is empty - checks if the stack is empty

Question 7

Underflow

Answer 7

Attempting to pop from a stack that is empty

Question 8

What is the call stack

Answer 8

System level data structure
Provides mechanism for passing parameters and return addresses to subroutines
Call stack is hidden in high level languages

Question 9

Subroutine calls in the call stack

Answer 9

The parameters are saved unto the stack
Local variables are saved onto the stack
Address to which execution returns after the end of the subroiutine is saved onto the stack
Execution is transferred to subroutine code

Question 10

Subroutine execution in the call stack

Answer 10

Stack space is allocated for local variables
Subroutine code executes
Return address is retrieved
Parameters are popped
Execution is transferred back to the return address

Question 11

What is a collision

Answer 11

When an algorithm generates the same address for different primary keys

Question 12

What is the midsquare method

Answer 12

• first square the item
• extract some portion of the resulting digits
• perform the mod step to get an address

Question 13

the folding method

Answer 13

• divide the item into equal size pieces
• add the pieces together
• perform the mod step to get an address

Question 14

what is an undirected graph

Answer 14

it is undirected because there are no arrows on the edges indicating direction

Question 15

definition of a tree

Answer 15

tree is connected undirected graph with no cycles