Stacks, queues and recursion Flashcards
What is a recursively defined procedure?
A procedure that defined in terms of itself
What is the role of the stack when a recursively defined procedure is executed?
To store local variables, parameters and and return addresses
What is an advantage of storing a tree in an array rather than linked nodes?
faster access// no memory wasted for pointers
Give one disadvantage of storing a tree in an array
Fixed size// cannot allocate memory dynamically// memory wasted if the array isn’t full
What is meant by a recursive subroutine?
A subroutine that calls itself
Why is the stack necessary to execute procedure X recursively?
The current state of the machine is pushed onto the stack when the procedure is called. This can be restored when the procedure is finished by popping the stack
Why is a queue a suitable date structure in some cases?
It is a first in first out
It is a last in last out
Advantages of dynamic data structures
No wasted memory, No limit on number of items that can be added, resources allocated when needed
Disadvantages of dynamic data structures
Additional memory needed for pointers, Memory leak, longer to access items directly
