Font size
WorksheetsDSA final (FIT HANU)
Total questions: 158
Worksheet time: 1hrs 23mins
Which of the following is wrong about
graph? Choose one answer.
Weigh of an edge must be positive.
Weight of an edge can be negative.
Adjacency matrix is an appropriate representation of a graph.
Adjacency list is an appropriate representation of a graph.
In a hash table of the size N using linear probing, what is the probing
hash function hi(k)?
hi(k)=h(k) mod N.
hi(k)=(h(k)+i) mod N.
hi(k)=i + k.
hi(k)=i mod N.
Which statement is correct about array-based
list? Choose one answer.
Array-based is faster than linked-list in case of accessing list’s items.
Array-based is faster than linked-list in case of inserting new item into the list.
Elements of array-based list can be located dynamically and discontinuously.
They can be implemented by Java language only.
In the ADT of the list data structure, isEmpty() method returns a/an _______
value? Choose one answer.
Real number.
String.
Integer.
Boolean.
A queue Q has 05 character items, Q={“A”, “B”, “C”, “D”, “E”} where “E” is
the rear and “A” is the front of the queue. What is the content of Q if we perform the following
list of operations on the queue: enqueue(“F”)-->dequeue()-->dequeue()-->dequeque()--
>enqueue(“D”)?
Choose one answer.
Q={“D”, “E” ,“F” ,“D”}
Q={“D”, “F”, “A”, “B”}
Q={“C”, “D”, “E”, “F”}
Q={“A”, “B”, “C”, “D”}
Which statement below is wrong in the context of linear sorting
algorithm? Choose one answer.
The sorted order is determined based on the comparisons between sort keys.
Counting sort and Radix sort are linear sorting algorithms.
The time complexity is linear.
The sort key must be numeric.
One difference between a queue and a stack
is: Choose one answer.
Stacks require linked lists, but queues do not.
Queues require linked lists, but stacks do not.
Queues use two ends of the structure; stacks use only one.
Stacks use two ends of the structure, queues use only one.
Bubble sort algorithm is used to sort the array A={23,78,45,8,32,56} in
the ascending order. What are the items of A after 03 sort pass?
Choose one answer.
A={8,23,32,45,56,78}
A={23,45,8,32,56,78}
A={8,32,23,45,56,78}
A={23,32,78,56,45,8}
Which of the following is correct about array-based binary implementation using
perfect binary tree indexing scheme?
Choose one answer.
The parent of node i is i/2.
Array L is used to store node’s labels and array P is used to store the index of node’s
parent.
The left child and right child of node i are 2i+1 and 2i+2.
The left child and right child of node i are 2i+2 and 2i+1.
Evaluate the following expression:* - + 7 3 + 9 1 5 + 2 8 3? Choose one answer.
150
105
510
501
Consider the recursive, nested representation of binary trees: T=(O L R) indicates a binary tree T with the root node O, the left sub-tree L and the right sub-tree R. Note that L and R may be null or further nested. Which of the following represents a valid binary tree? Choose one answer.
(1 (2 3 4) (5 6 7))
(1 (2 3 null) (4 5))
(1 (2 3) (4 5) (6 7))
(1 (2 3 4) (5 6) 7)
(1 2 3 4 5 6 7)
Suppose you push 10, 20, 30, 40 onto a stack, then you pop three items. Which one is left on the stack? Choose one answer.
30
40
10
20
In Merge sort algorithm …? Choose one answer.
The worst case is O(N^2).
The input array is divided into two parts at the middle of the array.
The merge algorithm combines two sorted array by attaching the second array to the end of the first one.
The input array is divided into two parts based on the pivot values.
Which statement is wrong about list-based queue? Choose one answer.
Queue is empty when front=rear.
List-based queue ADT does not have isFull() operation
A linked-list is used to implement the queue.
front is the head and rear is the tail of the linked-list.
Which statement is wrong concerning to the best-case time complexity of an algorithm? Choose one answer.
The best case of an algorithm A is estimated as the minimum number of primitive operations performed by A on an input size n.
The best-case gives us an lower bound on the time complexity of algorithms.
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 is used frequently to analyze the time complexity of algorithms.
get an item without deleting it from the stack.
get the total items in the stack.
add an item to the stack.
take an item out of the stack.
Which sorting algorithm scans and exchanges any pair of elements that is out of-order? Choose one answer.
Heap sort.
Bubble sort.
Insertion sort.
Selection sort.
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by? Choose one answer.
Warshall’s algorithm.
Dijkstra’s algorithm starting from S.
Performing a BFS starting from S.
Performing a DFS starting from S.
Which of the following is not an application of the queue data structure? Choose one answer.
Evaluating a posfix expression.
Job scheduling.
Packet queueing.
Stack reversing.
Complete the code below to insert a new node X at the POS position of a Singly Linked List?
Y.setNext(tail).
X.getNext().
X.setNext(Y).
Y.getNext().
A perfect binary tree with 2N+1 nodes contain? Choose one answer.
2N leaf nodes.
N leaf nodes.
N interior nodes.
2N interior nodes.
Given a binary tree T and a method print() as the following. What will be printed on the screen, if we call: print(T,5)
U
A
E
Z
What is time complexity of an algorithm? Choose one answer.
The response time of the algorithm.
The amount of time needed to implement the algorithm.
The upper limits for execution time of the algorithm
The amount of time that the algorithm needs to run for an input of a given size n.
To implement Dijkstra’s shortest path algorithm on unweighted graphs the data structure to be used is? Choose one answer.
Heap
Tree
Stack
Queue
A complete N-ary tree is a tree which each node has N children or no children. Let I be the number of interior nodes and L be the number of leaves in a complete N-aray tree. If L=41 and I=10, what is the value of N? Choose one
3
6
5
4
The method below represent a number k in base b using a stack. Please complete the code of this method?
(a)
If we use adjacency matrix for representing a weighted undirected graph, we will have? Choose one answer
An asymmetric matrix
A symmetric matrix contains only 0 and 1.
A matrix contains only 0 and 1.
A symmetric matrix over its diagonal
Method search() is used to search for an item in a singly linked list. Please complete the code for this method?
(a)
The maximum degree of any vertex in a simple graph with N vertices is? Choose one answer.
N
2N-1
2N
N-1
Number of leaf nodes in a perfect binary tree of depth h is? Choose one answer.
2h-1.
2^h.
2^(h+1)-1.
2^(h+1).
In a binary search tree, node B is right child of node A, and node C is the right child of B. Which of the following statements are true?
Value of node C is bigger than value of node B, but smaller than value of node A.
Value of node C is bigger than value of node A, but smaller than value of node B.
Node C has the smallest value.
Node C has the biggest value.
Evaluate the following expression:8 7 + 6 4 + 2 3 7 + - 1 -? Choose one answer.
291
129
192
219
In the context of search algorithms, which of the following statements are true? Choose one answer.
Linear search is faster than binary search
Binary search is the fastest search algorithm
Hash data structure is used to support sorting.
Binary search is faster than linear search, but it requires a sorted array
What are Big-Oh, Big-Omega, Big-Theta? Choose one answer.
They are very specific and pre-defined functions.
They are algorithm’s characteristic.
They are mathematic notation for comparing growth rates between functions.
They are mathematic notation to define the maximum growth rates of functions.
What is the time complexity of the following algorithm with respect to the input size N
O(N+M)
O(N*M)
O(N)
O(M)
Which of the following sorting algorithms has the lowest worst case time complexity?
Bubble sort
Quick sort
Merge sort
Insertion sort
Method search() is used to search for an item in a singly linked list. Please complete the code for this method?
(a)
In ADT of the Queue data structure, enqueue() method will?
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.
Remove an item from the queue at the rear position.
Which statement is correct concerning to the complexity of algorithm? Choose one answer.
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.
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.
What is O(T(N)) if
O(NlogN)
O(logN)
O(N^2)
O(2^N)
A close hashing hash table has an array size of 512. What is the maximum number of entries that can be placed in the table? Choose one answer.
256.
1024.
There is no maximum.
511.
512
– 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? Choose one answer. 1
1471 and 6171 has to different value.
Each element hashes to a different value.
All elements hash to the same value.
4199 and 9679 hash to the same value.
– In Radix sort algorithm …? Choose one answer.
A stable sorting algorithm is used to sort the digits
Sort key can be a string or an object.
The time complexity is O(NlogN).
Digits are sort from left most to right most.
Which array represents a Max-Heap? Choose one answer.
{78,56,45,32,23,8,15}
{8,78,56,32,15,23,45}
{78,23,15,56,32,8,45}
{8,15,23,32,56,45,78}
Which is the common form of a node X in a Doubly Linked List? Choose one answer.X(data, prev)
X(data, prev)
X(data, prev, next)
X(data)
X(data, next)
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? Choose one answer
We compare the value of TA and TB corresponding to every value of n.
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 grow rate of the leading terms of TA(N) and TB(N).
The time complexity of an algorithm T(N) is estimated by couting the number of primitive operations.…? Choose one answer.
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.
The relative order of elements with equal keys are not maintained.
In an array-based stack, which operation has time complexity O(N) in the worstcase? Choose one answer.
No operation that has time complexity O(N).
isEmpty().
push().
pop().
– Suppose that you are writing a program to evaluate if a given string input has proper closing parenthesis for every opening parenthesis. Which data structure should be used? Choose one answer.
Array of strings.
Stack.
Tree.
Queue.
The following method implement the recursive version of the binary search algorithm. Please complete the code of the method?
(a)
In an Array-based list, what does this code do to the list?
Traversing the list.
Remove an item from the list.
Duplicate items in the list.
Remove all item from the list except one.
Which statement below is correct? Choose one answer.
An algorithm takes the input to a problem and transforms it to the output which solves the problem. There is only one algorithm for a specific problem.
An algorithm is a program written in machine code.
An algorithm is a step-by-step procedure for solving a problem in a finite amount of time.
An algorithm is a representation of a program in pseudocode.
A queue Q has 05 character items, Q={“5”, “4”, “3”, “2”, “1”} where “1” is the front and “5” i the rear of Q. Which operations must be perform to change Q into a new state: Q={“3”, “2”, “1”, “4”, “5”} Choose one answer.
enqueue(“5”)-->enqueue(“4”)-->dequeue()-->dequeue()
enqueue(“4”)-->enqueue(“5”)-->dequeue()-->dequeue()
dequeue()-->enqueue(“5”)-->dequeue()-->enqueue(“4”)
dequeue()-->dequeue()-->enqueue(“5”)-->enqueue(“4”)
– Consider three algorithms which have the time complexity in Big-Oh notation below. Please arrange these algorithms in the ascending order of time efficiency (the slowest algorithm is the first one in t order).
Algorithm 3, Algorithm 1, Algorithm 2
Algorithm 1, Algorithm 3, Algorithm 2
Algorithm 1, Algorithm 2, Algorithm 3
Algorithm 3, Algorithm 2, Algorithm 1
A mathematical-model with a collection of operations defined on that model is called? Choose one answer.
Data structure
Primitive data type
Abstract Data Type
Algorithm.
In Merge sort algorithm …?
The worst case is O(N^2).
The input array is divided into two parts based on the pivot values.
The input array is divided into two parts at the middle of the array.
The merge algorithm combines two sorted array by attaching the second array to the end of the first one.
Complete the code for the dequeue() method in array-based circular queue?
rear=rear+1
front=(front+1)%maxSize
front=front+1
rear=(rear+1)%maxSize
Consider method F in Java and a singly linked list L below. Suppose that H is the head node of the list L. What is the result if we call F(H)?
‘F’-- >‘D’-->‘B’
‘A’-- >‘C’-->‘E’
‘E’-- >‘C’-->‘A’
‘B’ >‘D’ >‘F’
Please complete the code of the linear search method below?
(a)
Which statement is wrong concerning to the Heap data structure? Choose one answer.
It is used in Heap sort algorithm.
In a min-heap the parent node value is always greater than or equal to its children’s values.
An array can be used to store heap’s nodes
It is a tree where all nodes have zero, one or two children.
The method f3(N) calls two methods f1(N) and f2(N) as follows. What is the time complexit of method f3(N)?
O(N^4)
O(N^2)
O(N)
O(N^3)
Complete the code below to search for key in an array using linear search algorithm?
-1
i
a[i]
true
Method swap() is used to swap two nodes in a Singly Linked List. Please complete the code for this method
(a)
IDHSQ04 – In the method F below, q1 and q2 are two queues containing integer items. What should
metho F print on the screen?
1 2 3 4 5 6 7 8 9 10
9 7 5 3 1 10 8 6 4 2
1 3 5 7 9 2 4 6 8 10
9 10 7 8 5 6 3 4 1 2
IDEAOA05 – When evaluating algorithm’s complexity, which approach makes possible an evaluation
that independent of the hardware and software environments?
Choose one answer.
Theoretical approach.
Measuring the running time and memory space using the same hardware
and software environment.
Using input data sets of varying size.
Experimental approach.
IDMSOA01 – Selection sort algorithm is used to sort the array A={23,78,45,8,32,56} in the ascending
orde What are the items of A after 03 sort pass?
Choose one answer.
A={8,32,23,45,56,78}
A={78,45,56,8,32,23}
A={78,45,56,23,32,8}
A={23,32,8,45,56,78}
IDESQAS10 – Consider a hash table of size seven, with starting index zero, and a hash function
h(k)=(3k+ mod 7. What is the address of the key k=10?
Choose one answer.
0.
3.
6.
7.
Question17
Marks: 1
IDHSOA03 – Given an array A that is almost sorted (only one or two elements are misplaced). Which
sorti algorithm gives the best time efficiency when applied on A.
Choose one answer.
Selection sort
Insertion sort
Bubble sort
Quick sort
IDHSOA02 – Insertion sort is used to sort an array in the descending order. When does the
best case occur?
Choose one answer.
The array is already sorted in the ascending order.
The array is already sorted in the descending order.
The array contains several zero items.
The array has several duplicated items.
IDEAOA09 – Which statement is wrong concerning to the average-case time complexity of an
algorithm?
Choose one answer.
The average-case is easy to determine.
The average-case is places somewhere between the best-case and the worse-case.
The average-case of an algorithm A is depended on the characteristic of the input data.
The average-case of an algorithm A is estimated as the average number of primitive
operations performed by A on an input size n.
Quick sort algorithm is used to sort the array A={30,22,33,42,10,9,52,2}.
Suppose that the first array elements is chosen as the pivot for partitioning. What is the array
after the first partition?
Choose one answer.
A={10, 22, 9, 2, 30, 33, 42, 52}
A={10,22,2,9,30,42,52,33}
A={30,52,42,33,10,22,9,2}
A={30,2,9,10,22,33,42,52}
– What is the number of comparisons needed in the worst case to search for a
given node in a Singly Linked List of the length N nodes?
N
log(N)
N/2
Nlog(N)
IDESQAS01 – What is the worst-case time for linear search finding a single item in an
array? Choose one answer.
Quadratic time.
Logarithmic time.
Linear time.
Constant time.
IDELI07 – In a Singly Linked List, if a Node X(data,next) is a tail which is the value of the
X’s next?
Choose one answer.
head
null
0
undefined
IDMSOA12 – The Merge method in Merge sort algorithm is used to combine two sorted
array A={3,27,38,43} and B={9,10,82}. What is the result array C?
Choose one answer.
C={3,9,10,27,38,43,82}
C={3,82,9,43,10,38,27}
C={3,27,38,43,9,10,82}
C={9,10,82,3,27,38,43}
IDESQ11 – Which statement is wrong about list-based queue?
Choose one answer.
List-based queue ADT does not have isFull() operation
A linked-list is used to implement the queue.
Queue is empty when front=rear.
front is the head and rear is the tail of the linked-list.
IDESQAS14 – In the context of seach algorithms, which of the following statements are
true? Choose one answer.
Binary search is faster than linear search, but it requires a sorted
array.
Binary search is the fastest search algorithm.
Hash data structure is used to support sorting.
Linear search is faster than binary search.
IDMSOA02 – Insertion sort algorithm is used to sort the array A={23,78,45,8,32,56} in
the ascending order. What are the items of A after 03 sort pass?
Choose one answer.
A={45,56,78,23,32,8}
A={8,23,45,78,32,56}
A={8,23,45,56,32,78}
A={45,56,78,32,23,8}
IDESQ16 – What is the result of the following operation on the stack S:
S.peek(S.push(X))? Choose one answer.
IDHSOA01 – Selection sort is used to sort an array in the descending order. When does the
worst case occur?
Choose one answer.
The first and the last items of the array are the same.
The array is already sorted in the ascending order.
The array is already sorted in the descending order.
The array has several duplicated items.
IDMLI02 – In a Singly Linked List implementation, what do we do when assigning head to
null? Choose one answer.
Delete all nodes from the list.
Avoid traversing the list.
Remove the last node from the list.
Remove the first node from the list.
IDEAOA06 – What is time complexity of an
algorithm? Choose one answer.
The upper limits for execution time of the algorithm.
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 response time of the algorithm.
IDESOA13 – Which statement is wrong concerning to Counting sort
algorithm? Choose one answer.
It is a stable sorting algorithm.
It is an internal sorting algorithm.
It is a linear sorting algorithm.
The correct position of the key x is determined by the number of keys less than x.
– 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?
Choose one answer.
O(P(N+B)).
O(N.P.B).
O(P+N+B).
O(B+N).
IDESQAS06 – 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?
Choose one answer.
511.
512.
1024.
256.
IDMSQ03 – A stack S has 05 character items, S={“5”, “4”, “3”, “2”, “1”} where “1” is the top
of S. Which operations must be perform to change S into a new state: S={“5”, “4”, “2”, “3”,
“1”}?
Choose one answer.
pop()-->push(“2”)-->pop()-->push(“3”)-->pop()-->push(“1”)
pop()-->pop()-->pop()-->push(“2”)-->push(“3”)-->push(“1”)
push(“2”)-->pop()-->push(“3”)-->pop()-->push(“1”)-->pop()
push(“2”)-->push(“3”)-->push(“1”)-->pop()-->pop()-->pop()
IDEAOA08 – Which statement is wrong concerning to the best-case time complexity of an
algorithm?
Choose one answer.
The best-case is used frequently to analyze the time complexity of algorithms.
Many algorithms perform exactly the same in the best case.
The best-case gives us an lower bound on the time complexity of algorithms.
The best case of an algorithm A is estimated as the minimum number of
primitive operations performed by A on an input size n.
IDMLI04 – In a Singly Linked List implementation, what does this code to to the list?
Remove the tail node
Search for a node in the list
Remove the node at the pos position from the list
Remove the head node
IDMAOA05 – What is the time complexity of the following algorithm with respect to the input size N
O(2N)
O(1)
O(N)
O(N^2)
IDELI13 – In a Circular Linked List, if a Node X(data,next) is a tail which is the value of the X’s next? Choose one answer.
0
head
null
undefined
– In a hash table of the size N using linear probing, what is the probing hash function hi(k)? Choose one answer.
hi(k)=h(k) mod N
hi(k)=i + k.
hi(k)=i mod N.
hi(k)=(h(k)+i) mod N.
IDESQAS09 – Which of the following is not an application of the stack data structure? Choose one answer.
Backtracking
Arithmetic expression evaluation.
Managing function calls.
Message buffering.
IDMSQ05 – In method F below, the stack s contains character items. Which is the result if we call method F with the input string text=“datastructure”?
erutcurtsataderutcurtsatad
datastructure
erutcurtsatad
datastructuredatastructure
IDHSQ06 – In the method F below, s is a stack containing integer items. What is the content of s after calling F(), suppose that the top of the stack is the right most item?
3 9 5 4 2
4 3 5 9 2
4 2 9 5 3
3 5 9 2 4
IDEAOA12 – Which notation represents the upper-bound of the grow rate of a function? Choose one answer.
Big-Omega notation
Big-Theta notation
Big-Alpha notation
Big-Oh notation
IDMSOA13 – Heap sort algorithm is used to sort the array A={15,19,10,7,17,16} in the ascending order (using a Max-Heap). What is the content of A after calling BuildHeap() method? Choose one answer.
A={19,17,16,7,15,10}
A={10,7,15,19,16,17}
A={19,10,17,7,15,16}
A={10,15,17,19,7,16
IDHAOA02 – An algorithm that has the time complexity O(NlogN) spends 3 seconds to finish running with the input size N=1,000. Assuming that total number of primitive excution T(N) is directly proportional to NlogN, or T(N)=C.(NlogN) where C is a constant. Estimate how long this algorithm run with the input size N=10,000? Choose one answer
50 seconds
30 seconds
60 seconds
40 seconds
Method copyStack() is used to copy the content of the source stack into the destination stack. Please complete the code for this method.
(a)
– 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? Choose one answer.
T(N)=T(N/3)+T(2N/3)+O(N)
T(N)=2T(2N/3)+O(N)
T(N)=T(N/2)+T(3N/2)+O(N)
T(N)=2T(N/3)+O(N)
IDESOA01 - Which statement below is wrong in the context of sorting algorithms? Choose one answer.
The time complexity of some sorting algorithms can be faster than O(NlogN)
Stability and efficiency are two characteristics of a sorting algorithm.
Sorting algorithms rearrange a sequence of elements into numerical order based on the sort key.
The sort key must be numeric
Question16 Marks: 1 IDESQ01 - Which statement below is wrong concerning to stack data structure? Choose one answer.
A stack contains a sequence of zero or more items of the same type.
List-based stack has no limit on total number of items of the stack.
push() and pop() are two operations defined in Stack’s ADT.
It is a First In First Out (FIFO) list.
IDESQAS04 – What additional requirement is placed on an array, so that binary search may be used to search for a key?
The array must have at least 2 entries
The array elements must form a heap.
The array must be sorted.
The array's size must be a power of two
IDESQ13 – Suppose you push 10, 20, 30, 40 onto a stack, then you pop three items. Which one is left on the stack? Choose one answer.
20
10
40
30
IDMSQ01 – A stack S has 05 character items, S={“A”,“B”,“C”,“D”,“E”} where “E” is the top of S. What is the content of S if we perform the following list of operations on the stack: push(“F”) –-> pop() –-> pop() –-> pop() –-> push(“D”)? Choose one answer.
S={“B”,“E”, “F” ,“D”}
S={“C”,“D”,“E”,“F”}
S={“A”,“B”,“D”,“F”}
S={“A”,“B”,“C”,“D”}
IDMSOA05 – A sorting algorithm is used to sort the array A={51,11,56,83,20,26,33} in ascending order. The items of A in each sort pass are listed below. Which sorting algorithm is used?
Insertion sort
Selection sort
Merge sort
Bubble sort
IDEAOA03 – Which statement below is wrong? Choose one answer.
For the same data, some data structures may require more or less space.
A data structure is a piece of information (a physical instantiation of a data type)
A data structure is a way of organizing data for processing within a computer program.
For the same operations on the data, some data structures lead to more or less efficient algorithms.
IDELI11 – Complete the code below to insert a new node X at the POS position of a Singly Linked List?
X.setNext(Y).
Y.setNext(tail).
Y.getNext().
X.getNext().
IDMLI04 – In a Singly Linked List implementation, what does this code to to the list?
Remove the head node
Search for a node in the list
Remove the node at the pos position from the list
Remove the tail node
IDESOA08 – Which sorting algorithm scans and exchanges any pair of elements that is out of-order? Choose one answer.
Insertion sort
Selection sort
Heap sort.
Bubble sort
IDESQ04 – Which statement is correct about array-based stack? Choose one answer.
top is the first item of the array
top is the last item of the array.
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.
IDELI01 - Which statement below is wrong in the context of list data structure? Choose one answer.
In the list, items are referenced by their value
A list is a sequence of zero or more items of the same type.
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.
Method printList() is used to print out the data of all nodes in a Singly Linked List. Please complete the code of the method?
(a)
IDEAOA07 – Which statement is wrong? Choose one answer.
The estimated time complexity of an algorithm T(N) varies with the input data of the different size.
Pseudocode can be used to describe an algorithm for estimating its time complexity T(N).
The time complexity of an algorithm T(N) is estimated by couting the number of primitive operations.
The estimated time complexity of an algorithm T(N) does not vary with the input data of the same size N.
IDEAOA11 – Which one determines the asymptotic behavior of the function T(N)? Choose one answer.
The term has the biggest coefficient.
The last term.
The leading term
The first term.
IDMSOA07 – Quick sort algorithm is used to sort the array A={55,81,39,92,18,47,63,99,16}. Suppose that the first array element is chosen as the pivot for partitioning. What is the array after the first partition? Choose one answer
A={18,16,39,47,55,92,63,99,81}
A={99,81,92,63,55,39,47,18,16}
A={55,16,39,47,18,92,63,99,81}
A={55,99,81,63,92,47,39,16,18}
IDESQAS02 – What is the worst-case time for binary search finding a single item in an array? Choose one answer
Linear time.
Constant time.
Logarithmic time
Quadratic time.
IDESOA07 – Which statement is wrong about Insertion sort? Choose one answer.
Scan and exchange any pair of elements that is out-of-order.
Unsorted elements are inserted into an already sorted list.
It is O(n^2) sorting algorithm.
We must shift several elements to make place for the inserted one.
(1) Starting from the root and performing ____________, level order traversal of a rooted tree can be done.
(A) Breadth first search
(B) Depth first search
(C) In-order traversal
(D) Pre-order traversal
(2) We have a hash function and a hash table. The size of hash table is 7 with starting index zero. The hash function is (3x+4) mod 7. Assume that initially the hash table is empty and the sequence 1, 3, 8, 10 is inserted into the table using closed hashing. The content of the table is (‘_’ denotes an empty location in the table)
(A) 1, , , , , _, 3
(B) 8, , , , , _, 10
(C) 1, 8, 10, , , _, 3
(D) 1, 10, 8, , , _, 3
(3) Which one of the following statement is false if G is an undirected graph with distinct edge weight, Emax is the edge with maximum weight and Emin is the edge with minimum weight?
(A) Emin is present in every minimum spanning tree of G
(B) Emax is not present in any minimum spanning tree.
(C) The removal of Emax must disconnect G, if Emax is in a minimum spanning tree.
(D) G has a unique minimum spanning tree.
(4) Consider an array L. If an element in an array L is greater than all elements to the right of it then it is called a leader. The best algorithm to find all leaders in an array
(A) Solves it in time θ (n² )
(B) Solves it in linear time using a left to right pass of the array
(C) Solves it in linear time using a right to left pass of the array
(D) Solves it using divide and conquer in time θ (n logn)
(7) Consider a complete n-array tree. This tree is such that each node has either n number of children or no children. Let l = 10 be the number of internal nodes and L = 41 be the number of leaves in a complete n-array tree. The value of n is
(A) 5
(B) 4
(C) 3
(D) 2
What is the running time of f1(n) and f2(n) respectively?
(A) θ (2^n ) and θ (2^n )
(B) θ (n) and θ (2n )
(C) θ (2^n ) and θ(n)
(D) θ (n) and θ (n)
What is the return value of f1(8) and f2(8) respectively?
(A) 1661 and 1640
(B) 1640 and 1661
(C) 59 and 59
(D) 1640 and 1640
Let i, j and n be the integer variables of the C program fragment given below. For (i = n, j = 0; i > 0; i /=2, j += i). After termination of the for loop the value stored in the variable j is denoted by val (j). The statement, which is true for this,
(A) val (j) = θ (n/2)
(B) val (j) = θ (log n)
(C) val (j) = θ (2n)
(D) val (j) = θ (n)
) In a complete binary tree, LASTPOST denotes the last vertex visited in a post order traversal, LASTIN denotes the last vertex visited in an inorder traversal and LASTPRE denotes the last vertex visited in a preorder traversal. The statement, which always holds true, is
(A) LASTIN = LASTPRE
(B) LASTPRE = LASTPOST
(C) LASTIN = LASTPOST
(D) None of the above.
Consider an unweighted, undirected connected graph. In terms of time complexity, the shortest path from a node S to every other node is most efficiently computed by
(A) Performing a DFS starting from S
(B) Performing a BFS starting from S
(C) Warshall’s algorithm
(D) Dijkstra’s algorithm starting from S
_____________ in place sorting algorithm needs the minimum number of swaps
(A) Selection sort
(B) Quick sort
(C) Insertion sort
(D) Heap sort
(16) The algorithm is as given below:
Procedure A(n)
If n<=2
Return (1)
Else
Return (A( √n));
The running time of this algorithm is best described by
(A) O(log n)
(B) O(n)
(C) O(log log n)
(D) O(1)
Consider an undirected graph G whose depth first search tree is T and vertices u and v are the leaves of this tree. The degrees of both u and v in G are at least 2. The statement that holds true is
(A) There must exist a vertex whose removal disconnects u and v in G
(B) There must exist a vertex adjacent to both u and v in G
(C) There must exist a cycle in G containing u and all its neighbours in G
(D) There must exist a cycle in G containing u and v
) _____________ is used if the concatenation of two lists is to be performed on O(1) time?
(A) Array implementation of list
(B) Circular doubly linked list
(C) Singly linked list
(D) Doubly linked list
) The vertices of a cycle with n nodes is to be coloured in such a way that no two adjacent nodes have the same colour. The minimum number of colours required is
(A) n!
(B) 3
(C) n - 2 n/2 +2
(D) 2
(20) A set V = {v1, v2,…., vn} has n number of vertices. Out of this given set, the number of undirected graphs (not necessarily connected) that can be constructed are
(A) 2n(n-1)/2
(B) n
(C) n!
(D) None of the above
(21) Which data structure is to be used to implement Dijkstra’s shortest path algorithm on unweighted graphs so that runs in linear time?
(A) Stack
(B) Heap
(C) Queue
(D) B-Tree
(22) Which one of the following option is true for merge sort?
(A) It uses greedy approach
(B) It uses heuristic search
(C) It uses divide and conquer strategy
(D) It uses backtracking approach
) Consider two positive function of n: f(n) = n² log n and g(n) = n(log n) 10. The statement which is correct for these two functions, is
(A) f(n) = O(g(n)) and g(n) = O(f(n))
(B) f(n) ≠ O(g(n)) and g(n) ≠ O(f(n))
(C) f(n) = O(g(n)) and g(n) ≠ O(f(n))
(D) f(n) ≠ O(g(n)) and g(n) = O(f(n))
0) We have two sorted lists whose sizes are a and b. For merging these two lists into a sorted list of size a + b, we require comparisons of
(A) O (log a + log b)
(B) O (a + b)
(C) O (a)
(D) O (b)
(D) O (b) (31) The technique of sorting is called stable if and only if
(A) It uses divide and conquer technique
(B) It takes O (n) space
(C) It takes O (n log n) time
(D) It maintains the relative order of occurrence of non-distinct elements
We have a Max heap, which is represented by an array, and the process of inserting an element into it is going on. How many comparisons are done to find the position for the newly i
(A) θ (log2 n)
(B) θ (log2 log2 n)
(C) θ (log2 n/2)
(D) θ (n)
In the diagram of a binary tree, an arrow is called a(n) ____.
a. relation
b. path
c. directed line
d. directed branch
binary tree has a special node called the ____ node.
a. super
b. root
c. superparent
d. rootleaf
In a diagram of a binary tree, each node is represented as a(n) ____.
a. line
b. triangle
c. circle
d. rectangle
Three lines at the end of an arrow in the diagram of a binary tree indicate that the subtree ____.
a. has three branches
b. has three children
c. is full
d. is empty
Consider that A is a binary tree, C and D are the subtrees of A. Which of the following statements is always true?
a. C and D are binary trees.
b. C and D are search binary trees.
c. C and D are empty trees.
d. A is empty.
Each link in a binary tree node points to a(n) ____ of that node.
a. parent
b. child
c. value
d. sibling
Every node in a binary tree has at most ____ children.
a. one
b. two
c. three
d. four
Every node in a binary tree has ____ pointers.
a. one
b. two
c. three
d. four
A pointer to the root node of the binary tree is stored outside the binary tree in a pointer variable, usually called the ____.
a. node
b. parent
c. root
d. nodeType
A node in a binary tree is called a(n) ____ if it has no left and right children.
a. edge
b. branch
c. leaf
d. path
In a binary tree, the level of the children of the root node is ____.
a. 0
b. 1
c. 2
d. 3
The ____ of a node in a binary tree is the number of branches on the path from the root to the node.
a. height
b. level
c. width
d. size
. In copying a binary tree, if you use just the value of the pointer of the root node, you get a ____ copy of the data.
a. static
b. shallow
c. deep
d. local
The most common operation performed on a binary tree is a(n) ____.
a. insertion
b. deletion
c. search
d. traversal
The three traversal algorithms discussed for binary trees are ____, ____, and ____.
a. order, preorder, postorder
b. in, preorder, order
c. order, preorder, post
d. inorder, preorder, postorder
The listing of the nodes produced by the postorder traversal of a binary tree is called the ____.
a. postsequence
b. postorder sequence
c. postorder table
d. post-script
The sequence of operations in a postorder traversal is ____.
a. traverse left; traverse right
b. traverse left; traverse right; visit
c. visit; traverse left; traverse right
d. traverse left; visit; traverse right
A binary tree is also a(n) ____.
a. stack
b. linked list
c. graph
d. array
A binary tree is empty if root is ____.
a. 0
b. 1
c. "zero"
d. NULL
