Flashcards
Comp sci All topics part 1
Cards in this deck (195)
- 1What does a not gate look like and what are it's outputs
- 2What does an And gate look like and what are it's outputs
- 3What does an Or gate look like and what are it's outputs?
- 4What does an Xor gate look like and what are it's outputs?
- 5What does a Nand gate look like and what are it's outputs
- 6What does a Nor gate look like like and what are it's outputs?
- 7Why is Nand the universal gate?As it combines two gates in a single gate, different combinations can be used to recreate other gates
- 8Define HardwareHardware is the mechanical and electrical components of a computer
- 9Define SoftwareSoftware are the programs on the computer
- 10Define system softwareA program that manages the operation of the computer
- 11What is the role of an operating system?To manage the hardware resources in order to provide for an orderly and controlled allocation of the programs, memories and I/O devices among the various programs competing for them and manage the storage of data. It also hides the complexities of the hardware
- 12Define utility softwareUtility software is programs that assist with the running of a computer
- 13Define a LibraryA library is a collection of pre-compiled routines that can be used by other programs
- 14What is representational abstraction?representation arrived at by removing unnecessary details
- 15What is Abstraction by generalisation/categorisation?grouping by common characteristics to arrive at a hierarchical relationship of the 'is a kind of' type.
- 16What is procedural abstraction?The result of abstracting away the actual values used in a procedure
- 17What is functional abstraction?abstracting the values and the computational method.
- 18What is procedural decomposition?Dividing a problem into individual sub problems
- 19What is composition abstraction?combining procedures to form compound procedures
- 20What is data abstraction?combining data objects to from compound data
- 21Define application softwarecomputer software designed to perform a group of coordinated functions, tasks or activities for the benefit of the user
- 22What is a program counter?A program Counter is a register in a processor that contains the address of the instruction being executed at that time
- 23What is a memory buffer register?A register that stores the data being transferred ti and from the immediate access store
- 24What is the fetch execute cycle?1. Address of next instruction transferred from PC to MAR
2. PC incremented by 1
3.Instruction stored in location addressed by MAR is transferred to MBR
4.Instruction transferred from MBR to CIR
5.Instruction in CIR is decoded
6.Additional data if required by the instruction is fetched from memory and passed to the registers
7.Instruction is executed by the ALU
8.Registers are used to store intermediate data or results
9.The result is stored in the accumulator or general purpose register or memory - 25Define opcodeThe basic machine operation and the addressing code
- 26Define operandThe data or the address of the data depending on addressing mode
- 27What is the difference between immediate and direct addressing?Immediate is where the operand is the bit of data whilst in direct the operand is the location of the data.
- 28Define Baud rateBaud rate is how many times a signal can change a second
- 29Define bit rateHow many bits can be sent per unit time
- 30Define data typeThe specific category of data for a piece of data
- 31Define the following data types an integer, a real/float, Boolean, character, string, date/time, records and arraysInteger is a whole number.
real/float is a decimal number
Boolean is two states true or false
character is a letter or symbol
string is multiple characters
date/time is date/time
records is a piece of data in a table
array is a store of pieces of data - 32What is a variable?A value that is changed by the code when ran
- 33What is a constant?A value that isn't changed by the code when ran
- 34What is assignment?Setting one thing equal another
- 35What is iteration?Repeating through something for a certain amount of times or until a criteria is met
- 36What is selection?running something if a criteria is met
- 37What is a function and a procedure?A function is a group of code that returns a value a procedure doesn't have to
- 38How do you generate a random number in python?random.randint(x,y)
- 39What are local variables And what are the properties of them?Local variables are variables created within function. They exist only while the subroutine is executing and is only accessible only within the subroutine
- 40How do you read/write from/to a text file?open(r"File_Name","Access_Mode")
- 41Define an algorithmA sequence of steps that can be followed to complete a task and that always terminates
- 42Define natural numbersPositive integers including 0
- 43Define an integerA whole number
- 44Define Rational numbersAny number that can be represented by a fraction of two integers
- 45What is an irrational number?A number that can't be written as a fraction
- 46What is a Real number?Any number
- 47What are ordinal numbers?A number that describes a position
- 48What is base 10?A number system that each slot uses a range of 10 different values. E.g. decimal
- 49What is base 2?A number system that each slot uses a range of 2 different values. E.g. Binary
- 50What is base 16?A number system that each slot uses a range of 16 different values. E.g. Hexadecimal
- 51Convert 10110010 into decimal and hexadecimaldecimal = 128 + 32 + 16 + 2 = 178
Hex = First part = 8 + 2 + 1 = B
Second part = 2 = 2
= B2 - 52Convert 124 into binary and Hexadecimal124 - 64 = 60 60 - 32 = 28 28 - 16 = 12 12-8 =4 4-4 =0
01111100
124 / 16 = 7 remainder 12 12 = C
= 7C - 53Convert A4 into binary and decimalA = 10 10 - 8 = 2 2 - 2 = 0
4 - 4 = 0
A4 = 10100100
A = 10 10*16 = 160
4*1 = 4
160 + 4 = 164 - 54What is a byte?8 bits
- 55How many bytes are in KiB, KB, MiB, MB, GiB, GB, TiB, TB?KiB = 1024
KB = 1000
MiB = 1024 * 1024
MB = 1000 * 1000
GiB 1024 * 1024 * 1024
GB 1000 * 1000 * 1000
TiB 1024 * 1024 * 1024* 1024
TB 1000 * 1000 * 1000 * 1000 - 56What's the difference between signed and unsigned binarySigned uses a bit at the beginning to decide whether the number is positive or negative
- 57What are the minimum and maximum values for unsigned binary given n bits?0 and 2^(n) -1
- 58Add the two unsigned binary integers 01101011 and 0111010101101011
+ 01110101
= 11100000 - 59Multiply the two unsigned binary numbers 10110 and 11010110
110
10 * 10110 = 101100
100 * 10110 = 1011000
10000100 - 60Convert the two's compliment binary number 10110101 into decimal-128 + 32 + 16 + 4 + 1 = -75
- 61subtract 24 from 63 using two's compliment binary63 -24 = 63 +(-24) = 39
63 = 0111111
-24 = 1101000
(1)0100111
Remove carry bit as it is overflow
0100111 =
32 + 4 + 2 + 1 = 39 - 62convert 14.675 to 8 bit fixed point binary1110.1010
- 63What does ASCII stand for?American Standard Code for Information Interchange
- 64What is ASCII?ASCII is a binary representation of characters
- 65What is the difference between ASCII and unicode?Unicode uses 16 bits whilst ASCII uses 8
- 66What are the advantages of unicode over ASCII?Since unicode has more bits more characters can be represented. This has lead to characters from others languages to be represented in unicode
- 67Name four different types of error checking and correctionParity bits
majority voting
check digits
checksums - 68What are the two types of protocol used in parity bit checking?Odd parity and even parity
- 69How does parity bit error checking work?One bit in the byte of data sent is the parity bit. this dictates the total number of 1's and 0's in the byte. If even parity is used then the parity bit will be used to make sure there is an even number of 1's and 0's.
If odd parity is used then the parity bit will be used to make sure there is an odd number of 1's and 0's - 70How does majority voting work?The byte is sent 3 times then each bit is checked against the other two and the most common occurrence for each bit is selected
- 71Define a subroutineA named 'out of line' block of code that may be executed by simply writing it's name in a program
- 72What are the advantages of subroutines?Reduces duplication of code
Code can be reused in multiple programs
improves readability of code
Improves trace ability and shortens time to bug fix - 73Describe the use of parameters to pass data within the programParameters are values that are inserted into a subroutine which the subroutine can then act upon
- 74How do you return a value in a subroutineRETURN variablename
- 75Explain how a stack frame is used with subroutine calls to store return addresses, parameters and local variablesEach is inserted into the stack while the subroutine is running. When the subroutine is done the local variable values can be retrieved from the call stack if the subroutine is returned to. Parameters are held on the call stack to allow subroutines that require them to work properly once returned to. The return address is the location where the program will return to after the subroutine has finished. This is stored on the call stack so when the subroutine is done it returns to the correct place in the code
- 76Define recursionRecursion is where a subroutine calls itself within the subroutine
- 77What is a class?A class defines methods and attribute fields that capture the common behaviours and characteristics of objects
- 78What is an object?An instance of a class
- 79What is instantiation?Instantiation is the creation of an instance of a class
- 80Define encapsulationEncapsulation is attributes and methods being in a single entity
- 81what is inheritance?Gaining attributes and methods from a superclass to be used in a subclass
- 82Define aggregation associationEntity b exists without entity a
- 83Define composition aggregationentity b has no meaning to the system without entity a
- 84What is the symbol for composition?A filled diamond with a solid line
- 85What is the symbol for aggregation?An unfilled diamond with a solid line
- 86Define PolymorphismPolymorphism is when a method in a class hierarchy behave differently in each class
- 87What is overriding?Overriding is when a sub class creates it's own version of a method from a superclass
- 88Why is composition favoured over inheritanceIn java you can't do multiple inheritance. Inheritance breaks encapsulation
- 89How do you read from a 2-D array?vertically then horizontally
- 90Name all the ADT'sQueue
stack
graph
tree
hash table
dictionary
vector - 91What is the difference between a static and a dynamic data structureA static data structure has a fixed sized whilst a dynamic data structure has a varying size
- 92What are the advantages and disadvantages of static and dynamic data structuresNo oversight is needed for static as the memory size is fixed so there will be no overflow or underflow issues
Static is easier to program
Dynamic is more memory efficient as it takes up only the required amount of data needed, this also means the programmer can control the amount of memory used - 93In a queue how do you add an item, remove an item, test for an empty queue and a full queueenqueue() inserts an element to the end of a queue
dequeue() removes and returns the first element of the queue
isEmpty() return true if the queue is empty
isFull() return true if the queue is full - 94In a stack how do you do the following operations do? Push, pop, peek or top, test for empty stack and a full stackPop() Removes and returns the top element of the stack
Push() Inserts an element at one the top of the stack
peek() returns the element at the top of the stack without removing it
isEmpty() return true if the stack is empty
isFull() return true if the stack is full - 95What are the uses of graphs and give 3 examplesTo show the flow of computation
Google maps uses weighted graphs to work out shortest paths where intersections are vertices and edges are roads
Facebook users are considered vertices and if two users are friends then there is an edge between them. This is used in the suggest a friend algorithm
In the operating system there is the resource allocation graph where the
resources and process are vertices and the edges are from resources to allocated processes - 96Define a graphA graph is a non-linear data structure, which consists of vertices connected by edges where edges may be directed or un-directed
- 97Define a weighted graphA weighted graph is a graph where the edges have values
- 98Define a vertexIs a node within the graph
- 99Define an edgeAn edge connects vertices in a graph
- 100What is an un-directed graph?A graph where the edges have no direction and therefore the graph can be traversed in any direction.
- 101What is a directed graph?A directed graph is where the edges have a specific direction and can only be traversed in a specific direction
- 102What is an adjacency matrix?An adjacency matrix is a representation of which vertices are connected by edges. if the graph is weighted then the weight of each path is also shown
- 103What is an adjacency list?An adjacency list is a list for each vertex that display each connected vertex and the values of the edge if the graph is weighted
- 104Define a treeA tree is a connected undirected graph with no cycles
- 105What is a rooted tree?A tree with a vertex designated as the root. All other vertices have a parent-child relationships between nodes. The root is the only vertex with no parent and all other nodes are descendants of the root.
- 106What is a binary tree?A tree where each vertex has a maximum two children
- 107What are typical uses for a rooted tree?A binary tree can be used as a binary search tree
Family tree
organisation hierarchy tree - 108Define a hash tableA hash table is a data structure that creates a mapping between keys and values
- 109What are the uses of a hashing table?As a database
As caches to speed up the access to data - 110Using mod 6 store the following values into the hash table: 24, 37, 41, 8, 15, 640 : 24
1 : 37
2 : 8
3 : 15
4 : 64
5 : 41 - 111In a hash table when does a collision occur?A collision occurs when two key values compute to the same hash
- 112What is a dictionary?A collection of key-value pairs in which the value is accessed via the associated key
- 113What is the use of a dictionary?information retrieval
- 114In terms of vectors what does R^4 mean?4-vector over R meaning a vector with 4 different components
- 115In vectors what does f : S → R mean?The function f maps S to R
- 116Represent the following as a dictionary and a list • 0 ↦ 2.0 • 1 ↦ 3.14159 • 2 ↦ -1.0 • 3 ↦ 2.718281828Dictionary: {0:2.0, 1:3.14159, 2:-1.0, 3:2.718281828}
List [2.0, 3.14159, -1.0, 2.718281828] - 117Represent the following as a 1-D array [6, -2, 4]X Y Z
6 -2 4 - 118Calculate the following [2.3, 8.6] + [5.9, 3.4] [2.1, 3.4] * 2[8.2, 12]
[4.2, 6.8] - 119what is the equations for convex combination of two vectors and what does each letter mean?αu + βv
Where :
u and v are two vectors
α and β >= 1
α + β = 1 - 120Do the dot or scalar product of the following vectors: [6, 2] [3, 4]6*3 =18
2*4 = 8
18+8 = 26 - 121Name an application of dot productFinding the angle between two vectors
- 122Give an application of depth and breadth first traversalBreadth first: the shortest path for an unweighted graph
Depth first: Navigating a maze - 123Traverse the following tree using depth first and breadth first traversal. tree ---- j <-- root / \ f k / \ \ a h z \ dbreadth first = [j, f, k, a, h, z, d]
depth first = [j, f, a, f, h, k, z] - 124Traverse the following tree using pre-order in order and post order tree ---- j <-- root / \ f k / \ \ a h z \ dpre-order :[j, f, a, d, h, k, z]
in order: [a, d, f, h, j, k, z]
post- order : [d, a, h, f, z, k, j] - 125What are the uses of pre, in and post order traversals?pre order is used to for copying a tree
in order is used in a binary search tree to output the contents in ascending order
post order is used for infix to reverse polish notation conversions, producing a postfix expression from an expression tree, emptying a tree - 126Convert (2+4) * 6 + 8 into reverse polish notation24+6*8+
- 127Convert 728+*64/- into infix notation7*(2+8)-6/4
- 128Why is reverse polish used?It eliminates need for brackets in sub-expressions. Expressions in a form suitable for evaluation using a stack
- 129Where is reverse polish notation used?Giving two examples.Its used in interpreters based on a stack for example postscript and bytecode
- 130What is the time complexity of a linear search?O(n)
- 131How does a linear search algorithm work?Going through every item to find the correct one
- 132What is the time complexity of the binary search algorithm?O(log n)
- 133How does a binary search algorithm work?First the data has to be ordered. It checks the middle piece of data to see if the target data is greater than or less than this piece of data. It then changes it's parameters to be searching within the area that the target data is in. This process is repeated until the target piece of data is found
- 134How does a binary tree algorithm work?It looks at the root of the tree to see if the target piece is greater than or less than the root. It then moves to the side where the target piece of data is in and repeats the process until the target piece of data is found.
- 135What is the time complexity of the bubble sort algorithm?n^2
- 136How does a bubble sort algorithm work?It compares two adjacent items of data if one is greater than the other they are swapped this then continues until it reaches the end of the array. When the end on the array is reached this means the right most piece of data is sorted. this continues until all the data pieces are sorted
- 137How does a merge sort algorithm work?splitting up the data into pairs then sorting the pairs on which is greater. Then the pairs are merged with another pair and is sorted on which one is the greatest. Then these are merged together and sorted until the entire data collection is back together.
- 138How does Dijkstra's shortest path algorithm work?Going from a start node to a goal node each node with the shortest distance is visited. Each node apart from the initial starts with a values of infinity and is replaced with a different value if a path is found that has a lower combined value. When a node is visited it is added tho the visited list. The initial node starts with a value of 0. this continues until the goal node is reached and the lowest value to that path is set as its value.
- 139What is information hiding?Hiding all the details of an object that do not contribute to it's essential characteristics
- 140What is problem abstraction/reduction?Removing details until the problem is represented in a way that is possible to solve, because the problem reduces to one that has already been solved
- 141What is automation?Putting models into action to solve problems
- 142How is automation achieved?Creating algorithms
implementing the algorithms in program code
implementing the models in data structures
executing the code - 143What is the difference between an FSM and a Mealy machine.Mealy machine has outputs
- 144Define a setA set is an unordered collection of values in which each value occurs at most once
- 145What symbols denote a set?{}
- 146What does | mean in set notationsuch that
- 147Write the following numbers in a set using notation and set comprehension. 4, 1, 5, 2, 3A = {4, 1, 5, 2, 3}
A = {a | a ∈ N ^ a >= 1 ^ a <= 5} - 148What does ^ mean in set notation?and
- 149What does ∈ mean?is a member of
- 150What sets are denoted by the following letters : ℕ, Z, Q and RN = natural numbers e.g. positive integers
Z = Integers
Q = Rational e.g. any number that can be defined by a fraction of two integers
R = Any number - 151What are the symbols for an empty set?{} or Ø
- 152Write out the first three binary results of these compact string representations. {0(power)n 1(power)n| n>=1} {(01)(power)n| n>=1 ^ n≠3 } {01(power)n | n>=2}{01, 0011, 000111}
{01 , 0101, 01010101}
{011, 0111, 01111} - 153What is a finite set?A set where the elements can be counted using natural numbers and has an end e.g. 1st element 2nd element ..... 20th( and final element
- 154What is a infinite set?A set that goes on infinitely e.g. The set of natural numbers, ℕ and the set of real
numbers, ℝ - 155What is a countably infinite set?An infinite set that can be counted by natural numbers
- 156What is the cardinality of a finite set?The number of elements in a finite set
- 157What is the cartesian product of sets?The set of all ordered pairs e.g. (a,b) where a is a member of set A and b is a member of set B
- 158What does subset mean?A subset is where all the elements in set A are in set B
- 159What does proper subset mean?A subset where all the elements in set A are in set B but there is at least one element is set B that isn't in set A
- 160What is a countable set mean?A set with the same carnality as some subset of natural numbers
- 161What are the symbols for subset and proper subset?subset = ⊆
Proper subset = ⊂ - 162What do the following terms mean in terms of set intersection : A ∈ B , A ∪ B, A ∩ B and A\BA ∈ B = A is in set B
A ∪ B = All the elements unique in set A and set B
A ∩ B = All the elements that in both set A and B
A\B = All the elements that are in set A but not set B - 163What do the following metacharacters mean in terms of Regular expression? *, +, ? and |* = 0 or more
+ = 1 or more
? = 0 or 1
| = or - 164Describe the following Regular expression a(a|b)*1 a followed by any amount of a's and b's
- 165Define a regular languageAny language that can be represented by regular expression or an FSM
- 166Which of the following are accepted by the BNF of | 1. A2B 2. ABB 3. 2a2 4. 224 5. q661.yes
2.no
3. no
4. no
5. yes - 167Explain why BNF can represent some languages that can't be represented using regular expressionsBNF can represent a wider range of languages because it is much easier to define languages and takes less time. As well regular languages can't describe nested brackets
- 168How can two algorithms be compared?Expressing their complexity as a function relative to the size of the problem
- 169What are the two factors that effect the efficiency of an algorithmTime and space
- 170Define a functionA function is a mapping from one set of values, the domain, to another set of values, the co-domain.
- 171Give an example of a linear, polynomial, exponential and logarithmic function.K is just a constant
linear y = Kx
polynomial y = kx^k
exponential y = k^x
logarithmic y = log x - 172Give the time complexity in Big O notation of the following algorithms 1. n^2 + 4n 2. 8^n 3. n 4. 3 5. log n1. O(n^2)
2.O(8^n)
3.O(n)
4.O(3)
5.O(log n) - 173Sort the following in order of time complexity from worst to best. Constant Exponential linear logarithmic polynomial1. Exponential
2. polynomial
3. Linear
4. Logarithmic
5. Constant - 174Define tractable and intractable problemstractable are problems that has a polynomial or less time solution
intractable are problems that don't have a polynomial or less time solution - 175Describe the Halting problemThe halting problem is determining whether a program will stop if given an input
- 176What is the structure of a Turing machine?A tape divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. A head that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time. A state register that stores the state of the Turing machine. A finite table of instructions
- 177What is the importance of a Turing machine?Turing machine provide a general model of computation and provide a definition of what is computable
- 178Why are fixed point and floating point binary sometimes inaccurate?They can only go to a certain degree of accuracy as they can only represent some numbers
- 179How do you calculate the absolute and relative error between a number and it's fixed/ floating binary equivalent?Absolute :
fixed/floating number - actual number
Relative :
Absolute error/actual number - 180What are the advantages of and disadvantages of fixed point binary compared to floating point binary?fixed has a lower range and is generally less precise however it is quicker to calculate
- 181Normalise the following binary number with a 5 bit mantissa and a 3 bit exponent 11011001001 = 1
move floating point one to the right so that number start with 10
since we moved the point one to the right we minus 1 off the exponent
1-1 = 0
new exponent = 0 = 000
mantissa = 10110
new binary number = 10110000 - 182Explain underflow and overflow errors and explain when they occurAn underflow error is when a number is represented in binary it's lower than the actual value. An overflow error is when a number is represented in binary it's value is lower than the actual value. These occur when the number is a value that can't be represented in binary using either floating or fixed point so the number closest is used instead
- 183Explain how a check digit is used for verification on a barcodeAdd all the numbers up on the barcode except for the check digit(the far most right digit)
Add up all the numbers in the odd positions, then double it and add it to the the previous calculation
Subtract the last digit from the calculation from 10. the difference should be the check digit - 184How do checksums work?The data value is added up and a divisor is chosen. The data value is divided by the divisor and the remainder is taken and sent with the data. The recipient then does the same calculation do see if they get the same remainder
- 185Describe how bit patterns may represent other forms of data.The computer converts the form of media into a binary representation this is called a bit pattern. Different amount of bits are allocated depending on how much variation there is in the data
- 186Whats the difference between analogue and digital data?analogue is the data is its natural form while digital is it's encoded form
- 187Whats the difference between analogue and digital signals?Analogue signals are the signals in their natural form whilst digital is the signal encoded.
- 188Describe how an analogue to digital converter worksAn analogue to digital converter samples the analogue signal on each falling or rising edge of a sample clock. In each cycle, the ADC gets the analogue signal, measures and converts it into a digital value. The ADC converts the output data into a series of digital values
- 189Describe how a digital to analogue converter worksThe DAC converts the digital signals into analogue signals and then sends them to an amplifier to play out the signals
- 190What are bitmaps?Bitmaps are a regular mesh of cells called pixels. Each pixel contains a colour value.
- 191What is the resolution of a bitmap?It's height in pixels x it's width in pixels
- 192What is the colour depth of a bitmap?Number of bits stored for each pixel
- 193What is the size in pixels of an image?It's width in pixels x it's height in pixels
- 194How do you calculate the storage requirements for a bit mapped image?size in pixels x colour depth
- 195Give 3 examples of metadatawidth, height, colour depth, author, date created, date modified, file size
Information
- Description
- Flashcards on Comp sci All topics part 1, created by daniel upton on 04/03/2019.
- Created by
- daniel upton
- Views
- 6
- Rating