Data Structures

What is pre-order traversal.

Starting from the root node of a binary tree traversing the left then the right subtree, draw the points on the left

What is in-order traversal?

Traverses the left subtree, root node and then the right subtree. The point is below.

What is post-order traversal?

Traverses left-subtree, right-subtree and then the root node

State two uses of pre-order traversal?

• Copies the tree

• Generates a prefix expression of the tree(Polish Notation)

State three uses of in-order traversal.

• Puts data in alphabetical/numerical ascending order

• Retrieve all items in a sorted list

• (Generates an infix expression of the tree)

State two uses of post-order traversal

• Generates a postfix expression of the tree (Reverse Polish Notation)

• Delete data from a tree

Why are their different datatypes?

To enable related data to be efficiently organised in a variety of formats depending on the application and memory requirements for a certain task

Define all primitive data types

• Integer = Stores whole numbers (+ve or -ve)

• Real = Stores numbers that contain decimal places (and integers)

• Character = stores a single character which can be a letter, number or symbol

• String = Stores alphanumeric combinations and text, a sequence of characters

• Boolean = Stores True or False (1/0)

Define static structure

A static structure is where the size of the structure does not change while the program is running

Define Dynamic structure

A dynamic structure is where the size of the structure can change while the program is running

Define Record

• A record is a set of data items all related to a single entity

• They can contain multiple data types and be accessed through a common name

• One example of a record is a row in a database

Describe arrays

• They are a static data structure used to store multiple items of the same data type under a single identifier

• To add data, you search the array for an empty index to insert the data into

• To delete data, you search the array for the requirement element, setting the index to null

• Can be multi-dimensional

• Is a random access data structure

How do you reference a data item in A 2D array

You give the row index, then the column index (down, then across)

Define random access data structure

Every element can be accessed as quickly as another

State the disadvantage of 3D arrays

It is complex to program

State how stacks and queues are represented

Using a circular array.

• For stacks, there is a top pointer, inidicating the index of the last item added (where items should be pushed to and popped from)

• For queues, there is a front pointer, = where to read/removed from and a rear pointer = where to write to

  

Describe Stacks

• It is a data structure built on the concept of an array

• They are Last in First Out (LIFO) data structures

• It is only possible to push or pop an item from the top of the stack

• A top pointer indicate the top of the stack

• Static data structure

• Sequential access data structure

• A linear data structure which can be defined recursively

State when underflow and overflow occur for stacks

• Underflow occurs when an attempt is made to pop an empty stack

• Overflow occurs when an attempt is made to push to a full stack

Define recursive data structure

When the data structure can be broken down into smaller versions of the same data structure

Give the algorithm pseudo code for a stack

DECLARE stackArray as TYPE array of string
DECLARE stackpointer, maxLength as TYPE integer
DECLARE dataItem as Type stringh

FUNCTION push(dataItem):
	IF stackPointer < maxLenth then:
		stackPointer = stackPointer + 1
	ELSE output "Stack is full, data not saved"
	END IF
END FUNCTION

FUNCTION pop():
	IF stackPointer > 0 then:
		stackPointer = stackPointer + 1
	ELSE:
		output "Stack is empty, no data removed"
	END IF
END FUNCTION

State some uses for stacks

• Store register values during subroutine execution

• Reverse lists

• Check syntax during compilation

• Used for backtracking the users visited webpages (when back button pressed)

Describe queues

• A First In First Out (FIFO) data structure

• Items are added to the end of the queue (at the back pointer)

• Items are removed/read at the front of the queue (front pointer)

• Linear data structure

State how an item is removed from a queue and stack

• Queue = Front pointer incremented by 1

• Stack = Pointer decremented by 1

Describe linked lists

• Dynamic data structure

• The items are not necessarily held in contiguous (next to each other) data/memory locations

• Sequential access data structure = A node cannot be directly accessed, each node must be traversed until correct node accessed

• Each node contains a data field and the next address field (link/pointer field)

• First node is called the head node

• Pointer field in last item has Null value (-1)

• Recursive data structure

Explain a disadvantage of linked lists

It uses more memory than an array because it needs to store the address for the next node, on top of the data

Describe binary trees

• Dynamic data structure

• 0 or more nodes in hierarchal order

• Each parent has a maximum of 2 children

• Can be traversed in pre-order, in-order and post-order traversal

State the advantages and disadvantages of binary trees

Advantages

• Faster to add a value

• Faster to search for a value

Disadvantages

• More complex to program/process

• Processing + traversing may be slow if unbalanced

When are binary trees used

• When there is a large number of items to be stored, which need to be accessed quickly, or when sequenced lists are needed

• Representing arithmetic expressions

State the different parts of a binary tree

• Left+Right subtrees

• Root node = Has no parent

• Parent node = Has at least one child

• Branches connect nodes

• Leaf nodes = Have no children

State the rules for a binary tree

• Each parent has 2 children maximum

• If the element is <= current node,the element is the left child node

• If the element > current node, the element is the right child node

Describe Hash Tables

• Static data structure and the fastest data storage method

• Ideally will always match the data you are storing (uniformly distributed, minimal collisions, efficient)

1. The file memory location will be determined by passing the index/key value through an algorithm

2. If there is a collision, file stored in overflow area (serial file/linked list)

State a problems with hash files overflow area and the solution

• Searching the overflow area is slow, and the more files the slower the program becomes → Larger hash file created + new hashing algorithm

Define masking

The process of setting each bit in a byte to either on/off using bitwise operators

Which bitwise operator is used for encryption

XOR