COMPUTER SCIENCE CHAPTER 2 - FUNDAMENTALS OF DATA STRUCTURES

Question 1

array

Answer 1

-a variable that can contain more than one data item
-items can be changed or replaced

Question 2

contiguous

Answer 2

all data is stored together

Question 3

heterogeneous

Answer 3

can support more than one data type

Question 4

homogenous

Answer 4

only support a single data type

Question 5

tuples

Answer 5

-lists that can’t be changed once created
-fixed size
-immutable so cannot be changed or replaced
-can store more than one data type

Question 6

lists

Answer 6

-can be changed after created
-not a fixed size but can grow or shrink in size
-mutable as items can be changed or replaced

Question 7

file handling

Answer 7

opening, closing, writing to and reading from files by program codes

Question 8

binary file

Answer 8

-considered to be any file that isn’t a text file
-contains records of many different types of data
-stored as a pure binary number takes up less space
-reading it is language-specific so it requires you to know exact structure of file

Question 9

writing data to a file

Answer 9

1-open the file
2-write the data to the file
3-close the file

Question 10

reading / searching data from a file

Answer 10

1-open the file
2-create a boolean variable and set it to false, to indicate the end of file is not reached
3-while the end of file has not been reached , continue reading data from the file
4-compare if data matches the search criteria and if it does output it
5-check if end of file is reached and set boolean variable to true
6-close the file

Question 11

reading data from text files

Answer 11

1-open the file
2-use a flag to indicate end of file is reached
3-iterate through all the data in the file
4-end of file or output data from file
5-close the file

Question 12

writing data from files

Answer 12

1-open the file
2-write character data to the file
3-close the file of characters

Question 13

text file

Answer 13

contains human-readable characters organised into lines and can be read, created or edited by a computer program

Question 14

data structure

Answer 14

way of organising and storing data in a computer so it can be accessed and modified

Question 15

examples of data structure

Answer 15

-stacks
-queues
-graphs
-trees
-hash tables
-dictionaries
-vectors

Question 16

static data structures

Answer 16

-organisations or collections of data in memory that are fixed in size
-max size needs to be known in advance
-memory can’t be relocated once program is running

Question 17

dynamic data structures

Answer 17

-organisations or collections of data in memory that have the flexibility to grow or shrink in size
-programmer has control over how many memory is used

Question 18

static data advantages

Answer 18

-fixed memory allocation so no issues with adding or removing items from data structure
-easier to program as no need to check the size of data structure before accessing it

Question 19

static data disadvantages

Answer 19

-can be inefficient as memory for data structure is set aside at start so may not be utilised

Question 20

dynamic data advantages

Answer 20

-makes efficient use of memory as data structure only uses as much memory as it needs

Question 21

dynamic data disadvantages

Answer 21

-runs risk of overflow if it exceeds limit or underflow it its too empty
-harder to program as code needs to keep track of data structure size and location of items inside

Question 22

stack

Answer 22

-data structure that is essential for the operation of a computer
-LIFO (Last In First Out) structure as last item to be pushed onto stack must also be the the first to be popped off
-has a stack pointer that always points to the node at the top

Question 23

stack underflow

Answer 23

-attempt to pop an item off a empty stack

Question 24

stacks are used for:

Answer 24

-performing depth first searches on graph data structures
-keeping track of user inputs for undo operations
-backtracking algorithms , e.g maze
-evaluating mathematical expressions without brackets

Question 25

operations performed on a stack:

Answer 25

-push=adding an item to the top of the stack -pop=removing an item from the top of the stack -peek=returning the value from the top of the stack without removing it

Question 26

queue

Answer 26

-linear data structure -items are enqueued at the back of the queue and dequeued from the front of the queue -FIFO structure (First In First Out)

Question 27

priority queue

Answer 27

allows people to jump the queue

Question 28

circular queue

Answer 28

where the front and back pointers can move over the 2 ends of the queue

Question 29

linear queue

Answer 29

has 2 pointers and is used to identify where to place a item in a queue or to identify if there is a place at the front

Question 30

back/tail pointer

Answer 30

always points to the next available space

Question 31

front / head pointer

Answer 31

always points to the first item

Question 32

queue overflow

Answer 32

attempt to enqueue an item in a full queue

Question 33

queue underflow

Answer 33

attempt to dequeue an item in a empty queue

Question 34

queues are used for

Answer 34

-process scheduling -transferring data between processors and printer -performing breadth first searches on graph data structure

Question 35

operations performed on a queue

Answer 35

-enqueue=adding an item to the back of the queue -dequeue=removing an item from the front of the queue -peek=returning the value from the front of the ques without removing it

Question 36

programming a queue

Answer 36

-IsEmpty - returns the true if the queue has no content and it compares the front and back pointers -IsFull - returns true if the queue has no available position after the front pointer

Question 37

programming a stack

Answer 37

--IsEmpty and IsFull - same function as a queue -Stack.Peek()- returns (what it outputs )the value but doesn’t change the stack in any way -Stack.Push(“ “)-moves stack pointer to the top stack pop () - removes the first item and drops the stack pointer to item below - can also be used to assign variables or constants e.g. X ( arrow pointing to X) stack.pop this would sssing the value to X

Question 38

how to add an item to a stack (array)

Answer 38

1-check for stack overflow 2-move up stack pointer 3-insert new item at position where stack pointer is pointing at

Question 39

how to add an item to a stack (object)

Answer 39

1-check for stack overflow 2-create a new node and insert data 3-new node points to previous node 4-stack pointer points at new node

Question 40

how to add an item to a queue (array)

Answer 40

1-check for queue overflow 2-move up the tail pointer 3-insert new item where tail pointer is facing

Question 41

how to add an item to a queue (object)

Answer 41

1-check for queue overflow 2-create a new node and insert data 3-back pointer points at new node 4-if its the 1st node the front pointer points at new node

Question 42

how to remove an item from a stack (array)

Answer 42

1-check for stack underflow 2-copy data item pointed by pointer 3-reduce pointer

Question 43

how to remove an item from a queue (array)

Answer 43

1-check for queue underflow 2-copy data item pointed to by head pointer 3-move up the head pointer

Question 44

how to remove an item from a stack (object)

Answer 44

1-check for stack underflow 2-output node pointed to by stack pointer 3-set stack pointer to previous item

Question 45

how to remove an item from a queue (object)

Answer 45

1-check for queue underflow 2-output mode pointed to by front pointer 3-set front pointer to previous item

Question 46

traverse through a stack or queue

Answer 46

-use peek to look at front or top item

Question 47

graph

Answer 47

data structure consisting of nodes / vertices and pointers / edges

Question 48

the edges in a graph can :

Answer 48

-point in one direction (directed graph) -not specify a direction (undirected graph)

Question 49

edge value

Answer 49

required for some algorithms, can represent distance and time

Question 50

adjacency matrix

Answer 50

store graphs ,, each node in the graph is assigned a row and a column

Question 51

adjacency list

Answer 51

only records existing connections in a graph,, stores a list

Question 52

graphs implemented as a list of dictionaries

Answer 52

-the dictionary key represents the nodes -dictionary values represent the edge weights

Question 53

unweighted graph

Answer 53

-no edge weights so doesn't require a list of dictionaries -adjacency list contains a list of nodes

Question 54

advantages / disadvantages of adjacency matrix

Answer 54

-it’s time efficient as it allows you to query a edge very quickly by looking up its row and column -ADV -its memory inefficient as it stores every possible edge between nodes even though it doesn’t exist -DISADV

Question 55

advantages / disadvantages of adjacency list

Answer 55

-it's memory efficient as it stores edges that exist in a graph -ADV -it's time inefficient as it takes time to search each edge as the whole list needs to be searched-DISADV

Question 56

uses of graphs in computer science

Answer 56

-mapping road networks -storing social network data -resource allocation in operating systems -representing molecular structures and geometry

Question 57

operations performed on a graph (standard operations)

Answer 57

-adjacent=returns whether there is a edge between 2 vertices -neighbours=returns all vertices between 2 vertices -add=adds a new vertex from the graph -remove=removes a vertex from the graph -add edge=adds a new edge connecting one vertex to another -remove edge=removes edge connecting two vertices -get vertex value=returns data stored in a vertex -set vertex value=sets data for a vertex -get edge value=returns value of edge between 2 vertices -set edge value=sets value of edge between 2 vertices

Question 58

operations on a graph (search operations)

Answer 58

-depth first searches=starts at root of vertex then visits each vertex and explores each branch as far as possible before backtracking -breadth first searches=starts at the root node and visits each neighbouring node before making to vertices at next depth

Question 59

operations performed on a graph (traversal operations)

Answer 59

-pre-order traversal -in-order traversal -post-order traversal

Question 60

tree

Answer 60

connected, undirected graph with no cycles (no path in the tree that returns to the start node without going back and forth an edge twice)

Question 61

rooted tree

Answer 61

-one vertex had been designated as the root -root connects to 0,1 or more child nodes

Question 62

leaf nodes

Answer 62

nodes at the very bottom of the tree

Question 63

subtree

Answer 63

set of nodes or edges from a single node down through all its descendant

Question 64

typical uses for rooted trees

Answer 64

-storing and managing file and folder structures -implementations of A* pathfinding algorithms -storing and manipulating any form of hierarchical data that requires a parent node to have 0,1 or more child nodes

Question 65

binary tree

Answer 65

-standard rooted tree data structure consisting of nodes and pointers. -each node can have 0,1,2 pointers

Question 66

binary tree used in computer science

Answer 66

-database applications where efficient searching and sorting is required without moving items -wireless networking and router tables -operating systems scheduling process -huttman coding used for algorithms like Javascript and MP3

Question 67

operations performed on a tree

Answer 67

-add=adds a new node to the tree -remove=removes a node from the tree -binary search=returns data stored in a node -pre-order traversal= type of depth first search -post-order traversal="" -in-order traversal="" breadth-first search=starts at the root node and visits each node at same level before going deeper into the structure

Question 68

hashing algorithm

Answer 68

value ( arrow pointing to value) input hash ( arrow pointing to value) value MOD 3 RETURN Hash

Question 69

hash table

Answer 69

immediately finds a item in a sorted or unsorted list without the need to compare other items in the data set

Question 70

hashing function

Answer 70

used to calculate the position of a item in a hash table

Question 71

collision

Answer 71

hash table needs to be large enough to store all the data items but is larger to minimise the chance of algorithm returning to the same value for more than one item

Question 72

a good hashing function:

Answer 72

-calculated quickly -very few collisions -use as little memory as possible

Question 73

strategies to resolving collisions

Answer 73

-open addressing -linear probing -chaining

Question 74

open addressing

Answer 74

repeatedly check next available space in table with empty position is found

Question 75

linear probing

Answer 75

hashing function delivers start position from which linear search can be applied till item is found

Question 76

chaining

Answer 76

more than one item can be stored at the same position if using a 2 dimensional table

Question 77

disadvantage of linear probing

Answer 77

-prevents other items from being stored at their correct location -results in clustering (several positions being filled around common collision values)

Question 78

rehashing

Answer 78

finding a alternative position for items in a hash table

Question 79

applications of a hash table

Answer 79

-file systems linking a file name to path of file -identifying the keywords in a programming language during competition

Question 80

operations performed on hash table

Answer 80

-add=adds new item to hash table -remove=removes item from hash table =retrieve=retrieves an item from a hash table using its hash value

Question 81

adding a item to a hash table

Answer 81

1-calculate position of item using a hash function 2-if calculated position is empty insert item and stop 3-if calculated position isn't empty check 1st position in overflow table -a-if position is empty insert item and stop -b-increment position to check overflow table -c-repeat from step 3a

Question 82

removing an item from a hash table

Answer 82

1-calculate position of item in hash table using hashing function 2-if calculated position contains item to be deleted , delete and stop 3-if calculated positions doesn't contain items to be deleted a-if position contains item to be deleted just delete and stop b-increment position to check in overflow table c-repeat from step 3a until item to delete is discovered

Question 83

traversing a hash table

Answer 83

1-calculate position of item in hash table using hashing function 2-check if item in position is item to be found 3-if calculated position doesn't contain item to be found , move 1st position to overflow table a-check if item in that position is to be found b-if not increment to next position in overflow table c-repeat from step 3a until item is found

Question 84

dictionary

Answer 84

general purpose, abstract data structure used for storing groups of objects

Question 85

a dictionary has

Answer 85

-a set of keys -each key has a single value associated with it -when key is supplies, associated value is returned

Question 86

operations required to implement a dictionary:

Answer 86

-create a new empty dictionary -add a new key value pair -amend value of a key value pair -return the value of the key -return TRUE or FALSE -return the length of the dictionary

Question 87

use of dictionaries

Answer 87

-storing and retrieving data efficiently -implementing other data structures -counting groups of data -mapping and translating data

Question 88

vectors can be

Answer 88

stored easily in a computer as numbers , they can represent: -position, velocity, acceleration and force

Question 89

vectors

Answer 89

series of numbers that represents information

Question 90

vectors may be represented using notations like:

Answer 90

-list of numbers (R^4 , 4 vector over R) -dictionary (R^4 , 4 vector over R) e.g. 0:2,1:110 -2-d array , e.g. my vector [0] = 42 -function , e.g =. 0 (arrow) 42 ,, arrow symbol=maps too

Question 91

scaling

Answer 91

scalar-vector multiplication

Question 92

translation

Answer 92

vector addition

Question 93

convex combination of vectors

Answer 93

-shaded area between 2 vectors -aU + Bv -u and v are vectors - a + B = 1 - a and B must be greater than or equal to 0

Question 94

dot product or scalar product of 2 vectors is found by:

Answer 94

-multiplying each component of the first vector X bye each matching component of the second vector , then adding all the results together e.g. U [U*1, U*2, U*3...] V [V*1, V*2, V3...] = U*1 x V*1 + U*2 x V*2 + U*3 x V*3]...

Question 95

producing dot product of 2 vectors purpose:

Answer 95

-used to find the angle between two vectors

Question 96

formula for finding angle between 2 vectors:

Answer 96

- cos (0) = A.B / (||A|| . ||B||)

Question 97

"." meaning

Answer 97

to multiply together

Question 98

how to find the angle between 2 vectors:

Answer 98

1-calculate the dot product of A and B 2-calculate the lengths of vectors ||A|| and ||B|| using Pythagoras 3-calculate ||A|| and ||B|| 4-calculate cos(0)