Brainscape's Knowledge GenomeTM

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


See full index

Computer Science Paper 1 > Data Structures > Flashcards

Data Structures Flashcards

Remember page 351 in text book for Data Structures

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

What is an Array

A

An array is an ordered, finite set of elements of a single type

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

What Type of Array is a Linear Array

A

A one-dimensional array

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

How can you visualise a two-dimensional array

A

A 2D array can be visualised as a table/spreadsheet and when searching this type of array, first go down the rows and then across the columns

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

How can you visualise a three-dimensional array

A

A 3D array can be visualised as a multi-page spreadsheet

An element in a 3D array uses: threeDimensionalArray[z,y,x]

z = array number, y = row number, x = column number

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

What is a Record

A
  • A row in a file and is made up of fields
  • Records are used in databases
  • Each field in a record can be identified using the syntax
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a List

A

A data structure consisting of a number of ordered items where the items can occur more than once

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

Describe the List Operations

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

What is a Tuple

A

An immutable (cannot be changed) ordered set of values of any type

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

How is a tuple initalised

A

Initialised with regular brackets rather than square brackets

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

What is a Static and Dynamic Data Structure

A

Static - fixed size

Dynamic - can keep growing

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

What is a Linked List

A

A linked list is a dynamic data structure used to hold an ordered sequence

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

How is a Linked List Organised

A
  • The items in a linked list are not necessarily in contiguous data locations (the order they occur in the sequence)
  • Each item in the list is called a node and contains a data field and a next address field called a point field
  • The data field holds the actual data of the next list item and the pointer field holds the address of the next item
  • Also the list has a pointer variable showing the first node in the list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are the Disadvantages of using a Linked List

A
  • They waste memory, storing pointers mean 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; an item 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
14
Q

Describe the three different types of Graphs

A
  • Directed Graph - The edges can only be traversed in one direction
  • Undirected Graph - The edges can be traversed in both directions
  • Weighted Graph - A cost is attached to each edge.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Describe an example of an Adjacenecy Matrix

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

What are the Advantages and Disadvantages of the adjacency matrix

A
  • Convenient to work with due to quicker access times
  • Easy to add nodes
  • Most graphs leave most of the cells empty meaning the larger the graph the more memory space will be wasted
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Describe an example of an Adjacenecy List

A
18
Q

What is the Advantage of an Adjacenecy Lists

A

More space efficient for large, sparse networks

19
Q

What are the two ways of traversing a graph

A

Depth-first - you go as far down one route as you can before backtracking and taking the new route

Breadth-first - you visit all the neighbours of the first node and then all the neighbours of the second node and so on

20
Q

Describe some uses of graphs

A
  • Computer networks
  • Roads between towns
  • Tasks in a projects
  • Web pages and links
21
Q

What is a Stack

A

A data structure that operates on a first in last out basis

22
Q

What is a Queue

A

A data structure that acts on a first in first out bias

23
Q

Describe the Stack Operations and Names

A
24
Q

Describe the Queue Operations and Names

A
25
Q

Describe the pseudocode for a stack isEmpty

A

if(top == -1)

return true

else

return false

end if

end function

26
Q

Describe the pseudocode for a stack isFull

A

if top = maxSize then

return True

else

return False

end if

end function

27
Q

Describe the pseudocode for a stack push

A

If isFull() then

Print “The stack is full”

Else

top = top + 1

arrStack[top]=newValue

End if

End function

28
Q

Describe the pseudocode for a stack pop

A

if isEmpty() then

Print “The stack is empty”

else

item = arrStack[top]

top = top -1

Return item

End if

End function

29
Q

Describe the pseudocode for a stack peek

A

if isEmpty()

Print “Stack is empty”

Else

return arrStack[top]

endif

end function

30
Q

Describe the pseudocode for a Queue Enqueue

A

if(isFull() then

Print “The queue is full”

Else

rear = (rear+1) % maxSize

arrQueue[rear] = newValue

size = size + 1

Endif

End function

31
Q

Describe the pseudocode for a Queue Dequeue

A

int item

if(isEmpty()) then

Print “The queue is empty”

Else

item = arrQueue[front]

front = (front+1) % maxSize

size = size -1

Endif

End function

32
Q

What are the Applications of Stacks and Queues

A

Stacks - Stacks are used to reverse an action, such as to go back a page in web browsers and in ‘undo’ buttons

Queues - print tasks are stored on a print queue while waiting to be printed. When a set of tasks are waiting to be executed, a priority queue will be used to ensure that they are executed in the appropriate order

33
Q

What is a Tree

A

A connected form of a graph

34
Q

Describe the components of a Tree

A
  • Node - an item in the tree
  • Edge - connects two nodes together and is also known as a branch, or arc
  • Root - a single node which does not have any incoming nodes
  • Child - a node with incoming edges
  • Parent - a node with outgoing edges
  • Subtree - subsection of a tree consisting of a parent and all the children of a parent
  • Leaf - a node with no children
35
Q

What are the Similarities and Differences between a Tree and a Graph Data Structure

A

Similarites

  • Both have nodes and edges
  • Both are non-linear data structures
  • Both are dynamic data structures

Differences

  • A Tree is 1 directional whereas Graph is 2 directional
  • A Tree does not have cycles, a Graph does
  • A Tree will not be weighted whereas a Graphs edges can be weighted
36
Q

What are the three ways of traversing a binary tree

A
  • Pre-order
  • In-order
  • Post-order
37
Q

How do you execute the three traverses and what do they tell you

A
  • Pre-Order - order you pass the nodes on the left
  • In-Order - order you pass the nodes underneath
  • Post-Order - order you pass the nodes on the right
  • Pre-Order - gives the exact replication copy of the tree (allows duplication of tree)
  • In-Order - gives you the nodes in ascending order
  • Post-Order - gives you the the tree in a form that can be turned into any low level code
38
Q

What is a Hash Table

A

An array which is coupled with a hash function

39
Q

What is the main problem with a Hash Table

A

Collions may occur meaning the item has to be placed in the next available location

40
Q

What is the Appilcation of a Hash Table

A

Commonly used for indexing, as they provide fast access to data due to keys having a unique, one-to-one relationship with the address at which they are stored

Computer Science Paper 1 (16 decks)

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