ADS_2022-23

Q 1. A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?

• rear node

• front node

• not possible with a single pointer

• node next to front

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution? struct node {     int value;     struct node *next; }; Void rearrange (struct node *list ){     struct node *p, *q;     int temp;     if( !list || !list-> next) return;     p = list; q = list->next;     while (q) {       temp = p->value;       p-> value = q ->value;       q-> value = temp;       p = q-> next;       q = p ? p->next : 0;     } }

• 1,2,3,4,5,6,7

• 2,1,4,3,6,5,7

• 1,3,2,5,4,6,7

• 2,3,4,5,6,7,1

The best data structure to check whether an arithmetic expression has balanced parentheses is a

• Queue

• Trees

• Stack

• Linked List

Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

• A queue cannot be implemented using this stack.

• A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.

• A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.

• A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

What is the worst case time complexity of searching for singly linked list?

• O(1)

• O(n^2)

• O(n)

• O(log n)

which of the following is not the application of tree data structure

• In Compiler designing

• In AI for searching

• finding shortest distance

• sorting

Consider the skip list with three levels: L0: 2,5,9,11,13,18,22,25,28,33,36,40,44,46. L1:2,11,22,33,44. L2:2,33. How many comparisons needed for searching element 40

(a)  

How many BST you can construct using 3 keys 1,2,3

Maximum number of nodes in a complete binary tree of height 4

(a)  

Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?

• SLLdel is O(1) and DLLdel is O(n)

• Both SLLdel and DLLdel are O(log(n))

• Both SLLdel and DLLdel are O(1)

• SLLdel is O(n) and DLLdel is O(1)