Study Guides (390,000)
US (220,000)
Purdue (3,000)
CS (100)
All (10)
Final

CS 17700 Study Guide - Final Guide: Binary Search Algorithm, Bubble Sort, Merge SortExam


Department
Computer Sciences
Course Code
CS 17700
Professor
All
Study Guide
Final

This preview shows page 1. to view the full 4 pages of the document.
Q1 SE1 Consider a large sorted list of n numbers. Which statement is CORRECT about linear and binary
search when searching for a number in this list:
A) Linear Search runs as fast as Binary Search since the list is already sorted
B) *Binary Search should be used because the list is already sorted
C) Binary Search always runs faster than Linear Search when searching for any number in the sorted list
D) Linear Search should be used because the list is already sorted.
Q2 Consider the following search function:
def mySearch(something,aList):
for item in aList:
if item == something:
return "Found it!"
elif item > something:
return "Not Found"
Which statement is CORRECT about the values returned by the function calls: mySearch(5,[2,5,6,7,9,10])
and mySearch(5,[2,6,7,5,9,10]), respectively?
A) Both returned values are "Found it"
B) *mySearch(5,[2,5,6,7,9,10]) returns "Found it" while mySearch(5,[2,6,7,5,9,10]) returns "Not Found"
C) mySearch(5,[2,5,6,7,9,10]) returns "Not Found" while mySearch(5,[2,6,7,5,9,10]) returns "Found it"
D) Both returned values are "Not Found"
Q3 S2 Which is the number of swapping operations needed to sort a list of numbers: [8, 22, 7, 9 ] in
ascending order using bubble sort?
A) * 3
B) 5
C) 4
D) 16
Q4 S2 Which is the complexity of Bubble Sort and the complexity Merge Sort, respectively?
A) O(n) and O(log n)
B) O(n2) and O(log n)
C) * O(n2) and O(n log n)
D) O(log n) and O(n)
Q5 Consider the following functions that calculate ax. You can assume that both a and x are positive. Also
notice that if x is divisible by 2, ax = ax/2 * ax/2.
i)
def exponent(a,x):
if x ==1:
return a
else:
if (x%2 ==0):
return exponent(a,x/2)*exponent(a,x/2)
else:
return a*exponent(a,x-1)
ii)
def exponent(a,x):
if x ==1:
return a
else:
if (x%2 ==0):
return a*exponent(a,x/2)
else:
return a*exponent(a,x-1)
You're Reading a Preview

Unlock to view full version