Brainscape's Knowledge GenomeTM

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


See full index

Computing A level > Pseudocode and Algorithms > Flashcards

Pseudocode and Algorithms Flashcards

1
Q

queue

A

FIFO data structure: ordered collection of items added at the rear and removed from the front. sequence depends on order inserted, size depends on number inserted

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

array

A

a finite, ordered set of elements of the same type. grouped under one identifier, each element addressed using index

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

index

A

used to reference EACH element of an array

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

elementary data type

A

data type built into a programming language e.g. VB, pascal, python

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

tuple

A

dynamic data structure: ordered set of elements not necessarily of the same type able to inc/dec in size

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

structural data type

A

collection of data (made up of a number of elements) of a specified type e.g. array, string, record

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

primitive data type

A

data type PROVIDED by a programming language

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

n-dimensional array

A

a finite, ordered set of elements of a specified type indexed by n integers

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

abstract data type

A

a data type created by the programmer rather than defined by the programming language.
logical description of how data is viewed and operations that can be performed on it
programmer decides how to build and implement it and uses data types from programming language, user just needs to know state and behaviour
uses data abstraction: encapsulation, hiding details and implementation from user

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

encapsulation

A

ensuring a subroutine is completely self contained and independent of any global variables

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

dynamic data structure

A

data structure (a COLLECTION of data of a specified type in memory) with the ABILITY to grow and shrink in size in run time, with the aid of a heap

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

heap

A

portion of memory which is AUTOMATICALLY allocated and deallocated space as required (dynamic data structures)

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

adv of dynamic data structures and built in dynamic data structure

A
  • good for implementing data structures when you don’t know max size in advance (can have arbitrary max to prevent overflow but not necessary to allocate memory beforehand)
  • if built in dynamic data structure- many methods and functions e.g. pop already written and can be used in other data structures
  • good use of memory: only takes up storage required
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

disadv of dynamic data structures

A
  • can cause OVERFLOW if exceeds max memory limit
  • needs memory to store pointers
  • harder to program
  • often time consuming to search
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

static data structure

A

data structure (collection of data of a specified type in memory) which is fixed in size at compile time so can’t inc in size or free up memory whilst the PROGRAM IS RUNNING

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

adv static data structure

A
  • suitable for storing a fixed number of items e.g. months of year
  • size is known so easier to program
  • no need for memory wasted on pointers
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

disadv static data structure

A
  • size decided in advance and no more items can be added if full, irrespective if free space in memory
  • wastes storage if items stored is small relative to size of data structure
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

algorithm

A

a sequence of steps / set of rules SPECIFYING how to solve a problem, including inputs outputs and processing, written in a way it can easily be translated into high level code and then machine code for execution by the computer if in context of programming.
execute in finite time and produce an expected output for given inputs

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

a good algorithm

A
  • DESIGNED in such a way that others can UNDERSTAND and MODIFY if necessary
  • CLEAR, PRECISELY stated steps with correct OUTPUT for any valid input
  • should allow for invalid inputs
  • should execute efficiently with as few steps as possible
  • should TERMINATE at some point
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

pseudocode

A
  • halfway between a program, with its structural functions and english, with a solution expressed in a way that can be easily translated, and easily readable WITH NO CONCRETE SYNTAX
  • helps develop and outline algorithms and understand the functioning
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

input and output pseudocode

A

print(“what is your name”)
myname= input()

OR

myname= input(“what is your name”)

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

integer

A

whole number

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

float/real

A

number with a fractional part

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

boolean

A

only takes values of true or false

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

character

A

a letter, number or special character typically represented in ASCII

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

string

A

a number of characters, enclosed in single or double quote marks

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

how to round a number to 3 dp

A

round(mynum,3)

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

exponentials

A

y=x**5 or y= x^5

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

finding remainder

A

20 mod 3 = 2

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

dividing whole

A

20 div 2 = 10

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

find length of string

A

len(string) or stringx.length, returns index of first character, and -1 otherwise. assume 1 is first element of string

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

find ‘me’ in a string called firststring

A

firststring.find(me)

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

finds ASCII value of a character

A

ord(“a”)

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

chr(97) ?

A

finds the CHARACTER value represented by an INTEGER

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

“Johnny” + “Bates” - what does this do

A

concatentate strings

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

convert char to integer

A

int(“1”)

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

convert integer to string

A

str(123)

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

convert string to float

A

float(“123.4”)

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

date format

A

date(year, month, date)

printed: year-month-day

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

variables

A

identifiers (names) for memory locations whose contents will change throughout the course of the program

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

constants

A

values that never change WHILST THE PROGRAM is being run

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

why have constants

A

in a LONG complex program: no chance of accidentally changing a value by using the identifier for something else

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

how to define constants

A

CONST companyPhone = “0124638393”

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

why have meaningful var names

A

easier to follow and update

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

why have standards e.g. camelCaps for var names

A

less errors and inconsistencies

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

standards for var names

A

camelCaps, short meaningful names, caps for constants

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

program constructs

A

selection, sequence, iteration

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

sequence

A

two or more statements following one after the other. all statements are executed once in the order they appear

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

assignment statement

A

a statement where a value is assigned to a variable

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

selection

A

used to select which statement will be executed next, depending on some condition, formulated using a relational operator. some statements may not be executed as a result.

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

not equal to pseudocode

A

!=

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

selection eg

A

if..then..else, switch/case statement

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

what is a nested loop

A

a loop is placed within another allowing you to have several alternatives

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

why have a switch/case

A

useful when have several alternatives

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

switch case pseudocode

A 
switch choice:
     case 1 : print....
     case 2: ....
     case 3 : ...
else
     print ("...")
endswitch
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

which boolean operators take precedence

A

brackets then AND then OR

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

iteration

A

repetition, involves involves a loop to repeat a number of statements. It is either controlled by a condition or repeats a set number of times

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

iteration eg

A

while. ..endwhile
repeat. ..until
for. ..next

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

while…endwhile properties

A

expression controlling loop = boolean
expression tested at start of every loop :
so input to be tested should be at end of loop

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

repeat…until properties

A

boolean expression tested at end of program

done at least once

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

for…next properties

A

useful when know how many iterations to be performed

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

for…next pseudocode

A

for count = 2 to 12
product = 2 * count
print (“….”)
next count

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

how to generate a random number between 1 and 6

A

random(1, 6)

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

subroutines

A

a named block of code/SECTION OF THE PROGRAM performing a specific task within the program, used in a long complex program to break it into subroutines: helpful for designing a satisfactory solution. Used in modular programming

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

function aka inline

A

a subroutine which assigns a return value to a variable and can be used within expressions

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

procedure

A

called by just writing its name but does not assign a result to a variable

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

existing system function

A

len(x), int(“12”), input

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

procedure call vs procedure declaration

A

displayMenu = procedure call in main program

procedure displayMenu = procedure declaration

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

how to call a function in main program

A

option = getChoice //getChoice is function
print (option)

function getChoice
...
     choice = input()
     return choice
endfunction
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
70
Q

parameters

A

used to pass values or variables into a subroutine

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

byval

A

a copy of the actual value is passed and treated as a local variable so value outside the subroutine is not affected

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

byref

A

the address of the parameter is passed so if the value is change, it changes in the main program also

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

pseudocode byval vs byref

A 
procedure abc(x, y: integer; var z: integer)
 if var then byref, so z is byref
x, y is byval
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
74
Q

global variable

A

declared at the top. its scope is the whole program, so it can be accessed throughout the program. it allows data to be shared between subroutines.

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

local variable

A

can be used within a subroutine: its scope is the subroutine itself and only exists during its execution, can’t be accessed outside the subroutine and changing it has no effect on variables outside even if same name

76
Q

encapsulation

A

ensuring a subroutine is COMPLETELY self contained and independent of any global variables

77
Q

modular programming

A

when a long, complex program divided into separate self contained, specific well defined, tasks which can be WRITTEN and tested individually and subdivided further into smaller modules

78
Q

advantages of subroutines

A
  • understandable as a unit of code so can easily be modified, debugged, maintained, understood especially if the purpose is clearly DEFINED and documented
  • can be tested independently, so shortens time to get the whole program working
  • can reuse in different parts of the program/different programs once thoroughly tested
  • programmers can be given a set of subroutines to work on so program is finished sooner
  • the large program is easier to maintain and control
79
Q

IDE

A

integrated development environment: a single program helping you write and develop the program more easily made from a number of components. Provides you with many tools to help you enter, edit, compile, test and debug programs

80
Q

what can an IDE do

A
  • step through the code: allowing the programmer to see the effects of each line of code
  • debugging tools allow inspection of variable values, allowing run time detection of errors
  • set a watch on a variable so value is displayed every time it changes
  • insertion of a breakpoint allows the program to be stopped at a predetermined point in order to inspect its state
  • can display stack contents, to show the sequencing through modules/procedures
  • code can be examined whilst running, helping logical errors to be pinpointed
  • can produced a crash dump, showing the state of variables at the point an error occurs
81
Q

testing solutions

A

its complex and time consuming but has to be done throughly and systematically to try and uncover undetected errors. program should work irrespective of data inputted

82
Q

procedural programming

A

a program written with a series of step by step instructions on how to solve a problem, usually broken down into a number of smaller modules with calls in the main program to procedures and functions, calling other procedures and functions in turn

83
Q

how to interpret algorithms

A

look at comments
look at variable names
follow steps of program
dry run the program

84
Q

dry running

A

follow the logic program in the sequence of the computer and note whenever a variable value changes in a trace table and to what value

85
Q

divide and conquer algorithm

A

breaking situation into component parts then solving each separately eg binary search: whenever a guess is made, the search area is halved

86
Q

why have object orientated approach

A

water of time to decide how to implement abstract data structures and write own subroutines

87
Q

those using data structure only need to know

A

state and behaviour

88
Q

linear search

A

if items aren’t in a particular sequence, search one by one until required item is found or the end of the list is reached

89
Q

when are searching algorithms used

A

when searching items in a file or array in memory

90
Q

binary search

A

much more efficient but must be sorted. a divide and conquer algorithm: the portion of the data list to be searched repeatedly divides in half that could contain the desired item. Continued till only 1 item left

91
Q

types of test data

A

normal, boundary, erroneous

92
Q

normal test data

A

within the expected range and correct data type

93
Q

boundary test data

A

data at the ends of the expected range

94
Q

erroneous

A

outside the expected range or wrong data type

95
Q

initialise queue pseudocode

A 
procedure initialise
  front = 0
  rear = -1
  size = 0
  maxSize = len[array]
endprocedure
96
Q

test empty queue pseudocode

A 
function isEmpty
  if size == 0 then
    return TRUE
  else
    return FALSE
  endif
endfunction
97
Q

test full queue pseudocode

A 
function isFull
  if size == maxSize then
    return TRUE
  else
    return FALSE
  endif
endfunction
98
Q

add element queue pseudocode

A 
procedure enqueue(newitem)
  if isFull then
     print ("queue is full")
  else
     rear = rear + 1 MOD len[array]
     queue[rear] = newitem
     size = size + 1
  endif
endprocedure
99
Q

remove element queue pseudocode

A 
function dequeue
  if isEmpty then
    print ("queue is empty")
    item = null
  else
    item = queue[front]
    front = front + 1 MOD len[array]
    size = size - 1
  endif
  return item
endfunction
100
Q

why use a good sorting algorithm

A

reduces time spent on the task and for inc efficiency

101
Q

bubble sort

A

one of the most basic sorting algorithms. bubble up the largest/smallest item to the end of the list, then the second then the third until no more swaps needed

102
Q

how does a bubble sort work

A

bubble up the largest /smallest item to the end of the list etc until no more swaps needed. compare each item with the one next to it and swap if greater. repeat n-1 passes, reducing by one on each pass the number of elements to be examined. first n-1 comparisons then n-2 etc

103
Q

what is a flag for

A

to ensure no unnecessary passes are made through an already sorted list

104
Q

record

A

stores data permanently to read and up date in future in a file on disk. allows the creation and interrogation own files. files consist of a number of records. a record consists of a number of fields each holding one item of data

105
Q

record pseudocode

A

studentType= record
integer ID
string firstname
end record

variable studentA: studentType
studentA.surname=…..

106
Q

queue uses

A
  • output waiting to be printed, stored as a queue on disk: printed first come first serve
  • characters typed on a keyboard held in a keyboard buffer
  • simulation problems- modelling real life situations to learn something from it: eg optimum number of cashier queues using random number of customers, spending a random amount of time
107
Q

ways of implementing a queue

A
  • as items leave, all elements move up 1 space: front of queue always first element BUT a lot of processing time if long queue
  • implemented as an array with pointers to front and rear. Integer holds max size of array and no. items in queue BUT as space removed from front, free space can’t be filled, and can’t add anymore when rear pointer at the end of array
108
Q

circular queue

A

overcomes limitation of a static data structure, When queue full, rear pointer points to first element q[0] where next item will fill assuming empty

109
Q

problems of a circular queue

A

requires more effort from programmer and less flexible than dynamic if the maximum size isn’t known in advance

110
Q

list

A

an abstract data type consisting of a number of sequenced items where the same item may occur more than once. Sequenced so can refer/index a certain element

111
Q

list usefulness

A

useful for a variety of operations and can be used to implement other data structures eg queue

112
Q

list operation: isEmpty()

A

test for empty list, returns a boolean value

113
Q

list operation: append(item)

A

adds a new item to list at the end of the list

114
Q

list operation: remove(item)

A

removes the first occurance of an item from a list eg list1.remove(12)

115
Q

list operation: search(item)

A

search for an item in a list eg a.search(22) and returns a boolean value

116
Q

list operation: length()

A

returns the number of items

117
Q

list operation: index(item)

A

returns the position of an item

118
Q

list operation: insert(pos, item)

A

inserts a new item at position pos

119
Q

list operation: pop()

A

remove and return the last item in a list

120
Q

pop(pos)

A

remove and return the item at pos

121
Q

how else to implement a list

A

using an array(static data structure) if list data type isn’t supported and maximum number of data items is known in advance and small

122
Q

if an array is used to implement a list

A

programmer has to work out and code algorithms for each list operation

123
Q

inserting a new item into a list

A

test if full first, if held in sequential order, first determine where a new item to be added then start at end of list and move the rest of items along in order to make room

124
Q

deleting an item from the list

A

after item deleted, the items after have to be moved up one to fill up gap, so are copied into the previous spot in array then last element (duplicated now) is replaced with a blank

125
Q

stack

A

a last in first out data structure

126
Q

application of stacks

A
  • hold return addresses when subroutines are called
  • back button in web browsers
  • undo button in a word processor
127
Q

implementing stacks

A

implemented as static (eg array) with 2 more variables- pointer to top of stack and size of array/max stack size or dynamic

128
Q

stack operation: push(Item)

A

adds a new item to the top of the stack

129
Q

stack operation: pop()

A

removes and returns the top item from the stack

130
Q

stack operation: peek()

A

returns the top item from the stack but does not remove it

131
Q

stack operation: isEmpty()

A

tests to see whether stack is empty, returning a Boolean value

132
Q

stack operation: isFull()

A

tests to whether stack is full, and returns a Boolean value

133
Q

stack isEmpty pseudocode

A 
function isEmpty
  if top== -1 then 
    return TRUE
  else 
    return FALSE
  endif
endfunction
134
Q

stack isFull pseudocode

A 
function isFull
  if top==maxSize then
    return TRUE
  else
    return FALSE
  endif
endfunction
135
Q

stack push(item) pseudocode

A 
procedure push(item)
  if isFull then
    print ("Stack full")
  else
    top = top + 1
    s(top)= item
  endif
endprocedure
136
Q

stack pop pseudocode

A 
function pop
  if isEmpty then
    print ("stack empty")
    item = null
  else
    item = s(top)
    top = top - 1
    return item 
  endif
endfunction
137
Q

insertion sort

A

sorts one data item at a time, takes one data item from the list an dplaces it in the correct location in the list and repeated until no more unsorted data items in list. More efficient than bubble sort but less than quick/merge

138
Q

how insertion sort works

A

on each pass, current data item checked against those already sorted

139
Q

time complexity of bubble and insertion sorts

A

bubble sort close to n passes through list, with each pass requiring max n-1 swaps of order O(n^2)
Insertion sort has two nested loops so O(n^2) but if already almost sorted then reduced close to O(n)

140
Q

types of algorithms

A 
internet related (managing and manipulating huge amount of data on internet, finding pages with relevant info quickly)
route finding ( shortest/best distance between two points e.g. transmit packets of data and GPS)
compression algorithms (so can be transmitted faster or held in smaller storage space)
encryption (so if personal/confidential details intercepted, can't be read)
141
Q

Global v local variables

A

Global can be accessed in and outside subroutines and from more than one part of the program
Global is visible throughout program v visible in only one module/construct where declared

142
Q

Why global variables

A

Needs to be accessible from various parts of the program
Irrespective of where it’s accessed
E.g. Date

143
Q

Why prevent using global variables

A

Makes it difficult to integrate modules
Increases complexity of a program
Conflict with other names in other modules, changed inadvertently

144
Q

Why parameters better than global variables

A

Parameters only pass a copy of data so no unforeseen effects in other modules. (Case only if by val)

145
Q

logic error and when do they typically occur

A

an error in the logic of the code, although executing, causing it to produce unexpected results, resolved by performing a dry run with a trace table or setting breakpoints
they typically occur at points where decisions have to be made or in the conditions affecting the outcome of a decision

146
Q

syntax error

A

an error in the spelling and grammar of the code, identified by an interpreter, unable to execute a line of code

147
Q

execution error/runtime error

A

an error that becomes evident during run time, causing a crash because the program is being asked to do something it cannot e.g. retrieve an item from location 11 when only 10 locations

148
Q

linked list

A

dynamic data structure used to hold a sequence:

  • items in sequence not necessarily held in contiguous data locations or order which they occur in sequence
  • each item in list is called a node: it contains a data field (may consist of several subfields) and a next address field aka LINK/POINTER FIELD
  • Data field: holds actual data associated with the list item and pointer field holds address of the next item in the sequence
  • link field in last item uses null pointer to indicate no further items
  • associated with the list is a pointer variable, pointing to (containing the address of) the first node in the list
149
Q

how can linked lists be stored

A

array of records

150
Q

pseudocode: defining a node record

A

type nodeType
string name
integer pointer
endtype

(in delphi data type and identifier are the other way round and nodeType = record)

dim names[0..5] of nodeType

151
Q

initialising a linked list

A

One array consisting of one linked list of free space. Nextfree pointer = address of first item eg 0
Start pointer = first data item in list = null
Last item in free space pointer = null (last available free space in list)

152
Q

start, nextfree and array pointers when data items have been added

A

start: points to the first data item in list
nextfree: points to next free location in array (and first free space in free space linked list)
Last data item pointer = null
Last available free space = null

153
Q

names[p].name

A

holds name in node[p] ie node pointed to by p

154
Q

names[p].pointer

A

holds the value of the pointer in node[p]

155
Q

priority queue

A

data structure: ordered collection of items removed from the front. Logical order is dependent on priority of jobs so not necessarily added to the rear.

156
Q

implementing a priority queue

A

start at the rear and moving along one place until item with same or higher priority is found, then inserted.

157
Q

Overflow and underflow

A

Occurs because not indefinite growth of memory. Occurs if reaches limit/is full and a POP operation is attempted or is empty and PUSH operation is attempted, causing it to crash.

158
Q

When is overflow/underflow likely

A

If a faulty piece ends up calling itself in an endless loop ie infinite recursion

159
Q

Call stack

A

Stores information about active subroutines whilst a computer program is running. Each call to subroutine is given separate space on the call stack for return addresses, parameters, local variables. Details are hidden from user in all high level languages.

160
Q

Call stack and return addresses

A

Call stack keeps track of return address ie address of the instruction control should return to once a subroutine is completed .
Nested subroutines = stack contains several return addresses which are popped as completed.
Recursive subroutines = several calls to itself, so pushes itself to stack as return address. Then popped each time the subroutine ends.

161
Q

Call stack and local variables

A

Local variables are only know within the subroutine. Storing on the call stack is more efficient than dynamic memory allocation which uses heap space.

162
Q

Stack frame

A

A call stack is composed of stack frames, each corresponding to a call to a subroutine which has not yet terminated. Holds local variables, return address and parameters.

163
Q

hash table

A

collection of items stored in such a way that they can be quickly located without looking through all the records eg customer records

164
Q

how to make data quickly accessible

A

generate index of the physical address of the file with the data on it using a hashing algorithm

165
Q

how is an index generated

A

hashing algorithm applied to value in the key field of each record to transform into address

166
Q

common hashing technique

A

dividing key by number of available addresses, and using remainder as address ie MOD

167
Q

define synonym

A

two keys which hash to the same address

168
Q

collisions (hashing)

A

when two record keys hash to the same address

169
Q

implementing a hash table

A

array/list of a given size with a number of empty spaces

170
Q

searching for an item in a hash table

A

apply hashing algorithm to key field
examine resulting cell in the list
if the item is there- return it
if cell is empty- item isn’t in the table
if another item in the spot- keep moving forward until found or blank cell (ie not in table)

171
Q

folding method hashing

A

divide record key into equal parts, and add them together. if > number of spaces in hash table, then MOD by number of cells

172
Q

hashing a string

A

add up ascii values and MOD by number of cells in table

173
Q

when are collisions more likely and when do you take this into account

A

when the hash table is more full. take this into account when designing a hashing algorithm and deciding on the table size- you want to MINIMISE COLLISIONS for efficiency eg make it that table is only 70% full when all the items are added

174
Q

rehashing

A

process of finding an empty slot when a collision has occurred, can do this by adding one to the hashed address or the ‘plus three’ rehash or hash incremented by 1,3,5..etc

175
Q

uses of hash table

A

efficient lookup eg organise indexes as hash table, looking up telephone numbers, user codes and encrypted passwords that need to be searched and verified quickly, implementing dictionary (data structure)

176
Q

dictionaries

A

abstract data types consisting of associated pairs of item: a key and a value. eg Whenever the user supplies a key, the value is returned.

177
Q

implementation of dictionaries

A

built in data structures in Python and VB, otherwise can be static or dynamic

178
Q

operations on dictionaries

A

Create new empty dictionary
Delete a key:value pair eg DEL IDs[188]
Add a pair eg IDs[333]= ‘Maria’
Amend a pair eg IDs[333]= ‘Mandy’
Return a value associated with key k eg IDs[127]
Return True or False depending on whether key is in dictionary eg 634 in IDs
Returns length of dictionary eg len(IDs)

179
Q

dictionaries and hash tables

A

hashing key gives address to store in a hash table for fast lookup

180
Q

other things IDE does

A

compile/interpret
save/load
run programs
display syntax errors

181
Q

when would you not binary search

A

when not in order
when list is too small
when list is skewed

182
Q

statement

A

a single instruction which can be executed. some statements can contain others, eg IF and WHILE statements

183
Q

recursive subroutine

A

a subroutine which is defined in terms of itself

184
Q

conditions for recursive subroutines

A
  • must have a base case/stopping condition, so when met it stops calling itself and starts to unwind
  • for input values other than the base case, the subroutine should call itself
  • the stopping condition should be reached after a finite number of calls
185
Q

advantages of iterative over recursive

A
  • there’s no limit to how many times you can call it (ie no stack overflow)
  • its easier to trace through

Computing A level (19 decks)

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