Brainscape's Knowledge GenomeTM

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


See full index

A LEVEL CS > Paper 1 > Flashcards

Paper 1 Flashcards

1
Q

What are some advantages of subroutines?

A
  • Individual models can be written and tested independently, speeding up development process
  • modules can be reused
  • large programs can be split up into smaller modules that are easier to read, debug and maintain
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Define representational abstraction

A

Abstraction of a problem arrived at by removing any unnecessary details

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

Define abstraction by generalisation

A

A grouping by common characteristics to arrive at a hierarchical relationship of the “is a kind type”

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

Define procedural abstraction

A

Using a procedure to carry out a sequence of steps for achieving some task.

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

What is functional abstraction?

A

Further abstracting a procedure, removing all details of the implementation of the procedure, resulting in just a function

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

What is data abstraction?

A

Knowledge of details of how data are actually represented are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects.

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

Define information hiding

A

Hiding all details of an object that do not contribute to its essential characteristics

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

Define decomposition

A

Breaking down larger problems into smaller, identifiable problems

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

Define composition

A

Putting together smaller tasks to make larger, compound problems

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

Define automation

A

Putting models (abstraction of real world objects/phenomena) into action to solve problems. This is achieved by:

creating algorithms
implementing the algorithms in program code

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

What is an ADT?

A

An abstract data type is a logical model of how data is represented and the operations performed on it

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

What is a queue?

A

A queue is a FIFO data structure. Items are added to the back and removed from the front

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

Differences between dynamic and static data structure

A
  • Memory allocated dynamically by aid of heap to dynamic data structures, whereas static data structures cannot change in memory as memory needs to be decided on creation of data structure
  • dynamic data structures may require use of pointer variables
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How to add an element to a circular queue?

A

SUB queue(newitem)
if isFull():
OUTPUT(“Queue is full”)
else:
rear = (rear + 1) MOD maxSize
queue[rear] = newItem

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

how to dequeue from a queue?

A

SUB dequeue
if isEmpty():
OUTPUT(“queue is empty”)
else:
item = queue[front]
front = (front + 1) MOD maxSize
size = size - 1
return item

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

What is a dictionary?

A

ADT consisting of associated pairs of items

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

Time complexity of bubble sort

A

O(n^2)

18
Q

Time complexity of linear search

A

O(n)

19
Q

Time complexity of merge sort

A

O(logn)

20
Q

Time complexity of binary search

A

O(nlogn)

21
Q

What is a set?

A

Unordered collection of unique items

22
Q

What is Z

A

set of integers

23
Q

What is Q

A

set of rational numbers

24
Q

What is R

A

set of real numbers

25
Q

what is N

A

set of natural numbers

26
Q

What is the meaning of this set in set notation?

All even numbers greater than 2

A

{2n | n e N ^ n > 1}

27
Q

What is the set comprehension form of the set of square numbers such that n belongs to natural numbers and is greater than 4

A

{n^2 | n e N ^ n > 2}

28
Q

Write the compact representation of set of strings with equal number of 1s and 0s

A

A = {0^n 1^n | n}

29
Q

What is the cardinality of a finite set?

A

Number of items in the set

30
Q

What is a subset

A

If every element of A is a member of B, A is a subset of B

31
Q

What is a proper subset?

A

If A is a subset of B, but not identical to B, A is a proper subset of B

32
Q

What is a regular language?

A

A language can be defined as regular if it can be represented using a regular expression. A regular language is any language that a finite state machine can accept/

33
Q

What does | mean

A

“OR”

34
Q

what does * mean

A

0 or more of the preceeding element

35
Q

what does + mean

A

1 or more of the preceeding element

36
Q

what does ? mean

A

0 or 1 of the preceeding element

37
Q

Why is a turing machine theoretically more powerful than any modern computer

A

it has infinite memory (has an infinitely long tape)

38
Q

what is a universal turing machine?

A

A UTM is a turing machine that is capable of simulating the behaviour of any Turing Machine.

It faithfully executes the operations, exactly how the simulated TM would

39
Q

What are the orders of time complexity?

A

Constant
Logarithmic
Polynomial
Exponential
Factorial

40
Q

How to represent the difference of two sets A and B?

A

A-B or A\B

41
Q

Minimum number of passes in binary search?

A

log base 2 n + 1

42
Q

Why is local variable preferable over global variables?

A

Scope is only within subroutine it was created in so cannot be affected outside the subroutine = less side effects

A LEVEL CS (3 decks)

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