Programming and data structure miscellaneous
- Consider the function f defined below :
struct item {
int data;
struct item * next:
};
int f (struct item * p) {
return ((p = = NULL) P(p – > next = = NULL) P
((p– > data < = p – > next –> data) &&
f (p–> next)));
}
For a given linked list p, the function f returns 1, if and only, if
-
View Hint View Answer Discuss in Forum
Here the return 1 any 1 of the following should be correct.
(a) P == NULL i.e the list is empty (ends)
(b) P → next = NULL i.e., have one element.
(c) P->data <= p->next ->data i.e., the element is smaller than its next element also. This is true for whole list. Since &&f(p “next”) is also there. So overall it gives that the elements should be in sorted order.Correct Option: B
Here the return 1 any 1 of the following should be correct.
(a) P == NULL i.e the list is empty (ends)
(b) P → next = NULL i.e., have one element.
(c) P->data <= p->next ->data i.e., the element is smaller than its next element also. This is true for whole list. Since &&f(p “next”) is also there. So overall it gives that the elements should be in sorted order.
- Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest ?
-
View Hint View Answer Discuss in Forum
Membership & cardinality functions takes constt. time i.e. O(1), but union & intersection require emparison of 1 element with all the other elements so these two would be slowest.
Hence (d) is correct option.Correct Option: D
Membership & cardinality functions takes constt. time i.e. O(1), but union & intersection require emparison of 1 element with all the other elements so these two would be slowest.
Hence (d) is correct option.
- 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 en-queue and dequeue can be performed in constant time?
-
View Hint View Answer Discuss in Forum
Answer is not “(b) front node”, as we cannot get rear from front in O(1), but if P is rear we can implement both enqueue and de-Queue in O(1) because from rear we can get front in O(1). Below are sample functions. Shows The pointer points to the rear node : -
Enqueue :- Insert new node after rear, and make rear point to the newly inserted node :
Struct Node * New Node;
New Node → Next = Rear → Next,
Rear → Next = New Node;
Rear = New Node;
Dequeue :- Delete the front node, and make the second node the front node.
Rear → Next points to the front node.
Front → Next points to the second node.
Struct Node * Front;
Front = Rear → Next;
Rear → Next = Front → Next;
Free (front);Correct Option: A
Answer is not “(b) front node”, as we cannot get rear from front in O(1), but if P is rear we can implement both enqueue and de-Queue in O(1) because from rear we can get front in O(1). Below are sample functions. Shows The pointer points to the rear node : -
Enqueue :- Insert new node after rear, and make rear point to the newly inserted node :
Struct Node * New Node;
New Node → Next = Rear → Next,
Rear → Next = New Node;
Rear = New Node;
Dequeue :- Delete the front node, and make the second node the front node.
Rear → Next points to the front node.
Front → Next points to the second node.
Struct Node * Front;
Front = Rear → Next;
Rear → Next = Front → Next;
Free (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; } }
-
View Hint View Answer Discuss in Forum
The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.
Correct Option: B
The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.
- The following C function takes a simply-linked list as input argument. It modifies the list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.
type def struct node {
int value;
struct node *next;
} Node*;
Node *move_to_front (Node *head) {
Node *p, *q;
if (head = = NULL | | (head -> next = = NULL)) return head;
q = NULL; p = head;
while (p - > next! = NULL) {
q = p;
p = p - > next;
}
return head;
}
Choose the correct alternative to replace the blank line.
-
View Hint View Answer Discuss in Forum
When the while loop ends, q contains address of second last node and p contains address of last node. So we need to do following things after while loop.
(i) Set next of q as NULL (q->next = NULL).
(ii) Set next of p as head (p->next = head).
(iii) Make head as p (head = p)
Step (ii) must be performed before step (iii). If we change head first, then we lose track of head node in the original linked list.Correct Option: D
When the while loop ends, q contains address of second last node and p contains address of last node. So we need to do following things after while loop.
(i) Set next of q as NULL (q->next = NULL).
(ii) Set next of p as head (p->next = head).
(iii) Make head as p (head = p)
Step (ii) must be performed before step (iii). If we change head first, then we lose track of head node in the original linked list.
