Data Structures

Question 1

Define a 1D array

Answer 1

Is a structure of data elements all of the same data types

Question 2

Define a 2D array

Answer 2

Is a collection of data elements arranged in a grid like structure with rows and columns

Question 3

Define a 3D array

Answer 3

is a structure of data elements arranged in 3D grid structure, with elements in rows in slabs

Question 4

State three points about Stacks

Answer 4

Last in first out
Real world example; stack of books
Computing example; undo and redo buttons

Question 5

State three points about Queues

Answer 5

First in first out
Real world example; queue of people
Computing example; list of instructions with a CPU

Question 6

State one thing that both Stacks and Queues have in common

Answer 6

They are both Linear data structures

Question 7

Define a Tree

Answer 7

Is a connected, undirected graph with no cycles

Question 8

What does connected mean in reference to Tree’s

Answer 8

There is a path from one node to another

Question 9

What does undirected mean in reference to Tree’s

Answer 9

There is no direction associated with a path

Question 10

What does ,No cycles, mean in reference to Tree’s

Answer 10

There is only ever on route between two nodes

Question 11

Are Tree’s linear data structures

Answer 11

No

Question 12

What are the five different methods to traverse a Tree

Answer 12

Breadth-first traversal,
Depth-first traversal,
In-order traversal,
Pre-order traversal,
Post-order traversal

Question 13

Define Breadth-first traversal

Answer 13

You visit each node in a level before looking at any of the children nodes from that level

Question 14

Define Depth-first traversal

Answer 14

You visit all the children of a node before moving on to the next node on that level, starting from the left nodes

Question 15

Define In-order traversal

Answer 15

You visit the left most node and all of its children then the next left most node and it’s children and so on.

Question 16

Define Pre-order traversal

Answer 16

You visit the root node first then the left most child nodes, the the root nodes and then the right child node.

Question 17

Define Post-order traversal

Answer 17

You visit each parent node after visiting both of it’s child nodes

Question 18

What are the five components of a Tree

Answer 18

Root
Node
Edge
Leaf
children

Question 19

What are the four types of Trees

Answer 19

Rooted Trees
Binary Trees
Binary search Trees
Expression Trees

Question 20

Define Rooted Trees

Answer 20

A Tree with one node designated as the root, all other nodes descend from this node

Question 21

Define Binary Trees

Answer 21

A rooted Tree where very node has at most two child nodes

Question 22

Define Binary search Trees

Answer 22

A rooted Tree where the nodes of the tree are ordered

Question 23

Define Expression trees

Answer 23

They are trees that represent expressions

Question 24

Define Linked Lists

Answer 24

They are dynamic data structures which means they can grow in size during execution.

Question 25

What is each element in a linked list called

Answer 25

A node

Question 26

What do nodes store

Answer 26

a pointer to the next node and the data relating to the element

Question 27

What are the two additional pointers

Answer 27

One towards the front and one towards the end of the list

Question 28

What are the two types of linked lists

Answer 28

Ordered and Unordered

Question 29

What are the three steps to adding new nodes to a linked list

Answer 29

1. Creating the new node 2. Setting the pointer of the new node to the value of the next node 3. Setting the header point to point to the new node

Question 30

What is the special about deleting a from a linked list node

Answer 30

No actual data is deleted, it is just un assigned

Question 31

How to delete a node from a linked list

Answer 31

Set the pointer to the "Deleted" node to the next node

Question 32

Define Hashing Algorithms

Answer 32

They store the data in an array and assign them an index

Question 33

How are the index's in hashing algorithms assigned

Answer 33

They are dependent upon the position of the data within the array

Question 34

When do collisions occur, in hashing algorithms

Answer 34

When the hashing function produces the same hash value for two or more keys

Question 35

What are the two methods to deal with collisions

Answer 35

Linear Probing Chaining (Retrieving data)

Question 36

How does linear probing work

Answer 36

It assigns the second key with the next position in the table that is available

Question 37

How does Chaining work

Answer 37

It creates a chain or linked list within the data table, the hash value that had the collision will then store the location or the linked list.

Question 38

Uses of Pre-order Traversal

Answer 38

Copy a tree, or search for a node within the tree

Question 39

Uses of In-order traversal

Answer 39

Create an ordered list of the nodes, or to recreate the order that the tree was made in

Question 40

Uses of Post-order traversal

Answer 40

Deleting a tree, since it visits each leaf node before visiting the parent node

Question 41

What is the easy way of remembering InOrder traversal

Answer 41

Left, Root, Right

Question 42

What is the easy way of remembering PreOrder traversal

Answer 42

Root, Left, Right

Question 43

What is the easy way of remembering PostOrder Traversal

Answer 43

Left, Right, Root

Question 44

What is the method of adding items to a stack called

Answer 44

Pushing

Question 45

What is the method of removing items from a stack called

Answer 45

Popping