Topc 5 ADT

Question 1

ADT

Answer 1

Abstract Data types

Question 2

What are ADT’s? (Examples)

Answer 2

2D Arrays Linked List Stacks Queues Trees

Question 3

Characteristics of stacks (3)

Answer 3

Vertical Last in; first out (LIFO) Collections (Unknown size; don’t know if it’s sorted)

Question 4

Adding an element to a stack

Answer 4

.push()

Question 5

Removing an element from a stack

Answer 5

.pop()

Question 6

Reverse collection pseudocode

Answer 6

// declare an empty stack int count = 0 loop while collection.hasNext() stack.push(collection.getNext() ) count ++; end loop loop i from 0 to count-1 newarray[i] = stack.pop() end loop

Question 7

Characteristics of a Queue

Answer 7

Horizontal First in; first out (FIFO)

Question 8

Array to Stack pseudocode

Answer 8

loop i from 0 to array.length-1 S.push(array[i]) end loop (same can be done with queues; except enqueue)

Question 9

Printing out a stack pseudocode

Answer 9

loop while not stack.isEmpty() output( stack.pop() ) end loop

Question 10

Adding an item to a Queue

Answer 10

.enqueue()

Question 11

Removing an item from a Queue

Answer 11

.dequeue()

Question 12

Real world examples of a Queue

Answer 12

Printer Queues Supermarket Queues

Question 13

Static (3)

Answer 13

Size determined at creation Not good use of memory space For loops

Question 14

Dynamic (4)

Answer 14

Changes size Nodes and pointers Good use of memory space While loops

Question 15

Accessing element in 2D arrays

Answer 15

array[row][column]

Question 16

Declaring 2D array example

Answer 16

int [ ] num = new int [row][col]

Question 17

Finding the number of rows

Answer 17

array.length

Question 18

Averaging an array pseudocode

Answer 18

int count = 0; int average = 0; int total = 0; loop i from 0 to array.length-1; count = count + array[i]; total ++; end loop average = count / total;

Question 19

Finding the number of columns

Answer 19

array[0].length

Question 20

Recursion

Answer 20

A method that calls itself in a program; which becomes more simple and stops calling itself at some stage

Question 21

Constructing a binary search tree

Answer 21

1. Initial value 2. Second value greater than initial = right 3. Second value less than initial = left

Question 22

Root pointer

Answer 22

Top most element in the tree

Question 23

Subtrees

Answer 23

Point either left or right

Question 24

Null pointer

Answer 24

Points to no elements

Question 25

Types of linked lists

Answer 25

Singly; Singly circular and Doubly linked list

Question 26

Parent

Answer 26

Node that has children

Question 27

Leaf

Answer 27

Node with no children

Question 28

Full binary tree

Answer 28

Each node has 0 or 2 children

Question 29

Preorder

Answer 29

Left

Question 30

Inorder

Answer 30

Bottom

Question 31

Postorder

Answer 31

Right

Question 32

Best use of stack

Answer 32

Implementing function calls

Question 33

Best uses of queues

Answer 33

Computing applications (E.g. CPU) Buffers Playlist Interrupt handling (C; B; P; I)

Question 34

Best uses of linked list (2)

Answer 34

Unknown size Want to insert and delete from anywhere

Question 35

Best uses of arrays

Answer 35

Random access to elements Speed when iterating

Question 36

Best uses of binary trees

Answer 36

Binary Search Tree Heap (Priority Queues) GGM Trees Syntax tree

Question 37

Binary tree vs singly linked list

Answer 37

Binary tree - More storage; 2 pointers; Binary search can be used and more efficient Singly linked list - Less storage; 1 pointer; Linear search (slower) and less efficient

Question 38

Stacks and recursion

Answer 38

Recursive calls involves use of stacks - storing; popping and pushing

Question 39

Advantages of making a queue dynamic

Answer 39

No pre determined/ fixed size Efficient use of memory