Data Structures Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

Define a 1D array

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Define a 2D array

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Define a 3D array

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

State three points about Stacks

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

State three points about Queues

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

State one thing that both Stacks and Queues have in common

A

They are both Linear data structures

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Define a Tree

A

Is a connected, undirected graph with no cycles

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What does connected mean in reference to Tree’s

A

There is a path from one node to another

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What does undirected mean in reference to Tree’s

A

There is no direction associated with a path

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

There is only ever on route between two nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Are Tree’s linear data structures

A

No

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are the five different methods to traverse a Tree

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Define Breadth-first traversal

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Define Depth-first traversal

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Define In-order traversal

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Define Pre-order traversal

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Define Post-order traversal

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are the five components of a Tree

A

Root
Node
Edge
Leaf
children

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are the four types of Trees

A

Rooted Trees
Binary Trees
Binary search Trees
Expression Trees

20
Q

Define Rooted Trees

A

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

21
Q

Define Binary Trees

A

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

22
Q

Define Binary search Trees

A

A rooted Tree where the nodes of the tree are ordered

23
Q

Define Expression trees

A

They are trees that represent expressions

24
Q

Define Linked Lists

A

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

25
Q

What is each element in a linked list called

A

A node

26
Q

What do nodes store

A

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

27
Q

What are the two additional pointers

A

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

28
Q

What are the two types of linked lists

A

Ordered and Unordered

29
Q

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

A
  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
30
Q

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

A

No actual data is deleted, it is just un assigned

31
Q

How to delete a node from a linked list

A

Set the pointer to the “Deleted” node to the next node

32
Q

Define Hashing Algorithms

A

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

33
Q

How are the index’s in hashing algorithms assigned

A

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

34
Q

When do collisions occur, in hashing algorithms

A

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

35
Q

What are the two methods to deal with collisions

A

Linear Probing
Chaining (Retrieving data)

36
Q

How does linear probing work

A

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

37
Q

How does Chaining work

A

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.

38
Q

Uses of Pre-order Traversal

A

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

39
Q

Uses of In-order traversal

A

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

40
Q

Uses of Post-order traversal

A

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

41
Q

What is the easy way of remembering InOrder traversal

A

Left, Root, Right

42
Q

What is the easy way of remembering PreOrder traversal

A

Root, Left, Right

43
Q

What is the easy way of remembering PostOrder Traversal

A

Left, Right, Root

44
Q

What is the method of adding items to a stack called

A

Pushing

45
Q

What is the method of removing items from a stack called

A

Popping