Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Ultimate Computing > 1.4.2 Data Structures > Flashcards

1.4.2 Data Structures Flashcards

1
Q

Array

A

A static data structure used for storing a finite, ordered set of data of the same data type within a single identifier. They are contiguous.

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

How to find a given position within a 2D/3D array

A

Use the reverse to the method used to find a set of coordinates.
EG: 3D [z,y,x]

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

How can a 2D array be visualized as?

A

Table/spreadsheet

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

How can a 3D array be visualised as?

A

Multi-page spreadsheet / multiple 2d arrays

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

Record

A

A data structure that stores data in elements called fields, organised based on attributes.

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

What is a List?

A
  • A dynamic data structure that can store multiple values of different data types.
  • They are mutable, meaning values can be changed or replaced.
  • List values are stored non-contiguously.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Tuple

A

A data structure for storing an immutable, ordered set of data, which can be of different data types, within a single identifier.

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

Linked list

A
  • A dynamic data structure consisting of an ordered sequence of nodes.
  • Each node has a data field and pointer field.
  • Each pointer points to the next node in the sequence.
  • They are non-contiguous.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Name the pointers used by linked lists.

A

Start Pointer
Free Pointer

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

What is the procedure for adding an item to a linked list.

A

Add the new value to the end of the linked list, and update the free pointer.
Update the node that currently has a null pointer to point to the new item.
Update the pointer of the new item to have a null pointer.

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

What is the procedure for removing an item from a linked list.

A

The pointer in the previous item changes to the pointer held by the item that is to be removed, effectively bypassing the removed item.

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

Disadvantages of linked list

A
  • Removing nodes from a linked list does not truly remove it. This wastes memory.
  • Storing pointers also means more memory is required compared to an array.
  • As items in linked lists are stored in a sequence, they can only be traversed in this order. This means they cannot be directly accessed, as is possible in an array.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Graph

A

A dynamic data structure. It is a collection of data nodes (known as vertices), connected by edges.

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

Describe the three categories of graph.

A

Directed: Edges can only be traversed in one direction
Undirected: Edges can be traversed in both directions
Weighted: A cost is attached to each edge.

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

What are the two ways of traversing a graph?

A

Breadth-first (using queue)
Depth-first (using stack)

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

Stack

A

A LIFO data structure, meaning items are added to the top and removed from the top.
They have a pointer which points to the top of the stack, where the next piece of data can be added.

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

Name some operations you can perform with a stack.

A

Push
Pop
isFull
isEmpty
peek
size

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

Queue

A

A FIFO data structure, meaning items are added to the end of the queue and removed from the front.
It uses a front and back pointer to show the item that can be removed and the item that can be added.

19
Q

Name some operations you can perform with a queue

A

enQueue
deQueue
isEmpty
isFull

20
Q

What is the difference between circular and linear queues?

A

Once the queue’s rear pointer is equal to the queue’s max size, it loops back to the front of the array and stores values there (provided it is empty).

21
Q

Pros/Cons of circular queue

A

Uses space in an array more effectively.
Harder to implement.

22
Q

Why are linear queues ineffective compared to circular queues.?

A

Linear queues implemented using an array can become ineffective over time as dequeued elements leave unused spaces in the array, while circular queues are more efficient as they wrap around and reuse the array space as elements are dequeued.

23
Q

Tree

A
  • A dynamic data structure that branches.
  • It has a root node at the top, and other nodes arranged in levels beneath it.
  • Each node in a tree can have zero or more child nodes, which are connected to it by edges/branches.
24
Q

Edge/Branch

A

Connects two nodes togetherq

25
Q

Root

A

Single node which does not have incoming nodes

26
Q

Child

A

Node with incoming edges

27
Q

Parent

A

Node with outgoing edges

28
Q

Subtree

A

Subsection of a tree consisting of a parent and all the children of a parent.

29
Q

Leaf

A

Node with no children.

30
Q

Binary Tree

A

A type of tree where each node has a maximum of two children.

31
Q

How are binary trees commonly implemented?

A

A 2D array holding the left pointer, data value and right pointer.

32
Q

Why use binary trees?

A

To represent info for binary searches

33
Q

What are the three methods for traversing a binary tree?
What is an easy method that covers all of these?

A

Pre-order, In-order, Post-order.
Use the outline method (draw around the tree starting from left side)

34
Q

Pre-order (binary tree)

A

Order: Root node, left subtree, right subtree.

35
Q

In-order (binary tree)

A

Order: Left subtree, rootnode, right subtree

36
Q

Post-order (binary tree)

A

Order: Left subtree, right subtree, root node.

37
Q

What two data structures allow random access to elements?

A

Array (via direct index)
Hash table

38
Q

What is a hash table?

A
  • A dynamic data structure.
  • Data is stored in a table.
  • A mapping function uses the data that is going to be entered into the table to generate the location in the table where the data should be stored.
39
Q

What is a simple way of dealing with collisions in a hash table? Whats the problem with this?

A

The data can be stored in the next available space. However, this further increases the likelyhood of collisions (clustering).

40
Q

What makes a hashing algorithm good?

A

If it has a low probability of collisions occuring.

41
Q

What are hash tables normally used for?

A

Indexing, as they provide fast access to data.

42
Q

How are linked lists used in hash tables to solve the problem of collisions and clustering?

A
  • A technique called separate chaining is used.
  • The original table is used to store an overflow linked list for the index where a collision occurs.
  • This means when a collision occurs, a new node can be created in the linked list to hold the new data.
43
Q

Whats a simple hash function?

A

(k*k) MOD m
k: key value
m: a prime number close to the required num of locations.

44
Q

What is one way of using non-numeric fields for key values?

A

Use the ASCII values of the characters to create a numeric value, then use a suitable hashing function.

Ultimate Computing (25 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions