- Consider an implementation of unsorted single linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the representation, which of the following operation cannot be implemented in O(1) time ?
(A) Insertion at the front of the linked list.
(B) Insertion at the end of the linked list.
(C) Deletion of the front node of the linked list.
(D) Deletion of the last node of the linked list.
Answer: D
Explanation:
A)Insertion at the front of the linked list.
new_node->next=head;
head=new_node;
Θ(1)
B) Insertion at the end of the linked list.
Tail->next=new_node;
new_node->next=NULL;
Θ(1)
C) Deletion of the front node of the linked list.
Next_node=Head;
Head=Next_node->next;
free(Next_node);
Θ(1)
D)Deletion of the last node of linked list
Here, we have tail pointer but it will be of no use because there is no previous pointer (as it is single linked list).we need to have second last pointer so that we make it the last pointer and can free the last pointer i.e deleting the last node.So we need to traverse the whole linked list making it Θ(n).
struct node *p,*prev;
p=head;
while(p)
{
prev=p;
p=p->next;
}
prev->next=NULL;
free(p);
so ANSWER is (d)
- Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j) | 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a, b) and (c, d) if |a – c| ≤ 1 or |b–d| ≤ 1. The number of edges in this graph is
(A) 726 (B) 796
(C) 506 (D) 616
Answer: C
Explanation:
Satisfying conditions for |a -c 1| ≤1
1. condition type1 :a=c
2. condition type2: a-c=1 or c-a=1.
total number of pairs (a,c) satisfying condition1 : 12
total number of pairs (a,c) satisfying condition2 : 11
so satisfying combinations for ‘a’ and ‘c’ = 11+12 =23
IN Similar way satisfying combinations for ‘b’ and ‘d’ = 23
[ a b]
*
[ c d]
So total solutions = 23*23 = 529
Now there are some cases where loop exists
like :
[1,2] [5,5]
[1,2] OR [5,5]
There will be 23 such cases .
So remove such cases : 529-23 = 506
Another way for solution:
If you think of a 12 * 12 grid (like a chess board of size 12*12), then each each point (i,j), which is in ith row and jth column, is a vertex (i,j).
Now we are allowed to connect only those points which are atmost 1 distance apart (in both horizontal and vertical direction). So we will connect only horizontal neighbours, vertical neighbours, and diagonal neighbours.
So horizontal edges on each row are 11 i.e. 11*12 = 132 horizontal edges. Similarly we have 132 vertical edges.
To count diagonal edges, think of 1*1 square boxes in which diagonals meet each other. There are 11*11 such square boxes, and each box contains 2 diagonals, so total diagonals = 242.
So total edges = 132 + 132 + 242 = 506.
- The runtime for traversing all the nodes of a binary search tree with n nodes and printing them in an order is
(A) O(lg n) (B) O(n lg n)
(C) O(n) (D) O(n2)
Answer: C
Explanation:
Printing the elements in an order means the elements should be printed in sorted order and we know inorder traversal of BST takes gives the sorted order and takes O(n) time.The recurrence involved is :
T(n) = 2T(n/2) + c for balanced BST which on solving gives O(n).
- Consider the following statements :
S1: A queue can be implemented using two stacks.
S2: A stack can be implemented using two queues.
Which of the following is correct ?
(A) S1 is correct and S2 is not correct.
(B) S1 is not correct and S2 is correct.
(C) Both S1 and S2 are correct.
(D) Both S1 and S2 are not correct.
Answer: C
Explanation:
Both of the statements are true.
A queue can be implemented using two stacks:
Consider two stacks s1 & s2 ( we will be using STL stacks for implementation ).
Enqueue Operation :: Simply push the element onto s1.
Dequeue Operation :: Transfer all elements from s1 onto s2. Pop the top element from s2. Transfer remaining elements from s2 back to s1.
A stack can be implemented using two queues:
Let S1 and S2 be the two Stacks to be used in the implementation of queues.
struct Stack
{ struct Queue *Q1;
struct Queue *Q2;
}
We make sure that one queue is empty always.
Push operation : Whichever queue is not empty, insert the element in it.
- Check whether queue Q1 is empty or not. If Q1 is empty then Enqueue the element in it.
- Otherwise EnQueue the element into Q1.
Push (struct Stack *S, int data) { if(isEmptyQueue(S->Q1) EnQueue(S->Q2, data); else EnQueue(S->Q1, data); }
Time Complexity: O(1)
Pop Operation: Transfer n-1 elements to other queue and delete last from queue for performing pop operation.
- If queue Q1 is not empty then transfer n-1 elements from Q1 to Q2 and then, DeQueue the last element of Q1 and return it.
- If queue Q2 is not empty then transfer n-1 elements from Q2 to Q1 and then, DeQueue the last element of Q2 and return it.
- Given the following prefix expression:
* + 3 + 3 ↑ 3 + 3 3 3
What is the value of the prefix expression?
(A) 2178 (B) 2199
(C) 2205 (D) 2232
Answer: C
Explanation:
=> * + 3 + 3 ^ 3 ( 3+ 3) 3
=> * + 3 + 3 ^ 3 6 3
=> * + 3 + 3 (3^6) 3
=> * + 3 + 3 729 3
=> * + 3 ( 3 + 729 ) 3
=> * + 3 732 3
=> * ( 3 + 732) 3
=> * 735 3
=> (735 ) * 3
=> 2205 ( ans- C)
- Which of the following statements is not true with respect to microwaves?
(A) Electromagnetic waves with frequencies from 300 GHz to 400 THz.
(B) Propagation is line-of-sight.
(C) Very high-frequency waves cannot penetrate walls.
(D) Use of certain portions of the band requires permission from authorities.
Answer: A
Explanation:
electromagnetic radiationwith wavelengths ranging from one meter to one millimeter; with frequencies between 300 MHz (100 cm) and 300 GHz (0.1 cm).
- In a fast Ethernet cabling, 100 Base-TX uses ……….. cable and maximum segment size is …………
(A) 100 Base-TX uses, 100 metres (B) twisted pair, 200 metres
(C) fibre optics, 1000 metres (D) fibre optics, 2000 metres
Answer: A
Explanation:
100 Base-TX uses 100 Base-TX uses cable and maximum segment size is 100 metres
- A network with bandwidth of 10 Mbps can pass only an average of 12,000 frames per minute with each frame carrying an average of 10,000 bits. What is the throughput of this network ?
(A) 1 Mbps (B) 2 Mbps
(C) 10 Mbps (D) 12 Mbps
Answer: B
Explanation:
12000*10000/60= 2 Mbps
- Match the following:
List – I List – II
- Session layer i. Virtual terminal software
- Application layer ii. Semantics of the information transmitted
- Presentation layer iii. Flow control
- Transport layer iv. Manage dialogue control
Codes :
a b c d
(A) iv i ii iii
(B) i iv ii iii
(C) iv i iii ii
(D) iv ii i iii
Answer: A
Explanation:
a) Application layer is the topmost layer in TCP/IP protocol stack.Hence is related to software related things.
b) Presentation layer presents the data in proper format for transmission so it is concerned with semantics of the data.
c) Session layer maintains multiple connections and synchronization since we know session is a combination of multiple connections and hence it is associated with dialog control management
d) transport layer deals with flow control and congestion control mainly.
- Which of the following protocols is used by email server to maintain a central repository that can be accessed from any machine?
(A) POP3 (B) IMAP
(C) SMTP (D) DMSP
Answer: B
Explanation:
IMAP is used by email server to maintain a central repository that can be accessed from any machine