Short answers 2

Describe an Abstract Data Type (ADT). What is the function of an ADT?

Abstract Data Type(ADT) is a collection of data and associated subprograms/methods stored as a single module. Function: An ADT enables you to interact with a data structure without having to know how the data structure is implemented and how it functions

Define a stack

Stack is an ordered collection of objects in which insertions and deletions are restricted to one end. LIFO structure.

Backtracking is a technique used in recursion. Describe how backtracking works. Give an example of a backtracking algorithm.

see the word doc!

Explain what is meant by a Breadth First Traversal of a binary tree. Which ADT is used to implement a Breadth First Traversal?

Breadth first traversal: Proceed horizontally from the root to all of its children then to its children’s children and so on until all nodes have been processed. To implement this traversal a queue is used

Insert, in the order given, the following numbers into an initially empty Binary Search Tree (BST): 6, 2, 5, 1, 7, 9, 3, 8, 4

r1 6 r2 2,7 r31,5,9 r4 3,8 r5 4

Describe a data structure. Give an example of a data structure

ggg

Define a queue

Queue is an ordered collection of objects in which insertions are restricted to one end (tail) and deletions are restricted to the other (head)

Explain what is meant by Tail End Recursion. Give an example of Tail End recursion. Justify your answer

Tail end recursion occurs when there is one recursive call in an algorithm and this call is the very last thing the method does. eg reversing an array

Explain what is meant by a Depth First Traversal of a binary tree. Which data structure is used to implement a Depth First Traversal?

Depth First Traversal: Proceed along a path from the root through one child to the most distant descendant of that first child before processing the second child To implement this traversal a stack is used

Describe a data structure. Give an example of a data structure

A Data Structure consists of 2parts: Collection of elements each of which is either a data type or another data structure and A set of associations or relationships (the structure) involving the collection of elements.eg. Array, Linked List, Binary Tree