Brainscape's Knowledge GenomeTM

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


See full index

Python > Exam theory > Flashcards

Exam theory Flashcards

1
Q

Which of the following is not true in case of a Python dictionary?
A. Matches “keys” to “values”
B. We can look up one item by another item
C. Order is guaranteed
D. Key can be any immutable type (dictionary mutable)

A

C. Order is NOT guaranteed

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

CLASSES OF TESTS

A 
Unit testing
• testing each function separately
Regression testing
• catch reintroduced errors that were previously fixed
Integration testing
• does overall program work?
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

SIMPLIFICATION EXAMPLES

A 
• drop	constants and multiplicative factors	
• focus	on	dominant	terms	
O(n^2): n^2 + 2n + 2 
O(n^2): n^2 + 100000n + 31000 
O(n): log(n) + n + 4 
O(n*logn) : 0.0001*n*log(n) + 300n 
O(3^n) : 2n^30 + 3^n
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

BUBBLE SORT

A

• compare consecutive pairs of elements
• swap elements in pair such that smaller is first
• largest unsorted element always at end after the pass, so at most n passes
• complexity is O(n^2) where n is len(L)
(swap and for)

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

SELECTION SORT

A
  • extract minimum element
  • swap it with element at index 0 (1,2, … and so on)
  • at i’th step, first i elements in list are sorted (all other bigger)
  • O(n^2) where n is len(L)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

MERGE SORT

A
  1. if list is of length 0 or 1, already sorted
  2. if list has more than one element, split into two lists, and sort each by comparing first elements
  3. merge sorted sublists (add smaller element to the result list)
    • complexity O(n * log(n)) where n is len(L)
  4. Overall complexity of similar Quick sort = O(n*log(n)) - average; O(n^2) - worst case
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q 
range()
find()
list[::]
.append(item)
.extend(item)
round()
A

range(start, stop, step) - not including stop (spaces in strings also indexed; when numbers wrongly specified, just does not execute (range(10,1,2)); when floats=TypeError )
find(value, start, end) - not including stop; finds first occurrence of specified value
list[ Initial : End : IndexJump ] - not including end
.append(item) - [ , , , [ , , ]]
.extend(item) - [ , , , , , ]
round(number, digits) - number of digits after dot

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

BLACK BOX TESTING

A
  1. It is designed without looking at the code.
  2. Can be done by someone other than the implementer.
  3. Testing can be reused if implementation changes.
  4. Paths through specification (docstring)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

GLASS BOX TESTING

A
  1. Code is used directly to guide design of the test cases
  2. Testing cannot be reused if implementation changes
  3. Explores paths through the code
  4. It is called path-complete if every potential path through the code is tested at least once
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Bisection/binary search

divide and conquer

A
  • list MUST be sorted to give correct answer
  • linear search => O(n)
  • binary search => O(log n)
    (assumes the list is sorted!)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Monkey Sort

aka bogosort - stupid sort - slowsort - permutation sort - shotgun sort

A

is a random sort, every time through the list get randomly sorted and if lucky it is ordered!

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

Monkey Sort - complexity

A

Best case:
O(n) where n is len(L)
Worst case:
O(?) is unbound if really unlucky

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

LOGIC OPERATORS ON bools (a and b)

A

not a -> True if a is False
False if a is True
a and b -> True if both are True
a or b -> True if either or both are True

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

Syntax

A

arrangement of words and phrases to create will-formed sentences in a language.

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

Static semantics

A

whether syntactically valid string has any meaning

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

Tuples

A

ordered sequence of elements, can mix element types.
represented with Parentheses
Immutable (cannot change element values)

17
Q

Lists

A

ordered sequence of information, accessible by index.
represented by Square brackets
mutable

18
Q 
class Deque(): 
a_list.append(item)
insert a_list.insert(i,item)
pop a_list.pop()
pop a_list.pop(i)
sort a_list.sort()
reverse a_list.reverse()
del del a_list[i]
index a_list.index(item)
count a_list.count(item)
remove a_list.remove(item)
A

append a_list.append(item) – Adds a new item to the end of a list
insert a_list.insert(i,item) – Inserts an item at the 𝑖th position in a list
pop a_list.pop() – Removes and returns the LAST item in a list
pop a_list.pop(i) – Removes and returns the 𝑖th item in a list
sort a_list.sort() – Modifies a list to be sorted
reverse a_list.reverse() – Modifies a list to be in reverse order
del del a_list[i] – Deletes the item in the 𝑖th position
index a_list.index(item) – Returns the index of the first occurrence of item
count a_list.count(item) – Returns the number of occurrences of item
remove a_list.remove(item) – Removes the first occurrence of item

19
Q
  1. what is the output when print(office == home) in which __eq__ not specified
  2. what is the output when print(workstation.set_brand(‘DELL’))
A
  1. As __eq__ not specified, python checks if both refer to same object and since two different calls of classes => False is the output
  2. When try to simultaneously call for two procedural attributes, output is None (except special operators like __add__; and dot notations like self.age())
20
Q 
Overall complexity?
def genSubsets(L):
\_\_\_smaller = genSubsets(L[:-1])
\_\_\_for small in smaller:
\_\_\_\_\_\_new.append(small+extra)
A

Know that for a set of size k there are 2^k cases. So overall complexity O(2^k) – exponential

21
Q 
Overall complexity?
def isSubset(L1, L2):
\_\_\_for e1 in L1:
\_\_\_\_\_\_matched = False
\_\_\_\_\_\_\_\_\_for e2 in L2:
\_\_\_\_\_\_\_\_\_\_\_\_if e1 == e2:
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_matched = True
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_break
\_\_\_\_\_\_\_\_\_\_\_\_if not matched:
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_return False
\_\_\_\_\_\_\_\_\_return True
A

nested loops, each iterating n times. So O(n^2)

22
Q 
O(1)	
O(log n)	
O(n) 	
O(n * log n)
O(n^c)	
O(c^n)
A

O(1) – code does not depend on size of problem
O(log n) – reduce problem in half each time through process
O(n) – simple iterative or recursive programs
O(n * log n) – merge sort
O(n^c) – nested loops or recursive calls
O(c^n) – multiple recursive calls at each level
Big O() – growth of program’s run time as input size grows

23
Q
  • Stack()
  • push(item)
  • pop()
  • peek()
  • is_empty()
  • size()
A
  • Stack() – creates a new stack that is empty. It needs no parameters and returns an empty stack.
  • push(item) – adds a new item to the top of the stack. It needs the item and returns nothing.
  • pop() – removes the top item from the stack. It needs no parameters and returns the item. The stack is modified.
  • peek() – returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.
  • is_empty() – tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
  • size() – returns the number of items on the stack. It needs no parameters and returns an integer.
24
Q 
What are the outputs?
a = '05'
print(a[1] == 5)
print('5'== 5)
print('aba'==5)
A

False
False
False

25
Q
  • BinaryTree()
  • get_left_child()
  • get_right_child()
  • set_root_val(val)
  • get_root_val()
  • insert_left(val)
  • insert_right(val)
A
  • BinaryTree() – creates a new instance of binary tree.
  • get_left_child() – returns the binary tree corresponding to the left child of the current node.
  • get_right_child() – returns the binary tree corresponding to the right child of the current node.
  • set_root_val(val) – stores the object in parameter val in the current node.
  • get_root_val() – returns the object stored in the current node.
  • insert_left(val) – creates a new binary tree and installs it as the left child of the current node.
  • insert_right(val) – creates a new binary tree and installs it as the right child of the current node.
26
Q 
Overall complexity?
def f(x):
\_\_\_assert type(x)==int and x>=0
\_\_\_answer = 0
\_\_\_s = str(x)
\_\_\_for c in s:
\_\_\_\_\_\_answer += int(c)
\_\_\_return answer
def intToStr(i): 
\_\_digits = '0123456789'
\_\_if i == 0:
\_\_\_\_return '0'
\_\_res = ''
\_\_while i > 0:
\_\_\_\_res = digits[i%10] + res
\_\_\_\_i = i//10
\_\_return result
A

x/i is a integer!

overall complexity is O(log(n)) where n is the number of digits ( len(str(i)) = log(n) where n = 10^(# of digits))

27
Q 
Overall complexity?
def addDigits(s):
 \_\_val = 0
 \_\_for c in s:
 \_\_\_\_val += int(c)
 \_\_return val
A

s is a string!

overall complexity is O(n) where n=len(s)

28
Q

Overall complexity of:
fibonacci iterative
fibonacci recursive

A

for loop, so O(n)

recursion, so O(2^n); but when use dictionary also becomes O(n) as number of iterations is 2*n-3

29
Q

Insertion sort

A

The insertion sort always maintains a sorted sublist in the lower positions of the list. Each new item is then “inserted” back into the previous sublist such that the sorted sublist is one item larger.
Overall complexity is O(n^2)

Python (1 decks)

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