Data Structures And Algorithms (UCS408 And UCS613)

1.

The worst case complexity of bubble sort is ____________.

A.

O(nlogn)
B.

O(logn)
C.

O(n)
D.

O(n²)

Correct Answer
D. O(n²)

Explanation
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. In the worst case scenario, where the input list is in reverse order, bubble sort would need to make n-1 passes through the list to sort it completely. In each pass, it compares and swaps adjacent elements, resulting in a complexity of O(n^2), where n is the number of elements in the list. Thus, the worst case complexity of bubble sort is O(n^2).

Rate this question:

2.

Given the value of the size of the stack, STACK_SIZE is 10; what is the value of the top pointer?

A.

10
B.

9
C.

11
D.

12
E.

None

Correct Answer
B. 9

Explanation
The value of the top pointer is 9 because the size of the stack is given as 10, which means there are 10 elements in the stack. However, the top pointer is used to indicate the position of the topmost element in the stack, and since indexing starts from 0, the top pointer would be 9 for a stack of size 10.

Rate this question:

3.

How many iterations will be required to sort the following array, arr={4,5,7,6} using bubble sort algorithm?

A.

4
B.

2
C.

1
D.

0

Correct Answer
A. 4

Explanation
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. In each iteration, the largest element in the unsorted portion of the array "bubbles" up to its correct position. In this case, the array {4,5,7,6} requires 4 iterations to be sorted using bubble sort.

Rate this question:

4.

___________ datastructure is appropriate to elicite hierarchical relationship between items.

A.

Graph
B.

Tree
C.

Linked List
D.

Priority Queue

Correct Answer
B. Tree

Explanation
A tree data structure is appropriate to elicit hierarchical relationships between items. In a tree, each item is connected to one parent node except for the root node, which has no parent. This structure allows for a clear and organized representation of hierarchical relationships, where each item can have multiple child nodes. Unlike a graph or linked list, a tree enforces a specific hierarchical structure, making it the most suitable choice for representing and navigating hierarchical relationships between items. A priority queue, on the other hand, is not designed to capture hierarchical relationships but rather to prioritize and retrieve items based on their priority levels.

Rate this question:

5.

The binary Search algorithm is based on

A.

Brute Force Technique
B.

Divide and Conqure
C.

Greedy Algorithm
D.

Dynamic Programming

Correct Answer
B. Divide and Conqure

Explanation
The correct answer is "Divide and Conquer." The binary search algorithm is based on the divide and conquer technique, which involves breaking down a problem into smaller subproblems, solving them independently, and then combining the solutions to obtain the final result. In binary search, the algorithm repeatedly divides the search space in half, eliminating one half each time based on a comparison with the target value. This approach significantly reduces the search space and allows for efficient searching in sorted arrays or lists.

Rate this question:

6.

Following is true about linked list over array:

A.

Arrays have better cache locality that can make them better in terms of performance.
B.

It is easy to insert and delete elements in Linked List
C.

Random access is not allowed in a typical implementation of Linked Lists
D.

The size of array has to be pre-decided, linked lists can change their size any time.
E.

All of the above

Correct Answer
E. All of the above

Explanation
Linked lists and arrays have different characteristics that make them suitable for different scenarios.

The statement "Arrays have better cache locality that can make them better in terms of performance" is true because arrays store elements in contiguous memory locations, which allows for faster memory access and cache utilization compared to linked lists.

The statement "It is easy to insert and delete elements in Linked List" is true because linked lists have dynamic memory allocation, allowing for easy insertion and deletion of elements by simply adjusting the pointers.

The statement "Random access is not allowed in a typical implementation of Linked Lists" is true because linked lists do not support direct access to elements by index. To access a specific element, one must traverse the list from the beginning.

The statement "The size of array has to be pre-decided, linked lists can change their size any time" is true because arrays have a fixed size that needs to be determined before allocation, while linked lists can dynamically allocate memory and adjust their size as needed.

Therefore, all of the above statements are true about linked lists over arrays.

Rate this question:

7.

The queue doesn't support the following operation

A.

Insertion
B.

Deletion
C.

Retrieval
D.

Traversal

Correct Answer
D. Traversal

Explanation
The correct answer is Traversal because a queue is a data structure that follows the FIFO (First-In-First-Out) principle, where elements are inserted at the rear and removed from the front. Traversal refers to the process of accessing and examining each element in a data structure, which is not applicable to a queue. In a queue, elements can only be inserted at the rear, removed from the front, or retrieved from the front without altering the queue's structure.

Rate this question:

8.

The first node is given (head of the linked list); What does the following function do? void fun1(struct node* head) { if(head == NULL) return; fun1(head->next); printf("%d ", head->data); }

A.

Prints all nodes of linked lists
B.

Prints all nodes of linked list in reverse order
C.

Prints alternate nodes of Linked List
D.

Prints alternate nodes in reverse order

Correct Answer
B. Prints all nodes of linked list in reverse order

Explanation
The function fun1 takes the head of a linked list as input. It first checks if the head is NULL, and if so, it returns. If the head is not NULL, it recursively calls fun1 with the next node in the linked list. This recursive call ensures that the function traverses to the end of the linked list. After the recursive call, it prints the data of the current node. Since the recursive call is made before the print statement, the function will print the nodes in reverse order, starting from the last node and ending at the head node. Therefore, the correct answer is "Prints all nodes of linked list in reverse order".

Rate this question:

9.

What will be the Output of the following code?

A.

Value of jRef: 20, Value of j: 25
B.

Value of jRef: 25, Value of j: 20
C.

Value of jRef: 20, Value of j: 20
D.

Value of jRef: 25, Value of j: 25

Correct Answer
A. Value of jRef: 20, Value of j: 25

Explanation
The output of the code will be "Value of jRef: 20, Value of j: 25".

Rate this question:

10.

Following is/are the differences between References and Pointers:

A.

No null references as pointers do
B.

A reference is bound to its initializer for its whole lifetime, pointers don’t
C.

A reference must be initialized after object is created, pointers can be initialized any time
D.

All of the above

Correct Answer
D. All of the above

Explanation
References and pointers have several differences. Firstly, references do not have the capability to be null, whereas pointers can be assigned a null value. Secondly, a reference is bound to its initializer for its entire lifetime, meaning it cannot be reassigned to refer to a different object. On the other hand, pointers can be reassigned to point to different objects at any time. Lastly, a reference must be initialized after the object is created, while pointers can be initialized at any time. Therefore, all of the given statements are correct in describing the differences between references and pointers.

Rate this question:

Data Structures And Algorithms (Ucs408 And Ucs613)

The worst case complexity of bubble sort is ____________.

Given the value of the size of the stack, STACK_SIZE is 10; what is the value of the top pointer?

How many iterations will be required to sort the following array, arr={4,5,7,6} using bubble sort algorithm?

___________ datastructure is appropriate to elicite hierarchical relationship between items.

The binary Search algorithm is based on

Following is true about linked list over array:

The queue doesn't support the following operation

The first node is given (head of the linked list); What does the following function do? void fun1(struct node* head) { if(head == NULL) return; fun1(head->next); printf("%d ", head->data); }

What will be the Output of the following code?

Following is/are the differences between References and Pointers: