gs gs122 Searching - Fibonacci Search - Quiz No.1
gs gs122 Data Communication and Computer Network Quiz
This quiz belongs to book/course code gs gs122 Data Communication and Computer Network of gs organization. We have 268 quizzes available related to the book/course Data Communication and Computer Network. This quiz has a total of 8 multiple choice questions (MCQs) to prepare and belongs to topic Searching. NVAEducation wants its users to help them learn in an easy way. For that purpose, you are free to prepare online MCQs and quizzes.
NVAEducation also facilitates users to contribute in online competitions with other students to make a challenging situation to learn in a creative way. You can create one to one, and group competition on an topic of a book/course code. Also on NVAEducation you can get certifications by passing the online quiz test.
Question 1: Which algorithmic technique does Fibonacci search use?
Brute force
Divide and Conquer
Greedy Technique
Backtracking
Question 2: Choose the recursive formula for the Fibonacci series.(n>=1)
F(n) = F(n+1) + F(n+2)
F(n) = F(n) + F(n+1)
F(n) = F(n-1) + F(n-2)
F(n) = F(n-1) – F(n-2)
Question 3: Write a function for the Fibonacci search method.
public static int fibSearch(final int key, final int[] a) { int low = 0; int high = a.length - 1; int fibCurrent = 1; int fibPrev = 1; int N = a.length; while (low <= high) { while(fibCurrent < N) { int tmp = fibCurrent + fibPrev; fibPrev = fibCurrent; fibCurrent = tmp; N = N - (fibCurrent - fibPrev); } final int mid = low + (high - low) - (fibCurrent + fibPrev); if (key < a[mid]) high = mid - 1; else if (key > a[mid]) low = mid + 1; else return mid; } return -1; } public static int fibSearch(final int key, final int[] a) { int low = 0; int high = a.length - 1; int fibCurrent = 1; int fibPrev = 1; int N = a.length; while (low <= high) { int tmp = fibCurrent + fibPrev; fibPrev = fibCurrent; fibCurrent = tmp; N = N - (fibCurrent - fibPrev); final int mid = low + (high - low) - (fibCurrent + fibPrev); if (key < a[mid]) high = mid - 1; else if (key > a[mid]) low = mid + 1; else return mid; } return -1; } public static int fibSearch(final int key, final int[] a) { int low = 0; int high = a.length - 1; int fibCurrent = 1; int fibPrev = 1; int N = a.length; while (low <= high) { while(fibCurrent < N) { int tmp = fibCurrent + fibPrev; fibPrev = fibCurrent; fibCurrent = tmp; N = N - (fibCurrent - fibPrev); } final int mid = low + (high - low) - (fibCurrent + fibPrev); if (key < a[mid]) low = mid + 1; else if (key > a[mid]) high = mid - 1; else return mid; } } public static int fibSearch(final int key, final int[] a) { int low = 0; int high = a.length - 1; int fibCurrent = 1; int fibPrev = 1; int N = a.length; while (low <= high) { while(fibCurrent < N) { int tmp = fibCurrent + fibPrev; fibPrev = fibCurrent; fibCurrent = tmp; N = N - (fibCurrent - fibPrev); } final int mid = low + (high - low) - (fibCurrent + fibPrev); if (key < a[mid]) low = mid - 1; else if (key > a[mid]) high = mid - 1; else return mid; } }
Question 4: What is the time complexity of Fibonacci Search?
O(logn)
O(n)
O(n2)
O(nlogn)
Question 5: Which of the following is not an advantage of Fibonacci Search?
When the element being searched for has a non uniform access storage
Can be used in magnetic tapes
Can be used for large arrays which do not fit in the CPU cache or in the RAM
It can be applied efficiently on unsorted arrays
Question 6: What is the length of the step in jump search?
n
n/2
sqrt(n)
1
Question 7: Select the code snippet for Jump Search.
public int jumpSearch(int arr[], int key) { int size = arr.length; int step = floor(sqrt(size)); int prev = 0; while (arr[(step > size ? step : size)] < key) { prev = step; step += floor(sqrt(size)); if (step >= size) { return -1; } } while (arr[prev] < key) { prev++; if (prev == (step < size ? step : size)) { return -1; } } if (arr[prev] == key) { return prev; } return -1; } public int jumpSearch(int arr[], int key) { int size = arr.length; int step = floor(sqrt(size)); int prev = 0; while (arr[(step < size ? step : size)] < key) { prev = step; step += floor(sqrt(size)); if (step >= size) { return -1; } } while (arr[prev] < key) { prev++; if (prev == (step < size ? step : size)) { return -1; } } if (arr[prev] == key) { return prev; } return -1; } public int jumpSearch(int arr[], int key) { int size = arr.length; int step = floor(sqrt(size)); int prev = 0; while (arr[(step > size ? step : size)] < key) { prev = step; step += floor(sqrt(size)); if (step >= size) { return -1; } } while (arr[prev] > key) { prev++; if (prev == (step < size ? step : size)) { return -1; } } if (arr[prev] == key) { return prev; } return -1; } public int jumpSearch(int arr[], int key) { int size = arr.length; int step = floor(sqrt(size)); int prev = 0; while (arr[(step > size ? step : size)] < key) { prev = step; step += floor(sqrt(size)); if (step <= size) { return -1; } } while (arr[prev] > key) { prev++; if (prev == (step < size ? step : size)) { return -1; } } if (arr[prev] == key) { return prev; } return -1; }
Question 8: What is the time complexity of Jump Search?
O(logn)
O(n)
O(sqrt(n))
O(nlogn)
Online Quizzes of gs122 Data Communication and Computer Network
Sorting - Insertion Sort - Quiz No.1
gs gs122
Data Communication and Computer Network Online Quizzes
Sorting - Insertion Sort - Quiz No.2
gs gs122
Data Communication and Computer Network Online Quizzes
Sorting - Insertion Sort - Quiz No.3
gs gs122
Data Communication and Computer Network Online Quizzes
Sorting - LSD Radix Sort - Quiz No.1
gs gs122
Data Communication and Computer Network Online Quizzes
Sorting - MSD Radix Sort - Quiz No.1
gs gs122
Data Communication and Computer Network Online Quizzes
Sorting - MSD Radix Sort - Quiz No.2
gs gs122
Data Communication and Computer Network Online Quizzes
