NEW
Font size
WorksheetsDSA mid-term revision (FIT HANU) pt.1
Total questions: 80
Worksheet time: 40mins
- Which is not a property of a algorithm?
It must terminate for all inputs.
The order of the algorithm’s steps must be precisely defined.
The execution time and the memory needed for a algorithm must be percisely defined.
It must be correct and composed of precisely defined steps.
– Which statement below is wrong?
Select one:
For the same data, some data structures may require more or less space.
A data structure is a way of organizing data for processing within a computer program.
A data structure is a piece of information (a physical instantiation of a data type)
For the same operations on the data, some data structures lead to more or less efficient algorithms.
– Which statement is correct concerning to the complexity of algorithm?
Select one:
The complexity of an algorithm is determined by the total lines of code of the program that implements
the algorithm using a given programming language.
The complexity of an algorithm is a measure of the amount of time and cost needed to implement this
algorithm.
The complexity of an algorithm is a measure of the amount of time and space required by the algorithm
for an input of a given size n.
The complexity of an algorithm is determined by the maximum value of the input size n that does not
affect the correctness of the algorithm.
– When evaluating algorithm’s complexity, which approach makes possible an evaluation that is
independent of the hardware and software environments?
Select one:
Using input data sets of varying size.
Theoretical approach.
Measuring the running time and memory space using the same hardware and software environment.
Experimental approach.
– What is time complexity of an algorithm?
Select one:
The amount of time needed to implement the algorithm.
The amount of time that the algorithm needs to run for an input of a given size n.
The upper limits for excution time of the algorithm.
The response time of the algorithm.
– Which statement is wrong concerning to the best-case time complexity of an algorithm?
Select one:
The best case of an algorithm A is estimated as the minimum number of primitive operations performed
by A on an input size n.
Many algorithms perform exactly the same in the best case.
The best-case is used frequently to analyze the time complexity of algorithms.
The best-case gives us an lower bound on the time complexity of algorithms.
– Which statement is wrong concerning to the average-case time complexity of an algorithm?
Select one:
The average-case is places somewhere between the best-case and the worse-case.
The average-case of an algorithm A is estimated as the average number of primitive operations
performed by A on an input size n.
The average-case of an algorithm A is depended on the characteristic of the input data.
The average-case is easy to determine.
– Which statement is wrong concerning to the worst-case time complexity of an algorithm?
Select one:
The worst case gives us an upper bound on time complexity of an algorithm.
The worst-case of an algorithm A is estimated as the maximize number of primitive operations performed
by A on an input size n.
At the worst-case the algorithm takes more time to finish than it does at the average-case and best-case.
The worst-case is not very informative because many algorithms rarely perform at their worst-case.
– Which one determines the asymptotic behavior of the function T(n)?
The leading term.
The term has the biggest coefficient.
The first term.
The last term.
– Which notation represents the upper-bound of the grow rate of a function?
Big-Theta notation
Big-Omega notation
Big-Oh notation
Big-Alpha notation
– Suppose that the estimated time complexity of algorithm A and algorithm B is TA(N) and
TB(N) respectively. How can we compare the time complexity of A and B?
We compare the value of TA and TB corresponding to some special value of n.
We compare the value of TA and TB corresponding to a very large, pre-defined value of n.
We compare the value of TA and TB corresponding to every value of n.
We compare the grow rate of the leading terms of TA(N) and TB(N).
- Which statement below is wrong in the context of list data structure?
Select one:
In the list, items are referenced by their value.
Every item in the list, except for the head and tail, has an unique predecessor and an
unique successor.
List can be implemented using an array or a collection of linked nodes.
A list is a sequence of zero or more items of the same type.
– In the ADT of the list data structure, getLength() method returns a/an ______ value?
Select one:
Real number.
Boolean.
String.
Integer.
– In the ADT of the list data structure, isEmpty() method returns a/an _______ value?
Select one:
String.
Real number.
Boolean.
Integer.
– Which statement is correct about array-based list?
Select one:
Array-based is faster than linked-list in case of accessing list’s items.
They can be implemented by Java language only.
Array-based is faster than linked-list in case of inserting new item into the list.
Elements of array-based list can be located dinamically and discontinuously.
– Which statement is correct about linked-list?
Linked-list cost more than array-based list in term of deleting and inserting operations.
Elements of linked-list can be located dinamically and discontinuously.
Elements of linked-list must be stored in consecutive memory blocks.
Array-based list is more flexible in list’s size than linked-list.
– In the ADT of the list data structure, remove(int post) method will?
Select one:
Remove an item at the pos position form the list.
Remove the last item form the list.
Remove the first item from the list.
Remove all items from the list.
– In a single linked-list, if a NodeX(data,next) is a tail which is the value of the X’s
next?
undefined
null
head
0
– In a Singly Linked List that have only one node X, which value does X.getNext()
return?
Select one:
null
The tail node
The head it self
undefined
– Suppose that X is a node in the middle of the Singly Linked List. Complete the code
below to delete all nodes after X from the list?X.setNext( _____ );
Select one:
null.
X.getNext().
X.getNext().getNext().
tail.
– Suppose that X is a node in the middle of the Singly Linked List. Complete the code
below to delete one node after X from the list?X.setNext( _____ );
null.
X.getNext().
X.getNext().getNext().
tail.
– Complete the code below to insert a new node X at the POS position of a Singly
Linked List?
SLNode Y = traversing(POS); //travel to POS position
X.setNext(__________);
Y.setNext(X);
Y.setNext(tail).
Y.getNext().
X.getNext().
X.setNext(Y).
– Complete the code below to travel from the head node to the POS position of a Singly
Linked List?
int c = 1;
SLNode node = head;
while(c < POS) {
_______;
node = node.getNext();
}
return node;
node++
node=node.setNext(tail)
c=c+1
c=c.getNext()
– In a Circle linked-list, if a NodeX(data,next) is a tail which is the value of the X’s
next?
Select one:
undefined
null
head
0
– Which is the common form of a node X in a Doubly Linked List?
Select one:
X(data, next)
X(data)
X(data, prev, next)
X(data, prev)
– Which is common form of a node X in a Singly Linked List?
Select one:
X(data, next)
X(data)
X(data, prev, next)
X(data, prev)
– A mathematical-model with a collection of operations defined on that model is called?
Select one:
Primitive data type.
Data structure.
Algorithm.
Abstract Data Type.
- Which statement below is wrong about comparison sorting algorithms?
Select one:
The time complexity of some comparison sorting algorithms can be faster than O(NlogN).
Bubble sort, Merge sort and Heap sort are comparison sorting algorithms.
The time complexity of a comparison sorting algorithm is based on the number of comparisons
and moves during sorting.
The sorted order is determined based only on the comparisons between sort keys.
– Which statement below is wrong in the context of linear sorting algorithm?
Select one:
The time complexity is linear.
The sorted order is determined based on the comparisons between sort keys.
The sort key must be numeric.
Counting sort and Radix sort are linear sorting algorithms.
– In a stable sort algorithm ...?
Select one:
The relative order of elements with equal keys are not maintained.
The order of both key and non-key values are maintained.
The relative order of elements with equal keys are maintained.
The order of key values are maintained.
– Merge sort and Quick sort are ...?
Select one:
Based on Divide and Conquer approach.
O(n^2) sorting algorithms.
Linear sorting algorithm.
The fastest sorting algorithms.
– Which sorting algorithm locates the largest (or smallest) key and its index in each sort pass?
Select one:
Bubble sort.
Selection sort.
Insertion sort.
Heap sort.
– Which statement is wrong about Insertion sort?
Select one:
Scan and exchange any pair of elements that is out-of-order.
It is O(n^2) sorting algorithm.
Unsorted elements are inserted into an already sorted list.
We must shift several elements to make place for the inserted one.
– Which sorting algorithm scans and exchanges any pair of elements that is out-of-order?
Select one:
Insertion sort.
Bubble sort.
Selection sort.
Heap sort.
– Which statement is wrong concerning to the Heap data structure?
Select one:
It is a tree where all nodes have zero, one or two children.
In a min-heap the parent node value is always greater than or equal to its children’s values.
It is used in Heap sort algorithm.
An array can be used to store heap’s nodes.
– In Merge sort algorithm...?
Select one:
.The input array is divided into two parts at the middle of the arra
The input array is divided into two parts based on the pivot values
The merge algorithm combines two sorted array by attaching the second array to the end of the
first one
The worst case is O(N^2)
– Which statement is wrong about Quick sort?
Select one:
A merge algorithm is needed to combine two partitioned arrays
The worst case is O(N^2)
The array is partitioned based on the pivot value
By choosing the pivot carefully, we can reduce the running time of the algorithm.
– Suppose that we are using Radix sort on N elements, each element has P digits in base b (each
digit is in the range [0 .. B-1]), and couting sort algorithm is used to sort the digits. What is the
time complexity of the Radix sort algorithm?
Select one:
O(N.P.B).
O(P+N+B).
O(B+N).
O(P(N+B)).
– What is an operation in which a list of elements is arranged either in ascending order or in
descending order?
Select one:
Searching.
Hashing.
Sorting.
Traversing.
– Which of the following sorting algorithm does not have a worst case time complexity of O(n^2)?
Select one:
Insertion sort.
Quick sort.
Buble sort.
Merge sort.
- Which statement below is wrong concerning to stack data structure?
Select one:
It is a First In First Out (FIFO) list.
A stack contains a sequence of zero or more items of the same type.
push() and pop() are two operations defined in Stack’s ADT.
List-based stack has no limit on total number of items of the stack.
– Which statement below is wrong about queue data structure?
Select one:
Dequeue is a special type of queue.
It is a First In First Out (FIFO) list.
Queue can be implemented using an array or a linked-list.
enqueue() and dequeue() operations must be performmed at one end of the queue.
– In the ADT of the Stack data structure, push() method is used to
Select one:
take an item out of the stack
get the total items in the stack
get an item without deleting it from the stack
add an item to the stack
– Which statement is correct about array-based stack?
Select one:
To add a new item into the stack: firstly, top is increased by 1, then current items will be shifted
one slot to the right to make space for the new item.
To add a new item into the stack: firstly, top is increased by 1, then current items will be shifted
one slot to the left to make space for the new item.
top is the first item of the array.
top is the last item of the array.
– In the ADT of the Queue data structure, dequeue() method will?
Select one:
Remove an item from the queue at the rear position.
Add a new item to the queue at the front position.
Add a new item to the queue at the rear position.
Remove an item from the queue at the front position.
– In ADT of the Queue data structure, enqueue() method will?
Select one:
Add a new item to the queue at the front position.
Remove an item from the queue at the front position.
Remove an item from the queue at the rear position.
Add a new item to the queue at the rear position.
– Which statement is wrong about array-based circular queue?
Select one:
when front=rear the queue is empty.
rear can be wrap around to the beginning of the array.
front can be wrap around to the beginning of the array.
when front=rear the queue is full.
– Complete the code for the enqueue() method in array-based circular queue?
Select one:
rear=rear+1
rear=(rear+1)%maxSize
front=front+1
front=(front+1)%maxSize
– Complete the code for the dequeue() method in array-based circular queue?
public void dequeue() {
if(!isEmpty()) {
int pos = front;
__________;
return items[pos];
}
}
front=front+1
rear=rear+1
front=(front+1)%maxSize
rear=(rear+1)%maxSize
– Which statement is wrong about list-based queue?
Select one:
front is the head and rear is the tail of the linked-list.
A linked-list is used to implement the queue.
Queue is empty when front=rear.
List-based queue ADT does not have isFull() operation
– Which of the following statement is true?
Select one:
In both array-based stack and queue, when removing an item the corresponding index is increase
by 1
The top of a stack corresponds to the front of a queue
The contents of a queue can wrap around , while those of a stack can not
.The pop() operation on a stack is simpler than the dequeue() operation on a queue.
– Suppose you push 10, 20, 30, 40 onto a stack, then you pop three items. Which one is left on the stack?
Select one:
40
30
10
20
– Suppose you enqueue 10, 20, 30, 40 onto a queue, then you dequeue three items. Which one is left on
the queue?
Select one:
40
30
10
20
– The end which a new element gets added to a queue is called
Select one:
Bottom
Top
Rear
Front
– What is the result of the following operation on the stack S: S.peek(S.push(X))?
Select one:
X.
S.push(X).
Null.
S.top.
– What is the worst-case time for linear search finding a single item in an array?
Select one:
Logarithmic time.
Linear time.
Constant time.
Quadratic time.
IDESQAS03
– What is the worst-case time for finding a key in a hash table (assume that there is no
collision)?
Select one:
Constant time.
Linear time.
Quadratic time.
Logarithmic time.
– What additional requirement is placed on an array, so that binary search may be used to search
for a key?
Select one:
The array elements must form a heap.
The array must be sorted.
The array must have at least 2 entries.
The array's size must be a power of two.
– What is the best definition of a collision in a hash table?
Select one:
Two entries with different keys have the same exact hash value.
Two entries are identical except for their keys.
Two entries with the exact same key have different hash values.
Two entries with different data have the exact same key.
– A separate chaining hash table has an array size of 512. What is the maximum number of
entries that can be placed in the table?
Select one:
512.
There is no maximum.
511.
1024.
IDESQAS08
– Which of the following is not an application of the queue data structure?
Select one:
Job scheduling
Evaluating a posfix expression
Stack reversing
Packet queueing
– Consider a hash table of size seven, with starting index zero, and a hash function h(k)=(3k+4)
mod 7. What is the address of the key k=10?
Select one:
3.
0.
7.
6.
– Complete the code below to search for key in an array using linear seach algorithm?
Select one:
-1.
true.
a[i].
i.
– In a hash table of the size N using linear probing, what is the probing hash function hi(k)?
Select one:
hi(k)=(h(k)+i) mod N.
hi(k)=i mod N.
hi(k)=h(k) mod N.
hi(k)=i + k.
– Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash
function: h(k)=k mod 10. Which of the following statements are true?
Select one:
All elements hash to the same value.
1471 and 6171 has to different value.
Each element hashes to a different value.
4199 and 9679 hash to the same value.
– In the context of seach algorithms, which of the following statements are true?
Select one:
Binary search is the fastest search algorithm.
Linear search is faster than binary search.
Hash data structure is used to support sorting.
Binary search is faster than linear search, but it requires a sorted array.
– Which of the following statements is used in binary search algorithm to halve the array?
Select one:
middle=middle/2
middle=(right-left)/2
middle=(left + right)/2
middle=midlle*2
– Suppose that you want to sort a singly linked list, each list’s item is a large object. which of
the following sort algorithms should be used to minimum the time complexity?
Select one:
Quick sort.
Insertion sort.
Heap sort.
Bubble sort.
– Method reverse() below is used to reverse the order of items in a Singly Linked List. Please
complete the code of the method?
int maxSum = 0;
for(int i =0; i < a.length; i++)
for(int j = i; j < a.length; j++) {
int thisSum = 0;
for(int k = i; k<=j; k++)
thisSum += a[k];
if(thisSum>maxSum)
maxSum=thisSum;
}
prev=head
head=current
current=head
head=prev
– Consider a Singly Linked List contains N nodes (N > 8), a method f1() is designed to find the
8th node from beginning, and method f2() is designed to find the 8th node from end. Which is
the time complexity of f1() and f2()?
Select one:
O(N) and O(1)
O(N) and O(N)
O(1) and O(N)
O(1) and O(1)
– Method deleteTail() below is used to delete the last node in a Singly Linked List. Please
complete the code of the method?
public void deleteTail() {
int pos = getLength();
SLNode beforeTail = traversing(pos-1);
____________
}
beforeTail.setNext(null)
beforeTail = tail
beforeTail.setNext(tail)
beforeTail = null
– Method tailToFront() below moves the last node of a Singly Linked List into the front of the
list. Please complete the code of the method?
public void tailToFront() {
int pos = getLength();
SLNode beforeTail = traversing(pos-1);
SLNode tail = beforeTail.getNext();
____________
}
beforeTail.setNext(null); tail.setNext(head); head=tail;
tail.setNext(null); beforeTail.setNext(head); head=beforeTail;
tail.setNext(head); head.setNext(null); beforeTail=head;
head.setNext(null); beforeTail.setNext(tail); tail=beforeTail;
– Selection sort is used to sort an array in the descending order. When does the worst case
occur?
Select one:
The array has several duplicated items.
The array is already sorted in the ascending order.
The array is already sorted in the descending order.
The first and the last items of the array are the same.
– Insertion sort is used to sort an array in the descending order. When does the best case occur?
Select one:
The array contains several zero items.
The array is already sorted in the descending order.
The array is already sorted in the ascending order.
The array has several duplicated items.
–Given an array A that is almost sorted (only one or two elements are misplaced). Which sorting
algorithm gives the best time efficiency when applied on A?
Select one:
Quick sort
Bubble sort
Merge sort
Insertion sort
– Which of the following sorting algorithms has the minimum number of swap operations in general?
Select one:
Heap sort
Insertion sort
Quick sort
Bubble sort
– Consider a modified version of Merge sort where the input array is partitioned at the position one-third
of the length N of the array. What is the recurrence of this algorithm?
Select one:
T(N)=2T(2N/3)+O(N)
T(N)=2T(N/3)+O(N)
T(N)=T(N/3)+T(2N/3)+O(N)
T(N)=T(N/2)+T(3N/2)+O(N)
– Which of the following sorting algorithms has the lowest worst case time complexity?
Select one:
Quick sort
Bubble sort
Merge sort
Insertion sort
– Consider an array A where the items are in the range from 1 to n^3. Which of the following
sorting algorithms gives the best time efficiency when applied on A?
Select one:
Radix sort
Counting sort
Quick sort
Heap sort
– What data structure would you mostly likely see in a non-recursive implementation of a
recursive algorithm?
Select one:
Tree.
Queue.
Stack.
Linked-List.
