Brainscape's Knowledge GenomeTM

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


See full index

A Level Computer Science > ADTs > Flashcards

ADTs Flashcards

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

Name 9 ADTs

A
  • Queue
  • Stack
  • List
  • Arrays
  • Linked Lists
  • Hash Tables
  • Graphs
  • Trees
  • Binary Trees
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a Queue’s priority

A

FiFo

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

What is a Stack’s priority

A

LiFo

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

What is Static and Dynamic

A

Static - Fixed size e.g. arrays
Dynamic - Variable sized e.g. Lists

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

What are the parts of linked lists

A

There are 2 parts
Data (can be complex data structure)
Pointer (index of next node)

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

What is Encapsulation

A

To hide data from users. To hide inner workings of program.

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

What is Overflow

A

Trying to push to a full stack

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

What is underflow

A

Trying to pop from an empty stack

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

What is a Call Stack

A

Provides a system for passing parameters and return addresses to subroutines

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

What are the functions for adding to and removing from a Queue

A

enQueue(item)
deQueue()

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

What are the functions for adding to and removing from a stack

A

Push(item)
Pop()

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

What are the functions to check if a stack or queue is full or empty

A

IsFull()
IsEmpty()

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

What is the function to view whats on top of the stack

A

Peek()

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

What’s the function to return the num of items on a stack

A

size()

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

What is a Hash table

A

Uses a hashing algorithm to find data quickly
Each record is assigned a unique address
Collision occurs if addresses are the same, they are remade if this happens

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

What function is in most hashing algorithms

A

MOD by number of slots. The remainder is the address

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

What is a collision

A

Keys that generate the same address for different primary keys, referred to as synonyms

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

What is clustering

A

After a collision, if you put the item in the next available spot, clustering occurs

19
Q

What could you do to prevent clustering

A

Implement Skip value to add 1, 3, 5 instead

20
Q

What happens when an item is deleted from a hash

A

The space is replaced with a dummy item

21
Q

What is a Dictionary

A

ADT made of associated pairs
Each pair has a key and a value
The value is accessed via the key
In a dictionary multiple items can have the same key

22
Q

What is the address of the key

A

Value pair is calculated using a hashing algorithm

23
Q

What is a graph

A

an ADT representing complex relationships

24
Q

What are the 2 types of graphs

A

Directed
Undirected

25
Q

How can you tell if a graph is directed

A

If there are arrows between nodes

26
Q

How can you represent a graph

A

With an adjacency matrix or adjacency list

27
Q

Advantages and Disadvantages of a Matrix

A

Adv: Convenient to work with, adding edge is simple
Dis: Sparse graph will leave cells empty wasting lots of memory space.

28
Q

Advantages of a List

A

More space efficient (for large sparse graphs)

29
Q

What are 3 applications of graphs

A
  • Maps
  • Computer Networks
  • Social Networks
30
Q

What is a tree

A

A connected, undirected graph with no cycles

31
Q

What are the parts of a tree

A

Root (at top), Branches, Leaves. Can have subtrees

32
Q

What is a rooted tree

A

Has one node as the root, every node except the root has one unique parent.

33
Q

What is a binary tree

A

Each node has a max of two children

34
Q

What are the 3 parts of a node

A

Data
Left Pointer to child
Right Pointer to child

35
Q

What is a binary search tree

A

Nodes are added in order given starting at root each time. If item is less, its added to left. Larger, right

36
Q

How is a tree represented

A

In an array

37
Q

What are the three types of traversal

A
  • Pre-order
  • In-Order
  • Post-Order
38
Q

What is Pre-order Traversal

A

Draw Road:
Left

39
Q

What is Post-order Traversal

A

Draw Road:
Right

40
Q

What is In-order Traversal

A

Draw Road:
Underneath

41
Q

What are the 3 cases when deleting a node

A
  • Leaf has no children
  • Leaf has 1 child
  • Leaf has 2 children
42
Q

What happens if the leaf deleted has no children

A

Nothing, it simply disappears

43
Q

What happens if the leaf deleted has one child

A

Child takes parents place

44
Q

What happens if the leaf deleted has 2 children

A

Leaf replaced with the leftmost value on its right subtree

A Level Computer Science (8 decks)

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