Buscar
Estás en modo de exploración. debe iniciar sesión para usar MEMORY

   Inicia sesión para empezar

level: Level 1

Questions and Answers List

level questions: Level 1

QuestionAnswer
Quick sort doesn't use additional memory like merge sort doesWhat are 4 examples of abstract data types?
- Keys pressed on a keyboard - Printer QueueWhat are 2 real world examples of queues?
enQueue(item)how do you add an item to the end of a queue? (code)
Removes the front item from the queue and returns itWhat does deQueue() do?
isEmpty()how do you check if a queue is empty?
isFull()how do you check if a queue is full?
- Dynamic data structures are ones which can grow or shrink in size - They require a heap in order to workWhat is a dynamic data structure and what do they require in order to work?
A portion of memory from which space is automatically allocated or de-allocated as neededWhat is the heap?
A listWhat's an example of a dynamic data structure in python?
May grow too large and cause overflow, crashing the programWhat's a downside of using a dynamic data structure
- moving the items forward items are removed (may cause long processing time with large queues) - keeping the items in place and using pointers insteadWhat are 2 ways of implementing a linear queue?
- Space which can't be filled will slowly show up at the start of the queue - Can be fixed with a circular queue - putting new items at the start of the queue once the end is reached like a loopWhat is an issue with using pointers in a linear queue and how can it be fixed?
A queue where the items are ordered by priority, not order in which they were addedWhat is a priority queue?
Check the priority of each item in the queue, starting at the back and moving it along one place until an item with the same or lower priority is found, at which point the new item can be insertedHow would you implement a priority queue?
Trying to pop from a stack which is already emptyIn the context of stacks, what is underflow?
myList.isEmpty()In python, how do you test if a list "myList" is empty?
- Pressing the back button on a web browser - Pressing undo in photoshop or wordWhat are two common everyday applications of a stack?
- A pointer to the top of the stack - A var holding the size of the array (the maximum size of the stack)A stack can be implemented with either a dynamic or a static data structure, what two additional variables are needed if a static data structure is used?
push(item)How do you add a new item to a stack? (code)
pop()How do you remove and return an item from a stack? (code)
Returns the top item from the stack without removing itIn the context of stacks, what does peek() do?
The address of the instruction that control should return to when a subroutine endsWhat does the call stack hold?
- Stack frames are groupings in the stack, they show the stuff related to different subroutines calledWhat is a stack frame?
MOD returns the remainder of a division, DIV just divides the numberWhat's the difference between MOD and DIV?
initialises the queueWhat does this pseudocode do? (queues) front = 0 rear = -1 size = 0 maxSize = size of array
Checks if the queue is emptyWhat does this pseudocode do? (queues) if size == 0 then return True else return False endif
Checks if the queue is fullWhat does this pseudocode do? (queues) if size == maxSize then return True else return False endif
Adds an element to the queueWhat does this pseudocode do? (queues) if isFull then print("Queue full") else rear = (rear + 1) MOD maxSize q[rear] = newItem size = size + 1
Removes an item from the queueWhat does this pseudocode do? (queues) if isEmpty then print("Queue empty") item = Null else item = q[front] front = (front + 1) MOD maxSize size = size - 1
Functions produce information, procedures perform a taskWhat's the difference between functions and procedures?
Function - input("bruh") Procedure - print("bruh")Give one python example of a function and one of a procedure
- small enough to be easily understood and debug - subroutines can be tested independently - once thoroughly tested, a subroutine can be reused with confidence in different programs - modular approach makes it easier for multiple programmers to collaborateWhat are some advantages of using subroutines?
Recursion is calling itself within itself, iteration is just loopingWhat is the difference between recursion and iteration?
Recursive algorithms are often much shorter but they can cause stack overflow if called too many times, an iterative routine has no limit to the number of times it can be calledWhat's one advantage and one disadvantage of recursion over iteration?
Round down(binary search) how do determine the middle item in a list with an even number of items?
(first + last) / 2When coding a binary search algorithm, how do you find the middle item?
- binary search - merge sortwhat is one search and one sort algorithm that use divide and conquer?
There must be a condition which will end the recursion, otherwise it will go forever until stack overflowWhat is a requirement when using recursion?
Quicker - good time complexity Takes more space - bad space complexityWhat are the advantages and disadvantages of merge sorts in terms of time and space complexity?
Quick sort doesn't use additional memory like merge sort doesWhat is the advantage of quick sort over merge sort?
left subtree -> root node -> right subtreeWhat order is the tree traversed in an in-order traversal?
left subtree -> right subtree -> root nodeWhat order is the tree traversed in a post-order traversal?
root node -> left subtree -> right subtreeWhat order is the tree traversed in a pre-order traversal?
A binary search treeWhat is a typical use of a rooted tree?
- An array of records - left, data, rightWhen implementing a binary search tree, what would be the appropriate data type and what would be the 3 pieces of data which would need to be stored?
In-order traversalWhich tree traversal order is ideal for searching efficiently?
The pointer will hold the value "null"In a linked list, how do you know a node is the last one?
Integrated Development EnvironmentWhat does IDE stand for?
a software package that helps you write code more easilyWhat is an IDE?
Normal: 1 and 99 Boundary: 0 and 100 Erroneous: -1 and 101If something required an input between 1 and 100, what would be an example or normal data, boundary data, and erroneous data?
Running through a program on paper and noting down when variables change in the trace tableWhat is dry-running?
passing variables into and out of a subprogram (procedure e.g. function)What is parameter parsing?
By Value - when you don't want the subprogram to change the value of the variable (input) - only passes the actual value of the var By Reference - when you want to get data from the subprogram (output) - passes the memory location of the var, therefore allowing it to be changedWhat are the two types of parameter parsing? (name and description)
Backtracking is incrementally building up towards a solution, abandoning partial success when the solution can't be completed and then going back to a previously successful match - for example, getting to a dead end in a maze and then going back slightly to try a different wayWhat is backtracking and what is an example of it?
Analysing vast amounts of data in order to discover new information and trendsWhat is data mining?
making use of experience to find a solution which is 'good enough' - like an educated guessWhat are heuristics?
Statements used to select which statement will be executed next, depending on some condition For example, an if statementWhat are selection statements? And what is an example in terms of code?
Switch or Case statementWhat is an alternative to a nested if statement?
switch choice: burger: print("you have selected option burger") fries: print("you have selected option fries") drink: print("you have selected option drink") else: print("You must select either burger, fries or drink") endswitchHow does a switch statement work?
The underground mapWhat is an example of abstraction that I'd be familiar with living in London?
Grouping by common characteristics - "is a type of"What is abstraction by generalisation?
A logical description of how data is viewed and the actions which can be performed on it, not how those actions are actually physically carried outWhat is data abstraction?
How a procedure is called, what arguments are required, what data type each one is, and what order they need to be written inWhat is procedure interface?
Breaking down a problem into sub-problems to make it easier to solveWhat is problem decomposition?
Breaking down a problem into individual tasks and then breaking the tasks into subtasks and so on until each subtask is simple enough to be written as a self-contained module or subroutineWhat is top-down design and where is it especially useful?
Parallel computing is when multiple tasks are being executed simultaneously - requires multiple processors Concurrent processing is when multiple tasks are running at the same time but by sharing processor timeWhat's the difference between parallel and concurrent computing?
- More tasks completed in a given time - Time that would be wasted by the processor waiting for the user to input data is used on another task - But if a large number of users are all trying to run programs and some of these programs involve a lot of computation, they'll take longer to completeWhat are two advantages and a drawback of concurrent processing?
- Several tasks can be completed simultaneously by different processors - A browser can display several webpages in different windows and still run a lengthy search simultaneously - But some tasks may run faster with a single processorTwo benefits of parallel processing and one drawback
- An algorithm which always executes in the same time, regardless of the size of the data set - O(1)What is a constant complexity (Big O) and what is the notation?
- An algorithm which halves the data set in each pass (good for large data sets) - O(log n)What is a logarithmic complexity and what is the notation? (Big O)
- An algorithm whose performance is proportional to the size of the data set and declines as the data set grows - O(n)What is linear complexity and what is the notation? (Big O)
- An algorithm whose performance is proportional to the SQUARE of the size of the data set. Significantly reduces efficiency with increasingly large data sets - O(n^2)What is polynomial complexity and what is the notation? (Big O)
An algorithm that doubles with each addition to the data set in each pass. Inefficient and should be avoided - O(2^n)What is exponential complexity and what is the notation? (Big O)
Constant - O(1)What is the Big O notation for an algorithm with no loop?
Linear - O(n)What is the Big O notation for an algorithm with a for/while loop?
Polynomial - O(n^num of loops)What is the Big O notation for an algorithm with a Nested loop?
Exponential - O(2^n)What is the Big O notation for a recursive algorithm?
A repeat until loop checks the condition at the END of each loop so it will always run at least onceWhat is the difference between a while loop and a repeat until loop? An the effect of the difference.
Ensures that each subroutine is completely self-containedWhat is the advantage of local variables for subroutines?
Giving the computer a list of instructions on what is should do step by step in order to finish the task at handWhat is procedural programming?