Brainscape's Knowledge GenomeTM

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


See full index

Computer Science Cards Rewrite > Data Structures > Flashcards

Data Structures Flashcards

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

What are the 4 basic data types

A

Integer
Real
String
Boolean

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

Define a data structure

A

A collection or group of related data items

Collects together the basic data types and allows data to be organised in a convenient and logical manner related to the program being developed

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

Where are data structures held

A

They are held in memory and therefore the data item is lost when the computer is turned off.

Usually not a problem as it is easy to write a procedure to copy a data structure into a file and then load it back in again when a program starts

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

Advantage of data structures

A

Data structures are held in memory it means the data can be accessed, searched, sorted etc. much more quickly than data held in a file

Can relate to specific problems

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

What is a 1d array

A

A 1d array is used to represent a list of data

Allows for the efficient processing of the data e.g. sorting, searching as it is a data structure

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

What is a 2d array

A

Used to represent a table of data

E.g. record sales figures for 4 sales people for each month of the year

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

What is a 3d array?

A

Used to represent tables of data

If a company wanted to record sales figures over a 10 year period a 3d array could be used

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

Advantage of array

A

Access elements in an array without any search being required

E.g. print sales(3,5 8) would immediately print the contents of that cell without needing to search through other elements

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

Disadvantages of array

A

Static data structures - the size is set and can’t be changed dynamically as the program runs

E.g. an array that might have 1000 names needs to be set to have 1000 elements, even if 800 are currently blank

If a new item of data needs to be inserted into an element in an array, all the elements after it need to be shifted up to make space for it

And vice versa if an element needs to be removed (items shifted down to fill the gap)

All elements in an array need to be of the same type

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

What does the record data structure allow

A

Allows items of data relating to something to be grouped together into a single record type

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

What is a stack

A

A last in first out data structure (LIFO)

E.g. like a stack of plates, last one that goes in comes out first

Limited access data structure, only the top item can be removed (popped)

Items are added (pushed) on to the top of the stack

A stack pointer always points at the last element added to the stack

A stack can be used as a recursive data structure

Underflow occurs when an attempt is made to pop an empty stack

Overflow occurs when an attempt is made to add to a full stack

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

Define popped

A

Removing an item from a stack

Display item indicated by stackpointer and then decrement from stackpointer

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

Define pushed

A

Item is added to the top of the stack

Increment the stack pointer and place the value in position indicated by stackpointer

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

Where is a stack (LIFO) Data structure used

A

Run time stack mechanism - an OS uses when running a program to keep track or where it is up to when making procedure calls

Back button in a Web browser

Undo feature

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

How is a stack implemented

A

Using an array and a variable known as a stack pointer which always points to the last element added to the stack

To add:
Increment stack pointer and place the value in position indicated by stackpointer

To remove:
Decrement stack pointer and place the value in the position indicated by the stack pointer

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

Why can a stack be considered a recursive data structure

A

A stack is either empty

Or has a top item and a pointer to a stack (e.g. a stack with an item c points to another stack with an item b which points to another stack and etc.)

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

What type of data structure is a queue

A

A first in first out data structure (FIFO)

E.g. queueing in a shop

A queue data structure is circular so if the end pointer goes beyond the last bit, it starts at the beginning again at e.g. 1

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

How are queues implemented

A

Using an array and two pointers to indicate the start and the end of the queue

End is the end of the queue where the new item will be added

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

How do you add data in a queue (FIFO)

A

Putting data into the end pointer position and incrementing(+1) the End Pointer

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

How do you remove data in a queue (FIFO)

A

Removing data involves displaying the data in a position indicated by start pointer and then incrementing(+1) the start pointer

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

Define linked list

A

A dynamic data structure, its size can be increased and decreased as required. An array is static and therefore its size is fixed

Items can be added into a linked list without having to move the existing items to make space

When being compared to an array:
Items can be removed from a linked list without having to shift the other items to fill in the gap left

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

How is a linked list represented

A

Using 2 arrays for the data and the pointer to the next item in the list, that item will point to the next and so on

There is also another linked list of free locations

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

Removing an item from a linked list

A

..

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

What type of data structures are trees and why is it useful

A

Non-linear

Useful for storing data that could he hierarchical e.g. car parts, organisation structure

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

What is a binary tree

A

A binary tree is a type of tree where all nodes can either have 0,1 or 2 children

I.e. a node with data and pointers left and right or either

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

What can binary trees be used for

A

To keep an ordered list for searching using the rule that anything ‘less than’ or before the data in the alphabet is to the left and everything ‘greater than’ or after the data to the right

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

How to add to a binary tree

A

Starting at the root node of the tree

Compare the data you want to add to the current node

If the new data is less than the node then follow the left pointer else follow the right pointer

Repeat this until you reach the end of the tree

Update the pointers of the last node to point to the new one

28
Q

Removing data from a binary tree

A

Removing data from a binary tree is a little trickier compared to adding an item. The steps you will follow will depend on the type of node being added

These are:
A node with no children
A node with one child
A node with 2 children

29
Q

What is tree traversal

A

Traversal is a process to visit all the nodes of a tree and may print their values too. We always start from the root node

We traverse a tree to search or locate a given item or key

There are three ways:
Pre order traversal
In-order traversal
Post-order traversal

30
Q

Why is tree traversal used

A

To search or locate given item or key in the tree or to print all the values it contains

31
Q

Pre order traversal

A

In this traversal method, the root node is visited first, then left subtree and finally right subtree

32
Q

In order traversal

A

In this traversal method, left-subtree is visited first, then the root node and then the right sub-tree

An example of this is searching for a file in the file system

33
Q

Postorder traversal

A

In this method, the root node is visited last, hence the name. First we traverse the left subtree, then right subtree then finally root

34
Q

What is a hash table

A

Has 2 components

A table where the actual data is stored and a mapping function (hash function/hash algorithm).

The hash function uses the data that is going to be stored to generate the location in the table where it will be stored.

They are a quick way to store, organise and search for data (allowing us to jump to the location of the stored data if we were performing a search)

Used for database indexing, caches, sets

35
Q

Hash tables - separate chaining

A

…

36
Q

How do you get over the issue of not being able to have mixed data types in an array?

A

Create an array of records

37
Q

Where is a stack data structure used

A

Run time stack mechanism-

An Operating system uses it when running a program to keep track of where it is upto when making procedure calls

The back button in a Web browser/undo function in an application

Recursion values

38
Q

Describe the FIFO data structure

A

Often implemented using an array and two pointers to indicate the start and end of a queue

39
Q

What is good about a binary tree if it is balanced

A

Very quick to find data

This is because the number of items being searched is effectively halved as the search moves down each level of the tree

40
Q

Describe the term record

A

A set of data items all related to a single entity

Can include data of different types

41
Q

A drawback of a 3 dimensional array

A

More complex to program compared to the others

42
Q

algorithm to add an item to a stack

A

If stackPointer < stackMaximum then
stackPointer = stackPointer + 1
stackArray(stackPointer) = dataItem
Else
Display ”Stack is full – your data has not been saved”

43
Q

algorithm to remove an item from a stack

A

If stackPointer > 0 then
dataItem = stackArray(stackPointer)
stackPointer = stackPointer – 1
Else
Display ”Stack is empty – no data can be retrieved”

44
Q

algorithm to remove a person from the queue or identify if the queue is empty

A

Procedure RemoveFromQueue
If startpointer <> EndPointer then
Output Queue[startpointer]
Queue[startpointer] = null
Startpointer = startpointer + 1
Else
Output “queue is empty”
End if
End procedure

45
Q

what should happen when an attempt is made to add an item to a full queue

A

If the queue is full, any attempt to add to it should return an appropriate message or condition

46
Q

describe a situation where a queue would be used in a computer system

A

Printer queue, keyboard buffer

why:
In each case, because the natural / desirable processing order is first in first out so the job waiting longest should be printed next

47
Q

define the term linked list

A

a set (accept list) of data elements, where each element contains
• the data itself
• a pointer to the next element

48
Q

Benefits of a linked list

A

New items can be inserted without rearranging all the other elements

If programmed dynamically uses memory more efficiently

49
Q

Drawbacks of a linked list

A

More complex to program than an array

Extra programming required to access the data in the opposite direction

Can only be accessed in a linear manner

50
Q

Why are data structures useful in computing

A

They are the best way of organising data related to a real problem

51
Q

What are the advantages of data structures

A

Allows for the efficient processing of the data

E.g. sorting and searching

52
Q

Add item to a queue pseudocode

A

Procedure AddtoQueue(NewItem)
If EndPointer < MaxSize then
Queue[EndPointer] = NewItem
Endpointer = endpointer + 1
Else
Output “queue is full”

53
Q

Compare linked lists to 1d arrays

A

They are both used to hold a list of data but linked list has a few advantages over 1d array:

-linked list is a dynamic data structure (size can be increased/decreased as required. An array is static and therefore its size fixed)

-items can be added to the list without having to remove existing items to make space

-items can be removed from a linked list without having to shift other items to fill the gap left

Linked list uses more memory than an array as it needs to store the address/reference of the next node in addition to the data

54
Q

How is the free list used in linked lists

A

Items that are removed from the linked list are added to the front of the free list

Items that are added to the linked list are obtained from the front of the free list

55
Q

Pseudocode procedure to display all the items in a linked list

A

Procedure DisplayAll
p = start
While p <> -1
Display data(p)
p = next(p)
End while
End procedure

56
Q

Pseudocode to search for an item in a linked list

A

P = start
Found = false
While p <> -1 and found = false
If searchitem = data(p) then
Found = true
Display “Found it”
Else
P = next(p)
End if
End while
If Found = false then
Display “Item not found”

57
Q

What are nodes with no children called

A

Leaf nodes

58
Q

How do you represent data in a binary tree in a table

A

Using a 3d array

Horizontal column arrays = left, data, right

Vertical column: 1,2,3,4,5 etc.

59
Q

Pseudocode to search a binary tree

A

P = root
Found = false
While found= false and p <>-1
If searchitem = data(p) then
Found=true
Display “Found item”
Else if searchitem < data(p) then
P = left(p)
Else
P = right(p)
End if
End while

60
Q

Why is a binary tree recursive

A

The traversal algorithm uses itself to traverse the child nodes

61
Q

Algorithm for pre order traversal

A

Procedure PreOrderTraverse(root)
Visit the root node
If there is a left subtree then
PreOrdeTraverse(left sub-tree)
If there is a right subtree then
PreOrderTraverse(right sub-tree)
End procedure

62
Q

Algorithm for in order traversal

A

Procedure InOrderTraverse(root)
If there is a left sub-tree then
InOrderTraverse(left sub-tree)
Visit the root node (e.g. display it)
If there is a right sub-tree then
InOrderTraverse(right sub-tree)
End Procedure

63
Q

Algorithm for in order traversal

A

Procedure InOrderTraverse(root)
If there is a left sub-tree then
InOrderTraverse(left sub-tree)
Visit the root node (

64
Q

Algorithm for post order traversal

A

Procedure PostOrderTraversal(root)
if there is a left sub-tree then
PostOrderTraverse(Left sub-tree)
If there is a right sub-tree then
PostOrderTraverse(right sub-tree)
Visit the root node
End procedure

65
Q

Describe the characteristics of a linked list

A

Dynamic data structure - can grow or shrink in size after declaration

Each element in the list is known as a node, first element being the head node

Each node consisted of the data itself and the address/reference to the next node

Computer Science Cards Rewrite (18 decks)

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